# Recent Theoretical Advances in Non-Convex Optimization

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Dec 2020.

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

- [A Geometric Analysis of Neural Collapse with Unconstrained Features](https://mlsanity.com/paper/2105.02375/) (2021)
- [MARINA: Faster Non-Convex Distributed Learning with Compression](https://mlsanity.com/paper/2102.07845/) (2021)
- [Toward Understanding Why Adam Converges Faster Than SGD for Transformers](https://mlsanity.com/paper/2306.00204/) (2023)
- [The Complexity of Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2103.15888/) (2021)
- [Federated Learning with Sparsified Model Perturbation: Improving Accuracy under Client-Level Differential Privacy](https://mlsanity.com/paper/2202.07178/) (2022)
- [Convergence of gradient descent for deep neural networks](https://mlsanity.com/paper/2203.16462/) (2022)
- [Integrating LLMs with ITS: Recent Advances, Potentials, Challenges, and Future Directions](https://mlsanity.com/paper/2501.04437/) (2025)
- [DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization](https://mlsanity.com/paper/2202.01268/) (2022)
- [Maximizing Communication Efficiency for Large-scale Training via 0/1 Adam](https://mlsanity.com/paper/2202.06009/) (2022)
- [Randomized Asymmetric Chain of LoRA: The First Meaningful Theoretical Framework for Low-Rank Adaptation](https://mlsanity.com/paper/2410.08305/) (2024)
- [Quantum Boltzmann machine learning of ground-state energies](https://mlsanity.com/paper/2410.12935/) (2024)
- [Unraveling the Gradient Descent Dynamics of Transformers](https://mlsanity.com/paper/2411.07538/) (2024)
- [The Ball-Proximal (="Broximal") Point Method: a New Algorithm, Convergence Theory, and Applications](https://mlsanity.com/paper/2502.02002/) (2025)
- [First-Order Methods for Convex Optimization](https://mlsanity.com/paper/2101.00935/) (2021)
- [Finite-Time Convergence and Sample Complexity of Actor-Critic Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2405.03082/) (2024)
- [Efficient Learning of Decision-Making Models: A Penalty Block Coordinate Descent Algorithm for Data-Driven Inverse Optimization](https://mlsanity.com/paper/2210.15393/) (2022)
- [Deep Loss Convexification for Learning Iterative Models](https://mlsanity.com/paper/2411.10649/) (2024)
- [A Fully First-Order Layer for Differentiable Optimization](https://mlsanity.com/paper/2512.02494/) (2025)
- [Escaping Local Minima Provably in Non-convex Matrix Sensing: A Deterministic Framework via Simulated Lifting](https://mlsanity.com/paper/2602.05887/) (2026)
- [Damped Proximal Augmented Lagrangian Method for weakly-Convex Problems with Convex Constraints](https://mlsanity.com/paper/2311.09065/) (2023)
- [Beyond Log-Concavity: Theory and Algorithm for Sum-Log-Concave Optimization](https://mlsanity.com/paper/2309.15298/) (2023)
- [Stochastic Two Points Method for Deep Model Zeroth-order Optimization](https://mlsanity.com/paper/2402.01621/) (2024)
- [Stochastic Control Methods for Optimization](https://mlsanity.com/paper/2601.01248/) (2026)
- [AdaCubic: An Adaptive Cubic Regularization Optimizer for Deep Learning](https://mlsanity.com/paper/2604.09437/) (2026)
- [GRACE: A Dynamic Coreset Selection Framework for Large Language Model Optimization](https://mlsanity.com/paper/2604.11810/) (2026)
- [AGGLIO: Global Optimization for Locally Convex Functions](https://mlsanity.com/paper/2111.03932/) (2021)
- [Unified analysis of SGD-type methods](https://mlsanity.com/paper/2303.16502/) (2023)
- [Learning-Rate-Free Learning: Dissecting D-Adaptation and Probabilistic Line Search](https://mlsanity.com/paper/2308.03102/) (2023)
- [Accelerated Fully First-Order Methods for Bilevel and Minimax Optimization](https://mlsanity.com/paper/2405.00914/) (2024)
- [Enabling Pareto-Stationarity Exploration in Multi-Objective Reinforcement Learning: A Multi-Objective Weighted-Chebyshev Actor-Critic Approach](https://mlsanity.com/paper/2507.21397/) (2025)

## Abstract (arXiv)

Motivated by recent increased interest in optimization algorithms for non-convex optimization in application to training deep neural networks and other optimization problems in data analysis, we give an overview of recent theoretical results on global performance guarantees of optimization algorithms for non-convex optimization. We start with classical arguments showing that general non-convex problems could not be solved efficiently in a reasonable time. Then we give a list of problems that can be solved efficiently to find the global minimizer by exploiting the structure of the problem as much as it is possible. Another way to deal with non-convexity is to relax the goal from finding the global minimum to finding a stationary point or a local minimum. For this setting, we first present known results for the convergence rates of deterministic first-order methods, which are then followed by a general theoretical analysis of optimal stochastic and randomized gradient schemes, and an overview of the stochastic first-order methods. After that, we discuss quite general classes of non-convex problems, such as minimization of α-weakly-quasi-convex functions and functions that satisfy Polyak--Lojasiewicz condition, which still allow obtaining theoretical convergence guarantees of first-order methods. Then we consider higher-order and zeroth-order/derivative-free methods and their convergence rates for non-convex optimization problems.