# Invex Programs: First Order Algorithms and Their Convergence

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 29 references that are in the map.
- First posted on arXiv 10 Jul 2023.

## Builds on (most cited first, 14 of 14)

- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity Characterization](https://mlsanity.com/paper/2209.08037/) (2022)
- [Non-convex Optimization for Machine Learning](https://mlsanity.com/paper/1712.07897/) (2017)
- [Variational Policy Gradient Method for Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2007.02151/) (2020)
- [First-order Methods for Geodesically Convex Optimization](https://mlsanity.com/paper/1602.06053/) (2016)
- [Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond](https://mlsanity.com/paper/1906.11985/) (2019)
- [Riemannian Optimization via Frank-Wolfe Methods](https://mlsanity.com/paper/1710.10770/) (2017)
- [Simple algorithms for optimization on Riemannian manifolds with constraints](https://mlsanity.com/paper/1901.10000/) (2019)
- [Convex Learning of Multiple Tasks and their Structure](https://mlsanity.com/paper/1504.03101/) (2015)
- [Provable Acceleration of Heavy Ball beyond Quadratics for a Class of Polyak-Lojasiewicz Functions when the Non-Convexity is Averaged-Out](https://mlsanity.com/paper/2206.11872/) (2022)
- [Improved Imaging by Invex Regularizers with Global Optima Guarantees](https://mlsanity.com/paper/2211.10112/) (2022)
- [Fair Sparse Regression with Clustering: An Invex Relaxation for a Combinatorial Problem](https://mlsanity.com/paper/2102.09704/) (2021)
- [Sparse Mixed Linear Regression with Guarantees: Taming an Intractable Problem with Invex Relaxation](https://mlsanity.com/paper/2206.01167/) (2022)
- [Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspective](https://mlsanity.com/paper/2209.15130/) (2022)

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

- [Cauchy-Schwarz Regularizers](https://mlsanity.com/paper/2503.01639/) (2025)

## Abstract (arXiv)

Invex programs are a special kind of non-convex problems which attain global minima at every stationary point. While classical first-order gradient descent methods can solve them, they converge very slowly. In this paper, we propose new first-order algorithms to solve the general class of invex problems. We identify sufficient conditions for convergence of our algorithms and provide rates of convergence. Furthermore, we go beyond unconstrained problems and provide a novel projected gradient method for constrained invex programs with convergence rate guarantees. We compare and contrast our results with existing first-order algorithms for a variety of unconstrained and constrained invex problems. To the best of our knowledge, our proposed algorithm is the first algorithm to solve constrained invex programs.