Sam Powerhttps://arxiv.org/abs/2307.04456
'Invex Programs: First Order Algorithms and Their Convergence'
- Adarsh Barik, Suvrit Sra, Jean Honorio
There is substantial recent interest in identifying classes of non-convex functions for which optimisation problems are nevertheless tractable in some sense. This work studies such a class ("invex" functions), proposes an algorithm which is adapted to solving optimisation problems from this class, and carries out a theoretical analysis of this algorithm. In particular, this algorithm is able to perform well in scenarios in which gradient descent may run into problems.
Invex Programs: First Order Algorithms and Their Convergence
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.