Research map / Optimization / Optimizers
Non-asymptotic Analysis of Biased Adaptive Stochastic Approximation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives non-asymptotic convergence guarantees for adaptive stochastic approximation (Adagrad, RMSProp, AMSGrad) with time-dependent biased gradient estimators, under PL and non-convex smooth settings, and validates on IWAE/BR-IWAE VAE experiments on CIFAR-10.
Problem
Stochastic gradient methods with adaptive steps are widely used, but existing non-asymptotic theory assumes unbiased gradients, while many applications (RL, generative models with Monte Carlo, bilevel and conditional stochastic optimization, IWAE) produce biased gradients.
Approach
A unified biased adaptive stochastic approximation framework with a time-dependent bias term r_n and a bias-control assumption on the preconditioner A_n, yielding O(log n/sqrt(n) + b_n) rates for Adagrad, RMSProp and AMSGrad on non-convex smooth functions and linear rates under PL.
Key results
- Adagrad, RMSProp and AMSGrad with biased gradients converge to critical points at rate O(log n/sqrt(n) + b_n) for non-convex smooth objectives, matching the unbiased rate when bias is O(n^{-1/4}).
- Under the PL condition, the analysis yields a linear convergence rate in expectation for the risk.
- On CIFAR-10 VAE experiments, BR-IWAE gives lower test negative log-likelihood than IWAE, which beats VAE, across Adagrad, RMSProp and Adam; observed gradient-norm decay is at least as fast as the predicted rates.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use IWAE instead of VAE | VAE on CIFAR-10 · CIFAR-10 test set | negative log-likelihood | Helped |
| Use BR-IWAE instead of IWAE | IWAE on CIFAR-10 · CIFAR-10 test set | negative log-likelihood | Helped |
| Increase the bias-decay exponent α | IWAE with Adagrad, RMSProp, or Adam · CIFAR-10 | squared gradient norm convergence | Helped |
| Increase α beyond a threshold | IWAE with Adagrad, RMSProp, or Adam · CIFAR-10 | squared gradient norm convergence | No clear effect |
| Use Adam instead of Adagrad or RMSProp | IWAE · CIFAR-10 | squared gradient norm convergence | Helped |
Surprising findings
- Empirical gradient-norm convergence is faster than the predicted theoretical rates, and the authors suggest the bounds on FashionMNIST may be closer to tight.
Limitations
- Results require bias control assumption (H3) and bounded eigenvalues of A_n (H4), with boundedness of stochastic gradients (H5) needed for the sharper Adagrad/RMSProp rates.
- Optimal number of Monte Carlo samples per iteration for a given generative model is left open.
Experimental setup
Datasets: CIFAR-10 FashionMNIST
Benchmarks: CIFAR-10 FashionMNIST
Metrics: negative log-likelihood squared gradient norm
Baselines: VAE IWAE BR-IWAE
Builds on: Adagrad RMSProp AMSGrad IWAE BR-IWAE
Closest papers by meaning
- A Guide Through the Zoo of Biased SGD (NeurIPS 2023 · similarity 0.90)
- The Implicit Bias for Adaptive Optimization Algorithms on Homogeneous Neural Networks (ICML 2021 · similarity 0.90)
- Robustness Analysis of Non-Convex Stochastic Gradient Descent using Biased Expectations (NeurIPS 2020 · similarity 0.90)
- Direction Matters: On the Implicit Bias of Stochastic Gradient Descent with Moderate Learning Rate (ICLR 2021 · similarity 0.90)
- The Global Convergence Time of Stochastic Gradient Descent in Non-Convex Landscapes: Sharp Estimates via Large Deviations (ICML 2025 · similarity 0.88)
- A Comprehensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.