Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems

Christopher De, Christopher Ré, Kunle Olukotun

Type: Preprint

Publication Date: 2014-01-01

Citations: 88

DOI: https://doi.org/10.48550/arxiv.1411.1134

View

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems	2014	Christopher De Kunle Olukotun Christopher Ré
+	On the Convergence of Stochastic Gradient Descent with Low-Rank Projections for Convex Low-Rank Matrix Problems	2020	Dan Garber
+ PDF Chat	Exact Linear Convergence Rate Analysis for Low-Rank Symmetric Matrix Completion via Gradient Descent	2021	Trung Vu Raviv Raich
+	Exact Linear Convergence Rate Analysis for Low-Rank Symmetric Matrix Completion via Gradient Descent	2021	Trung Nghia Vu Raviv Raich
+	Exact Linear Convergence Rate Analysis for Low-Rank Symmetric Matrix Completion via Gradient Descent	2021	Trung Vu Raviv Raich
+ PDF Chat	Guaranteed Matrix Completion via Nonconvex Factorization	2015	Ruoyu Sun Zhi‐Quan Luo
+ PDF Chat	Scaled stochastic gradient descent for low-rank matrix completion	2016	Bamdev Mishra Rodolphe Sepulchre
+	Scaled stochastic gradient descent for low-rank matrix completion	2016	Bamdev Mishra Rodolphe Sepulchre
+	Scaled stochastic gradient descent for low-rank matrix completion	2016	Bamdev Mishra Rodolphe Sepulchre
+	Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent	2016	Chi Jin Sham M. Kakade Praneeth Netrapalli
+	Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees	2015	Yudong Chen Martin J. Wainwright
+	Efficient Low-Rank Stochastic Gradient Descent Methods for Solving Semidefinite Programs	2014	Jianhui Chen Tianbao Yang Shenghuo Zhu
+	A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery	2017	Lingxiao Wang Xiao Zhang Quanquan Gu
+	On Global Linear Convergence in Stochastic Nonconvex Optimization for Semidefinite Programming	2019	Jinshan Zeng Ke Ma Yuan Yao
+	Fast global convergence of gradient descent for low-rank matrix approximation	2023	Hengchao Chen Xin Chen Mohamad Elmasri Qiang Sun
+	Efficient and Practical Stochastic Subgradient Descent for Nuclear Norm Regularization	2012	Haim Avron Satyen Kale Shiva Prasad Kasiviswanathan Vikas Sindhwani
+	Efficient and Practical Stochastic Subgradient Descent for Nuclear Norm Regularization	2012	Haim Avron Satyen Kale Shiva Prasad Kasiviswanathan Vikas Sindhwani
+	Linear Convergence of Stochastic Iterative Greedy Algorithms with Sparse Constraints	2014	Nam Nguyen Deanna Needell Tina Woolf
+	Fast Stochastic Algorithms for Low-rank and Nonsmooth Matrix Problems	2018	Dan Garber Atara Kaplan
+	Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition	2022	Michał Dereziński Elizaveta Rebrova

Cited by (69)

