# On Stochastic Variance Reduced Gradient Method for Semidefinite Optimization

arXiv: https://arxiv.org/abs/2101.00236 · HTML: https://mlsanity.com/paper/2101.00236/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 33 references that are in the map.
- First posted on arXiv 1 Jan 2021.

## Builds on (most cited first, 18 of 18)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014)
- [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015)
- [Phase Retrieval using Alternating Minimization](https://mlsanity.com/paper/1306.0160/) (2013)
- [Dropping Convexity for Faster Semi-definite Optimization](https://mlsanity.com/paper/1509.03917/) (2015)
- [A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements](https://mlsanity.com/paper/1506.06081/) (2015)
- [Barzilai-Borwein Step Size for Stochastic Gradient Descent](https://mlsanity.com/paper/1605.04131/) (2016)
- [Phase Retrieval from Coded Diffraction Patterns](https://mlsanity.com/paper/1310.3240/) (2013)
- [A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation](https://mlsanity.com/paper/1610.05275/) (2016)
- [On the low-rank approach for semidefinite programs arising in synchronization and community detection](https://mlsanity.com/paper/1602.04426/) (2016)
- [Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent](https://mlsanity.com/paper/1605.08370/) (2016)
- [Towards closing the gap between the theory and practice of SVRG](https://mlsanity.com/paper/1908.02725/) (2019)
- [Stochastic Non-convex Ordinal Embedding with Stabilized Barzilai-Borwein Step Size](https://mlsanity.com/paper/1711.06446/) (2017)
- [Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements](https://mlsanity.com/paper/1701.00481/) (2017)
- [A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery](https://mlsanity.com/paper/1701.02301/) (2017)
- [Finding Global Optima in Nonconvex Stochastic Semidefinite Optimization with Variance Reduction](https://mlsanity.com/paper/1802.06232/) (2018)
- [Fast Stochastic Ordinal Embedding with Variance Reduction and Adaptive Step Size](https://mlsanity.com/paper/1912.00362/) (2019)

## Built on by (most cited first, 1 of 1)

- [KKT Conditions, First-Order and Second-Order Optimization, and Distributed Optimization: Tutorial and Survey](https://mlsanity.com/paper/2110.01858/) (2021)

## 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.