Stochastic Optimization of PCA with Capped MSG

We study PCA as a stochastic optimization problem and propose a novel stochastic approximation algorithm which we refer to as "Matrix Stochastic Gradient" (MSG), as well as a practical variant, Capped MSG. We study the method both theoretically and empirically.

stat.ML cs.LG Computer Science Mathematics

Paper

References (20)

01Stochastic Approximation approach to Stochastic ProgrammingA. Juditsky, Guanghui Lan, A. Nemirovski et al.2013 · 1.7k citations

02Stochastic optimization for PCA and PLSR. Arora, Andrew Cotter, Karen Livescu et al.2012 · Allerton Conference on Communication, Control, and Computing · 160 citations

03On the Universality of Online Mirror DescentN. Srebro, Karthik Sridharan, Ambuj Tewari2011 · Neural Information Processing Systems · 154 citations In Library

04Online identification and tracking of subspaces from highly incomplete informationL. Balzano, R. Nowak, B. Recht2010 · Allerton Conference on Communication, Control, and Computing · 446 citations In Library

05Convex OptimizationStephen P. Boyd, L. Vandenberghe2010 · IEEE Transactions on Automatic Control · 41k citations

06Stochastic methods for l1 regularized loss minimizationS. Shalev-Shwartz, Ambuj Tewari2009 · International Conference on Machine Learning · 394 citations

07Efficient projections onto the l1-ball for learning in high dimensionsJohn C. Duchi, S. Shalev-Shwartz, Y. Singer et al.2008 · International Conference on Machine Learning · 1.6k citations

08SVM optimization: inverse dependence on training set sizeS. Shalev-Shwartz, N. Srebro2008 · International Conference on Machine Learning · 289 citations

09Exponentiated Gradient Algorithms for Conditional Random Fields and Max-Margin Markov NetworksM. Collins, A. Globerson, Terry Koo et al.2008 · Journal of machine learning research · 184 citations

10The Tradeoffs of Large Scale LearningL. Bottou, O. Bousquet2007 · Neural Information Processing Systems · 1.7k citations

11Pegasos: primal estimated sub-gradient solver for SVMS. Shalev-Shwartz, Y. Singer, N. Srebro et al.2007 · International Conference on Machine Learning · 2.4k citations

12Mirror descent and nonlinear projected subgradient methods for convex optimizationA. Beck, M. Teboulle2003 · Operations Research Letters · 1.4k citations

Scroll for more · 8 remaining

Similar papers

Convergence of Stochastic Gradient Descent for PCAOhad Shamir2015 · International Conference on Machine Learning · 89 citations In Library

Stochastic Approximation for Canonical Correlation AnalysisR. Arora, T. Marinov, Poorya Mianjy et al.2017 · Neural Information Processing Systems · 40 citations In Library

An Online Riemannian PCA for Stochastic Canonical Correlation AnalysisZihang Meng, Rudrasis Chakraborty, Vikas Singh2021 · arXiv (Cornell University) · 12 citations In Library

Efficient Globally Convergent Stochastic Optimization for Canonical Correlation AnalysisWeiran Wang, Jialei Wang, D. Garber et al.2016 · Neural Information Processing Systems · 31 citations In Library

Online Stochastic DCA With Applications to Principal Component AnalysisHoai An Le Thi, Hoang Phuc Hau Luu, Tao Pham Dinh2022 · IEEE Transactions on Neural Networks and Learning Systems In Library

Average performance analysis of the stochastic gradient method for online PCAS. Chrétien, C. Guyeux, Z. Ho2018 · International Conference on Machine Learning, Optimization, and Data Science · 5 citations In Library

CatCMA : Stochastic Optimization for Mixed-Category ProblemsRyoki Hamano, Shota Saito, Masahiro Nomura et al.2024 · Annual Conference on Genetic and Evolutionary Computation · 13 citations In Library

Online Stochastic DCA with applications to Principal Component AnalysisHoai An Le Thi, Hoang Phuc Hau Luu, Tao Pham Dinh2021 · arXiv (Cornell University) · 8 citations In Library

Stochastic and Private Nonconvex Outlier-Robust PCATyler Maunu, Chenyu Yu, Gilad Lerman2022 · arXiv (Cornell University) · 4 citations In Library

MAC, a novel stochastic optimization methodAttila Nagy, Goitom Simret Kidane, Tamás Turányi et al.2023 · arXiv (Cornell University) In Library

Source of record

arXiv

44B

Welcome.

This panel sticks with you. Pick anything below and it opens right beside it, so you can dig through 60,000-plus records without ever losing your spot here.

Travel 44B

LibraryPapers, policy, standards, statute LabsEvery organization building AI ModelsIntelligence, price, and speed BenchmarksThe evaluation catalog IncidentsAI failures and harms SearchOne field across everything DashboardThe state of AI accountability in NY 44B RegistryThe Art. 44-B compliance portal