Ergodic convergence of a stochastic proximal point algorithm

DOI10.1137/15M1017909MaRDI QIDQ2828340zbMATH OpenFDO

Authors Pascal Bianchi

Publication date 25 October 2016

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

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

zbMATH Keywords

convex programmingproximal point algorithmstochastic approximation

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25)

Abstract: The purpose of this paper is to establish the almost sure weak ergodic convergence of a sequence of iterates $(x_n)$ given by $x_{n+1}=(I+lambd{a}_{n}A(x{i}_{n+1},,.,){)}^{-1}(x_n)$ where $(A(s,,.,):sinE)$ is a collection of maximal monotone operators on a separable Hilbert space, $(x{i}_n)$ is an independent identically distributed sequence of random variables on $E$ and $(lambd{a}_n)$ is a positive sequence in $$. The weighted averaged sequence of iterates is shown to converge weakly to a zero (assumed to exist) of the Aumann expectation $mathbbE(A(x{i}_1,,.,))$ under the assumption that the latter is maximal. We consider applications to stochastic optimization problems of the form $minmathbbE(f(x{i}_1,x))$ w.r.t. $$ where $f$ is a normal convex integrand and $(X_i)$ is a collection of closed convex sets. In this case, the iterations are closely related to a stochastic proximal algorithm recently proposed by Wang and Bertsekas.

Recommendations

• scientific article; zbMATH DE number 776083
• Convergence of stochastic proximal gradient algorithm
• Nonasymptotic convergence of stochastic proximal point methods for constrained convex optimization
• Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
• New nonasymptotic convergence rates of stochastic proximal point algorithm for stochastic convex optimization
• Sub-linear convergence of a stochastic proximal iteration method in Hilbert space
• Convergences of regularized algorithms and stochastic gradient methods with random projections
• Ergodic convergence in subgradient optimization
• Convergence properties of stochastic optimization procedures
• Convergence of Proximal-Like Algorithms

Cites work

• A convex programming algorithm for noisy discrete tomography
• A Stochastic Approximation Method
• A unified approach to the asymptotic almost-equivalence of evolution systems without Lipschitz conditions
• An Introduction to Variational Inequalities and Their Applications
• Convex analysis and measurable multifunctions
• Convex analysis and monotone operator theory in Hilbert spaces
• Convex integral functionals
• Ergodic convergence to a zero of the sum of monotone operators in Hilbert space
• Familles d'opérateurs maximaux monotones et mesurabilite
• scientific article; zbMATH DE number 3462661 (Why is no real title available?)
• scientific article; zbMATH DE number 3449561 (Why is no real title available?)
• scientific article; zbMATH DE number 3222421 (Why is no real title available?)
• scientific article; zbMATH DE number 3341597 (Why is no real title available?)
• scientific article; zbMATH DE number 3376275 (Why is no real title available?)
• Incremental constraint projection methods for variational inequalities
• Incremental proximal methods for large scale convex optimization
• Integrals which are convex functionals
• Measurable dependence of convex sets and functions on parameters
• Monotone (nonlinear) operators in Hilbert space
• Monotone Operators and the Proximal Point Algorithm
• Nonlinear Differential Equations of Monotone Types in Banach Spaces
• On perturbed proximal gradient algorithms
• On Projection Algorithms for Solving Convex Feasibility Problems
• On the Asymptotic Optimality of the Gradient Scheduling Algorithm for Multiuser Throughput Allocation
• On the interchange of subdifferentiation and conditional expectation for convex functionals
• On the Maximality of Sums of Nonlinear Monotone Operators
• On the upper and lower semicontinuity of the Aumann integral
• Produits infinis de resolvantes
• Random algorithms for convex minimization problems
• Robust Stochastic Approximation Approach to Stochastic Programming
• Set-valued analysis
• Solving variational inequalities with stochastic mirror-prox algorithm
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Stability of Stochastic Approximation under Verifiable Conditions
• Stochastic Programs with Recourse
• Strong conical hull intersection property, bounded linear regularity, Jameson's property \((G)\), and error bounds in convex optimization
• The structure and stability of competitive dynamical systems

Cited in

(31)

• Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping. II: Mean-square and linear convergence
• Convergence of stochastic proximal gradient algorithm
• Stochastic proximal splitting algorithm for composite minimization
• SRKCD: a stabilized Runge-Kutta method for stochastic optimization
• Sub-linear convergence of a stochastic proximal iteration method in Hilbert space
• Asymptotic equivalence of evolution equations governed by cocoercive operators and their forward discretizations
• Subgradient averaging for multi-agent optimisation with different constraint sets
• On the computation of equilibria in monotone and potential stochastic hierarchical games
• Ergodic convergence in subgradient optimization with application to simplical decomposition of convex programs
• Ergodic convergence in subgradient optimization
• Nonasymptotic convergence of stochastic proximal point methods for constrained convex optimization
• Stochastic Estimation of the Frobenius Norm in the ACA Convergence Criterion
• Stochastic model-based minimization of weakly convex functions
• scientific article; zbMATH DE number 7079312 (Why is no real title available?)
• Constant step stochastic approximations involving differential inclusions: stability, long-run convergence and applications
• Sublinear convergence of a tamed stochastic gradient descent method in Hilbert space
• The stochastic auxiliary problem principle in Banach spaces: measurability and convergence
• New nonasymptotic convergence rates of stochastic proximal point algorithm for stochastic convex optimization
• On the Convergence to Stationary Points of Deterministic and Randomized Feasible Descent Directions Methods
• Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
• A strong law of large numbers for random monotone operators
• Stochastic regularized Newton methods for nonlinear equations
• Bellman filtering and smoothing for state-space models
• Variance reduction techniques for stochastic proximal point algorithms
• The stochastic proximal distance algorithm
• A guide to stochastic optimisation for large-scale inverse problems
• Nonconvex stochastic Bregman proximal gradient method with application to deep learning
• Revisiting stochastic proximal point methods: generalized smoothness and similarity
• Dynamical behavior of a stochastic forward-backward algorithm using random monotone operators
• Implicit score-driven filters for time-varying parameter models
• A fully stochastic primal-dual algorithm

This page was built for publication: Ergodic convergence of a stochastic proximal point algorithm

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