Multi-iteration Stochastic Optimizers

Abstract We introduce Multi-Iteration Stochastic Optimizers, a novel class of first-order stochastic methods that control the relative $$L^2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>L</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:math> 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})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>t</mml:mi> <mml:mi>o</mml:mi> <mml:msup> <mml:mi>l</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> stochastic gradient evaluations, compared to $$O(tol^{-1}\log (tol^{-1}))$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>t</mml:mi> <mml:mi>o</mml:mi> <mml:msup> <mml:mi>l</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mo>log</mml:mo> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>t</mml:mi> <mml:mi>o</mml:mi> <mml:msup> <mml:mi>l</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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.