On smoothing, regularization, and averaging in stochastic approximation methods for stochastic variational inequality problems

DOI10.1007/S10107-017-1175-YzbMATH Open1457.90102arXiv1411.0209OpenAlexW1822292100WikidataQ105583485 ScholiaQ105583485MaRDI QIDQ1680973FDOQ1680973

Authors: Farzad Yousefian, Angelia Nedić, Uday V. Shanbhag 

Publication date: 17 November 2017

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: Traditionally, stochastic approximation schemes for SVIs have relied on strong monotonicity and Lipschitzian properties of the underlying map. In contrast, we consider monotone stochastic variational inequality (SVI) problems where the strong monotonicity and Lipschitzian assumptions on the mappings are weakened. In the first part of the paper, to address such shortcomings, a regularized smoothed SA (RSSA) scheme is developed wherein the stepsize, smoothing, and regularization parameters are diminishing sequences updated after every iteration. Under suitable assumptions on the sequences, we show that the algorithm generates iterates that converge to a solution in an almost sure sense, extending the results in [16] to the non-Lipschitzian regime. Motivated by the need to develop non-asymptotic rate statements, in the second part of the paper, we develop a variant of the RSSA scheme, denoted by aRSSA${}_r$, in which we employ a weighted iterate-averaging, parametrized by a scalar $r$ where $r=1$ provides us with the standard averaging scheme. We make several contributions in this context: First, we show that the gap function associated with the sequences by the aRSSA${}_r$ scheme tends to zero when the parameter sequences are chosen appropriately. Second, we show that the gap function associated with the averaged sequence diminishes to zero at the optimal rate $calO(1/sqrtK)$ after $K$ steps when smoothing and regularization are suppressed and $r<1$, thus improving the rate statement for the standard averaging which admits a rate of $calO(ln(K)/sqrtK)$. Third, we develop a window-based variant of this scheme that also displays the optimal rate for $r<1$. Notably, we prove the superiority of the scheme with $r<1$ with its counterpart with $r=1$ in terms of the constant factor of the error bound when the size of the averaging window is sufficiently large.

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

Recommendations

• Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants
• Sample average approximation method for a class of stochastic variational inequality problems
• Stochastic variational inequalities: residual minimization smoothing sample average approximations
• A fast stochastic approximation-based subgradient extragradient algorithm with variance reduction for solving stochastic variational inequality problems
• Sample average approximation method based on regularized gap function for stochastic mixed variational inequality problems

zbMATH Keywords

gap functionleast norm solutionsmoothed Tikhonov trajectory

Mathematics Subject Classification ID

Applications of game theory (91A80) Stochastic programming (90C15) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Variational inequalities (49J40)

Cites Work

• Variational Analysis
• Acceleration of Stochastic Approximation by Averaging
• Title not available (Why is that?)
• A Stochastic Approximation Method
• Robust Stochastic Approximation Approach to Stochastic Programming
• On stochastic gradient and subgradient methods with adaptive steplength sequences
• Title not available (Why is that?)
• Finite-Dimensional Variational Inequalities and Complementarity Problems
• Sample average approximation methods for a class of stochastic variational inequality problems
• Lectures on Stochastic Programming
• Introduction to Stochastic Programming
• Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework
• Stochastic Approximation Approaches to the Stochastic Variational Inequality Problem
• Weak Sharp Solutions of Variational Inequalities
• Solving variational inequalities with stochastic mirror-prox algorithm
• Nondifferential optimization via adaptive smoothing
• A class of gap functions for variational inequalities
• General bounds and finite-time improvement for the Kiefer-Wolfowitz stochastic approximation algorithm
• Confidence regions for stochastic variational inequalities
• Regularized Iterative Stochastic Approximation Methods for Stochastic Variational Inequality Problems
• Monte Carlo sampling approach to stochastic programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the characterization of solution sets of smooth and nonsmooth convex stochastic Nash games
• Addressing supply-side risk in uncertain power markets: stochastic Nash models, scalable algorithms and error analysis
• stochastic quasigradient methods and their application to system optimization^†
• On stochastic subgradient mirror-descent algorithm with weighted averaging
• Decentralized Resource Allocation in Dynamic Networks of Agents
• Stochastic optimization problems with nondifferentiable cost functionals
• Randomized smoothing for stochastic optimization
• Distributed computation of equilibria in monotone Nash games via iterative regularization techniques
• On smoothing, regularization, and averaging in stochastic approximation methods for stochastic variational inequality problems
• Symmetric confidence regions and confidence intervals for normal map formulations of stochastic variational inequalities
• Self-Tuned Stochastic Approximation Schemes for Non-Lipschitzian Stochastic Multi-User Optimization and Nash Games
• Adaptive smoothing method, deterministically computable generalized Jacobians, and the Newton method

