RECORD
On Stochastic Variance Reduced Gradient Method for Semidefinite Optimization
Optimization and Control · Submitted 1 Jan 2021
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim Equipped with this, we establish the global linear submanifold convergence (i.e., converging exponentially fast to a submanifold of a global minimum under the orthogonal group action) of the proposed SVRG method, given a provable initialization scheme and under certain smoothness and restricted strongly convex assumptions.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
The low-rank stochastic semidefinite optimization has attracted rising attention due to its wide range of applications. The nonconvex reformulation based on the low-rank factorization, significantly improves the computational efficiency but brings some new challenge to the analysis. The stochastic variance reduced gradient (SVRG) method has been regarded as one of the most effective methods. SVRG in general consists of two loops, where a reference full gradient is first evaluated in the outer loop and then used to yield a variance reduced estimate of the current gradient in the inner loop. Two options have been suggested to yield the output of the inner loop, where Option I sets the output as its last iterate, and Option II yields the output via random sampling from all the iterates in the inner loop. However, there is a significant gap between the theory and practice of SVRG when adapted to the stochastic semidefinite programming (SDP). SVRG practically works better with Option I, while most of existing theoretical results focus on Option II. In this paper, we fill this gap via exploiting a new semi-stochastic variant of the original SVRG with Option I adapted to the semidefinite optimization. Equipped with this, we establish the global linear submanifold convergence (i.e., converging exponentially fast to a submanifold of a global minimum under the orthogonal group action) of the proposed SVRG method, given a provable initialization scheme and under certain smoothness and restricted strongly convex assumptions. Our analysis includes the effects of the mini-batch size and update frequency in the inner loop as well as two practical step size strategies, the fixed and stabilized Barzilai-Borwein step sizes. Some numerical results in matrix sensing demonstrate the efficiency of proposed SVRG method outperforming Option II counterpart as well as others.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | The low-rank stochastic semidefinite optimization has attracted rising attention due to its wide range of applications. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s1 | The nonconvex reformulation based on the low-rank factorization, significantly improves the computational efficiency but brings some new challenge to the analysis. | background 0.99 | 0.07 | 0.02 | asserted 1.00 |
| s2 | The stochastic variance reduced gradient (SVRG) method has been regarded as one of the most effective methods. | background 0.99 | 0.04 | 0.02 | asserted 0.95 |
| s3 | SVRG in general consists of two loops, where a reference full gradient is first evaluated in the outer loop and then used to yield a variance reduced estimate of the current gradient in the inner loop. | background 0.81 | 0.05 | 0.02 | asserted 1.00 |
| s4 | Two options have been suggested to yield the output of the inner loop, where Option I sets the output as its last iterate, and Option II yields the output via random sampling from all the iterates in the inner loop. | background 0.78 | 0.07 | 0.02 | asserted 0.99 |
| s5 | However, there is a significant gap between the theory and practice of SVRG when adapted to the stochastic semidefinite programming (SDP). | gap 1.00 | 0.14 | 0.03 | asserted 1.00 |
| s6 | SVRG practically works better with Option I, while most of existing theoretical results focus on Option II. | gap 0.98 | 0.15 | 0.05 | asserted 0.99 |
| s7 | In this paper, we fill this gap via exploiting a new semi-stochastic variant of the original SVRG with Option I adapted to the semidefinite optimization. | contribution 0.98 | 0.93 | 0.17 | asserted 1.00 |
| s8 | Equipped with this, we establish the global linear submanifold convergence (i.e., converging exponentially fast to a submanifold of a global minimum under the orthogonal group action) of the proposed SVRG method, given a provable initialization scheme and under certain smoothness and restricted strongly convex assumptions. | result 0.89 | 0.95 | 0.80 | asserted 1.00 |
| s9 | Our analysis includes the effects of the mini-batch size and update frequency in the inner loop as well as two practical step size strategies, the fixed and stabilized Barzilai-Borwein step sizes. | contribution 0.56 | 0.91 | 0.07 | asserted 0.98 |
| s10 | Some numerical results in matrix sensing demonstrate the efficiency of proposed SVRG method outperforming Option II counterpart as well as others. | result 1.00 | 0.94 | 0.19 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
The low-rank stochastic semidefinite optimization has attracted rising attention due to its wide range of applications. The nonconvex reformulation based on the low-rank factorization, significantly improves the computational efficiency but brings some new challenge to the analysis. The stochastic variance reduced gradient (SVRG) method has been regarded as one of the most effective methods. SVRG in general consists of two loops, where a reference full gradient is first evaluated in the outer loop and then used to yield a variance reduced estimate of the current gradient in the inner loop. Two options have been suggested to yield the output of the inner loop, where Option I sets the output as its last iterate, and Option II yields the output via random sampling from all the iterates in the inner loop. However, there is a significant gap between the theory and practice of SVRG when adapted to the stochastic semidefinite programming (SDP). SVRG practically works better with Option I, while most of existing theoretical results focus on Option II. In this paper, we fill this gap via exploiting a new semi-stochastic variant of the original SVRG with Option I adapted to the semidefinite optimization. Equipped with this, we establish the global linear submanifold convergence (i.e., converging exponentially fast to a submanifold of a global minimum under the orthogonal group action) of the proposed SVRG method, given a provable initialization scheme and under certain smoothness and restricted strongly convex assumptions. Our analysis includes the effects of the mini-batch size and update frequency in the inner loop as well as two practical step size strategies, the fixed and stabilized Barzilai-Borwein step sizes. Some numerical results in matrix sensing demonstrate the efficiency of proposed SVRG method outperforming Option II counterpart as well as others.
Human review
How the literature uses it
1 arXiv paper cite this in 1 sentence
What it cites · 8 sentences without a confident label
Compares with 2 papers
-
In order to demonstrate the effectiveness of the proposed method, we consider the following batch and stochastic methods as competitors: factored gradient descent (FGD) method [ref] , stochastic gradient descent (SGD) methods [ref] with a fixed step size (SGD-fix) or diminishing step sizes (SGD-diminish), SVRG with with Option I (SVRG-I, where the update in the inner loop of Algorithm [ref] is the traditional one, $∇f_i_t(X^t)U^t - (∇f_i_t(X̃^k)-∇f(X̃^k))Ũ^k$), and SVRG-LR [ref] which is of Option II.
A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery · Experimental settings · 0.85
-
Under the regular Lipschitz gradient and restricted strongly convex assumptions, we at first establish a local linear submanifold convergence of the proposed SVRG method (see Theorem [ref]), where the radius of the initial ball permitted to guarantee the linear submanifold convergence is larger than existing results established in the literature [ref] , as listed in Table [ref].
Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements · Introduction · 0.99
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.