Action	Title	Year	Authors
+	A Nonconvex Splitting Method for Symmetric Nonnegative Matrix Factorization: Convergence Analysis and Optimality	2017	Songtao Lu Mingyi Hong Zhengdao Wang
+	Convergence of Stochastic Gradient Descent for PCA	2015	Ohad Shamir
+	Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm	2016	Prateek Jain Chi Jin Sham M. Kakade Praneeth Netrapalli Aaron Sidford
+	History PCA: A New Algorithm for Streaming PCA	2018	Puyudi Yang Cho‐Jui Hsieh Jane-Ling Wang
+	On Global Linear Convergence in Stochastic Nonconvex Optimization for Semidefinite Programming	2019	Jinshan Zeng Ke Ma Yuan Yao
+	Bootstrapping the error of Oja's Algorithm	2021	Robert Lunde Purnamrita Sarkar Rachel Ward
+	Parallel SGD: When does averaging help?	2016	Jian Zhang Christopher De Ioannis Mitliagkas Christopher Ré
+	The local convexity of solving systems of quadratic equations	2015	Chris D. White Sujay Sanghavi Rachel Ward
+	Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates	2021	De Huang Jonathan Niles‐Weed Rachel Ward
+	Concentration inequalities for random matrix products	2020	Amelia Henriksen Rachel Ward
+	Concentration inequalities for random matrix products	2019	Amelia Henriksen Rachel Ward
+	Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm	2016	Prateek Jain Chi Jin Sham M. Kakade Praneeth Netrapalli Aaron Sidford
+	Convergence of Stochastic Gradient Descent for PCA	2015	Ohad Shamir
+ PDF Chat	AgFlow: fast model selection of penalized PCA via implicit regularization effects of gradient flow	2021	Haiyan Jiang Haoyi Xiong Dongrui Wu Ji Liu Dejing Dou
+	Guaranteed Matrix Completion via Non-Convex Factorization	2016	Ruoyu Sun Zhi‐Quan Luo
+	First-Order Methods for Fast Feasibility Pursuit of Non-convex QCQPs	2017	Aritra Konar Nicholas D. Sidiropoulos
+ PDF Chat	Guarantees of riemannian optimization for low rank matrix completion	2020	Ke Wei Jian‐Feng Cai Tony F. Chan Shingyu Leung
+	When Are Nonconvex Optimization Problems Not Scary	2016	Ju Sun
+	Global Optimality of Local Search for Low Rank Matrix Recovery	2016	Srinadh Bhojanapalli Behnam Neyshabur Nathan Srebro
+ PDF Chat	A nonconvex splitting method for symmetric nonnegative matrix factorization: Convergence analysis and optimality	2017	Songtao Lu Mingyi Hong Zhengdao Wang
+ PDF Chat	The non-convex geometry of low-rank matrix optimization	2018	Qiuwei Li Zhihui Zhu Gongguo Tang
+ PDF Chat	Near-optimal stochastic approximation for online principal component estimation	2017	Chris Junchi Li Mengdi Wang Han Liu Tong Zhang
+	Guarantees of Riemannian Optimization for Low Rank Matrix Completion	2016	Ke Wei Jian‐Feng Cai Tony F. Chan Shingyu Leung
+	An Improved Gap-Dependency Analysis of the Noisy Power Method	2016	Maria-Florina Balcan Simon S. Du Yining Wang Adams Wei Yu
+ PDF Chat	Learning Stochastic Optimal Policies via Gradient Descent	2021	Stefano Massaroli Michael Poli Stefano Peluchetti Jinkyoo Park Atsushi Yamashita Hajime Asama
+	Jo-DPMF: Differentially private matrix factorization learning through joint optimization	2018	Feng Zhang Victor E. Lee Kim‐Kwang Raymond Choo
+	Rank-one matrix estimation: analytic time evolution of gradient descent dynamics	2021	Antoine Bodin Nicolas Macris
+	Low-rank solutions of linear matrix equations via procrustes flow	2016	Stephen Tu Ross Boczar Max Simchowitz Mahdi Soltanolkotabi Benjamin Recht
+	Low-rank Solutions of Linear Matrix Equations via Procrustes Flow	2015	Stephen Tu Ross Boczar Max Simchowitz Mahdi Soltanolkotabi Benjamin Recht
+	Riemannian Perspective on Matrix Factorization.	2021	Kwangjun Ahn Felipe Suárez
+	Structured Signal Recovery From Quadratic Measurements: Breaking Sample Complexity Barriers via Nonconvex Optimization	2019	Mahdi Soltanolkotabi
+	Grassmannian Optimization for Online Tensor Completion and Tracking With the t-SVD	2022	Kyle Gilman Davoud Ataee Tarzanagh Laura Balzano
+	Global optimality of local search for low rank matrix recovery	2016	Srinadh Bhojanapalli Behnam Neyshabur Nathan Srebro
+ PDF Chat	Lock-Free Optimization for Non-Convex Problems	2017	Shen-Yi Zhao Gong-Duo Zhang Wu-Jun Li
+ PDF Chat	A Geometric Analysis of Phase Retrieval	2017	Ju Sun Qing Qu John Wright
+	Streaming PCA and Subspace Tracking: The Missing Data Case	2018	Laura Balzano Yuejie Chi Yue M. Lu
+	A Formal Framework For Probabilistic Unclean Databases	2018	Christopher De Ihab F. Ilyas Benny Kimelfeld Christopher Ré Theodoros Rekatsinas
+ PDF Chat	Convolutional Phase Retrieval via Gradient Descent	2019	Qing Qu Yuqian Zhang Yonina C. Eldar John Wright
+	Scatterbrain: Unifying Sparse and Low-rank Attention Approximation	2021	Beidi Chen Tri Dao Eric Winsor Zhao Song Atri Rudra Christopher Ré
+ PDF Chat	Taming Convergence for Asynchronous Stochastic Gradient Descent with Unbounded Delay in Non-Convex Learning	2020	Xin Zhang Jia Liu Zhengyuan Zhu

