Acceleration of Stochastic Approximation by Averaging

DOI10.1137/0330046zbMath0762.62022OpenAlexW2086161653WikidataQ59650387 ScholiaQ59650387MaRDI QIDQ4012456

Boris T. Polyak, Anatoli B. Juditsky

Publication date: 27 September 1992

Published in: SIAM Journal on Control and Optimization (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/6dc61f37ecc552413606d8c89ffbc46ec98ed887

zbMATH Keywords

identificationstochastic optimizationasymptotic normalityalmost sure convergencenonlinear problemaveraging of trajectoriesestimation of the regression parametershighest possible rate of convergencenew recursive algorithm

Mathematics Subject Classification ID

Estimation and detection in stochastic control theory (93E10) Strong limit theorems (60F15) Identification in stochastic control theory (93E12) Stochastic approximation (62L20)

Related Items (only showing first 100 items - show all)

L^p and almost sure rates of convergence of averaged stochastic gradient algorithms: locally strongly convex objective ⋮ Accelerated and Instance-Optimal Policy Evaluation with Linear Function Approximation ⋮ Ascent-Based Monte Carlo Expectation– Maximization ⋮ Probability maximization via Minkowski functionals: convex representations and tractable resolution ⋮ Semi-discrete optimal transport: hardness, regularization and numerical solution ⋮ Technical note—Knowledge gradient for selection with covariates: Consistency and computation ⋮ Online Principal Component Analysis in High Dimension: Which Algorithm to Choose? ⋮ Parallel and distributed asynchronous adaptive stochastic gradient methods ⋮ A probability approximation framework: Markov process approach ⋮ Online Covariance Matrix Estimation in Stochastic Gradient Descent ⋮ Batching Adaptive Variance Reduction ⋮ First-Order Newton-Type Estimator for Distributed Estimation and Inference ⋮ A Systematic Approach to Lyapunov Analyses of Continuous-Time Models in Convex Optimization ⋮ Estimation and inference in adaptive learning models with slowly decreasing gains ⋮ A Convergence Study of SGD-Type Methods for Stochastic Optimization ⋮ The right complexity measure in locally private estimation: it is not the Fisher information ⋮ Distribution-free algorithms for predictive stochastic programming in the presence of streaming data ⋮ Beating a Benchmark: Dynamic Programming May Not Be the Right Numerical Approach ⋮ Parametric level-set inverse problems with stochastic background estimation ⋮ Scalable Bayesian approach for the DINA Q-matrix estimation combining stochastic optimization and variational inference ⋮ Central limit theorems for stochastic gradient descent with averaging for stable manifolds ⋮ Convergence of gradient algorithms for nonconvex \(C^{1+ \alpha}\) cost functions ⋮ Convergence in quadratic mean of averaged stochastic gradient algorithms without strong convexity nor bounded gradient ⋮ Distributed optimal frequency control under communication packet loss in multi-agent electric energy systems ⋮ Distributed stochastic compositional optimization problems over directed networks ⋮ Stochastic Fixed-Point Iterations for Nonexpansive Maps: Convergence and Error Bounds ⋮ An Asymptotic Analysis of Random Partition Based Minibatch Momentum Methods for Linear Regression Models ⋮ Backward Importance Sampling for Online Estimation of State Space Models ⋮ Online Bootstrap Inference For Policy Evaluation In Reinforcement Learning ⋮ Estimation and inference by stochastic optimization ⋮ $l_p$ Regularization for Ensemble Kalman Inversion ⋮ Shallow neural networks for fluid flow reconstruction with limited sensors ⋮ A Distributed Optimal Control Problem with Averaged Stochastic Gradient Descent ⋮ Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis ⋮ On the design of a stable adaptive filter for state estimation in high dimensional systems ⋮ Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization ⋮ An Empirical Interpolation and Model-Variance Reduction Method for Computing Statistical Outputs of Parametrized Stochastic Partial Differential Equations ⋮ Asymptotically efficient recursive estimation for incomplete data models using the observed information. ⋮ Stochastic approximation algorithms: overview and recent trends. ⋮ Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization ⋮ Scalable estimation strategies based on stochastic approximations: classical results and new insights ⋮ An Efficient Stochastic Newton Algorithm for Parameter Estimation in Logistic Regressions ⋮ Probabilistic Bisection Converges Almost as Quickly as Stochastic Approximation ⋮ BRANCHING PARTICLE PRICERS WITH HESTON EXAMPLES ⋮ Parallel Simultaneous Perturbation Optimization ⋮ Projected Stochastic Gradients for Convex Constrained Problems in Hilbert Spaces ⋮ Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity ⋮ Convergence Rate of Incremental Gradient and Incremental Newton Methods ⋮ An Uncertainty-Weighted Asynchronous ADMM Method for Parallel PDE Parameter Estimation ⋮ Subsampling Algorithms for Semidefinite Programming ⋮ Privacy Aware Learning ⋮ Robust Accelerated Gradient Methods for Smooth Strongly Convex Functions ⋮ Entropy-SGD: biasing gradient descent into wide valleys ⋮ On Modification of an Adaptive Stochastic Mirror Descent Algorithm for Convex Optimization Problems with Functional Constraints ⋮ Estimation bias and bias correction in reduced rank autoregressions ⋮ An Adaptive Gradient Method with Energy and Momentum ⋮ Simulation Optimization: A Review and Exploration in the New Era of Cloud Computing and Big Data ⋮ Asymptotic Properties of Stationary Solutions of Coupled Nonconvex Nonsmooth Empirical Risk Minimization ⋮ Smoothed Variable Sample-Size Accelerated Proximal Methods for Nonsmooth Stochastic Convex Programs ⋮ Some Limit Properties of Markov Chains Induced by Recursive Stochastic Algorithms ⋮ A framework for adaptive Monte Carlo procedures ⋮ Generalization error rates in kernel regression: the crossover from the noiseless to noisy regime* ⋮ Quantile estimation with adaptive importance sampling ⋮ Solving Stochastic Optimization with Expectation Constraints Efficiently by a Stochastic Augmented Lagrangian-Type Algorithm ⋮ On-Line Expectation–Maximization Algorithm for latent Data Models ⋮ Convergence acceleration of ensemble Kalman inversion in nonlinear settings ⋮ Stochastic Multilevel Composition Optimization Algorithms with Level-Independent Convergence Rates ⋮ Streaming constrained binary logistic regression with online standardized data ⋮ ASTRO-DF: A Class of Adaptive Sampling Trust-Region Algorithms for Derivative-Free Stochastic Optimization ⋮ Complexity Analysis of stochastic gradient methods for PDE-constrained optimal Control Problems with uncertain parameters ⋮ A universal procedure for parametric frailty models ⋮ The multivariate Révész's online estimator of a regression function and its averaging ⋮ Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization ⋮ Asymptotic optimality in stochastic optimization ⋮ Online algorithm for variance components estimation ⋮ Optimal Transport-Based Distributionally Robust Optimization: Structural Properties and Iterative Schemes ⋮ A strong interference suppressor for satellite signals in GNSS receivers ⋮ Approaches for solving the stochastic equilibrium assignment with variable demand: internal vs. external solution algorithms ⋮ Optimizing Adaptive Importance Sampling by Stochastic Approximation ⋮ The Stochastic Auxiliary Problem Principle in Banach Spaces: Measurability and Convergence ⋮ Some multivariate risk indicators: Minimization by using a Kiefer–Wolfowitz approach to the mirror stochastic algorithm ⋮ Risk-Sensitive Reinforcement Learning via Policy Gradient Search ⋮ Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization ⋮ Iterate averaging, the Kalman filter, and 3DVAR for linear inverse problems ⋮ Optimal non-asymptotic analysis of the Ruppert-Polyak averaging stochastic algorithm ⋮ Mitigating Uncertainty via Compromise Decisions in Two-Stage Stochastic Linear Programming: Variance Reduction ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the rates of convergence of parallelized averaged stochastic gradient algorithms ⋮ Time Averaging Algorithms with Stopping Rules for Multi-Agent Consensus with Noisy Measurements ⋮ Nonlinear acceleration of momentum and primal-dual algorithms ⋮ On Sampling Rates in Simulation-Based Recursions ⋮ A Concentration Bound for Stochastic Approximation via Alekseev’s Formula ⋮ On the Adaptivity of Stochastic Gradient-Based Optimization ⋮ Application of kernel-based stochastic gradient algorithms to option pricing ⋮ Recursive aggregation of estimators by the mirror descent algorithm with averaging ⋮ Discriminative Bayesian filtering lends momentum to the stochastic Newton method for minimizing log-convex functions ⋮ The averaged Robbins-Monro method for linear problems in a Banach space ⋮ Penalty methods with stochastic approximation for stochastic nonlinear programming ⋮ Monte carlo estimation for guaranteed-coverage non-normal tolerance intervals

This page was built for publication: Acceleration of Stochastic Approximation by Averaging