Stochastic gradient with least-squares control variates

2025/07/28 by Nobile, Fabio, Raviola, Matteo, Schaeffer, Nathan
#FOS: Mathematics #Numerical Analysis (math.NA) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2507.20981

Abstract

The stochastic gradient descent (SGD) method is a widely used approach for solving stochastic optimization problems, but its convergence is typically slow. Existing variance reduction techniques, such as SAGA, improve convergence by leveraging stored gradient information; however, they are restricted to settings where the objective functional is a finite sum, and their performance degrades when the number of terms in the sum is large. In this work, we propose a novel approach which is well suited when the objective is given by an expectation over random variables with a continuous probability distribution. Our method constructs a control variate by fitting a linear model to past gradient evaluations using weighted discrete least-squares, effectively reducing variance while preserving computational efficiency. We establish theoretical sublinear convergence guarantees for strongly convex objectives and demonstrate the method's effectiveness through numerical experiments on random PDE-constrained optimization problems.

Citations

• Multi-level Monte-Carlo Gradient Methods for Stochastic Optimization with Biased Oracles
• One-shot Learning of Surrogates in PDE-constrained Optimization Under Uncertainty
• Double Control Variates for Gradient Estimation in Discrete Latent Variable Models
• Multi-Iteration Stochastic Optimizers
• A Multilevel Stochastic Gradient method for PDE-constrained Optimal Control Problems with uncertain parameters
• Momentum-Based Variance Reduction in Non-Convex SGD
• Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates
• PDE-constrained optimal control problems with uncertain parameters using\n SAGA
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Sequential sampling for optimal weighted least squares approximations in hierarchical spaces
• Adaptive Sampling Strategies for Stochastic Optimization
• Control Variates for Stochastic Gradient MCMC
• Multivariate approximation in downward closed polynomial spaces
• Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method
• Optimal weighted least-squares methods
• Optimization Methods for Large-Scale Machine Learning
• Optimization Methods for Large-Scale Machine Learning
• Multilevel Monte Carlo analysis for optimal control of elliptic PDEs with random coefficients
• General multilevel adaptations for stochastic approximation algorithms
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly\n Convex Composite Objectives
• Multi-level stochastic approximation algorithms
• Minimizing Finite Sums with the Stochastic Average Gradient
• A Stochastic Approximation Method

Related

• Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization
• A Variance Controlled Stochastic Method with Biased Estimation for Faster Non-convex Optimization
• Stochastic Reweighted Gradient Descent
• Guaranteed Sufficient Decrease for Variance Reduced Stochastic Gradient Descent
• Accelerating Stochastic Gradient Descent For Least Squares Regression