Help
Cart
Skip main navigation

Available Issues

February 19, 2019 - May 1, 2026

Available Issues

February 19, 2019 - May 1, 2026

Adaptive Stochastic Variance Reduction for Subsampled Newton Method with Cubic Regularization

Published Online:2 Nov 2021https://doi.org/10.1287/ijoo.2021.0058

References

  • Agarwal N, Allen-Zhu Z, Bullins B, Hazan E, Ma T (2017) Finding approximate local minima faster than gradient descent. Proc. 49th Annual ACM SIGACT Sympos. Theory Comput., 1195–1199.Google Scholar
  • Allen-Zhu Z, Hazan E (2016) Variance reduction for faster non-convex optimization. Proc. 33rd Internat. Conf. Machine Learn., vol. 48, 699–707.Google Scholar
  • Bianconcini T, Liuzzi G, Morini B, Sciandrone M (2015) On the use of iterative methods in cubic regularization for unconstrained optimization. Comput. Optim. Appl. 60(1):35–57.Google Scholar
  • Carmon Y, Duchi JC (2019) Gradient descent finds the cubic-regularized non-convex Newton step. SIAM J. Optim. 29(3):2146–2178.Google Scholar
  • Cartis C, Gould NIM, Toint PL (2011a) Adaptive cubic regularisation methods for unconstrained optimization. Part I: Motivation, convergence and numerical results. Math. Programming 127(2):245–295.Google Scholar
  • Cartis C, Gould NIM, Toint PL (2011b) Adaptive cubic regularisation methods for unconstrained optimization. Part II: Worst-case function- and derivative-evaluation complexity. Math. Programming 130(2):295–319.Google Scholar
  • Chen X, Jiang B, Lin T, Zhang S (2019) Adaptively accelerating cubic regularized newton’s methods for convex optimization via random sampling. Preprint, submitted February 15, https://arxiv.org/abs/1802.05426.Google Scholar
  • Erdogdu MA, Montanari A (2015) Convergence rates of sub-sampled Newton methods. Adv. Neural Inform. Processing Systems 28:3052–3060.Google Scholar
  • Fang C, Li CJ, Lin Z, Zhang T (2018) Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. Adv. Neural Inform. Processing Systems, 689–699.Google Scholar
  • Ghorbani B, Krishnan S, Xiao Y (2019) An investigation into neural net optimization via Hessian eigenvalue density. Proc. 36th Internat. Conf. Machine Learn., vol. 97, 2232–2241.Google Scholar
  • Hazan E, Koren T (2016) A linear-time algorithm for trust region problems. Math. Programming 158(1):363–381.Google Scholar
  • Johnson R, Zhang T (2013) Accelerating stochastic gradient descent using predictive variance reduction. Adv. Neural Inform. Processing Systems 26:315–323.Google Scholar
  • Kohler JM, Lucchi A (2017) Sub-sampled cubic regularization for non-convex optimization. Proc. 34th Internat. Conf. Machine Learn., vol. 70, 1895–1904.Google Scholar
  • Nesterov Y (2004) Introductory Lectures on Convex Optimization: A Basic Course (Kluwer, Boston).Google Scholar
  • Nesterov Y, Polyak BT (2006) Cubic regularization of Newton method and its global performance. Math. Programming 108(1):177–205.Google Scholar
  • Nguyen LM, Liu J, Scheinberg K, Takáč M (2017) Sarah: A novel method for machine learning problems using stochastic recursive gradient. Preprint, submitted March 1, https://arxiv.org/abs/1703.00102.Google Scholar
  • Pearlmutter BA (1994) Fast exact multiplication by the Hessian. Neural Comput. 6(1):147–160.Google Scholar
  • Pham NH, Nguyen LM, Phan DT, Tran-Dinh Q (2020) Proxsarah: An efficient algorithmic framework for stochastic composite nonconvex optimization. J. Machine Learn. Res. 21(110):1–48.Google Scholar
  • Reddi SJ, Sra S, Póczos B, Smola A (2016a) Fast incremental method for smooth nonconvex optimization. IEEE 55th Conf. Decision Control (IEEE), 1971–1977.Google Scholar
  • Reddi SJ, Sra S, Poczos B, Smola AJ (2016b) Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization. Adv. Neural Inform. Processing Systems, vol. 29, 1145–1153.Google Scholar
  • Reddi S, Hefny A, Sra S, Póczós B, Smola A (2016c) Stochastic variance reduction for nonconvex optimization. Proc. 33rd Internat. Conf. Machine Learn., vol. 48, 314–323.Google Scholar
  • Reddi S, Zaheer M, Sra S, Póczós B, Bach F, Salakhutdinov R, Smola A (2018) A generic approach for escaping saddle points. Proc. 21st Internat. Conf. Artificial Intelligence Statist., vol. 84, 1233–1242.Google Scholar
  • Roosta-Khorasani F, Mahoney MW (2019) Sub-sampled Newton methods. Math. Programming 174(1):293–326.Google Scholar
  • Sagun L, Evci U, Güney VU, Dauphin Y, Bottou L (2018) Empirical analysis of the Hessian of over-parametrized neural networks. Internat. Conf. Learn. Representations.Google Scholar
  • Tripuraneni N, Stern M, Jin C, Regier J, Jordan MI (2018) Stochastic cubic regularization for fast nonconvex optimization. Adv. Neural Inform. Processing Systems 31:2899–2908.Google Scholar
  • Tropp JA (2015) An introduction to matrix concentration inequalities. Foundations Trends Machine Learn. 8(1–2):1–230.Google Scholar
  • Wang Z, Zhou Y, Liang Y, Lan G (2018) Sample complexity of stochastic variance-reduced cubic regularization for nonconvex optimization. Preprint, submitted February 20, https://arxiv.org/abs/1802.07372v1.Google Scholar
  • Wang Z, Zhou Y, Liang Y, Lan G (2019a) Stochastic variance-reduced cubic regularization for nonconvex optimization. Proc. 22nd Internat. Conf. Artificial Intelligence Statist., vol. 89, 2731–2740.Google Scholar
  • Wang Z, Ji K, Zhou Y, Liang Y, Tarokh V (2019b) Spiderboost and momentum: Faster variance reduction algorithms. Adv. Neural Inform. Processing Systems 32:2406–2416.Google Scholar
  • Xiao L, Zhang T (2014) A proximal stochastic gradient method with progressive variance reduction. SIAM J. Optim. 24(4):2057–2075.Google Scholar
  • Xu P, Roosta-Khorasani F, Mahoney MW (2019) Newton-type methods for non-convex optimization under inexact Hessian information. Math. Programming 184(1):35–70.Google Scholar
  • Xu P, Yang J, Roosta-Khorasani F, Ré C, Mahoney MW (2016) Sub-sampled Newton methods with non-uniform sampling. Adv. Neural Inform. Processing Systems 29:3000–3008.Google Scholar
  • Ye H, Luo L, Zhang Z (2017) Approximate Newton methods and their local convergence. Proc. 34th Internat. Conf. Machine Learn., vol. 70, 3931–3939.Google Scholar
  • Zhang L, Mahdavi M, Jin R (2013) Linear convergence with condition number independent access of full gradients. Adv. Neural Inform. Processing Systems 26:980–988.Google Scholar
  • Zhang J, Xiao L, Zhang S (2018) Adaptive stochastic variance reduction for subsampled Newton method with cubic regularization. Preprint, submitted November 28, https://arxiv.org/abs/1811.11637.Google Scholar
  • Zhou D, Gu Q (2019) Lower bounds for smooth nonconvex finite-sum optimization. Proc. 36th Internat. Conf. Machine Learn., vol. 97, 7574–7583.Google Scholar
  • Zhou D, Xu P, Gu Q (2018) Stochastic variance-reduced cubic regularized Newton methods. Proc. 35th Internat. Conf. Machine Learn., vol. 80,5990–5999.Google Scholar
  • Zhou D, Xu P, Gu Q (2019) Stochastic variance-reduced cubic regularization methods. J. Machine Learn. Res. 20(134):1–47.Google Scholar
  • Zhou D, Xu P, Gu Q (2020) Stochastic nested variance reduction for nonconvex optimization. J. Machine Learn. Res. 21(103):1–63.Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree