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

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, Asymptotically optimal smoothing of averaged LMS estimates for regression parameter tracking, Estimating the geometric median in Hilbert spaces with stochastic gradient algorithms: \(L^p\) and almost sure rates of convergence, A Bayesian stochastic approximation method, Convergence rate of linear two-time-scale stochastic approximation., An incremental off-policy search in a model-free Markov decision process using a single sample path, A new class of stochastic EM algorithms. Escaping local maxima and handling intractable sampling, Stopping rules for optimization algorithms based on stochastic approximation, A primal-dual algorithm for risk minimization, Multi-level stochastic approximation algorithms, Berry-Esseen bounds for multivariate nonlinear statistics with applications to M-estimators and stochastic gradient descent algorithms, Generalization properties of doubly stochastic learning algorithms, Convergence and efficiency of adaptive importance sampling techniques with partial biasing, Online statistical inference for parameters estimation with linear-equality constraints, Stochastic optimization using a trust-region method and random models, Inversion-free subsampling Newton's method for large sample logistic regression, Some results about averaging in stochastic approximation, Asymptotic properties of dual averaging algorithm for constrained distributed stochastic optimization, An adaptive zero-variance importance sampling approximation for static network dependability evaluation, Convergence rate and averaging of nonlinear two-time-scale stochastic approximation algo\-rithms, Stochastic optimization algorithms of a Bayesian design criterion for Bayesian parameter estimation of nonlinear regression models: Application in pharmacokinetics, Weighted averaging and stochastic approximation, Deviation inequalities for stochastic approximation by averaging, Parameter calibration in wake effect simulation model with stochastic gradient descent and stratified sampling, On the information-adaptive variants of the ADMM: an iteration complexity perspective, Statistical inference for model parameters in stochastic gradient descent, Trajectory averaging for stochastic approximation MCMC algorithms, Algorithms for stochastic optimization with function or expectation constraints, Individual confidence intervals for solutions to expected value formulations of stochastic variational inequalities, On smoothing, regularization, and averaging in stochastic approximation methods for stochastic variational inequality problems, Importance accelerated Robbins-Monro recursion with applications to parametric confidence limits, Nonparametric recursive quantile estimation, Computing highly accurate confidence limits from discrete data using importance sampling, Variance-constrained actor-critic algorithms for discounted and average reward MDPs, Pixelated semantic colorization, A stochastic variational framework for fitting and diagnosing generalized linear mixed models, A new hybrid stochastic approximation algorithm, Mini-batch learning of exponential family finite mixture models, Calculating quantiles of noisy distribution functions using local linear regressions, Bridging the gap between constant step size stochastic gradient descent and Markov chains, Stochastic heavy ball, An optimal method for stochastic composite optimization, A fast and recursive algorithm for clustering large datasets with \(k\)-medians, Online expectation maximization based algorithms for inference in hidden Markov models, On stochastic gradient and subgradient methods with adaptive steplength sequences, On stochastic mirror-prox algorithms for stochastic Cartesian variational inequalities: randomized block coordinate and optimal averaging schemes, A sparsity preserving stochastic gradient methods for sparse regression, A stochastic Kaczmarz algorithm for network tomography, Modeling the dynamics of PDE systems with physics-constrained deep auto-regressive networks, Accelerated randomized stochastic optimization., Why random reshuffling beats stochastic gradient descent, Rates of convergence of adaptive step-size of stochastic approximation algorithms, Non asymptotic controls on a recursive superquantile approximation, On variance reduction for stochastic smooth convex optimization with multiplicative noise, On a multistage discrete stochastic optimization problem with stochastic constraints and nested sampling, A one-measurement form of simultaneous perturbation stochastic approximation, Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions, Adaptive sampling of large deviations, Stochastic gradient descent with Barzilai-Borwein update step for SVM, Minimizing finite sums with the stochastic average gradient, Self-healing umbrella sampling: convergence and efficiency, General multilevel adaptations for stochastic approximation algorithms. II: CLTs, Distributed randomized algorithms for opinion formation, centrality computation and power systems estimation: a tutorial overview, Multistep stochastic mirror descent for risk-averse convex stochastic programs based on extended polyhedral risk measures, Semimartingale stochastic approximation procedure and recursive estimation, Arithmetic means and invariance principles in stochastic approximation, Adaptive importance sampling and control variates, Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm, Fast estimation of the median covariation matrix with application to online robust principal components analysis, Convergence of stochastic proximal gradient algorithm, Dynamic stochastic approximation for multi-stage stochastic optimization, Inexact stochastic mirror descent for two-stage nonlinear stochastic programs, Validation analysis of mirror descent stochastic approximation method, Sample size selection in optimization methods for machine learning, Concentration inequalities for additive functionals: a martingale approach, Online natural gradient as a Kalman filter, Optimizing cluster structures with inner product induced norm based dissimilarity measures: theoretical development and convergence analysis, Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants, A baseline-free procedure for transformation models under interval censorship, A selective overview of deep learning, A stochastic approximation algorithm with multiplicative step size modification, Asymptotic distribution and convergence rates of stochastic algorithms for entropic optimal transportation between probability measures, Stochastic approximation algorithms for superquantiles estimation, Convergence of a stochastic approximation version of the EM algorithm, A stochastic gradient type algorithm for closed-loop problems, Concentration bounds for temporal difference learning with linear function approximation: the case of batch data and uniform sampling, Stochastic approximation search algorithms with randomization at the input, How does a stochastic optimization/approximation algorithm adapt to a randomly evolving optimum/root with jump Markov sample paths, Edgeworth expansions for stochastic approximation theory, Asymptotic expansions of the Robbins-Monro process, Optimization of computer simulation models with rare events, Revisiting the ODE method for recursive algorithms: fast convergence using quasi stochastic approximation, Assessments of epistemic uncertainty using Gaussian stochastic weight averaging for fluid-flow regression, Fundamental design principles for reinforcement learning algorithms, A stochastic Nesterov's smoothing accelerated method for general nonsmooth constrained stochastic composite convex optimization, Computation for latent variable model estimation: a unified stochastic proximal framework, On stochastic accelerated gradient with convergence rate, On a continuous time stochastic approximation problem, Two-stage linear decision rules for multi-stage stochastic programming, A hybrid stochastic optimization framework for composite nonconvex optimization, Accelerated gradient methods for nonconvex nonlinear and stochastic programming, 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, Uncertainty Quantification for Stochastic Approximation Limits Using Chaos Expansion, EXPLICIT HESTON SOLUTIONS AND STOCHASTIC APPROXIMATION FOR PATH-DEPENDENT OPTION PRICING, On the asymptotic rate of convergence of stochastic Newton algorithms and their weighted averaged versions, A Continuous-Time Analysis of Distributed Stochastic Gradient, Variance-Based Extragradient Methods with Line Search for Stochastic Variational Inequalities, Continuous-time stochastic approximation: Convergence and asymptotic efficiency, An Asymptotically Optimal Set Approach for Simulation Optimization, Recursive least-squares and accelerated convergence in stochastic approximation schemes, A companion for the Kiefer-Wolfowitz-Blum stochastic approximation algorithm, Maximum Likelihood Estimation of Regularization Parameters in High-Dimensional Inverse Problems: An Empirical Bayesian Approach. Part II: Theoretical Analysis, Near optimal step size and momentum in gradient descent for quadratic functions, Large-Scale Machine Learning with Stochastic Gradient Descent, Stochastic Approximation for Multivariate and Functional Median, A Central Limit Theorem and Hypotheses Testing for Risk-averse Stochastic Programs, Optimization Methods for Large-Scale Machine Learning, On the regularizing property of stochastic gradient descent, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Nonasymptotic convergence of stochastic proximal point algorithms for constrained convex optimization, The Robbins-Monro type stochastic differential equations. III. Polyak's averaging, Adaptive random search for continuous simulation optimization, Unnamed Item, Central limit theorems for stochastic approximation with controlled Markov chain dynamics, Comparison of Phase II Control Charts Based on Variable Selection Methods, Unnamed Item, On Recursive Estimation in Incomplete Data Models, Minimax Optimal Procedures for Locally Private Estimation, A new convergent hybrid learning algorithm for two-stage stochastic programs, Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach, Spatially-Dimension-Adaptive Sparse Grids for Online Learning, A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares), Stochastic approximation schemes for economic capital and risk margin computations, Noisy Hamiltonian Monte Carlo for Doubly Intractable Distributions, Nesterov-aided stochastic gradient methods using Laplace approximation for Bayesian design optimization, Analysis of a stochastic approximation algorithm for computing quasi-stationary distributions, On the Solution of Stochastic Optimization and Variational Problems in Imperfect Information Regimes, Online estimation of the asymptotic variance for averaged stochastic gradient algorithms, Making the Last Iterate of SGD Information Theoretically Optimal, Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization, Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression, Computing VaR and CVaR using stochastic approximation and adaptive unconstrained importance sampling, Unnamed Item, Reliable Quantification and Efficient Estimation of Credit Risk, Statistical Inference for Online Decision Making via Stochastic Gradient Descent, Unnamed Item, Unnamed Item, Unnamed Item, A Finite Time Analysis of Temporal Difference Learning with Linear Function Approximation, Implicit Regularization and Momentum Algorithms in Nonlinearly Parameterized Adaptive Control and Prediction, Random minibatch subgradient algorithms for convex problems with functional constraints, Finite-Time Analysis and Restarting Scheme for Linear Two-Time-Scale Stochastic Approximation, Recursive algorithms for parameter estimation with adaptive quantizer, Unnamed Item, Unnamed Item, On the Effectiveness of Richardson Extrapolation in Data Science, One-dimensional system arising in stochastic gradient descent, Probabilistic tracking control of dissipated Hamiltonian systems excited by Gaussian white noises