On Stochastic Variance Reduced Gradient Method for Semidefinite Optimization
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 18 of its 33 references that are in the map. First posted on arXiv 1 Jan 2021.
Builds on
18 of 33 references.
References · 18
- 2014Convex Optimization: Algorithms and Complexitycited by 569
- 2013Minimizing Finite Sums with the Stochastic Average Gradientcited by 164
- 2014Phase Retrieval via Wirtinger Flow: Theory and Algorithmscited by 123
- 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
- 2013Phase Retrieval using Alternating Minimizationcited by 58
- 2015Dropping Convexity for Faster Semi-definite Optimizationcited by 40
- 2015A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurementscited by 34
- 2016Barzilai-Borwein Step Size for Stochastic Gradient Descentcited by 33
- 2013Phase Retrieval from Coded Diffraction Patternscited by 26
- 2016A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimationcited by 21
- 2016On the low-rank approach for semidefinite programs arising in synchronization and community detectioncited by 17
- 2016Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descentcited by 15
6 more
- 2019Towards closing the gap between the theory and practice of SVRGcited by 6
- 2017Stochastic Non-convex Ordinal Embedding with Stabilized Barzilai-Borwein Step Sizecited by 4
- 2017Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurementscited by 1
- 2017A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recoverycited by 1
- 2018Finding Global Optima in Nonconvex Stochastic Semidefinite Optimization with Variance Reductioncited by 1
- 2019Fast Stochastic Ordinal Embedding with Variance Reduction and Adaptive Step Sizecited by 1
Built on by
Citing papers per year: 2021: 1.
1 paper.