# On The Convergence of First Order Methods for Quasar-Convex Optimization

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

## Key facts

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

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

- [Federated Minimax Optimization: Improved Convergence Analyses and Algorithms](https://mlsanity.com/paper/2203.04850/) (2022)
- [Aiming towards the minimizers: fast convergence of SGD for overparametrized problems](https://mlsanity.com/paper/2306.02601/) (2023)
- [Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimization](https://mlsanity.com/paper/2302.07851/) (2023)
- [Practical and Matching Gradient Variance Bounds for Black-Box Variational Bayesian Inference](https://mlsanity.com/paper/2303.10472/) (2023)
- [Minimisation of Quasar-Convex Functions Using Random Zeroth-Order Oracles](https://mlsanity.com/paper/2505.02281/) (2025)
- [Tackling benign nonconvexity with smoothing and stochastic gradients](https://mlsanity.com/paper/2202.09052/) (2022)
- [On the Convergence to a Global Solution of Shuffling-Type Gradient Algorithms](https://mlsanity.com/paper/2206.05869/) (2022)
- [Smooth Quasar-Convex Optimization with Constraints](https://mlsanity.com/paper/2510.01943/) (2025)

## Abstract (arXiv)

In recent years, the success of deep learning has inspired many researchers to study the optimization of general smooth non-convex functions. However, recent works have established pessimistic worst-case complexities for this class functions, which is in stark contrast with their superior performance in real-world applications (e.g. training deep neural networks). On the other hand, it is found that many popular non-convex optimization problems enjoy certain structured properties which bear some similarities to convexity. In this paper, we study the class of textitquasar-convex functions to close the gap between theory and practice. We study the convergence of first order methods in a variety of different settings and under different optimality criterions. We prove complexity upper bounds that are similar to standard results established for convex functions and much better that state-of-the-art convergence rates of non-convex functions. Overall, this paper suggests that textitquasar-convexity allows efficient optimization procedures, and we are looking forward to seeing more problems that demonstrate similar properties in practice.