Cited In (42)

• Variance-based single-call proximal extragradient algorithms for stochastic mixed variational inequalities
• A Variable Sample-Size Stochastic Quasi-Newton Method for Smooth and Nonsmooth Stochastic Convex Optimization
• An infeasible stochastic approximation and projection algorithm for stochastic variational inequalities
• Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants
• A Hybrid Newton Method for Stochastic Variational Inequality Problems and Application to Traffic Equilibrium
• Preface
• Infeasible interior-point algorithms based on sampling average approximations for a class of stochastic complementarity problems and their applications
• On Stochastic and Deterministic Quasi-Newton Methods for Nonstrongly Convex Optimization: Asymptotic Convergence and Rate Analysis
• Variance-Based Modified Backward-Forward Algorithm with Line Search for Stochastic Variational Inequality Problems and Its Applications
• Variance-based extragradient methods with line search for stochastic variational inequalities
• On the solution of stochastic optimization and variational problems in imperfect information regimes
• A Method with Convergence Rates for Optimization Problems with Variational Inequality Constraints
• The Tikhonov regularization for vector equilibrium problems
• Hybrid SGD algorithms to solve stochastic composite optimization problems with application in sparse portfolio selection problems
• Improved variance reduction extragradient method with line search for stochastic variational inequalities
• Incremental Constraint Projection Methods for Monotone Stochastic Variational Inequalities
• Minibatch Forward-Backward-Forward Methods for Solving Stochastic Variational Inequalities
• New First-Order Algorithms for Stochastic Variational Inequalities
• A stochastic projection and contraction algorithm with inertial effects for stochastic variational inequalities
• Randomized Lagrangian stochastic approximation for large-scale constrained stochastic Nash games
• Ensemble of Convolutional Neural Networks for the Detection of Prostate Cancer in Multi-parametric MRI Scans
• Dynamic stochastic projection method for multistage stochastic variational inequalities
• Inexact stochastic subgradient projection method for stochastic equilibrium problems with nonmonotone bifunctions: application to expected risk minimization in machine learning
• On the analysis of variance-reduced and randomized projection variants of single projection schemes for monotone stochastic variational inequality problems
• Variance-based subgradient extragradient method for stochastic variational inequality problems
• A self-adaptive stochastic subgradient extragradient algorithm for the stochastic pseudomonotone variational inequality problem with application
• Primal-dual incremental gradient method for nonsmooth and convex optimization problems
• Two fast variance-reduced proximal gradient algorithms for SMVIPs -- stochastic mixed variational inequality problems with suitable applications to stochastic network games and traffic assignment problems
• A fast stochastic approximation-based subgradient extragradient algorithm with variance reduction for solving stochastic variational inequality problems
• Stochastic approximation for estimating the price of stability in stochastic Nash games
• Stochastic relaxed inertial forward-backward-forward splitting for monotone inclusions in Hilbert spaces
• On smoothing, regularization, and averaging in stochastic approximation methods for stochastic variational inequality problems
• Extragradient Method with Variance Reduction for Stochastic Variational Inequalities
• Simple and Optimal Methods for Stochastic Variational Inequalities, I: Operator Extrapolation
• Variable sample-size optimistic mirror descent algorithm for stochastic mixed variational inequalities
• An online convex optimization-based framework for convex bilevel optimization
• Complexity guarantees for an implicit smoothing-enabled method for stochastic MPECs
• Evolution of Mixed Strategies in Monotone Games
• Open Problem—Iterative Schemes for Stochastic Optimization: Convergence Statements and Limit Theorems
• On stochastic mirror-prox algorithms for stochastic Cartesian variational inequalities: randomized block coordinate and optimal averaging schemes
• An accelerated stochastic extragradient-like algorithm with new stepsize rules for stochastic variational inequalities
• Variable sample-size operator extrapolation algorithm for stochastic mixed variational inequalities

This page was built for publication: On smoothing, regularization, and averaging in stochastic approximation methods for stochastic variational inequality problems

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