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

DOI10.1007/S10107-017-1175-YMaRDI QIDQ1680973zbMATH OpenOpenAlexWikidataFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(42)

• A method with convergence rates for optimization problems with variational inequality constraints
• New first-order algorithms for stochastic variational inequalities
• 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
• Evolution of Mixed Strategies in Monotone Games
• Dynamic stochastic projection method for multistage stochastic variational inequalities
• Variance-based extragradient methods with line search for stochastic variational inequalities
• Variance-based modified backward-forward algorithm with line search for stochastic variational inequality problems and its applications
• A self-adaptive stochastic subgradient extragradient algorithm for the stochastic pseudomonotone variational inequality problem with application
• 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
• A Variable Sample-Size Stochastic Quasi-Newton Method for Smooth and Nonsmooth Stochastic Convex Optimization
• Incremental Constraint Projection Methods for Monotone Stochastic Variational Inequalities
• Variance-based subgradient extragradient method for stochastic variational inequality problems
• Improved variance reduction extragradient method with line search for stochastic variational inequalities
• An infeasible stochastic approximation and projection algorithm for stochastic variational inequalities
• Variance-based single-call proximal extragradient algorithms for stochastic mixed variational inequalities
• An accelerated stochastic extragradient-like algorithm with new stepsize rules for stochastic variational inequalities
• Variable sample-size optimistic mirror descent algorithm for stochastic mixed variational inequalities
• Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants
• A fast stochastic approximation-based subgradient extragradient algorithm with variance reduction for solving stochastic variational inequality problems
• A hybrid Newton method for stochastic variational inequality problems and application to traffic equilibrium
• Minibatch forward-backward-forward methods for solving stochastic variational inequalities
• Preface
• 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
• On stochastic mirror-prox algorithms for stochastic Cartesian variational inequalities: randomized block coordinate and optimal averaging schemes
• Stochastic approximation for estimating the price of stability in stochastic Nash games
• On the solution of stochastic optimization and variational problems in imperfect information regimes
• Extragradient Method with Variance Reduction for Stochastic Variational Inequalities
• Infeasible interior-point algorithms based on sampling average approximations for a class of stochastic complementarity problems and their applications
• Variable sample-size operator extrapolation algorithm for stochastic mixed variational inequalities
• Ensemble of convolutional neural networks for the detection of prostate cancer in multi-parametric MRI scans
• Simple and optimal methods for stochastic variational inequalities. I: Operator extrapolation
• The Tikhonov regularization for vector equilibrium problems
• On stochastic and deterministic quasi-Newton methods for nonstrongly convex optimization: asymptotic convergence and rate analysis
• Open problem: Iterative schemes for stochastic optimization: convergence statements and limit theorems
• An online convex optimization-based framework for convex bilevel optimization
• Complexity guarantees for an implicit smoothing-enabled method for stochastic MPECs
• Primal-dual incremental gradient method for nonsmooth and convex optimization problems
• A stochastic projection and contraction algorithm with inertial effects for stochastic variational inequalities
• Hybrid SGD algorithms to solve stochastic composite optimization problems with application in sparse portfolio selection problems
• Randomized Lagrangian stochastic approximation for large-scale constrained stochastic Nash games

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)