Graphical Convergence of Subgradients in Nonconvex Optimization and Learning
Authors:
- 1 February 2022
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 47 (1) , 209-231
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 17 references indexed in Scilit:
- Efficiency of minimizing compositions of convex functions and smooth mapsMathematical Programming, 2018
- A Vector-Contraction Inequality for Rademacher Complexities2016
- Understanding Machine Learning2014
- Concentration Inequalities2013
- Variational Analysis and Generalized Differentiation I2006
- Local Rademacher complexitiesThe Annals of Statistics, 2005
- Singularities of Semiconcave Functions in Banach Spaces1999
- Variational Analysis1998
- On the method of bounded differences1989
- Convex Analysis1970