Citing (26)

Action	Title	Year	Authors
+	Optimization Algorithms on Matrix Manifolds	2007	P.-A. Absil Robert Mahony Rodolphe Sepulchre
+ PDF Chat	Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming	1995	Michel X. Goemans David P. Williamson
+ PDF Chat	Low-Rank Optimization with Trace Norm Penalty	2013	Bamdev Mishra Gilles Meyer Francis Bach Rodolphe Sepulchre
+ PDF Chat	Counting Processes and Survival Analysis.	1992	Dorota M. Dabrowska Thomas R. Fleming David P. Harrington
+ PDF Chat	Parallel stochastic gradient algorithms for large-scale matrix completion	2013	Benjamin Recht Christopher Ré
+ PDF Chat	Low-Rank Optimization on the Cone of Positive Semidefinite Matrices	2010	Michel Journée Francis Bach Pierre-Antoine Absil Rodolphe Sepulchre
+	Local Minima and Convergence in Low-Rank Semidefinite Programming	2004	Samuel Burer Renato D. C. Monteiro
+	A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization	2003	Samuel Burer Renato D. C. Monteiro
+	The Noisy Power Method: A Meta Algorithm with Applications	2014	Moritz Hardt Eric Price
+ PDF Chat	Stochastic optimization for PCA and PLS	2012	Raman Arora Andrew Cotter Karen Livescu Nathan Srebro
+	Guaranteed Matrix Completion via Non-Convex Factorization	2016	Ruoyu Sun Zhi‐Quan Luo
+	Fast Exact Matrix Completion with Finite Samples	2015	Prateek Jain Praneeth Netrapalli
+	The Fast Convergence of Incremental PCA	2015	Akshay Balsubramani Sanjoy Dasgupta Yoav Freund
+ PDF Chat	Understanding Alternating Minimization for Matrix Completion	2014	Moritz Hardt
+	Riemannian geometry	1992	Manfredo do Carmo
+ PDF Chat	Solving ptychography with a convex relaxation	2015	Roarke Horstmeyer Richard Y. Chen Xiaoze Ou Brendan Ames Joel A. Tropp Changhuei Yang
+ PDF Chat	Low-rank matrix completion using alternating minimization	2013	Prateek Jain Praneeth Netrapalli Sujay Sanghavi
+	Phase Retrieval using Alternating Minimization	2013	Praneeth Netrapalli Prateek Jain Sujay Sanghavi
+	Stochastic Optimization of PCA with Capped MSG	2013	Raman Arora Andy Cotter Nati Srebro
+ PDF Chat	Solving Quadratic Equations via PhaseLift When There Are About as Many Equations as Unknowns	2013	Emmanuel J. Candès Xiaodong Li
+	A Stochastic PCA Algorithm with an Exponential Convergence Rate.	2014	Ohad Shamir
+	Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization	2011	Alexander Rakhlin Ohad Shamir Karthik Sridharan
+	HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent	2011	Feng Niu Benjamin Recht Christopher Ré Stephen J. Wright
+	A Reliable Effective Terascale Linear Learning System	2011	Alekh Agarwal Olivier Chapelle Miroslav Dudı́k John Langford
+ PDF Chat	Online identification and tracking of subspaces from highly incomplete information	2010	Laura Balzano Robert D. Nowak Benjamin Recht
+ PDF Chat	Phase Retrieval via Wirtinger Flow: Theory and Algorithms	2015	Emmanuel J. Candès Xiaodong Li Mahdi Soltanolkotabi