Adaptive Sequential Stochastic Optimization

DOI10.1109/TAC.2018.2816168MaRDI QIDQ4629807zbMATH OpenOpenAlexWikidataFDO

Authors Craig Wilson, Angelia Nedić, Venugopal V. Veeravalli

Publication date 28 March 2019

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.01970

Mathematics Subject Classification ID

Stochastic programming (90C15)

Abstract: A framework is introduced for sequentially solving convex stochastic minimization problems, where the objective functions change slowly, in the sense that the distance between successive minimizers is bounded. The minimization problems are solved by sequentially applying a selected optimization algorithm, such as stochastic gradient descent (SGD), based on drawing a number of samples in order to carry the iterations. Two tracking criteria are introduced to evaluate approximate minimizer quality: one based on being accurate with respect to the mean trajectory, and the other based on being accurate in high probability (IHP). An estimate of a bound on the minimizers' change, combined with properties of the chosen optimization algorithm, is used to select the number of samples needed to meet the desired tracking criterion. A technique to estimate the change in minimizers is provided along with analysis to show that eventually the estimate upper bounds the change in minimizers. This estimate of the change in minimizers provides sample size selection rules that guarantee that the tracking criterion is met for sufficiently large number of time steps. Simulations are used to confirm that the estimation approach provides the desired tracking accuracy in practice, while being efficient in terms of number of samples used in each time step.

Cited in

(8)

• Optimal adaptive policies for sequential allocation problems
• ASD+M: automatic parameter tuning in stochastic optimization and on-line learning
• Non-asymptotic error bounds for constant stepsize stochastic approximation for tracking mobile agents
• Adaptive sequential machine learning
• Adaptive System Optimization Using Random Directions Stochastic Approximation
• Stochastic approximation with nondecaying gain: Error bound and data‐driven gain‐tuning
• Maximum likelihood with a time varying parameter
• Tracking time varying parameters via online simplified maximum likelihood

This page was built for publication: Adaptive Sequential Stochastic Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4629807)