Invex Programs: First Order Algorithms and Their Convergence
This addresses the optimization challenge for invex problems, which are common in machine learning, but the work is incremental as it builds on known methods with specific improvements.
The paper tackles the slow convergence of gradient descent for invex programs, a non-convex class with global minima at stationary points, by proposing new first-order algorithms with convergence rates and extending them to constrained problems, achieving the first such algorithm for constrained invex programs.
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.