2020

Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions

Zhang, Jingzhao, Lin, Hongzhou, Jegelka, Stefanie et al.

Understand

We provide the first non-asymptotic analysis for finding stationary points of nonsmooth, nonconvex functions.

In particular, we study the class of Hadamard semi-differentiable functions, perhaps the largest class of nonsmooth functions for which the chain rule of calculus holds.
This class contains examples such as ReLU neural networks and others with non-differentiable activation functions.
We first show that finding an $\epsilon$-stationary point with first-order methods is impossible in finite time.

Built on

General theory of differentiation in linear topological spaces
Sova, M · 1964
Earlier work this paper cites.
Optimization of lipschitz continuous functions
Goldstein, A · 1977
Earlier work this paper cites.
An algorithm for constrained optimization with semismooth functions
Mifflin, R · 1977
Earlier work this paper cites.
Optimization and nonsmooth analysis , volume 5
Clarke, F. H · 1990
Earlier work this paper cites.
On concepts of directional differentiability
Shapiro, A · 1990
Earlier work this paper cites.
An introduction to o-minimal geometry
Coste, M · 2000
Earlier work this paper cites.
Approximating subdifferentials by random sampling of gradients
Burke, J. V., Lewis, A. S., and Overton, M. L · 2002
Earlier work this paper cites.
Stochastic approximations and differential inclusions
Benaïm, M., Hofbauer, J., and Sorin, S · 2005
Earlier work this paper cites.
Convergence of the gradient sampling algorithm for nonsmooth nonconvex optimization
Kiwiel, K. C · 2007
Earlier work this paper cites.
Learning multiple layers of features from tiny images
Krizhevsky, A. and Hinton, G · 2009
Earlier work this paper cites.
Adaptive subgradient methods for online learning and stochastic optimization
Duchi, J., Hazan, E., and Singer, Y · 2011
Earlier work this paper cites.
Stochastic first-and zeroth-order methods for nonconvex stochastic programming
Ghadimi, S. and Lan, G · 2013
Earlier work this paper cites.
Escaping from saddle points—online stochastic gradient for tensor decomposition
Ge, R., Huang, F., Jin, C., and Yuan, Y · 2015
Earlier work this paper cites.
Adam: A method for stochastic optimization
Kingma, D. P. and Ba, J · 2015
Earlier work this paper cites.
Deep residual learning for image recognition
He, K., Zhang, X., Ren, S., and Sun, J · 2016
Earlier work this paper cites.

Similar

Stochastic variance reduction for nonconvex optimization
Reddi, S. J., Hefny, A., Sra, S., Poczos, B., and Smola, A · 2016
Cited alongside, same era.
Finding approximate local minima faster than gradient descent
Agarwal, N., Allen-Zhu, Z., Bullins, B., Hazan, E., and Ma, T · 2017
Cited alongside, same era.
Lower bounds for finding stationary points I
Carmon, Y., Duchi, J. C., Hinder, O., and Sidford, A · 2017
Cited alongside, same era.
How to escape saddle points efficiently
Jin, C., Ge, R., Netrapalli, P., Kakade, S. M., and Jordan, M. I · 2017
Cited alongside, same era.
Automatic differentiation in pytorch
Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang, E., DeVito, Z., Lin, Z., Desmaison, A., Antiga, L., and Lerer, A · 2017
Cited alongside, same era.
How to make the gradients small stochastically: Even faster convex and nonconvex SGD
Allen-Zhu, Z · 2018
Cited alongside, same era.
First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems
Bolte, J., Sabach, S., Teboulle, M., and Vaisbourd, Y · 2018
Cited alongside, same era.
Gradient sampling methods for nonsmooth optimization
Original
Burke, J. V., Curtis, F. E., Lewis, A. S., Overton, M. L., and Simões, L. E · 2018
Cited alongside, same era.
Accelerated methods for nonconvex optimization
Carmon, Y., Duchi, J. C., Hinder, O., and Sidford, A · 2018
Cited alongside, same era.
Escaping saddles with stochastic gradients
Daneshmand, H., Kohler, J., Lucchi, A., and Hofmann, T · 2018
Cited alongside, same era.
Stochastic subgradient method converges on tame functions
Davis, D., Drusvyatskiy, D., Kakade, S., and Lee, J. D · 2018
Cited alongside, same era.
Stochastic methods for composite and weakly convex optimization problems
Duchi, J. C. and Ruan, F · 2018
Cited alongside, same era.

Then

Lectures on convex optimization , volume 137
Nesterov, Y · 2018
Later among the works it cites.
On the convergence rate of stochastic mirror descent for nonsmooth nonconvex optimization
Original
Zhang, S. and He, N · 2018
Later among the works it cites.
Stochastic nested variance reduction for nonconvex optimization
Zhou, D., Xu, P., and Gu, Q · 2018
Later among the works it cites.
Lower bounds for non-convex stochastic optimization
Original
Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Srebro, N., and Woodworth, B · 2019
Later among the works it cites.
Conservative set valued fields, automatic differentiation, stochastic gradient method and deep learning
Original
Bolte, J. and Pauwels, E · 2019
Later among the works it cites.
Stochastic model-based minimization of weakly convex functions
Davis, D. and Drusvyatskiy, D · 2019
Later among the works it cites.
Introduction to optimization and Hadamard semidifferential calculus, 2019
Delfour, M. C · 2019
Later among the works it cites.
The complexity of finding stationary points with stochastic gradient descent
Original
Drori, Y. and Shamir, O · 2019
Later among the works it cites.
Efficiency of minimizing compositions of convex functions and smooth maps
Drusvyatskiy, D. and Paquette, C · 2019
Later among the works it cites.
Sharp analysis for nonconvex sgd escaping from saddle points
Fang, C., Lin, Z., and Zhang, T · 2019
Later among the works it cites.
The complexity of making the gradient small in stochastic convex optimization
Original
Foster, D., Sekhari, A., Shamir, O., Srebro, N., Sridharan, K., and Woodworth, B · 2019
Later among the works it cites.
Optimal finite-sum smooth non-convex optimization with SARAH
Original
Nguyen, L. M., van Dijk, M., Phan, D. T., Nguyen, P. H., Weng, T.-W., and Kalagnanam, J. R · 2019
Later among the works it cites.
On the convergence to stationary points of deterministic and randomized feasible descent directions methods
Beck, A. and Hallak, N · 2020
Closest in time.
Can we find near-approximately-stationary points of nonsmooth nonconvex functions?
Original
Shamir, O · 2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…