Invex Programs: First Order Algorithms and Their Convergence

Many learning problems are modeled as optimization problems. With the explosion in deep learning, many of these problems are modeled as non-convex optimization problems -- either by using non-convex objective functions or by the addition of non-convex constraints. While well-studied algorithms with fast convergence guarantees are available for convex problems, such mathematical tools are more limited for non-convex problems. In fact, the general class of non-convex optimization problems is known to be NP-hard (Jain et al., 2017). Coming up with global certificates of optimality is the major difficulty in solving non-convex problems. In this paper, we take the first steps towards solving a special class of non-convex problems, called invex problems, which attain global minima at every stationary point (Hanson, 1981; Ben-Israel and Mond, 1986). Invex problems are tractable in the sense that we can use local certificates of optimality to establish the global optimality conditions.