Fetching the paper…
Reading the bibliography…
In this paper, we give a sharp analysis for Stochastic Gradient Descent (SGD) and prove that SGD is able to efficiently escape from saddle points and find an $(\epsilon, O(\epsilon^{0.5}))$-approximate second-order stationary point in $\tilde{O}(\epsilon^{-3.5})$ stochastic gradient computations for generic nonconvex optimization problems, when the objective function satisfies gradient-Lipschitz, Hessian-Lipschitz, and dispersive noise assumptions.
Stochastic recursive variance-reduced cubic regularization methods
Zhou, D. & Gu, Q. (2019) · 1901
Earlier work this paper cites.
Stochastic gradient descent escapes saddle points efficiently
Jin, C., Netrapalli, P., Ge, R., Kakade, S. M., & Jordan, M. I. (2019) · 1902
Earlier work this paper cites.
A stochastic trust region method for non-convex minimization
Shen, Z., Zhou, P., Fang, C., & Ribeiro, A. (2019) · 1903
Earlier work this paper cites.
A stochastic approximation method
Robbins, H. & Monro, S. (1951) · 1951
Earlier work this paper cites.
On tail probabilities for martingales
Freedman, D. A. (1975) · 1975
Earlier work this paper cites.
Some dimension-free features of vector-valued martingales
Kallenberg, O. & Sztencel, R. (1991) · 1991
Earlier work this paper cites.
Optimum bounds for the distributions of martingales in banach spaces
Pinelis, I. (1994) · 1994
Earlier work this paper cites.
Speaker verification using adapted gaussian mixture models
Reynolds, D. A., Quatieri, T. F., & Dunn, R. B. (2000) · 2000
Earlier work this paper cites.
Introductory lectures on convex optimization: A basic course
Nesterov, Y. (2004) · 2004
Earlier work this paper cites.
Reducing the dimensionality of data with neural networks
Hinton, G. E. & Salakhutdinov, R. R. (2006) · 2006
Earlier work this paper cites.
Cubic regularization of newton method and its global performance
Nesterov, Y. & Polyak, B. T. (2006) · 2006
Earlier work this paper cites.
High-probability regret bounds for bandit online linear optimization
Bartlett, P. L., Dani, V., Hayes, T. P., Kakade, S. M., Rakhlin, A., & Tewari, A. (2008) · 2008
Earlier work this paper cites.
The tradeoffs of large scale learning
Bottou, L. & Bousquet, O. (2008) · 2008
Earlier work this paper cites.
Information-theoretic lower bounds on the oracle complexity of convex optimization
Agarwal, A., Wainwright, M. J., Bartlett, P. L., & Ravikumar, P. K. (2009) · 2009
Earlier work this paper cites.
Exact matrix completion via convex optimization
Candès, E. J. & Recht, B. (2009) · 2009
Earlier work this paper cites.
Principal component analysis
Jolliffe, I. (2011) · 2011
Earlier work this paper cites.
Making gradient descent optimal for strongly convex stochastic optimization
Rakhlin, A., Shamir, O., & Sridharan, K. (2012) · 2012
Earlier work this paper cites.
Most tensor problems are np-hard
Hillar, C. J. & Lim, L.-H. (2013) · 2013
Cited alongside, same era.
Low-rank matrix completion using alternating minimization
Jain, P., Netrapalli, P., & Sanghavi, S. (2013) · 2013
Cited alongside, same era.
Accelerating stochastic gradient descent using predictive variance reduction
Johnson, R. & Zhang, T. (2013) · 2013
Cited alongside, same era.
Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
Dauphin, Y. N., Pascanu, R., Gulcehre, C., Cho, K., Ganguli, S., & Bengio, Y. (2014) · 2014
Cited alongside, same era.
SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives
Defazio, A., Bach, F., & Lacoste-Julien, S. (2014) · 2014
Cited alongside, same era.
Escaping from saddle points – online stochastic gradient for tensor decomposition
First-order methods almost always avoid saddle points
Lee, J. D., Panageas, I., Piliouras, G., Simchowitz, M., Jordan, M. I., & Recht, B. (2017) · 2017
Later among the works it cites.
Non-convex finite-sum optimization via scsg methods
Lei, L., Ju, C., Chen, J., & Jordan, M. I. (2017) · 2017
Later among the works it cites.
Convergence analysis of two-layer neural networks with relu activation
Li, Y. & Yuan, Y. (2017) · 2017
Later among the works it cites.
Minimizing finite sums with the stochastic average gradient
Schmidt, M., Le Roux, N., & Bach, F. (2017) · 2017
Later among the works it cites.
Complete dictionary recovery over the sphere i: Overview and the geometric picture
Sun, J., Qu, Q., & Wright, J. (2017) · 2017
Later among the works it cites.
A hitting time analysis of stochastic gradient langevin dynamics
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Ge, R., Huang, F., Jin, C., & Yuan, Y. (2015) · 2015
Cited alongside, same era.
When are nonconvex problems not scary?
Sun, J., Qu, Q., & Wright, J. (2015) · 2015
Cited alongside, same era.
Tensorflow: A system for large-scale machine learning
Abadi, M., Barham, P., Chen, J., Chen, Z., Davis, A., Dean, J., Devin, M., Ghemawat, S., Irving, G., Isard, M., Kudlur, M., Levenberg, J., Monga, R., Moore, S., Murray, D. G., Steiner, B., Tucker, P., Vasudevan, V., Warden, P., Wicke, M., Yu, Y., & Zheng, X. (2016) · 2016
Cited alongside, same era.
Gradient descent efficiently finds the cubic-regularized non-convex newton step
Carmon, Y. & Duchi, J. C. (2016) · 2016
Cited alongside, same era.
Matrix completion has no spurious local minimum
Ge, R., Lee, J. D., & Ma, T. (2016) · 2016
Cited alongside, same era.
Guaranteed matrix completion via non-convex factorization
Sun, R. & Luo, Z.-Q. (2016) · 2016
Cited alongside, same era.
Finding approximate local minima faster than gradient descent
Agarwal, N., Allen-Zhu, Z., Bullins, B., Hazan, E., & Ma, T. (2017) · 2017
Cited alongside, same era.
Zhang, Y., Liang, P., & Charikar, M. (2017) · 2017
Later among the works it cites.
Recovery guarantees for one-hidden-layer neural networks
Zhong, K., Song, Z., Jain, P., Bartlett, P. L., & Dhillon, I. S. (2017) · 2017
Later among the works it cites.
Neon2: Finding local minima via first-order oracles
Allen-Zhu, Z. & Li, Y. (2018) · 2018
Later among the works it cites.
Accelerated methods for nonconvex optimization
Carmon, Y., Duchi, J. C., Hinder, O., & Sidford, A. (2018) · 2018
Later among the works it cites.
Escaping saddles with stochastic gradients
Daneshmand, H., Kohler, J., Lucchi, A., & Hofmann, T. (2018) · 2018
Later among the works it cites.
Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator
Fang, C., Li, C. J., Lin, Z., & Zhang, T. (2018) · 2018
Later among the works it cites.
A generic approach for escaping saddle points
Reddi, S., Zaheer, M., Sra, S., Poczos, B., Bach, F., Salakhutdinov, R., & Smola, A. (2018) · 2018
Later among the works it cites.
Stochastic cubic regularization for fast nonconvex optimization
Tripuraneni, N., Stern, M., Jin, C., Regier, J., & Jordan, M. I. (2018) · 2018
Later among the works it cites.
First-order stochastic algorithms for escaping from saddle points in almost linear time
Xu, Y., Rong, J., & Yang, T. (2018) · 2018
Later among the works it cites.
A proximal stochastic gradient method with progressive variance reduction
Xiao, L. & Zhang, T. (2014) · 2075
Closest in time.
Learning bounds for kernel regression using effective data dimensionality
Zhang, T. (2005) · 2098
Closest in time.