Non-convex Optimization for Machine Learning
Open accessAbstract
A vast majority of machine learning algorithms train their models and perform inference by solving optimization problems. In order to capture the learning and prediction problems accurately, structural constraints such as sparsity or low rank are frequently imposed or else the objective itself is designed to be a non-convex function. This is especially true of algorithms that operate in high-dimensional spaces or that train non-linear models such as tensor models and deep networks. The freedom to express the learning problem as a non-convex optimization problem gives immense modeling power to the algorithm designer, but often such problems are NP-hard to solve. A popular workaround to this has been to relax non-convex problems to convex ones and use traditional methods to solve the (convex) relaxed optimization problems. However this approach may be lossy and nevertheless presents significant challenges for large scale optimization. On the other hand, direct approaches to non-convex optimization have met with resounding success in several domains and remain the methods of choice for the practitioner, as they frequently outperform relaxation-based techniques - popular heuristics include projected gradient descent and alternating minimization. However, these are often poorly understood in terms of their convergence and other properties. This monograph presents a selection of recent advances that bridge a long-standing gap in our understanding of these heuristics. We hope that an insight into the inner workings of these methods will allow the reader to appreciate the unique marriage of task structure and generative models that allow these heuristic techniques to (provably) succeed. The monograph will lead the reader through several widely used nonconvex optimization techniques, as well as applications thereof. The goal of this monograph is to both, introduce the rich literature in this area, as well as equip the reader with the tools and techniques needed to analyze these simple procedures for non-convex problems.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Loki Decompose applied Tangram's nonconvex optimization algorithm to deconvolute OmiCLIP embeddings of an H&E image patch or a Visium spot's transcriptomic profile rather than raw gene expression data, providing cell-type composition.
“As an application of Tangram with OmiCLIP embeddings instead of gene expression data, Loki Decompose applied Tangram’s nonconvex optimization algorithm47 to deconvolute the OmiCLIP embeddings of an H&E image patch or the embeddings of a Visium spot’s transcriptomic profile rather than raw gene expression data, providing the cell-type composition of an image patch or a Visium spot (Fig. 5a).”
From A visual–omics foundation model to bridge histopathology with spatial transcriptomics (2025) · cites this paper as [47]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
The citation lists haven’t been fetched yet
References 119 · Cited by 364
Research works printed but not linked: 22
- Kamyar Azizzadenesheli, Alessandro Lazaric, and Anima Anandkumar. Reinforcement Learning of POMDPs using Spectral Methods. In Proceedings of the 29th Conference on Learning Theory (COLT), 2016.
- Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
- Alon Brutzkus and Amir Globerson. Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs. In Proceedings of the 34th International Conference on Machine Learning (ICML), 2017.
- Emmanuel J. Candès, Xiaodong Li, and Mahdi Soltanolkotabi. Phase Retrieval via Wirtinger Flow: Theory and Algorithms. IEEE Transactions on Information Theory, 61(4):1985-2007, 2015.
- Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions. In Proceedings of the 34th International Conference on Machine Learning (ICML), 2017.
- Yeshwanth Cherapanamjeri, Kartik Gupta, and Prateek Jain. Nearly-optimal Robust Ma- trix Completion. In Proceedings of the 34th International Conference on Machine Learning (ICML), 2017.
- Arthur P. Dempster, Nan M. Laird, and Donald B. Rubin. Maximum Likelihood from Incom- plete Data via the EM Algorithm. Journal of the Royal Statistical Society, Series B, 39(1): 1-38, 1977.
- David L. Donoho. Compressed Sensing. IEEE Transactions on Information Theory, 52(4): 1289-1306, 2006.
- John Duchi, Shai Shalev-Shwartz, Yoram Singer, and Tushar Chandra. Efficient Projections onto the ℓ 1 -Ball for Learning in High Dimensions. In Proceedings of the 25th International Conference on Machine Learning (ICML), 2008.
- Simon Foucart. A Note on Guaranteed Sparse Recovery via ℓ 1 -minimization. Applied and Computational Harmonic Analysis, 29(1):97-103, 2010.
- Simon Foucart and Ming-Jun Lai. Sparsest solutions of underdetermined linear systems via ℓ q - minimization for 0 < q ≤ 1. Applied and Computational Harmonic Analysis, 26(3):395-407, 2009.
- Rahul Garg and Rohit Khandekar. Gradient Descent with Sparsification: An iterative algorithm for sparse recovery with restricted isometry property. In Proceedings of the 26th International Conference on Machine Learning (ICML), 2009.
- Rong Ge, Jason D. Lee, and Tengyu Ma. Matrix Completion has No Spurious Local Minimum. In Proceedings of the 30th Annual Conference on Neural Information Processing Systems (NIPS), 2016.
- Gene H. Golub and Charles F. Van Loan. Matrix Computations. Johns Hopkins Studies in Mathematical Sciences. The John Hopkins University Press, 3rd edition, 1996.
- Peter J. Huber and Elvezio M. Ronchetti. Robust Statistics. Wiley Series in Probability and Statistics. John Wiley & Sons, 2nd edition, 2009.
- Prateek Jain and Praneeth Netrapalli. Fast Exact Matrix Completion with Finite Samples. In Proceedings of The 28th Conference on Learning Theory (COLT), 2015.
- Prateek Jain, Raghu Meka, and Inderjit Dhillon. Guaranteed Rank Minimization via Singular Value Projections. In Proceedings of the 24th Annual Conference on Neural Information Processing Systems (NIPS), 2010.
- Prateek Jain, Ambuj Tewari, and Purushottam Kar. On Iterative Hard Thresholding Methods for High-dimensional M-Estimation. In Proceedings of the 28th Annual Conference on Neural Information Processing Systems (NIPS), 2014.
- Praneeth Netrapalli, Prateek Jain, and Sujay Sanghavi. Phase Retrieval using Alternating Min- imization. In Proceedings of the 27th Annual Conference on Neural Information Processing Systems (NIPS), 2013.
- Meng Wang, Weiyu Xu, and Ao Tang. On the Performance of Sparse Recovery Via ℓ p - Minimization (0 ≤ p ≤ 1). IEEE Transactions on Information Theory, 57(11):7255-7278, 2011.
- Allen Y. Yang, Zihan Zhou, Arvind Ganesh Balasubramanian, S Shankar Sastry, and Yi Ma. Fast ℓ 1 -Minimization Algorithms for Robust Face Recognition. IEEE Transactions on Image Processing, 22(8):3234-3246, 2013.
- Yuchen Zhang, Percy Liang, and Moses Charikar. A Hitting Time Analysis of Stochastic Gra- dient Langevin Dynamics. In Proceedings of the 30th Conference on Learning Theory, 2017.
- Authors
- Jain, P., & Kar, P.
- Affiliations
- Microsoft Research (India) (IN)
- Indian Institute of Technology Kanpur (IN)
- Venue
- Foundations and Trends® in Machine Learning
- Publisher
- Emerald
- Published
- 2017-12-04
- Volume
- 10
- Issue
- 3-4
- Pages
- 142-336
- ISSN
- 1935-8237 (ISSN-L)
- 1935-8245
- OpenAlex
- W2772283936
- Cited by
- 364
- References
- 119
- Citations by year
- 2026: 32 · 2025: 31 · 2024: 55 · 2023: 54 · 2022: 47 · 2021: 68 · 2020: 36 · 2019: 29 · 2018: 11 · 2017: 1
- FWCI
- 12.56
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Foundations and Trends® in Machine Learning (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Physical Sciences › Engineering › Computational Mechanics › Sparse and Compressive Sensing Techniques
- Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
- Keywords
- non-convex optimization, projected gradient descent, alternating optimization, convergence analysis, sparsity constraints, low-rank constraint, tensor models, deep neural network, high-dimensional learning, generative models
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
