Variance-Reduced Splitting Schemes for Monotone Stochastic Generalized Equations

• URL: http://arxiv.org/abs/2008.11348v4
• Date: Mon, 18 Oct 2021 01:54:49 GMT
• Title: Variance-Reduced Splitting Schemes for Monotone Stochastic Generalized Equations
• Authors: Shisheng Cui and Uday V. Shanbhag
• Abstract summary: We consider monotone inclusion problems where the operators may be expectation-valued. A direct application of splitting schemes is complicated by the need to resolve problems with expectation-valued maps at each step. We propose an avenue for addressing uncertainty in the mapping: Variance-reduced modified forward-backward splitting scheme.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider monotone inclusion problems where the operators may be expectation-valued, a class of problems that subsumes convex stochastic optimization problems as well as subclasses of stochastic variational inequality and equilibrium problems. A direct application of splitting schemes is complicated by the need to resolve problems with expectation-valued maps at each step, a concern that is addressed by using sampling. Accordingly, we propose an avenue for addressing uncertainty in the mapping: Variance-reduced stochastic modified forward-backward splitting scheme (vr-SMFBS). In constrained settings, we consider structured settings when the map can be decomposed into an expectation-valued map A and a maximal monotone map B with a tractable resolvent. We show that the proposed schemes are equipped with a.s. convergence guarantees, linear (strongly monotone A) and O(1/k) (monotone A) rates of convergence while achieving optimal oracle complexity bounds. The rate statements in monotone regimes appear to be amongst the first and rely on leveraging the Fitzpatrick gap function for monotone inclusions. Furthermore, the schemes rely on weaker moment requirements on noise and allow for weakening unbiasedness requirements on oracles in strongly monotone regimes. Preliminary numerics on a class of two-stage stochastic variational inequality problems reflect these findings and show that the variance-reduced schemes outperform stochastic approximation schemes and sample-average approximation approaches. The benefits of attaining deterministic rates of convergence become even more salient when resolvent computation is expensive.

Related papers

• An Inexact Halpern Iteration with Application to Distributionally Robust Optimization [9.529117276663431]
  We investigate the inexact variants of the scheme in both deterministic and deterministic convergence settings. We show that by choosing the inexactness appropriately, the inexact schemes admit an $O(k-1) convergence rate in terms of the (expected) residue norm.
  arXiv  Detail & Related papers  (2024-02-08T20:12:47Z)
• Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions [18.086061048484616]
  We study finite-sum monotone inclusion problems, which model broad classes of equilibrium problems. Our main contributions are variants of the classical Halpern iteration that employ variance reduction to obtain improved complexity guarantees. We argue that, up to poly-logarithmic factors, this complexity is unimprovable in the monotone Lipschitz setting.
  arXiv  Detail & Related papers  (2023-10-04T17:24:45Z)
• High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise [96.80184504268593]
  gradient, clipping is one of the key algorithmic ingredients to derive good high-probability guarantees. Clipping can spoil the convergence of the popular methods for composite and distributed optimization.
  arXiv  Detail & Related papers  (2023-10-03T07:49:17Z)
• First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
  We present a unified approach for the theoretical analysis of first-order variation methods. Our approach covers both non-linear gradient and strongly Monte Carlo problems. We provide bounds that match the oracle strongly in the case of convex method optimization problems.
  arXiv  Detail & Related papers  (2023-05-25T11:11:31Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  We propose algorithms with high-probability convergence results under less restrictive assumptions. These results justify the usage of the considered methods for solving problems that do not fit standard functional classes in optimization.
  arXiv  Detail & Related papers  (2023-02-02T10:37:23Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  We prove the first high-probability results with logarithmic dependence on the confidence level for methods for solving monotone and structured non-monotone VIPs. Our results match the best-known ones in the light-tails case and are novel for structured non-monotone problems. In addition, we numerically validate that the gradient noise of many practical formulations is heavy-tailed and show that clipping improves the performance of SEG/SGDA.
  arXiv  Detail & Related papers  (2022-06-02T15:21:55Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  We study the problem of estimating the fixed point of a contractive operator defined on a separable Banach space. We establish non-asymptotic bounds for both the operator defect and the estimation error.
  arXiv  Detail & Related papers  (2022-01-21T02:46:57Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO. We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size. Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
  arXiv  Detail & Related papers  (2021-06-30T18:32:46Z)
• Stochastic Variance Reduction for Variational Inequality Methods [19.061953585686986]
  We propose variance reduced algorithms for solving convex-concave saddle point problems, monotone variational inequalities, and monotone inclusions. Our framework applies to extragradient, forward-backward-forward, and forward-reflected-backward methods both in Euclidean and Bregman.
  arXiv  Detail & Related papers  (2021-02-16T18:39:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.