Multi-iteration Stochastic Optimizers

Applied Mathematics & Optimization, vol. 93

Abstract

Abstract We introduce Multi-Iteration Stochastic Optimizers, a novel class of first-order stochastic methods that control the relative $$L^2$$ L 2 error using successive control variates along the iteration path. By exploiting correlations between iterates, these control variates reduce the estimator’s variance, making an accurate mean gradient estimation computationally affordable. Our approach centers on the Multi-Iteration stochastiC Estimator (MICE), which can be seamlessly coupled with any first-order stochastic optimizer due to its non-intrusive design. The algorithm adaptively selects which iterates to include in its index set. We provide both an error analysis of MICE and a convergence analysis for Multi-Iteration Stochastic Optimizers across various problem classes, including some non-convex cases. In the smooth, strongly convex setting, we demonstrate that to approximate a minimizer within a tolerance tol , SGD-MICE requires, on average, $$O(tol^{-1})$$ O ( t o l - 1 ) stochastic gradient evaluations, compared to $$O(tol^{-1}\log (tol^{-1}))$$ O ( t o l - 1 log ( t o l - 1 ) ) for SGD with adaptive batch sizes. In numerical experiments, SGD-MICE achieved the desired tolerance with fewer than 3% of the gradient evaluations required by adaptive batch SGD. Additionally, MICE offers a straightforward stopping criterion based on the gradient norm, validated through consistency tests. To assess its efficiency, we present examples using both SGD-MICE and Adam-MICE, including a stochastic adaptation of the Rosenbrock function and logistic regression on various datasets. Compared to SGD, SAG, SAGA, SVRG, and SARAH, our approach consistently reduces the gradient sampling cost without the need for extensive parameter tuning.

Authors 4

1. André Gustavo Carlon corresponding Aachen Department of Mathematics

   RWTH Aachen University

   Affiliation as printed

   Department of Mathematics, RWTH Aachen University, Pontdriesch 14-16, 52062, Aachen, Germany

2. Luis Espath

   University of Nottingham

   Affiliation as printed

   School of Mathematical Sciences, University of Nottingham, NG7 2RD, Nottingham, UK

3. Rafael Holdorf Lopez

   Universidade Federal de Santa Catarina

   Affiliation as printed

   School of Engineering, Federal University of Santa Catarina, Rua João Pio Duarte da Silva, Florianópolis, SC, 88040-970, Brazil

4. Raul F. Tempone Aachen Department of Mathematics

   RWTH Aachen University · King Abdullah University of Science and Technology

   Affiliation as printed

   Alexander von Humboldt Professor in Mathematics for Uncertainty Quantification, RWTH Aachen University, Aachen, Germany

   Computer, Electrical and Mathematical Sciences & Engineering Division, King Abdullah University of Science & Technology, 23955-6900, Thuwal, Saudi Arabia

   Department of Mathematics, RWTH Aachen University, Pontdriesch 14-16, 52062, Aachen, Germany