Invex Programs: First Order Algorithms and Their Convergence
Adarsh Barik Suvrit Sra Jean Honorio
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.