Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent

Understanding the ability of gradient-based stochastic optimization algorithms to find good minima of non-convex objective functions has become an especially important problem due to the success of stochastic gradient descent (SGD) in learning deep neural networks. Although there exist non-convex objective functions and domains for which SGD will necessarily lead to sub-optimal local minima, it appears that for many problems of interest in deep learning, across domains as varied as natural language and images, these worst-case situations do not arise. Indeed, a number of recent works have developed provable guarantees for GD and SGD when used for objective functions defined in terms of neural networks over certain distributions, despite the non-convexity of the underlying optimization problem (Brutzkus et al., 2018; Allen-Zhu et al., 2019; Cao and Gu, 2020; Ji and Telgarsky, 2020; Frei et al., 2020, 2021b). To date, however, there has not been a framework which could unify the variegated approaches for guarantees in these settings. In this work, we introduce the notion of proxy convexity and demonstrate that many existing provable guarantees for learning with neural networks trained by gradient-based optimization fall into a problem satisfying proxy convexity.