Uniform Graphical Convergence of Subgradients in Nonconvex Optimization and Learning
Authors:
Preprint
Abstract
We investigate the stochastic optimization problem of minimizing population risk, where the loss defining the risk is assumed to be weakly convex. Compositions of Lipschitz convex functions with smooth maps are the primary examples of such losses. We analyze the estimation quality of such nonsmooth and nonconvex problems by their sample average approximations. Our main results establish dimension-dependent rates on subgradient estimation in full generality and dimension-independent rates when the loss is a generalized linear model. As an application of the developed techniques, we analyze the nonsmooth landscape of a robust nonlinear regression problem.Keywords
All Related Versions
This publication has 32 references indexed in Scilit:
- Stochastic Subgradient Method Converges on Tame FunctionsFoundations of Computational Mathematics, 2019
- Subgradient Methods for Sharp Weakly Convex FunctionsJournal of Optimization Theory and Applications, 2018
- Efficiency of minimizing compositions of convex functions and smooth mapsMathematical Programming, 2018
- Mini-batch stochastic approximation methods for nonconvex stochastic composite optimizationMathematical Programming, 2014
- Introduction to the non-asymptotic analysis of random matrices2012
- Uniform exponential convergence of sample average random functions under general sampling with applications in stochastic programmingJournal of Mathematical Analysis and Applications, 2010
- Smooth sample average approximation of stationary points in nonsmooth stochastic optimization and applicationsMathematical Programming, 2008
- Uniform laws of large numbers for set-valued mappings and subdifferentials of random functionsJournal of Mathematical Analysis and Applications, 2007
- Probabilistic bounds (via large deviations) for the solutions of stochastic programming problemsAnnals of Operations Research, 1995
- The quasigradient method for the solving of the nonlinear programming problemsCybernetics and Systems Analysis, 1975