A Stochastic Objective-Function-Free Adaptive Regularization Method with Optimal Complexity

Abstract

A fully stochastic second-order adaptive-regularization method for unconstrained nonconvex optimization is presented which never computes the objective-function value, but yet achieves the optimal $\mathcal{O}({\epsilon }^{-3/2})$ complexity bound for finding first-order critical points. The method is noise-tolerant and the inexactness conditions required for convergence depend on the history of past steps. Applications to cases where derivative evaluation is inexact and to minimization of finite sums by sampling are discussed. Numerical experiments on large binary classification problems illustrate the potential of the new method.

32 pages, 9 figures

References in corpus (22)

• Adam: A Method for Stochastic Optimization
• On the Convergence of Adam and Beyond
• AdaGrad stepsizes: Sharp convergence over nonconvex landscapes
• Bounds on the Lambert function and their application to the outage analysis of user cooperation
• On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization
• Better Theory for SGD in the Nonconvex World
• WNGrad: Learn the Learning Rate in Gradient Descent
• Stochastic Cubic Regularization for Fast Nonconvex Optimization
• The proximal point method revisited
• On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes
• A Simple Convergence Proof of Adam and Adagrad
• Stochastic Variance-Reduced Cubic Regularization for Nonconvex Optimization
• Stochastic Optimization Using a Trust-Region Method and Random Models
• Adaptive Regularization Algorithms with Inexact Evaluations for Nonconvex Optimization
• Adaptive Stochastic Variance Reduction for Subsampled Newton Method with Cubic Regularization
• Accelerating Adaptive Cubic Regularization of Newton's Method via Random Sampling
• Adaptive Regularization for Nonconvex Optimization Using Inexact Function Values and Randomly Perturbed Derivatives
• A note on solving nonlinear optimization problems in variable precision
• Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods
• Complexity of a Class of First-Order Objective-Function-Free Optimization Algorithms
• The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance
• First- and Second-Order Stochastic Adaptive Regularization with Cubics: High Probability Iteration and Sample Complexity