Sub-sampled Trust-Region Methods with Deterministic Worst-Case Complexity Guarantees

2025/07/23 by Goncalves, Max L. N., Grapiglia, Geovani N.
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2507.17556

Abstract

In this paper, we develop and analyze sub-sampled trust-region methods for solving finite-sum optimization problems. These methods employ subsampling strategies to approximate the gradient and Hessian of the objective function, significantly reducing the overall computational cost. We propose a novel adaptive procedure for deterministically adjusting the sample size used for gradient (or gradient and Hessian) approximations. Furthermore, we establish worst-case iteration complexity bounds for obtaining approximate stationary points. More specifically, for a given ε_g, ε_H∈ (0,1), it is shown that an ε_g-approximate first-order stationary point is reached in at most O(ε_g^-2 ) iterations, whereas an (ε_g,ε_H)-approximate second-order stationary point is reached in at most O(max\ε_g^-2ε_H^-1,ε_H^-3\) iterations. Finally, numerical experiments illustrate the effectiveness of our new subsampling technique.

Citations

• A Stochastic Objective-Function-Free Adaptive Regularization Method with Optimal Complexity
• Quadratic and Cubic Regularisation Methods with Inexact function and Random Derivatives for Finite-Sum Minimisation
• LSOS: Line-search Second-Order Stochastic optimization methods for nonconvex finite sums
• Stochastic Analysis of an Adaptive Cubic Regularisation Method under Inexact Gradient Evaluations and Dynamic Hessian Accuracy
• A Fully Stochastic Second-Order Trust Region Method
• Combining Stochastic Adaptive Cubic Regularization with Negative\n Curvature for Nonconvex Optimization
• Inexact restoration with subsampled trust-region methods for finite-sum\n minimization
• Subsampled Nonmonotone Spectral Gradient Methods
• Subsampled Inexact Newton methods for minimizing large sums of convex\n functions
• Cubic Regularization with Momentum for Nonconvex Optimization
• Adaptive Cubic Regularization Methods with Dynamic Inexact Hessian Information and Applications to Finite-Sum Minimization
• Accelerating Adaptive Cubic Regularization of Newton's Method via Random Sampling
• Sub-sampled Cubic Regularization for Non-convex Optimization

Related

• Inexact restoration with subsampled trust-region methods for finite-sum\n minimization
• An Adaptive Sample Size Trust-Region Method for Finite-Sum Minimization
• Trust-region algorithms: probabilistic complexity and intrinsic noise with applications to subsampling techniques
• Complexity of trust-region methods with unbounded Hessian approximations for smooth and nonsmooth optimization
• A stochastic first-order trust-region method with inexact restoration for finite-sum minimization