The stochastic auxiliary problem principle in Banach spaces: measurability and convergence

DOI10.1137/21M1402467zbMATH Open1497.90146arXiv2101.08073OpenAlexW4287374813WikidataQ114074085 ScholiaQ114074085MaRDI QIDQ5097016FDOQ5097016

Authors: Thomas Bittar, Jérôme Lonchampt, Pierre Carpentier, Jean-Philippe Chancelier 

Publication date: 19 August 2022

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

Abstract: The stochastic Auxiliary Problem Principle (APP) algorithm is a general Stochastic Approximation (SA) scheme that turns the resolution of an original optimization problem into the iterative resolution of a sequence of auxiliary problems. This framework has been introduced to design decomposition-coordination schemes but also encompasses many well-known SA algorithms such as stochastic gradient descent or stochastic mirror descent. We study the stochastic APP in the case where the iterates lie in a Banach space and we consider an additive error on the computation of the subgradient of the objective. In order to derive convergence results or efficiency estimates for a SA scheme, the iterates must be random variables. This is why we prove the measurability of the iterates of the stochastic APP algorithm. Then, we extend convergence results from the Hilbert space case to the Banach space case. Finally, we derive efficiency estimates for the function values taken at the averaged sequence of iterates or at the last iterate, the latter being obtained by adapting the concept of modified Fej{'e}r monotonicity to our framework.

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

Recommendations

• Stochastic approximation algorithm for minimax problems
• Iterative methods of solving stochastic convex feasibility problems and applications
• Approximating stationary points of stochastic optimization problems in Banach space
• Ergodic convergence of a stochastic proximal point algorithm
• Robust Stochastic Approximation Approach to Stochastic Programming

zbMATH Keywords

stochastic gradient descentstochastic approximation algorithmsAPPSA algorithmsstochastic mirror descentstochastic auxiliary problem principle

Mathematics Subject Classification ID

Convex programming (90C25) Stochastic programming (90C15) Programming in abstract spaces (90C48)

Cites Work

• Convex analysis and monotone operator theory in Hilbert spaces
• Introductory lectures on convex optimization. A basic course.
• Acceleration of Stochastic Approximation by Averaging
• A Stochastic Approximation Method
• Title not available (Why is that?)
• Robust Stochastic Approximation Approach to Stochastic Programming
• Title not available (Why is that?)
• Convex analysis and measurable multifunctions
• Optimization by decomposition and coordination: A unified approach
• Title not available (Why is that?)
• Stochastic optimal control. The discrete time case
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Convergence of stochastic proximal gradient algorithm
• On perturbed proximal gradient algorithms
• Stochastic Estimation of the Maximum of a Regression Function
• Stochastic proximal gradient methods for nonconvex problems in Hilbert spaces
• Convex optimization: algorithms and complexity
• Epi-convergence of sequences of normal integrands and strong consistency of the maximum likelihood estimator
• A stopping rule for the Robbins-Monro method
• Decomposition/Coordination Algorithms in Stochastic Optimization
• A stopping rule for stochastic approximation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Modified Fejér sequences and applications
• Title not available (Why is that?)
• Projected stochastic gradients for convex constrained problems in Hilbert spaces

This page was built for publication: The stochastic auxiliary problem principle in Banach spaces: measurability and convergence

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