Stochastic Projective Splitting: Solving Saddle-Point Problems with Multiple Regularizers
Authors: Patrick R. Johnstone
Jonathan Eckstein
Thomas Flynn
Shinjae Yoo
Venue: ICLR 2022 Submitted (2022)
Keywords: convex optimization
min-max games
saddle-point problems
first-order stochastic methods
proximal methods
operator splitting

Abstract: We present a new, stochastic variant of the projective splitting (PS) family of algorithms for monotone inclusion problems.  It can solve min-max and noncooperative game formulations arising in applications such as robust ML without the convergence issues associated with gradient descent-ascent, the current de facto standard approach in ML applications.  Our proposal is the first version of PS able to use stochastic gradient oracles. It can solve min-max games while handling multiple constraints and nonsmooth regularizers via projection and proximal operators. Unlike other stochastic splitting methods that can solve such problems, our method does not rely on a product-space reformulation of the original problem. We prove almost-sure convergence of the iterates to the solution and a convergence rate for the expected residual.  By working with monotone inclusions rather than variational inequalities, our analysis avoids the drawbacks of measuring convergence through the restricted gap function. We close with numerical experiments on a distributionally robust sparse logistic regression problem.

Under review as a conference paper at ICLR 2022
STOCHASTIC PRoJECTIVE SPLITTING: SOLVING REGULARIZERS
PROBLEMS WITH MULTIPLE
Anonymous authors Paper under double-blind review
ABSTRACT
We present new, stochastic variant of the projective splitting (PS) family of algorithms for monotone inclusion problems. It can solve min-max and noncoop- erative game formulations arising in applications such as robust ML without the convergence issues associated with gradient descent-ascent, the current de facto standard approach in ML applications. Our proposal is the first version of PS able to use stochastic gradient oracles. It can solve min- max games while handling multiple constraints and nonsmooth regularizers via projection and proximal op- erators. Unlike other stochastic splitting methods that can solve such problems, our method does not rely on a product-space reformulation of the original problem. We prove almost-sure convergence of the iterates to the solution and convergence rate for the expected residual. By working with monotone inclusions rather than variational inequalities, our analysis avoids the drawbacks of measuring conver- gence through the restricted gap function. We close with numerical experiments on distributionally robust sparse logistic regression problem.
INTRODUCTION
The most prominent application of optimization in ML is empirical risk minimization. However,
inspired by the success of GANs (Goodfellow et al., 2014). ML practittiss have developed more
complicated min-max and adversarial optimization formulations (Yu et al.|2021]
202T Kuhn al. 2019)
saneeezzadh--bbaade et al., 2015) Sinha et al. [2018 Lin et al. 2020; Namkoong & Duchi 2016
Huang et al. 2017] Wadsworth et al. 2018 Zhang et al. 2018 Edwards & Storkey 2015 Celis
& Keswani 2019h. Solving these multi-player games leads issues not seen when minimizing
single-player loss function. The competitive nature of game leads to rotational dynamics that can
cause intuitive gradient-basee methods to fail to converge (Gidel et al. 2019 Daskalakis et al. 2018
Hsieh et al. 2020).
A mathematical framework underlying both convex optimization and saddle-point problems is the monotone inclusion problem; see Ryu & Boyd (2016) for an introduction. Methods developed for monotone inclusions will converge for convex-concave, games as they are explicitly designed to handle such problems' governing dynamics. In recent years, monotone inclusion methods and theory have started to receive attention in the ML community (Diakonikolas 2020 Liu al. T
Ryu et al. 2020 Pathak & Wainwright 2020), with focus monotone variational inequalities, which form a special case of monotone inclusions (Antonakopoulos al. 2019 Gidel al. 2019
Daskalakis et al. 2018 Hsieh et al. 2020 Mertikopoulos al. 2019).
The most prevalent methods for solving min-max games in MI. are variants of gradient descent-ascent (GDA). This method alternates between gradient-descee descent step for the minimizing player and gradient-ascent step for the maximizing player. Unfortunately, GDA requires additional assumptions
to converge on convex-concave games, and it even fails for some simple 2D bilinear games (Gidel
et al.
2019
Prop. 1). While there have been several approaches to modify either GDA (Chavdarova Grnarova al. 2021: Balduzzi et al. (2018) or the underlying game objective (Mescheder
2021
ct al.
2018: Nagarajan Kolter 2017 |017] Mescheder et al.) 2017) to ensure convergence, this paper
instead develops method for solving monotone inclusions that can naturally handle game dynamics.

---

Under review as a conference paper at ICLR 2022
Our approach builds upon the recently proposed projective splitting (PS) method with forward steps (Johnstone & Eckstein 2020b). PS is designed specifically for solving monotone inclusions, thus does not fall prey the convergence issues that plague GDA, at least for convex-concar games. PS is within the general class of projective splitting methods invented by |Eckteii & Svaiter (2008) and developed further in |Eckteei & Svaiter (2009); Alotaibi al. (2014); Combettes & Eckstein
(2018); [ccsttein (2017); Johnstone & Eckstein (2019) 2021; 2020a). These methods work by creating
separating hyperplane between the current iterate and the solution and then moving closer the solution by projecting the current iterate onto this hyperplane (see Section B for an overview). Other than being able to natively handle game dynamics, the primary advantage of PS is that it fully splits problems involving an arbitrary number of regularizers and constraints. "Full splitting" means that the method can handle multiple regularizers and constraints through their respective individual proximal and projection operators, along with the smooth terms via gradients. What makes this useful is that many of the regularizers used in ML have proximal operators that are relatively easy to compute; see for example Parikhh & Boyd (2013).
Despite these advantages, the preexisting PS framework has a significant drawback: it requires deterministic gradient oracles. This feature makes it impractical for application to large datasets for which stochastic oracles may be the only feasible option.
Contributions
The primary contribution of this work is a new projective splitting algorithm that allows for a stochastic gradient oracle. We call the method stochastic projective splitting (SPS). Our method "fully splits" the monotone inclusion problem
Find Rdd s.t. O E A,(2) + B(=).
(1)
where is monotone and L-Lipschitz and each A; is maximal monotone and typically set valued, usually arising from a constraint or a nonsmooth regularizer in the underlying optimization problem or game; see for example Ryu & of ( see Section 2 and Appendix [A] Here, an algorithm that "fully splits" ( means one whose computational steps each involve only the individual operators AI...., An. B. Ours is the first method that can accomplish full splitting without a product-spat space reformulation that recasts [ as a two-operator problem on a nigher-dimensional space, a tactic whose disadvantages are discussed in Appendix F.7 Our method interrogates the Lipschitz operator B through stochastic oracle. Previous methods splitting |I have either required deterministic oracle for B, or have made far more restrictive assumptions on the noise or the operators (Briceño-Arias & Combettes) 201T] Combettes & Pesquet 2012 Malitsky & Tam [2020] Bot al.) |019 Van Dung & Vuj 2021) than we will require below. However, the stochastic methods of AAlacaggu et al. (2021) and Böhm et al. (2020), when combined with product-space reformulation, can solve (1) when all the A; are subdifferentials of convex functions; see Section 6
for definitions. For some example MI applications
When moving away from a deterministic gradient oracle in projective splitting, key difficulty is that the generated hyperplanes do not guarantee separation between the solution and the current point. We solve this issue by relaxing the projection: we only update each iterate in the direction of the noisy projection and scale its movement by decreasing stepsize that allows for control of the stochastic error. Using the framework of stochastic quasi-Fejé- monotonicity (Combettes & Pesquet 2015)). we prove almost-sure convergence of the final iterate and do not require averaging of the iterates (Theorem T. Section 5). We also provide a non-asymptotic convergence rate for the approximation residual (Theorem Section 5)
A special case of SPS is the eecently-dvvelppee Double Stepsize Extragradient Method (DSEG) (Hsich ett al. 2020). When = 0 and therefore only B is present in (T), DSEG and SPS coincide. Thus, our method extends DSEG to allow for regularizers and constraints. Our analysis also provides new interpretation for DSEG as a special case of projective splitting. Our nonasymptotic convergence rate for SPS also applies to DSEG under no additional assumptions. By contrast, the original convergence rate analysis for DSEG requires either strong monotonicity an error bound.
We close with numerical experiments on a distributionally robust sparse logistic regression problem. This is nonsmooth convex-concate min-max problem which can be converted to (I) with 2 set- valued operators. On this problems class, SPS compares well to the possible alternative splitting methods.
2

---

Under review as a conference paper at ICLR 2022
Non-monotone problems The work of Hsieh et al. (2020) included local convergence analysis for DSEG upplied to locally monotone problems. For min-max problems, if the objective is locally convex-coneave at solution and DSEG is initialized in close proximity, then for small enough stepsizes it converges to the solution with high probability. is possible to extend this result to SPS, along with our convergence rate analysis. This result is beyond the scope of this work, but Appendix | provides a proof sketch.
BACKGROUND ON MONOTONE INCLUSIONS
Since they are so important to SPS, this section provides some background material regarding mono- tone inclusions, along with their connections to convex optimization, games, and ML. Appendix G discusses their connections to variational inequalities. For more thorough treatment, we refer to Bauschke & Combettes (2017). See Appendix for a longer discussion of the applications of monotone inclusions to ML along with several examples.
Fundamentals Let f Fd - RURRU {oo} be closed, convex, and proper (CCP). Recall that its subdifferential 0f given by af(x) = (g- f(y) 2 f(x) + g (y x)). The map 0f has the property
u @f(z)) E ay()) = v
20
and any point-to-set map having this property is called monotone operator. A monotone operator T is called maximal if no additional points can be included in the image T(x) of any E Ied without violating the above property (Bauschke & Combettes 2017 Def. 20.20). Subgradient maps of CCP functions are maximal (Bauschke Combettes 2017 Thm. 20.25). A minimizer of is any x² such that 0 E (x)"). This is perhaps the simplest example of monotone inclusion, the problem of finding x such that 0 E T(x), where 7 is a monotone operator. If f is smooth, then 0f(z) = ( for all x, and the monotone inclusion 0 E 0z()) is equivalent the first-order optimality condition 0 = V/(z).
Under certain regularity conditions (Bauschke & Combettes 2017, Cor. 16.5), minimizing a sum of CCP functions fi....,f, is equivalent to solving the monotone inclusion formed from the sum of their subdifferential::
Era min
Σ f((x) = d
Σ 0f((z)).
ZERd
As throughout this paper for all set addition operations, the summation on the right-hand side of (2) s; S; V E I..n.. For convex set X, a constraint o E C' for some convex set C' may be imposed by setting one of the Ji to be the indicator function (c- defined by (x))) for C and (x) +oo for & C. Indicator functions of closed convex sets are CCP (Bauschke & Combettes] 2017 Ex. 1.25), and the subgradient map of 'g is also referred as the normal cone map Ne of C (Bauschke & Combettes 2017 Def. 6.37). Multiple constraints may be imposed by including multiple indicator functions in
is the Minkowski sum Σi= S. = (E
MI applications The form can be used to model ML problems with multiple constraints and/or nonsmooth regularizers, including sparse and overlapping group lasso (Jacob et al.] 2009), sparse and low-rank matrix estimation problems (Richard al. (012), and rare feature selection Yan & Bien
2020 see PPedregosa & Gidel (2018) for an overview.
Consider a two-player noncooperative game in which each player tries selfishly minimize its own loss, with each loss depending on the actions of both players. Typically, the goal is to find a Nash equilibrium, in which neither player can improve its loss by changing strategy:
Games
x² E arg min F(x, v²) and y" E arg min G(x",)) VER
Assuming that the admissible strategy sets θ dd and Ω C Rd, are closed and convex and that F and G are differentiable, then writing the first-order necessary conditions for each optimization problem in (3) yields
v.F(x*.8") G(((""))) ]
0E
+ (No(x*) Nolv"))
3

---

Under review as a conference paper at ICLR 2022
= ( is min-max game. If F is also convex in and concave in y, then B (x, y)
(V,F(z, y). -V, is monotond on RR: +dy (Rockafellar 1970). In many applications, B
is also Lipschitz continuous. In this situation, 4 is a monotone inclusion involving two operators
B and Nexn, with B being Lipschitz. Using the simultaneous version of GDA on (3) is equivalent to applying the forward-backe However, convergence of FB requires that the operator B be cocoercive (Bauschke & Combettes
method (FB) (Bauschke & Combettes) 2017 Thm. 26.14) (4)
2017 Def. 4.10), and not merely Lipschitz (Bauschke Combettes 2017 Thm. 14)14). Thus. simultaneous GDA fails to converge for (3) without additional assumptions; see Gidel et al. (0019
Prop. 1) for a simple counterexample.
Regularizers and further constraints may be imposed by adding more operators to ( For example, if one wished to apply a (nonsmooth) convex regularizer r Rd - IR U {+o0} to the æ variables
and a similar regularizer d TRd, - R U [+oo) to the y variables, one would add the operator A2 (x. u) - 0r(x) x Öd(y) to the right-hand side of
ML applications of games Distributionally robust supervised learning (DRSL) is an emerging framework for improving the stability and reliability of ML models in the face of distributional
shifts YYu et al., 202T, Kuhn et al. 2019 Shafieezadeh--Aaale
al.. 2015] Sinha et al., 2018 Lin
et al. 2020, Namkoong & Duchi 2016). Common approaches to DRSL formulate the problem as
a min-max game between a learner selecting the model parameters and an adversary selecting a worst-case distribution subject to some ambiguity set around the observed empirical distribution. This min-max problem is often further reduced to either a dinte-iimnnional saddlepoint problem or convex optimization problem.
DRSL is a source of games with multiple constraints/regulaiizees One such formulation, based on Yu et al. 2021), is discussed in the experiments below. The work in Namkoong & Duchi (2016) uses an ambiguity set based on f-divergences, while Sinha et al.] (2018) introduce a Lagrangian relaxation of the Wasserstein ball. When applied to models utilizing multiple regularizers (Jacob et al. 2009
Richard et al. 2012]] Yan & Bien 2020), both of these approaches lead to min-max problems with multiple regularizers.
Other applications of games in MI. although typically nonconvex, include generative adversarial net- works (GANs) (Goodfellow al. 2014 Arjovsky al. 2017 Loizou al. [020 2021| Mishchenko ct al.] (020). fair classification (Wadsworth et al. 2018 Zhang ct al. 2018 Edwards & Storkey 2015
Celis & Keswani 2019), and adversarial privacy (Huang et al. 2017).
Resolvents, proximal operators, and projections A fundamental computational primitive for solving monotone inclusions is the resolvent. The resolvent of monotone operator A is defined to be JA -1 A) -1 where I the identity operator and the inverse of any operator T simply T : x - {u Ty 2}.. If A is maximal monotone, then for any >> 0. JAA is single valued, nonexpansive, and has domain equal to Rd (Bauschke & Combettes, 2017 Thm. 21.1 and Prop. 23.8). Resolvents generalize proximal operators of convex functions: the proximal operator of a CCP function f is
prox pf (t) = arg min (pf(z) + xER
=|13
It easily proved that prox, pf Jpps. Like proximal operators, resolvents generalize projection onto convex sets: if f = Lc. then JoNe = prox, = proje for any p > 0. In many ML applications proximal operators, and hence resolvents, are relatively straightforward to compute. For examples, see Parikh & Boyd (2013) Sec. 6).
Operator splitting methods Operator splitting methods attempt to solve monotone inclusions such as (T) by sequence of operations that each involve only one of the operators A1, .i,..., An, B. Such methods are often presented in the context of convex optimization problems like (2), but typically
apply more generally to monotone inclusions such as (I). In the specific context of (T). each iteration of such method ideally handles each A; via its resolvent and the Lipschitz operator B by explicit
(not stochastic) evaluation. This is a feasible approach the original problem can be decomposed in
"Sufficient conditions for the monotonicity of in the case where G o - are discussed in e.g. Scutari 2014 Aiiceño-Arias & Combettes 2013
4

---

Under review as a conference paper at ICLR 2022
such way that the resolvents of each A, are relatively inexpensive compute, and full evaluations of B are possible. Although not discussed here, more general formulations in which matrices couple the arguments of the operators broaden the upplicability of operator splitting methods.
THE PROJECTIVE SPLITTING FRAMEWORK
Before introducing our proposed method, we give a brief introduction to the projective splitting class of methods.
The extended solution set Projective splitting is a primal-dual framework and operates in an extended space of primal and dual variables. Rather than directly finding a solution to (T. we find a point in the extended solution set (or Kuhn-TTucker set)
s= { (2, Wi,......... wh+1)
we E A(()ViE 1..n, Wh+1 = B(2). Ei=1 W/ =0]
(5) that x" solves (T). Conversely, given
Given p¹ (z", w 11) S, is straightforward a solution =² to there must exist wi..... w n such that (z", wi, W w+1) E S. Suppose p- = (2* w " 11) E S. Since 2 solves ① 2" is typically referred to as primal solution. The vectors wi..... W Wi+1 solve dual inclusion not described here, and are therefore called a dual solution. can be shown that closed and convex; see for example Johnstone Eckstein) (2020b).
We will assume throughout that solution to ① exists, therefore the set S is nonempty.
Separator-projectinn framework Projective splitting methods are instances of the general seppeutor-projeccionn algorithmic framework for locating a member of closed convex set S within a linear space P. Each iteration of algorithms drawn from this framework operates by finding a set H2 that separates the current iterate p P from S, meaning that S is entirely in the set and pe typically is not. One then attempts to "move closer" to by projecting the p onto Hg. In the particular case of projective splitting applied to the problem ( using (5). we select the space P be
P = (z, wi..... wn+1) E (n+2d
Σ wi =
(6)
and each separating set Hs be the half space {p E P (p((p) S 0} generated by an affine function
PPk P + IR. The general intention is to construct such that ( > O, but (px(p)) s 0 for all
p" S. The construction employed for pp in the case of (T] and (5) is of the form
(0 W1, Wa+1) = EntH x v m))
for some points v." 2d E 1..nn + that must be carefully chosen (see below). Any
function of the form 7 can be shown to be affine when restricted to P. As mentioned above, the standard separator-projees projeccionoo algorithm obtains its next iterate + by projecting De onto Hx. This calculation involves the usual projection step for a half space, namely
h+1 p² ag Vyk, where ag = (
(8)
and the gradient Vyp is computed relative to P. thus resulting in ++1 E P, i.e. Vipk a+1 1i=1 vt ak ....,,T4111 x+) where zh 2i=1 x
PROPOSED METHOD
The proposed method given in Algorithm I and called Stochastic Projective Splitting (SPS). Unlike prior versions of projective splitting, SPS does not employ the stepsize ag of (8) that places the next iterate exactly on the hyperplane given by (px(p) with pre-defined stepsize }. This fundamental change is required to deal with the stochastic noise on lines and This noise could lead to the usual choice of ar defined in (8) being unstable and difficult to analyze. In order to guarantee convergence, the parameters or and Ps must be chosen to satisfy certain conditions given below. Note that the gradient is calculated with respect to the subspace P defined in (6); since the algorithm is initialized within P, it remains in P. within which
Instead, it simply moves in the direction - Vyp
pp is affine. Collectively, the updates on lines 9 10 are equivalent to p**1 ph ag Vipk. where x (=* wtt . we w
5

---

Under review as a conference paper at ICLR 2022
Note that SPS does not explicitly evaluate (k,, which is only used in the analysis, but it does keep track of (xf yf*) for i E 1n.(n + 1). The algorithm's 's memory requirements scale linearly with the number of nonsmooth operators in the inclusion ([, with the simplest implementation storing (3n++5) -5d working-vecton elements. This requirement can reduced to (n+ + 7)d through a technique In most applications, n will be small, for example 2 or 3.
discussed in Appendix H
Updating (If,x²) The variables (a,, vt)) are updated on lines of Algorithm in which ex and e are Te -Valuleed random variables defined on a probability space (Ωt F. P). For B we use a new, noisy version of the wwo-forward-step procedure from Johnstone & Hckstein (2020b). For each A, i E I..n, we use the same resolvent step used in previous projective splitting papers, originating with (Eckstein & Svaiter 2008). In the case e e O, the selection of the (x y is identical to that proposed by Johnstone & Bckstein 2020b), resulting in the hyperplane {p (P)(p) 0} strictly separating pe from S.
SPS achieves full splitting of each A; is processed separately using resolvent and the Lipschitz term B processed via stochastic gradient oracle. When the A, arise from regularizers or constraints, as discussed in Section 2 their resolvents can be readily computed so long as their respective proximal//rojection operators have a convenient form.
Noise assumptions Let FR = of''..... . and & = (fe The stochastic estimators for the gradients, x and yn+1, are assumed to be unbiased, that is, the noise terms have mean conditioned on the past:
B[<]FA]] =0 [[c*|F)] = a.s.
(9)
We impose the following mild assumptions on the variance of the noise:
E [||* [R] S Nı + B2] a.s. E [le & 1 E < N3 + Nall 0.8.,
(10)
(11)
where S N2, N4 co. We do not require e and e to be independent of one another.
Stepsize choices
The stepsizes Pk and ag assumed to be deterministic. A constant stepsize choice which attains a non-asymptotic convergence rate will be considered the next section (Theorem 2). The stepsize conditions we will impose to guarantee almost-sure convergence (Theorem
1 are
Ees OLPK- = =0, E a 00, Ei a&p < c0, and Pk: <<<<<0 1/L.
(12)
For example, in the case L = 1, a particular choice which satisfies these constraints is
OAk - for 0 < x 0.5, and Pk 005++ for p 5 0.5p + 0.25.
For simplicity, the stepsizes used for the resolvent updates in lines 5 are fixed, but they could be allowed to vary with both i and k so long as they have finite positive lower and upper bounds.
Algorithm 1: Stochastic Projective Splitting (SPS)
Input: :p² (2), w1
w s.t. >x+1 w 0, {ax, )
for k = 1, 2. do
for i 1.n do
1 * Tw
x J=A. (1t)
x r (1t ax)
x B(=*)= + t
11 ck is unknown noise term
x = -² - wit)
s = Blx + t
11 th is unknown noise term
k+1 zk OKk nut1 v
w. k+1 wit a n+1
n-t x/) iE 1el.(n+1)
10

---

Under review as a conference paper at ICLR 2022
5 MAIN THEORETICAL RESULTS
Theorem 1, Suppose A1,..., An are maximal monotone, B I.-Lipschitz and monotone, and solution to 1 exists. For Algorithm suppose ② (12) hold. Then with probability one it holds that z + z,, where 2" solves (T. Further, with probability one, a. + for I....,
Proof sketch Theorem is proved in Appendix C but we provide brief sketch here. The proof begins by deriving simple recursion inspired by the analysis of SGD (Robbins & Monro, 195T). Since y = p* Or Vyk, a step of projective splitting can be viewed as GD applied to the affine hyperplane generator function ypk. Thus, for any p* P.
lp 1p*+1
2 1| p01 2a Pk: p p") V
= 1lp - p21 2a ( (p") px (p") a V
(13)
where in the second equation we have used that ya (p) is affine on P. The basic strategy is to show that, for any p² E ES,
B || S -p11==p"'1²+C' a.s.
for some C₁ C2 > O. This condition allows one to establish stochastic quasi-Fejér monotonicity (SQFM) (Comeettes & Pesquet 2015] Proposition 2.3) of the iterates to S. One consequence of SQFM that with probability one there exists a subsequence uk such that you, (p**) - Pea (p") converges to O. Furthermore, roughly speaking, we show that (p((")) - (px("") provides an upper bound on the following "approximation residual" for SPS:
G -i= llo/" w 1|2 + ΣT 1| x/ 1|2 + [B(=*) - -((=*)-w=++i 112.
(14)
Gk provides an approximation error for SPS, as formalized in the following lemma: Lemma 1. For SPS, p² (2*, wf...., wh+1) E S if and only if G 0.
Since u E (x,) for i E I..n, having G.. = 0 implies that 2 x. w = v/" and thus w. E (2*) for i E 1. Since w = B(=*) and E w
0. it follows that = solves (
The reverse direction proved in Appendix [
The quantity G5 generalizes the role played by the norm of the gradient in algorithms for smooth optimization. particular, in the special case where n = 0 and (=)) ff(z) for some smooth convex function f, one has G [[
Combining the properties of G1 with other results following from SQFM (such as boundedness) will allow to derive almost-sure convergence of the iterates to a solution of (
Convergence rate We can also establish non- -symptotioiic convergence rates for the approximation residual G2: Theorem 2. Fix the total iterations K 2 1 of Algorithm Mand set
Vk l,......,KK K :Kpp = min K 1/4 , .1/2L] and ag = Csp²
--14
(15)
for some Cj O. Suppose 9--1 hold. Then
(1/K) | =(K))((K-11)
where the constants are given (along with the proof) in Appendix
Theorem 2 implies that if we pick an iterate J uniformly at random from 1..K, then the expected value of G2 is OK-4//). As far as we know, this is the first convergence rate for stochastic full- splitting method solving (T) in the general discontinuous (i.e. set-valued) monotone inclusion case, and it not clear whether it can be improved, either by a better analysis or better method. Faster rates are certainly possible for deterministic methods under various continuity assumptions; Tseng's method obtains (KK11) rate (Monteiro & Svaiter 2010) and the accelerated Halpern iteration under Lipschitz continuity obtains O(K rate (Diakonikolas, 2020). While our rate may seem slow, it worth remembering that [T features n discontinuous operators A,, so we expect rates at least as slow as nonsmooth convex optimization, but perhaps worse because (I) is far more general than convex optimization. For a different error metric, the restricted gap function, in the special case of variational inequalities, faster rates have been established in Juditsky et al. (201T) and Böhm et al.) (2020). However, is unclear how to relate the restricted gap function to Gg. so these rates may not be directly comparable to Theorem 2
7

---

Under review as a conference paper at ICLR 2022
6 RELATED WORK
Arguably the three most popular classes of operator splitting algorithms are forward-backward splitting (FB) (Combettes & Pesquer] (20TT). Douglas-Rachford splitting (DR) (Lions & Mercier
1979), and Tseng's ss method (Tseng) 2000). The extragradient method (EG) is similar to Tseng's method, but has more projection steps per iteration and only applies to variational inequalities (Korpelevich]] 1977; Nemirovski] 2004 Li et al., 202T). The popular Alternating Direction Method of Multipliers (ADMM), in its standard form, is dual application of DR (Gabay) 1983). The three-operator splitting method (Davis & Yin 2017) can only be applied to if
if B is cocoercive rather than merely Lipchitz, and thus its usefulness is mostly limited to optimization applications and not games. FB, DR, and Tseng's s method apply to monotone inclusions involving two operators, with varying assumptions one of the operators. It is possible to derive splitting methods for the more complicated inclusion ( involving more than two operators, by applying an appropriate 2-operator splitting method such Tseng's 's method product-space reformulation (PSR) (Briceño-Arias & Combettes] 2011 Combettes & Pesquet 2012) (for more on PSR, see Appendix D. The recently developed
www.rreeeeeedacacweeeeeeeeeeee (FRB) method (Malitsky & Tam 2020) can be used in the same way. However, there are several disadvantages to using a PSR, as discussed in Appendix F.7
By using a PSR, the stochastic methods of Alacaoglu et al. (021) and Böhm et al. (2020) can be applied to ① in the case that each A; is subdifferential. Both of these methods are analyzed in terms of the restricted gap function. This merit function has drawback compared with our approximation residual in that it requires one to find bound for the iterates. However, [Alacaoglu et al. (202I) and Böhm et al. (220)) do not provide such a bound, meaning that their convergence rate results are somewhat incomplete. We discuss this issue in Appendix G
Theoretical convergence of the method of Böhm et al. (2020) requires the use of averaging, since the final iterate does not converge for certain problems (Hsich et al. (020)). Empirically, averaging tends to be slow and to destroy regularizer-induced structural properties such as sparsity or low matrix rank, so its utility is largely theoretical and it is usually avoided in practice. Furthermore, averaging loses even its theoretical benefits for nonconvex problems, so its use in such cases is rarer still. Another drawback of the analysis of BBöh et al. (2020) is that, unlike in SPS, the resolvent (proximal) stepsizes also need to vanish.
The method of Alaacaou et al. (2021) applies variance reduction techniques FRB. It only applies to finite-sum problems and requires the periodic computation of a full batch gradient, making it somewhat less flexible and scalable than our method, On the other hand, it has an accelerated ergodic rate for the restricted gap function in the variational inequality setting. We compare the empirical performance of SPS with Alacaoglu et al. (2021). Böhm et al.] (2020), and several deterministic methods using PSR in the numerical experiments described in Section
Additional related work is discussed in Appendix B
EXPERIMENTS
We now present some numerical results on distributionally robust supervised learning (DRSL) problems. We follow the approach Yu et al. (202I). which introduced min-max formulation of Wasserstein DRSL. While other approaches reduce the problem to convex optimization, Yu et al. (202T) reduce it to finite-dimensional min-max problem amenable to the use of stochastic methods on large datasets. However, unlike our proposed SPS method, the variance- reduccd extragradient method that Yu et al. (202T) propose cannot handle multiple nonsmooth regularizers or constraints on the model parameters. Consequently, we consider distributionally robust sparse logistic regression (DRSLR), problem class equivalent to that considered in Yu et al. (2021), but with an added ε regularizer, standard tool to induce sparsity. See the Appendix I for the full problem definition.
We compared our SPS method to several methods for solving DRSLR for a collection of real datasets
from the LIBSVM repository (Chang & Lin 2011). We implemented SPS with a₁ C.k and
Pk: = Cak -0.25 0.25 and called it SPS-decay. We also implement SPS with the fixed stepsize given in (15) and called it SPS-fixed. We compared the method to deterministic projective splitting (Johnstone &
Eckstein 2020b) and the following methods based on PSR: Tseng's 's method (Tseng) (onobetesss
& Pesquet 2012). the forward-reflected-hace
(FRB) method (Malitsky & Tam 2020), the
8

---

Under review as a conference paper at ICLR 2022
10
10f
5PS-deeay (oun))
agorosimation resodual
10P
1014
SPS-fuod loursi
109
10
10a
determiniztc
Twang's method
10"
10a
102
FRB
Scbeng
10"
FRB
10"
16
10"
10
10-3-
10-1
25
50
125 ranning time (2)
75
300
150
175
200
20
40
60
80
100
running time (5)
running time (S)
Figure 1: Approximation residual Versus running time for three LIBSVM benchmark datasets, with the markers at 10-iteration intervals. Left: epsilon, middle: SUSY, right: real-sim. For the stochastic algorithms (SPS. S-Tseng, and FRB-VR), we plot the median results over 10 trials, with unit standard deviation horizontal error bars for the running time and the vertical error bars displaying the min-to-max range of the approximation residual. The code is provided in the supplementary material.
stochastic Tseng Sseeng method Böhm et al. (2020), and the variance- reduced stochastic FRB method (Alacaoglu et al. 202I), abbreviated FRB- VR. The S-Tseng and FRB-V VR algorithms appear to be the only stochastic splitting methods other than SPS applicable to the tested problem class.
Figure 1 show results for three LIBSVM standard datasets: epsilon (m 4. 10 d 2000), SUSY Baldi et al. 2014 Dua & Graff 2017) (m = 2 10 d 18), and real-sin (m = 72,309, 20,958).
To measure the progress of the algorithms, we used the "approximation residual" R& defined in Appendix F As with Gg, having Rs 0 implies that = solves (T). We use Rg instead of G because it is also possible to compute essentially the same measure of convergence from the iterates of the other tested algorithms, establishing a fair comparison. Appendix [F) provides the details of the derivation of the residual measure for each algorithm, explores the relationship between Rs and Gk. and provides additional implementation details.
Figure plots the approximation residual versus running time for all seven algorithms under consid- eration. The computations were performed using Python 3.8.3 and numpy on a 2019 MacBook Pro with 2.4GHz 8-core Intel 19 processor and 32GB of RAM Being stochastic method, SPS-decay seems to outperform the deterministic methods at obtaining medium-accuracy solution quickly. also seems outperform the stochastic PSR-based methods S-Tseng and FRB-VR.
8 CONCLUSIONS AND FUTURE WORK
We have developed and analyzed a stochastic splitting method that can handle min-max problems with multiple regularizers and constraints. Going forward, this development should make it possible to incorporate regularizers and constraints into adversarial formulations trained from large datasets.
Recent versions of deterministic projective splitting (Combettes & Eckstein, 2018 Johnstone & Eckstein 2020b) allow for asynchronous and incremental operation, meaning that not all operators need to activated at every iteration, with some calculations proceeding with stale inputs. Such characteristics make projective splitting well-suited to distributed implementations. Many of our SPS results may be extended allow for these variations, but we leave those extensions future work.
REFERENCES
Ahmet Alacaoglu, Yura Malitsky, and Volkan Cevher. Forward--efiectee-aaeeee backward method with variance reduction. Computational Optimization and Applications, 2021. Available online.
source Original data httts::/peoppe...... cs. umass wwwaasseeduumnee

---

Under review as a conference paper at ICLR 2022
Abdullah Alotaibi, Patrick L Combettes, and Naseer Shahzad. Solving coupled composite mono- tone inclusions by successive Fejér approximations of their Kuhn-Tucker set. SIAM Journal on Optimization, 24(4):2076-200 2014.
Kimon Antonakopoulos, Veronica Belmega, and Panayotis Mertikopoulos. An adaptive mirror- prox method for variational inequalities with singular operators. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buus Buce E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, 2019.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 214-223, 06-1 11 Aug 2017.
Pierre Baldi, Peter Sadowski, and Daniel Whiteson. Searching for exotic particles in high-energy physics with deep learning. Nature communications, 5(1):1-9, 2014.
David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. The mechanics of n-player differentiable games. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 354-363. PMLR, 10-15 Jul 2018.
Heinz Bauschke and Patrick I. Combettes. Convex analysis and monotone operator theory in Hilbert spaces. Springer, 2nd edition, 2017.
Axel Böhm, Michael Sedlmayer, Ernö Robert Csetnek, and Radu Ioan Bot. Two steps at time taking GAN training in stride with Tseng's 's method. arXiv preprint arXiv:2006.0903:: 2020.
Radu Ioan Bot, Panayotis Mertikopoulos, Mathias Staudigl, and Phan Tu Vuong. Forward-backward- forward methods with variance reduction for stochastic variational inequalities. arXiv preprint arXiv:1902.03355, 2019.
Luis M Briceño-Arias and Patrick L. Combettes. A monotone+skew splitting model for composite monotone inclusions in duality. SIAM Journal on Optimization, 12:4-11230-2555 2011.
Luis M Briceño-Arine and Patrick I. Combettes. Monotone operator methods for Nash equilibria in non-potential games. In Computational and Analytical Mathematics, volume 50 of Springer Proceedings in Mathematics and Statistics, pp. 143-159. Springer, 2013.
Elisa Celis and Vijay Keswani. Improved adversarial learning for fair classification. arXiv preprint 19X14:190..10443, 2019.
Chih- Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2:27:1-27:27, 2011. Software available at http:// httt:://www..r . CS ntu. edu. tttp:w/in/nniiiiii ibsvn
Tatjana Chavdarova, Matteo Pagliardini, Sebastian Stich, François Fleuret, and Martin Jaggi. Taming GANs with lookahead-minmax. In International Conference on Learning Representations, 2021. URL battps::/openzeviev.cc wttp://wwwww..eeeoooooeeoeeeoeae
Patrick L. Combettes and Jonathan Eckstein. Asynchronous block-iterative primal-dual decomposition methods for monotone inclusions. Mathematical Programming, 168(1-2):645-677 2018.
Patrick I. Combettes and lean-Christopha Pesquet. Proximal splitting methods in signal processing. In H.H. Bauschke, R.S.S. Burachik, P.I.. Combettes, V. Elser, D.R. Luke, and H. Wolkowiez (eds.), Fixed-Poine Algorithms for Inverse Problems in Science and Engineering, pp. 185-212. Springer, 2011.
Patrick L Combettes and Jcan-Christophe Pesquet. Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators. Set- ValuVa and variational analysis, 20(2):307-330, 2012.
Patrick Combettes and Jean Christopet Pesquet. Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping. SIAM Journal Optimization, 25(2): 2015.
10

---

Under review as a conference paper at ICLR 2022
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. In International Conference on Learning Representations, 2018. URL https
//openreview.co net/ (rgeeaawweee...ttffooooaaaaeeas. Eot.:
Damek Davis and Wotao Yin. A three-operator splitting scheme and its optimization applications. Set-Valued and Variational Analysis, 25(4):829-8555 2017.
Jelena Diakonikolas. Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities. In Conference on Learning Theory, pp. 1428-1451. PMLR, 2020.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL htttt:tt/aachiice
ics. eoci.eddmmm.
Jonathan Eckstein. A simplified form of block-iterative operator splitting and an asynchronous algorithm resembling the multi-block alternating direction method of multipliers. Journal of Optimization Theory and Applications, 173(1):155-182 2017.
Jonathan Eckstein and Benar Fux Svaiter. A family of projective splitting methods for the sum of two maximal monotone operators. Mathematical Programming, 111(1):173-19, 2008
Jonathan Eckstein and Benar Fux Svaiter. General projective splitting methods for sums of maximal monotone operators. SIAM Journal on Control and Optimization, 48(2):787-81,, 2009.
Harrison Edwards and Amos Storkey. Censoring representations with an adversary. arXiv preprint arXiv:1511.05897, 2015.
Daniel Gabay. Applications of the method of multipliers variational inequalities. In M. Fortin and R. Glowinski (eds.). Augmented Lagrangian Methods: Applications to the Solution of Boundary Value Problems, chapter IX. pp. 299-340. North-Holland, Amsterdam, 1983.
Gauthier Gidel. Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julic A variational inequality perspective on generative adversarial networks. In International Confer- Learning Representations, 2019. URL httts:://oppettte
net forum?id=
a.nAA55mm
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 27. Curran Associates, 2014.
Paulina Grnarova, Yannic Kilcher, Kfir Y Levy, Aurelien Lucchi, and Thomas Hofmaann, Generative minimization networks: Training GANs without competition. arXiv preprint arXiv:2103.12685, 2021.
Patrick T Harker and Jong-Shi Pang. Fintte-dimensional variational inequality and nonlinear comple- mentarity problems: a survey of theory, algorithms and applications. Mathematical programming, 48(1):161-200, 1990.
Yu-Guan Hsich, Franck Iutzeler, Jérôme Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra-gradien methods. In H. Wallach, H. Larochelle, A. Beygelzimer, F. M/Aché-BBuc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32, Curran Associates, 2019.
Yu-Guan Hsieh, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. Explore aggres- sively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. In H. Larochelle, M. Ranzato, R. Hadsell,
Balcan, and Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 16223-16234. Curran Associates, 2020.
Chong Huang, Peter Kairouz, Xiao Chen, Lalitha Sankar, and Ram Rajagopal. Context-aware generative adversarial privacy. Entropy, 19(1))656,, 2017.
11

---

Under review as a conference paper at ICLR 2022
Laurent Jacob, Guillaume Obozinski, and rean-Philippe Vert. Group lasso with overlaps and graph lasso. In Léon Bottou and Michael Littman (eds.). Proceedings of the 26th International Conference on Machine Learning. pp. 433-440, Montreal, June 2009. Omnipress.
Patrick R Johnstone and Jonathan Eckstein. Convergence rates for projective splitting. SIAM Journal Optimization, 29(3):931-1157, 2019.
Patrick R Johnstone and Jonathan Eckstein. Projective splitting with forward steps only requires continuity. Optimization Letters, 14(1):229-247, 2020a.
Patrick R Johnstone and Jonathan Eckstein. Projective splitting with forward steps. Mathematical Programming, 2020b. Published online, appear in print.
Patrick R Johnstone and Jonathan Eckstein. Sigle-forwarde projective splitting: exploiting cocoercivity. Computational Optimization and Applications, 78(1):125-166, 2021.
Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with
stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
GM Korpelevich. Extragradient method for finding saddle points and other problems. Matekon, 13 (4):35-49, 1977.
Daniel Kuhn, Peyman Mohajerin Esfahani, Viet Anh Nguyen, and Soroosh Shafieezadeh-Abate Wasserstein distributionally robust optimization: Theory and applications in machine learning. In Serguei Netessine (ed.), Operations Research & Management Science in the Age of Analytics, Tutorials in Operations Research, pp. 130-166. INFORMS. 2019.
Chris Junchi Li, Yaodong Yu, Nicolas Loizou, Gauthier Gidel, Yi Ma, Nicolas Le Roux, and Michael I Jordan. On the convergence of stochastic extragradient for bilinear games with restarted iteration averaging, arXiv preprint 11t.i::217.000660 2021.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for Manconvex-concan minimax problems. In Hal Daumé III and Aarti Singh (eds.). Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 6083-6093, PMLR, 2020.
Pierre-Louis Lions and Bertrand Mercier. Splitting algorithms for the sum of two nonlinear operators. SIAM Journal on Numerical Analysis, 16(6):6649977) 979, 1979.
Mingrui Liu, Hassan Rafique, Qihang Lin, and Tianbao Yang. First-order convergence theory for weakly-convex-weakee wwwteeewwwwaly-connaeee min-max problems. Journal of Machine Learning Research, 22 1169) 2021.
Nicolas Loizou, Hugo Berard, Alexia Jolicoeur-Martinee Pascal Vincent, Simon Lacoste-Julien, and Ioannis Mitliagkas. Stochastic hamiltonian gradient methods for smooth games. In International Conference Machine Learning, pp. 1370-6381. PMLR, 2020.
Nicolas Loizou, Hugo Berard, Gauthier Gidel, Joannis Mitliagkas, and Simon Lacoste-Julien. Stochas- tic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity. arXiv preprint urXiv:2107.00053: 2021.
Yura Malitsky and Matthew K Tam. A forward-backwaad splitting method for monotone inclusions without cocoercivity. SIAM Journal on Optimization, 30(2):1451 2020.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent saddle-poin problems: Going the extra(- gradient) mile. In Internationaal Conference Learning Representations, 2019. URL https
Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. The numerics of GANs. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, 2017.
12

---

Under review as a conference paper at ICLR 2022
Lars Mescheder, Andreas Geiger, and Sebastian Nowozin. Which training methods for GANs do actually converge? Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 3481-3490. PMLR, 2018.
Konstantin Mishchenko, Dmitry Kovalev, Egor Shulgin, Peter Richtárik, and Yura Malitsky. Revisit- ing stochastic extragradient. In International Conference on Artificial Intelligence and Statistics, pp. 4573 PMLR, 2020.
Aryan Mokhtari, Asuman E Ozdaglar, and Sarath Pattathil. Convergence rate of o(1/k) for optimistic gradient and extragradient methods in smooth convex-coneave saddle point problems. SIAM Journal on Optimization, 30(4):3200-3211, 2020.
Renato DC Monteiro and Benar Fux Svaiter. On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean. SIAM Journal on Optimization, 20(6):755-22777, 2010.
Vaishnavh Nagarajan and J. Zico Kolter. Gradient descent GAN optimization is locally stable. In Guyon, U. V. Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, 2017.
Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distributionally robust optimization with f f-divergences. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 29, Curran Associates, 2016.
Arkadi Nemirovski. Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-251, 2004.
Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming, 109(2):319-34) 2007.
Neal Parikh and Stephen Boyd. Proximal algorithms. Foundations and Trends in Optimization, 1(3): 123 123-231, 2013.
Reese Pathak and Martin J Wainwright. Fedsplit: an algorithmic framework for fast federated optimization. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 7057-7066. Curran Asso- ciates, Inc., 2020. URL
wwwriigggn.euuuspee neurips....... cc / htcp/apppr/222//11ee..
Fabian Pedregosa and Gauthier Gidel. Adaptive three-operator splitting. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 4085-4094. PMLR, 10-15 Jul 2018.
Fabian Pedregosa, Kilian Fatras, and Mattia Casotto. Proximal splitting meets variance reduction. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), .. Proceedings of the Twenty-Secom Interna- fional Conference Artificial Intelligence and Statisties, volume 89 of Proceedingy of Machine Learning Research, pp. 1-10. PMLR, 16-18 Apr 2019.
Emile Richard, Pierre-Andre Savalle, and Nicolas Vayatis. Estimation of simultaneously sparse and low rank matrices. In John Langford and Joelle Pineau (eds.), Proceedings of the 29th International Conference on Machine Learning, pp. 1351-1358. Omnipress, 2012.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathmatical statistics, pp. 400-407, 1951.
Tyrrell Rockafellar. Monotone operators associated with saddle-functions and minimax problems. Nonlinear functional analysis, 18(part 1):397-407, 1970.
Ernest Ryu and Stephen Boyd. Primer on monotone operator methods. Appl. Comput. Math, 15(1): 3-43, 2016.
13

---

Under review as a conference paper at ICLR 2022
Ernest K. Ryu, Kun Yuan, and Wotao Yin. Ode analysis of stochastic gradient methods with optimism and anchoring for minimax problems, 2020.
Gesualdo Scutari, Francisco Facchinei, Jong-Shi Pang, and Daniel P Palomar. Real and complex monotone communication games. IEEE Transactions on Information Theory, 60(7)4419-44211, 2014.
Soroosh Shafieezadeh-Abate Peyman Mohajerin Esfahani, and Daniel Kuhn. Distributionally robust logistic regression. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett (eds.), Advances in Neural Information Prucessing Systems, volume 28, pp. 1584.
Curran Associates, 2015.
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying some distributional robustness with principled adversarial training. In International Conference on Learning Representations, 2018. URL httpthtss///pppeeeeeeeeee
net forum id=Hk 6xP
Paul Tseng, A modified forward-backward splitting method for maximal monotone mappings. SIAM Journal on Control and Optimization, 38(2):431-446 2000.
Nguyen Van Dung and Bang Cong Vu. Convergence analysis of the stochastic reflected forward- backward splitting algorithm. arXiv preprint arXiv:2102.08906, 2021.
Christina Wadsworth, Francesca Vera, and Chris Piech. Achieving faimess through adversarial learning: application recidivism prediction. arXiv preprint arXiv:1807.0011 2018.
Xiaohan Yan and Jacob Bien. Rare feature selection in high dimensions. Journal of the American Statistical Association, 2020. Published online, to appear in print.
Yaodong Yu, Tianyi Lin, Eric Mazumdar, and Michael Jordan. Fast distributionally robust learning with variance reduced min-max max optimization. arXiv preprint arXiv:2104. 13326, 2021.
Alp Yurtsever, Bang Cong Vu, and Volkan Cevher. Stochastic three-composite convex minimization. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 29, Curran Associates, 2016.
Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adversarial learning. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, pp. 335- 340, 2018
A ML APPLICATIONS OF THE MONOTONE INCLUSION
There are two main classes applications of I in ML: optimization problems and saddle-pon Moidt games.
Optimization Problems In this case the monotone inclusion arises from finding the zero of sum of subgradients of convex functions, as discussed in Section 2 empirical risk minimization problem
It is typical ML to solve the
min ZER 17L
Σ f5() + Σ rz(x)
(16)
over size-m dataset. Usually, the gradient of the loss function Sj for each datapoint j is Lipschitz continuous. The terms r; may be regularizers used to reduce overfitting or encourage structural properties such as sparsity or low matrix rank. They also may represent constraints the parameters such as nonnegativity or the being in the probability simplex. Crucially, these regularizers are rarely differentiable. The first-order necessary condition for the solution of [6)
0 0 VEV)(x²) - Σ dri(x"),
(17)
14

---

Under review as a conference paper at ICLR 2022
where f(z) = (z), thus -f(=)= Σラ= (z). The inclusion 17 is special case
of ( and our method may the standard stochastic oracle for (z()), namely
V((22)
B
JEB
which subsamples randomly selected minibatch of datapoints E {l....,m) m).
Games
Consider the following nonsmooth Nash equilibrium problem
x² E arg min F(r,y') Σ ri(x)) and y² E arg min G(x",y) Σ d((y).
(18)
xERde
MER*
The terms Ei= (x) and E (y) once again represent regularizers and constraints on each player's strategy. Note that min- (saddle-point) problems correspond to having F(x, -G(r, v). Under appropriate convexity conditions and constraint qualifications, the solutions of (18
correspond to the solutions of the following monotone inclusion in the form of (T)
max m2)) Σ
FeF EE
]
V,G((",''
(Ori(**) x (d:")"))
(19)
where for i >> min(n, m2) we include "dummy functions", either (I())) = 0 when n4 < Ti2 or dy) when n1 < n2. If the functions F and G arise averages in the same we as (16). then our method may again use stochastic oracle for them.
Distributionally-RRooo ML One example application of (19 is distributionalll-rrouus MI, as demonstrated in the numerical experiment in Section 7 The full problem statement is given in Appendix[[
Lagrangian Duality Consider
Another application of (19 is constrained optimization via Lagrangian duality.
min
f(x)
Σ (x))) 2=1
s.t. h5(x) 0 j -= j=
As in (6). I is a loss function and the r; may represent regularizers and ("simple") constraints; in addition, there are p functional constraints the model parameters Introducing Lagrange multipliers y E IP,, the problem can be written as
min max f(x) +
r((x) + Σ (z))(z)
RERd "EB"
j=1
Under appropriate convexity conditions and constraint-qqullffcatiii this reduces to the following inclusion in the form of (T)
Vf(z) + P 1
0E
Σ (ari(x") {0))
h((x)
where h(x)) = [hy (x), (x)x (x)..... (....,,,,,))) (T) For certain choices of h, such as linear or quadratic functions, the first term above is monotone and (locally) Lipschitz continuous (Alacaoglu al. 2021)
Bilinear Games with Many Constraints Finally, consider the bilinear saddlepoint problem subject to multiple constraints:
min max x Dy s.t. x C. j j= 1,..., 71,, yER"
VEC j j= -...., .22-
15

---

Under review as a conference paper at ICLR 2022
Under some regularity conditions, this problem reduces to the inclusion
max(ni maa
Dy - x
0
Σ
(Ney(a") Neg(v"),
where we introduce additional "dummy" sets CJ Idd or C. Rd when ii + n2. The first term linear and skew symmetric, and therefore can easily be shown to be Lipschitz continuous and monotone. If all the constraint sets are closed and convex, then the rest of the terms are maximal monotone, then the problem is of the form ( meaning that projective splitting may be applied, possibly using a stochastic oracle for the first term.
B ADDITIONAL RELATED WORK
The preprint by Bot et al. (2119) develops a stochastic version Tseng's method under the require- ment that the noise variance converges to O. In ML, this could be achieved with the use of perpetually increasing batch sizes, a strategy that impractical practical noise requirements, but has stronger
many scenarios. The stochastic version of
FRB proposed by Van Dung& & Vu 2021 has assumptions on the problem which are rarely satisfied in ML applications: either uniform/strong monotonicity bounded domain. The papers by Yurtsever al. (2016) and Pedregosa al. (2019) consider stochastic variants of three-operator splitting, but require B in ( to be cocoercive, essentially restricting them to optimization problems.
There are several alternatives to the (stochastic) extragradient method that reduce the number of gradient evaluations per iteration from two one (Hsteh al., 2019; Malitsky & Tam 2020 Gidel et al. 2019). However, these methods have more stringent stepsize limits, making it unclear priori whether they will outperform two-step methods.
DSEG is stochastic version of EG (Hsich et al. 2020)) The primary innovation of DSEG is using different stepsizes for the extrapolation and update steps, thereby resolving some of the convergence issues affecting stochastic EG. As noted earlier, DSEG is the special case of our SPS method in which n 0, that is, no regularizerssconstrains are present in the underlying game. The analysis in (Hsieh) al. 2020) also did not consider the fixed stepsize choice given in Theorem
In the context of GANs, several methods have been developed based on a variational inequal- ity/monotone inclusion approach (Gidel et al. 2019 Daskalakis et al. [2018] Hsiih et al.) [2099] 22020) Böhm et al., 2020). Many of these papers point out that variational incqualities provide a principled framework for studying the GAN training problem and correcting some of the flaws in the standard method GDA.
C PROOF OF THEOREM 1
C.1 STOCHASTIC QUASI-FEJER MONOTONICITY
The key to the analysis is showing that the algorithm satisfies Stochastic Quasi- Monotonicity (Combettes & Pesquet 2015).
Lemma 2 (Combettes & Pesquet 2015), Proposition 2.3). Suppose Dr is sequence of -a-vule
random variables defined on a probability space (Ω, (R,F,P) Let F& o(p'. .....p²), Let F be nonempty, closed subset of IRdd Suppose that, for every p E F, there exists x* (p) 2 n7 (p) Z
0, n* (p) 2 0 such that Σk=1 (pp) < co, Ex 1/ (p) < oc and
(Vk N) Eillp 6+1 - S (p))lp - pll - =² >>(pp) + (p).
Then the following hold:
1. F): Ee (p) < 00 ass
2. n is bounded a.s.
3. There exists Ô such that P[인] = and (Ilx(() pl1} converges for every w E and
p F.
16

---

Under review as a conference paper at ICLR 2022
C.2 IMPORTANT RECURSION FOR SPS
The following lemma summarizes the key recursion satisfied by Algorithm T Lemma 2
to which we will apply
Recall that L is the Lipschitz constant of B.
Lemma 3. For Algorithm
7
suppose
11 hold and
Pk: p
(20)
Let
Ts 7 > 135 wf +
1 pr
n
11
112 + + (L))BB)))(()))) w
p P==1
then for all p" E S, with probability one
[[Ipp=+1 - -p0 [F & (1 + Ciakt + C2aupE) -p"112 To + C2a + CLOxp (21)
where Cl...., C4 are nonegative constants defined in (3). 34 (48 and (49) below, respectively,
Note that Tg is a scaled version of the approximation residual G2 defined in 14
We proceed first prove Lemma and then exploit the implications of Lemma Referring to (IO) and (II). let N = maxjei..4 N, To simplify the constants, we will use N in place of N, for the
noise variance bounds given in 10
C.3 UPPER BOUNDING THE GRADIENT
Throughout the analysis, we fix some p* (2", .... wh++1 E S. All statements with probability one (almost surely), but for brevity we will omit this unless needs to be emphasized.
In this section, we derive appropriate upper bounds for |/V to use in (3 We begin with Ve
|| 1x
a+1
|1
211y + 21 2
Σ
B( e
4||B(c
+
Σ
y
+ 111
:=1
Now next take expectations with respect to F2 and &s, and use the bound on the variance of the noise in obtaining
[ Ex] s E (1|
Σ
3/4
|| +
11
Fr, En
i=1
4(N 1)] B( +1 +
Σ
4N,
where we have used that of is me-aauuuablee for i E 1.n. Thus, taking expectations over & conditioned on F& yields
Σ ッ | +
E P & 4(N + 1)8(I +
4N.
(22)
1=1
We will now bound the two terms on the right side of (22
C.3.1 FIRST TERM IN 20
First, note that
|B( BI B(=") B(2"))I1
$ B( - B(=")l² + B]=
$ 11 - =12 [12++1B((=)]
$ 21 1p" -p" =
(23)
17

---

Under review as a conference paper at ICLR 2022
Now, returning to the first term on the right of (22) we have
[[B(a )11 [|
+
B B12
(1 ]12
B
<
- 112
< 4 - ->' +1 4||(()) + +2221110++= - 1/1
(24)
where we have used (33 obtain (24
For the third term in
24
we have from the calculation on line 7 of the algorithm that
z x+
-px(r w = -P: + w11)
and therefore
|| n+1 - 2 2²112= = Bi + - 1|?
)=+) - w wntll 1| < 37 (1²
11 1 11
We next take expectations conditioned on Fs and use the noise variance bound TO to obtain
|| - 2 - E 3p (IB((*)) + || + I| 1 II²) FR]
< 37 ((N 1) B( I1 + || + N).
Therefore
E [[| A
=* 1 S ((N + 1) ()( + || 21 + || 113) + +P'
= 6p-
620 (2(N
1)23|1p -p= + 2(N B() )|
+ +1| w 2 + B [==)) + +372N N
< (7N(2NN)))
+
+ 1 - w
+ 188 +1)]+((=))]
< 18p (N 1) (0)((++++))))) - -00'->>"1((>>>>>>>> + 3pp N
(25)
where in the equality uses (23 and w = B(=*). Combining 24 and 25
we arrive at
E
B
?
Fi S 4L' [1+1++10000 9p 1)(N + +))]1= 1>"11==pp111 pp'112
+
6 L2N. L
(26)
C.3.2 SECOND TERM IN
22
For i E 1..n, line 5 of the algorithm may be rearranged into // = ( - xtt + wtt so
Σ
2²)) + +w
< 2
7
k - 1| +
1=1
< 2nT 2 Σ
|1a 211122 +
W
iml
n
n
< < -112 k -2=" 2=112 2 4nt-2
|| xx 112
+ 4n D
11
+
< (72 + 1)1l=* -p"1 1| + 4
2
|| 11 + 4
(27)
1=1
18

---

Under review as a conference paper at ICLR 2022
By the definition of the solution set S in (5) W E A,(=*), so 2" + Tw; E (I+TA))2") and since
the resolvent is single-valued (Bauschke & Combettes 2017 Cor. 23.9) we therefore obtain
(1 (I++
(2 Tw?))
From lines 3 and 4 of the algorithm, we also have Z = J, (s+ + Tw:) for E 1..n. Thus, using the nonexpansiveness of the resolvent (Bauschke & Combettes 2017 Def. 4.1 and Cor. 23.9), have
Σ > x 11
| + +ww?) - (=" + +Twl)l?
|| + rut -uo 11?
i=1
Σ i=1
|| -2" + +uuf - wo3
$ 2n|l =2²11 + 2T
1=1
s 2(n + 71p - p²' -='112
(28)
Combining 27 and 28
yields
2 (n + (1m++>))l+> 711 -p"1l2 +4
Σ w
(29)
i=1
i=1
Combining (26 and
29 with 22
yields
FA
< 24
(1+ + 1) + +)) +>)]
lpp
==112
2
+66 + 1)((1 + 9p (2 + +1))|B(=*>|| +
Σ
w
1=1
+ 2477" L3 + 1)N 4N.
(30)
C.3.3 DUAL GRADIENT NORM
Considering that Vipu is taken with respect to the subspace P, the gradients with respect to the dual variables are - see for example Bckstein & Svaiter (2009) for each 1.. + 1),
| w. Ww,
x
(x)
j=1
<
|| 2251/ 112
/=1
n+1
< 2
Σ (1
111 +112* =}11²)
j=1
Summing this inequality for i (n + 1) and collecting terms yields
V Te Px < 4(n +
| 2 *11
19

---

Under review as a conference paper at ICLR 2022
so taking expectations conditioned F& produces
n++
Ful v 4(n + 1) n+1
E V P
2 - 1
I 4(n + 1)
1 Fil + 1(n + 1) Σ Ell Bll 20112 FF.
< 4(n + 1)
- 1 Fi
+ +8n + 1) B11a 211 11 Fil + 8(n + 1) 11 20'1
< 4(n + 1)E[[|= - [F
+ +8( + 1)
B11aa 2 | 8(n + 1)3 - p² 112
I 8(n + 33 2
9p' -
+ +1]])(+))++] -p-112
+
(31)
where the final inequality employs 25
and 28
All told, using
30 and
31
and simplifying the constants, one obtains
E V pp
-B 2 F
|
B wi [F
<Cilpp - p011 + C2.
(32)
where
C = = + (n + 1)
1)²
+8(n + 1) (2T 6(n 1) +1+ 3(n + 7)
(33)
and
C2 16(N + +1 BB>*))|
8|| Σ w
N2T, +)
(34)
C.4 LOWER BOUND FOR GGAP
Recalling
13 that is,
lpp h+ 1²1 = 1|pt - -p113-2xx(xx00"=pp1111 - o
-
We may use the gradient bound from 32 to obtain
- 111 s (1 C - 1- - 2oxx(()( - (xxxx") + Cza (35)
E k+1
We now focus on finding a lower bound for the term Elpx(("*) - =p((p)) Fx), which we call the "Pa"gap". Recall that for p (z, WI...., Wn+1).
n+1
px(p) = Σ
(2 - x vt ws).
t=1
For each i E 1..(n++1 1), define (p,)(p) - (2 - xtt vt wi). We will call Elya, - (p"))(()) [FF
the "vrpe-gap". Note that (p((p) nn+1 (p).
20

---

Under review as a conference paper at ICLR 2022
C.5 LOWER BOUND FOR Pi,A OVER i 1..n
For i E I..n, we have from line of the algorithm that
- = =Ty"" - w
Since (t,x(p") = (2 - x v wf), one may conclude that for E 1.nn,
( 1 llu w 11 + / 11*
-
1
2f11?
2F
On the other hand, for p" E S and i E I..n, one also has (p") (=* at w 5\ 20 by the monotonicity of A, Therefore, for E I..,, it holds that
(36)
(1 - (p.k(p") 2 llut wfll 11 + 27
3
11 13.11
and taking expectations conditioned on F& leads to
[(pr,((p) (i,x((")) Fu _ llu. - w1 + 11 - -x,11 2/11
1
(37)
2T
where we have used that of and yf are both Fr mcaaurauee for i 1.n.
C.6 LOWER BOUND FOR PR+1AA-GA
From lines 6 of the algorithm, we have
x n+1 = (B(*(( - -wh+1 + +
Therefore,
(p+1 = (2t 1 vn w
(38)
= (2th - -x B(x²) wn+1
- + (2 - x xn Auti - B(z"))
(B((22 wh+ + te, B(*") - - + (2 -
- 2 kutz B(=*))
-PallB(=*) w 112 (z I Nittiiut butz B(z²)) +palet BB(²) wht1)
(=*) -w whitll1 + - s B(x B(=*)) + (2* w e
+ + " - w
2 Pkl B( k) "
+ 112 - 1 xht 112 + (2* -
+ fx B(2²) (
= B k) w 1 2| L |p (B(+k) w +)12 + t2 x x ety
+ pk (c B(²*) - -
= B k) w 1l 2| L - whit + t + 12t e
+ pa B(*²) - -w
= P1 |b - -w - p 11 + (2 2t e
+ p1 - 2.) , - w
(39)
where equality (a) uses line 8 of the algorithm and the inequality employs the Schwartz inequality followed by Lipschitz continuity of B.
On the other hand,
-p"+ = (2"
Fntt, w yntz)
(2" - n B(²*) B(x + (o - et))
(1 2" ee,))
(40)
21

---

Under review as a conference paper at ICLR 2022
where the second equality uses line the algorithm and the inequality follows from the monotonicity
of B.
Combining
(39 and 44) yields
*P*+IA(p"") -P+tIx(p"))) 2 Px(1 - P:::: w+tll + Px(11
- (,al))(eeBB( - -
+ (= 2/ Intr e ( -=" p 11
Mx (1 - Mk: I. B(2 w w 2 -
+ px - 2px L) (c: B(=²) - wn+ 1) + 12t 2² c²).
(41)
Now, if we take expectations conditioned on F& and use (9) we obtain
E (2* 2" ) Fi = (2* =" Bie Fxl) = 0.
(42)
Similarly, 9 also yields
E (c", B(=*)- w Fil (Ble*) [F,), B(x*)) - w un+1> (1:1))=00 0.
(43)
Thus, using and (43) and taking expectations of (41) yields
E| 1n++1 (p" FF 2 pk Ph: BB - PRLLEIIC+IPPF
z P - (b))) - - + |B
(44)
where in the second inequality we used 12) and the noise variance bound 1T).. Recall from 12 that
1- PL > O.
Next, we remark that
[1 = -
S
= 1| B[1 = 21 - pp111 +2|B==)
Substituting this inequality into 44 yields
B (((n+1,,((**) (p)) 2 (1 pT.)) B(= wn+1ll
2p 3 11p** -p'll3 NT + [{=))= (45)
Finalizing the lower bound on the gap Summing 37 over i E 1..n and using (45) yields
(xpxxx²*) (p)()))
(p) (in(
1
1l -
-w w/il2 +
Σ || att1?
2
2T
1=1
PM(1 [
wh+1l1 N. 1.21
11'11
NL + B(2
(46)
C.7 ESTABLISHING STOCHASTIC QUASI-FEJER MONOTONICITY
Returning to
35
+1
- < (1 G,a - -2-1 Elp (p(()) + C2a
we may now substitute (46 for the expectation the right-hand side. First, define
n
T
1l w1
PT Σ
- + ((1-))))B((=)) w
after which we may use (46) in 35 to yield
Elllp*+1 - n 112 FP) < (1 + Cias + C3az p012
CRPE To + C2a + Csaup
(47)
where C1 and C2 defined as before in 33 and (34 and
C3 = 4 3
(48)
C
(49)
This completes the proof of Lemma 3
22

---

Under review as a conference paper at ICLR 2022
C.8 A CONVERGENCE LEMMA
Before establishing almost-sure convergence, we need the following lemma to derive convergence of the iterates from convergence of Th defined above. Note that a more elaborate result would be needed in an ciinite-dimensionall setting.
Lemma 4. For deterministic sequences 2* R(++1)dd ((w)))) P, and (o R2((+))d suppose that y E A for E I.n, Exi w =0,
Σ llut - w 11 + E2 Σ 11 1111? Es|lB(>*) 1=1
w #++ll? +00
(50)
for scalars E1, E2, O, and pt = (**, wf...., w wh+1) + pp (8, W1 #n+1). Then P E S.
Proof. Fix any i E nl. Since lly. w
n).
by 50 and w - wis we also have
y - uhg. Similarly, (50) also implies that ||a x
so from zk we also have x +
Since y E A.(x.) and (a. )²) (2, dds), (Bauschke & Combettes 2017 Prop. 20.37) implies ib; E (2).). Since i was arbitrary, the preceding conclusions hold for i E I..n.
Now, (50 also implies that [IB(=*) w + O. Therefore, since w w + Wn+1, also have (22
un Much before, since (2*, B)=*)) (2, i,, we may apply (Bauschke & Prop. 20.37) to conclude that that t = B(2)
Combettes 2017
Since the linear subspace P defined in (6) must be closed, the limit (2, "i,..., un+1) of {(2 wi...., w 1)) C P must be in P. hence n 20 = 0.
Thus, the point p (2, .i....,, 1n+1) satisfies W; (a) for i E 1..,, Un+1 B(²), and ENH úē; 0. These are the three conditions defining membership in S from (5), so P E S.
C.9 FINISHING THE PROOF OF THEOREM
Given Ex of co, and Σ a co, satisfies the conditions of Stochastic Quasi-Fepp Monotonicity given in Lemma By applying Lemma 2 such that P[2+]] for = 1,2, and
we conclude that there exist 9, Q2 Sgg
1. for all e Ω
asppTh(U) < co,
(51)
2. for all v E O2 and p' E S, (v) - pl converges to a finite nonnegative random-variable
3. for all E 2z (v) remains bounded.
Since Ex akPs = co, 51 implies that for all v 22 there exists a subsequence qu (v) such that
T + 0.
(52)
Let O = 22 n 22 n Sag and note that P[S"] 1. Choose v E Lz. Since (v) remains bounded, so
does y (v) for (v) defined above in (2) Thus there exists subsequence rw(w)) (v(v) and
p(v) E (n+22)d such that (ra(o)()) (v) + p(v). But since (p + 0, it also follows that Tra(e) that is,
n ll (v) (e:)-w((log -
1 pr
Σ (2))(() (v) - 2x)(
+ 2(1 - B(
(v)) - (1())) (o)()(())) 0.
We then have from Lemma 4 that ((v) E S.
23

---

Under review as a conference paper at ICLR 2022
Since (v) + ((v). it follows that ||p">(() p(u)ll - 0. But since p(v) S, (1) p(v)]
converges by point 2 above. Thus
lim IIp" (v) =(u)]l
lim 1-+00
[Irx(())))) -(v)) =
Therefore p²(v) + p(v)= E S. Thus there exists P E S such that p a.s., which completes the
proof Theorem
C.10 TWo ADDITIONAL RESULTS
In this section, we prove two additional useful results about SPS. First, that 2. - 2 (a.s.) for i 1,..., n. Second, that G₁ 0 (a.s.).
Note that
a J+ (= + ruf))
and since z* and w convergence a.s., so does otC Consider the subsequence (x(v) such that (52) holds. Then
2
(x(1) 0
I;
thus
qh (v) + Σ.
2
Since x converges to some limit (a.s.), that limit must be 2.
Recall that
G¹ - E. ii llu will" 112
Σ 11 12212 + [B(=*)
wh
We have shown that x* and of share the same limit for i I,..., n (a.s.). Therefore zt x + (a.s.). Since
v w r (2 ) it follows that v w. - 0 (a.s.) for i = 1,..., Therefore
G [I w 1 1|2.
But since (z, di..................... wx+1) E S, u B(3) implying that G5 - 0 (a.s.).
D PROOF OF LEMMA
If Ge = 0, then
n. =i= I2: v = w and 2t = x
(53)
Since y (att)) for i 1..... n, (53 implies that that
Vi E 1..n: w Ar(*
(54)
Furthermore G1 = also implies that wht1 B(z*). Finally, since Et+ w/ = 0, we have that
(a "....., wh+1) S.
Conversely, suppose (2* wt wf... wh w S. The definition of S implies that ((2 w and
furthermore that wt¹ E As(2h) for E 1..n. For any i E 1..n, considering line 3 of Algorithm I
may write th * + Tw (I+ (z) implying 2* e (I + T (+t) ). But since the
resolvent JrA, = (I + AA) is single-valued (Bauschke & Combettes 2017 Prop. 23.8), we must
have ² (I A (t.). Thus, by line we have x = zh, We may also derive from line 5 that
: = - 24) = (2 Tw. - -2 x) w.
Thus, since of * and / wi for 1...., n and wht1 B(=*), have that G2 0.
24

---

Under review as a conference paper at ICLR 2022
E PROOF OF THEOREM 2
In addition to the proof, we provide a more detailed statement of the theorem:
Theorem 3. Fix the total iterations 2 of Algorithm 7 and set
vk ,....,K
K
Pk p = min
K 1/4
(55)
2L
vk ,.... K
ag = Cyp²
(56)
for some C O. Suppose 9
hold. Then for any p- E S
1
K
G
81,3 exp (C,(Cr +c))
(10 (lo'-p'11-
C4
for K < x2L)*
(57)
K
Cj minnt,,7~1J
0,0+CC
==1
exp (xp(C + C3)
C,02+ [1p 1101 CjC1 +
for K (2L)*. (58)
K
Cy min |
where G& is the approximation residual defined in 14 and C1. C2, C3, C2 are the nonegative constants defined in (33). (34). (48), and (49). respectively. Therefore,
K
K
Proof. Fix ag = and Pk: = p. where a and p are the respective right-hand sides of (55)-(56)
Lemma implies that (2I) so long as (9 (1-(IT) hold and the stepsize p satisfies p < L- Since
1
min 1/4
2T.
2T
we conclude that applies.
Rewriting (1 with and we have
Ellp k+1 1'1 < (1 C1a? + C3ap²) )pp* -p'l1
+ - - apTT C2aa + Ciap².
Therefore, taking expectations over FA. have
E Elp k+l
p 2²11 < C1a Csapp Bllp" p²112 appTT + Cza + Crap².
(59)
Recall that
Tk =
llu
w1112 1
2
2 2(1 - PL)]IB(2)) - w
pT
where for the first two terms we have simply set = p because the stepsize is constant. However, for the final term, we will still use upper bound, P. p. In the current setting, know that < (1/2)L-1 and therefore we may set p (1/2) L -1 Thus 1 - PL = 1/2, leading to
pET
Ellut
will
+
E
t
B(**) wh+1ll
Let
Us = E|((2*))
w 1
W6 =
Ellut w 12
E k
x 112
so that
pET, pUh, + Wk.
and also let
V6 = E1Ip* -1-12
25

---

Under review as a conference paper at ICLR 2022
Using these definitions in (59) we write
VE+1 s (1 Cia² + -oopp"Vs-opp - app - -aWp + C2a2 + C4ap².
Therefore,
V4+1 + +
+
1 (1+C + C3ap²) Cza + Cjapp
k-1
k-1
Vx+1 + ap
U3 + a
W3 Σ (1+ + C3ap") + ap
U3 + a
W
1=1
j=1
j=1
j=1
+ C2a² + Csap²
k-1
S (1+ C1a² + C3ap²)
Vx vx Σ
U, +
Σ
W
j=1
C2a² Caap²,
where we have used that UR. W 2 0. Letting
k-1
k-1
Rg V/: + ap Σ
UU+a + Σ W
we then have
R&41 S + 0ia + +3ap3) + C2a² + Cyap",
which implies
k R&t1 S (1+ Cia² + Caap²)* Ri + (C2a² + Caap²) Σ (1 + Cia² + Csapp)
Now,
k-1
(1+Cia2+ Czap2) = (1+ Cia + +LaCp=++Capp) Csap?'
Σ
1=
(1+ Cra² + yzap))
(1+Cia² + Czap²)
(1 Cia Caapp) -1
Cia² +Capp²
Cia² + 2zap2)k
+ +Cp++pppp
Therefore,
R&41 S (1+ + C
R1 +
Cia² + Czap2
Fix the number of iterations K 2 Now
K- 1/4 1
1
p == min
<
K1/1 I 1.
21
Therefore,
K ap) > (U, + W2) S app Σ
K
K
U
+
Σ W
j=1
j=1
j=1
< RK+1
Cza² + Caapp
$ (1 + Cia² + Csap?)
Rh
Cia² + Czap?
26

---

Under review as a conference paper at ICLR 2022
Dividing through by apk, obtain
1 K
C1a + Czap²)
R1 + Cza² + Cıap²)
10 U W)+
(60)
apK
Cia² Czap2
and since a Cyp² we also have
C2a² + Cjap²
C₁C2+
Cia² + Cgax?
CjCi +3
Furthermore,
p K
a a C
Substituting these into (60) yields
1+ (1C,
K UU + W 5
Cy0++C
R1+
K
apK
c/0++C3/
j=1
+c)) exp(C,(C,C Cz))
C,C2+Ca
R1
(61)
apK
CyCi+
where we have used that for any 2 0, 1/K S e//K so therefore (1 (1+1/K)* ee.
The worst-case rates in terms of K oceur when م K-1/4 and a C2K -1/2, This is the case when K 2 (2 Substituting these into the denominator yields, for K > (2L)*, that
1/22,
1 K
Σ UU, WU)+W,) exp(C,(C,Cr + C3)) CC))) C2K1/4
Rı c,C2+C,) CjC C2
Thus, since Gk S mmx T (Uk + Wx), we obtain
K
max T, T exp (C,(C)C1+ E|G
C,O2 (I'' C,0++C,,
K
Cj K1/4
which is 58
When K 4 57 can similarly be obtained by substituting p (2L) and Cy(2L) 2
into 61
F APPROXIMATION RESIDUALS
In this section we derive the approximation residual used to assess the performance of the algorithms in the numerical experiments. This residual relies the following product-space reformulation of T
F.1 PRODUCT-SPACE REFORMULATION AND RESIDUAL PRINCIPLE
Recall (I. the monotone inclusion we are solving:
Find E Rd :2d:0e : Σ A+(z)++B1)
1=1
In this section we demonstrate "product-space" reformulation of (1 which allows us to rewrite it in a standard form involving just two operators, one maximal monotone and the other monotone and Lipschitz. This approach was pioneered in (Briceño-Arias & Combettes 2011 Combettes & Pesquet] 2012). Along with allowing for simple definition of approximation residual measure of approximation error in solving (I). it allows one to apply operator splitting methods originally formulated for two operators problems such ( for any finite n.
27

---

Under review as a conference paper at ICLR 2022
Observe that solving T is equivalent to
Find (Wi,..., Wn: E (x(+1)dd
wy E (z))),
i 1.I
0 E Σ wi + B(z).
This formulation resembles that of the extended solution set used projective spitting, as given in (5), except that it combines the final two conditions in the definition of S, and thus does not need the final dual variable Wn+1-- From the definition of the inverse an operator, the above formulation is equivalent to
Find (Wi...., Wn, 2) E (n+1)d
DE (w;) - -2 iE 1..
w; + B(z). 0E
1=1
These conditions are in turn equivalent to finding (wi...., Wn, 2) E R [n++ljd such that s (wi...., Wni 2) + ((w:((( [w] ....... Wn: 2):
(62)
where of is the set-valued map o (wi,.... Why 2) AT (w1) Ar ... A (wx) {0) and is the single-valued operator
(63)
2 [1 Wny 2) T
+
(64)
W0
B(2)
It is easily established that 0 is maximal monotone and Lipschitz continuous, while e is maximal monotone. Letting I - d B, it follows from (Bauschke & Combettes 2017 Proposition 20.23) that T is maximal monotone. Thus. we have reformulated (I) as the monotone inclusion 0 E 9 (q) for q the product space ()++ vector E Idd solves (T) if and only if there exists (w,...., w,) Rad such that 0 E [g)).. where q = (wI,... (wi...., W,,, 2).
For any pair (q, v) such that o E (g). |0||2 represents an approximation residual for q in the sense that 2 0 implies is solution to (62). One may take ||2|| as measure of the error of q as an approximate solution to (62). and can only be if q a solution. Given two approximate solutions Qi and Ø2 with certificates E T(g)) and 02 (g2), we will treat qI as "better" approximate solution than d2 || l|2 < ||02||2. Doing so is somewhat analogous to the practice, common in optimization, of using the gradient [=)]
measure of quality of an approximate minimizer of some differentiable function f. However, note that since 9 (q1) a set, there may exist elements upper of T (n)) with smaller norm than t1- Thus any given certificate en only corresponds bound on dist? T (q:)).
F.2 APPROXIMATION RESIDUAL FOR PROJECTIVE SPLITTING
In SPS (Algorithm for E I..n, the pairs (a,t yf) are chosen so that y E A,())). This can be seen from the definition of the resolvent. Thus x E A, (v/²) Observe that
xf -
Evii 2).
(65)
x bb B(2²)
+ Dimi
The approximation residual for SPS is thus
R2 = 1 =
|
2//12 + )) + Σ 11
(66)
1=1
1=1
28

---

Under review as a conference paper at ICLR 2022
which is approximation residual for (yf..... ................................ yh x*) in the sense defined above. We may relate Rg to the approximation residual G₁ for SPS from Section as follows:
n
R
|1
2111 +
B(z +
y
a
n B(=*) +
n+1
11 1 112 +
W
11 2 + 211l(2*) - +
Σ
w
i=1
11 =1,1² + 2II 1112 2 2n Σ Σ ==1
11 m0,1 11
1=1
$ 2nCk
where in the second equality we have used the fact that Em w = 0. Thus, R3. has the same convergence rate as Gy given in Theorem
Note that while the certificate given in (65) focuses on the primal iterate zt, it may be changed to focus on any 2 for i ,,..., n. by using
2 x
of
x B(x)) + Σi=
The approximation residual || 112 may also be shown to have the same rate as G3 by following similar derivations to those above for Rg.
F.3
TSENG'S ' METHOD
Tseng's method (sengg 2000) be applied to (62 resulting in the following recursion with iterates g 9th E In+
dt Ja aB(T))
(67)
t+ &F +0(3(0)-
(68)
where of and H are defined in (63) and (64 The resolvent a may be readily computed from the
resolvents of the A, using Moreau's 's identity (Bauschke & Combettes 2017 Proposition 23. 23.20).
Analogous to SPS, Tseng's method has an approximation residual, which in this case an element of ((*)). In particular, using the general properties of resolvent operators applied to Ja we have
1 -a) -10")) E (g)))
Also, rearranging (68 produces
- k+1 + + B(g))
Adding these two relations produces
a (q" - xx+l) E o o + F(
Therefore,
R RT
|1g +
represents a measure of the approximation enror for Tseng's 's method equivalent to Rg defined in (66) for SPS.
29

---

Under review as a conference paper at ICLR 2022
F.4 FRB
The wwwardd-rffectted-acckwwwe method (FRB) (Malitsky & Tam 2020 is another method that may be applied to the splitting g = 3 for of and B defined in (63) and (64). Doing yields recursion
d Ja aa23((2)0"))
B(q ((g-))))
Following similar arguments to those for Tseng's method, it can be shown that
1 (q" )²) - E URB a
Thus, FRB admits the following approximation residual equivalent Rg for SPS:
Finally, remark that the stepsizes used in both the Tseng and FRB methods can be chosen via linesearch procedure that we do not detail here.
F.5 STOCHASTIC TSENG METHOD
The stochastic version of Tseng's method of (Böhm al. 2020) (S-Tseng) may be applied the
inclusion 0 E a + (g), since the operator a may be written as subdifferential. However, unlike the deterministic Tseng method, it does not produce valid residual. Note also that S-Tseng outputs an ergodic sequence L.g. To construct a residual for the ergodic sequence, we compute deterministic step of Tseng's 's method according (67)-
16-1668). starting at 2eg.. That is, letting
qh = Jaor (gerg Bl(grg))
g+1 q² al ((((g))))) B(²))),
can then compute essentially the same residual in Section F3
R Tseng
a 11
112.
To construct the stochastic oracle for S-Tseng, we assumed B(z)
1 Σ == Bi(=). Then we used
W1
0 ... Wny 2) +
:
+
(69)
0
-T
Wh
I
z
B
EjEn By(z)
for some minibatch B E f1, f1....,,m) m}.
F.6 VARIANCE-REDUCHE FRB
The FRB-VR method of Alacaoglu al. (001) can also be applied to 0 E s + B(), using the same stochastic oracle A defined in (69) if we let the iterates FRB- VR be (q then line 4 of Algorithm of Alacaoglu al. (2021) can be written as
nº = 9d T(B(p)) + ( 30ph))
(70)
h+1 = ( )T*)
(71)
Once again, the method does not directly produce residual, but one can be developed from the algorithm definition as follows: (7I) yields - (ah x+l) 1) E of (g and hence
(g" ,+1) B(g x-1) (el + (g
Therefore we use the residual
FRB-VR R
1 - / ,+1 + 01
Figure 1 plots Rs for SPS, TTway for Tseng's method, RERB for FRB, R S-Tseng for S-Tseng, and RFRB-VK for FRB-VR.
30

---

Under review as a conference paper at ICLR 2022
F.7 BENEFITS AND DRAWBACKS OF THE PRODUCT SPACE REFORMULATION
The main benefit of the product space reformulation (PSR) is that it allows one to use familiar 2-operator splitting schemes for solving 0 E .e (4) + B(4) solve the more complicated recursion @T. However, one drawback of this approach is that the operator 2, defined in (64), combines a skew-symeetric consensus matrix with the Lipschitz operator B. Treating D as single operator necessitates using single stepsize for both of its constituent operators, but the B component will generally have a much larger Lipschitz constant than the skew part, necessitating smaller stepsize than is ideal for the skew operator. This difficulty can be countered by using different stepsizes for the primal and dual components, but that strategy introduces additional tuning parameters. In other works, methods based on PSR have exhibited slower convergence than deterministic projective splitting methods (Johnstone & Eckstein 2021 2020b). However, in our experiments in Section] 7 the performance is comparable.
G VARIATIONAL INEQUALITIES
For a mapping B R Rd and a closed and convex set C, the variational inequality problem (Harker & Pang 1990) is to find x* E such that
B(=") (2 2²) 2 0, 0, EC
(72)
Consider the normal cone mapping discussed in Section 2 and defined as
Nc(x) = {g 9 g (y x) S 0 Vy C}
easily seen that 72) is equivalent to finding =* such that - -B(=)) E Nc(=*). Hence, if B is monotone, (72) is equivalent to the monotone inclusion
0 E B(²") + Ne(2").
(73)
Thus, monotone variational inequalities are special case of monotone inclusions with two operators, one of which is single-valued and the other is the normal cone map of the constraint C. As consequence, methods for monotone inclusions can be used to solve monotone variational inequality problems. The reverse, however, may not be true. For example, the analysis of the extragradient method (Korpelevich, 1977) relies on the second operator N: in (73) being a normal cone, as opposed to more general monotone operator. We are not aware of any direct extension of the extragradient method's issei analysis allowing more general resolvent to be used in place of the projection map corresponding to Ne.
The Restricted Gap Function There is disadvantage to pursuing convergence rates based on variational inequalities (as in Böhm et al. (2020) and Alacaoglu et al. (202I) rather than monotone inclusions. Convergence rate analyses for variational inequalities focus on the gap gup function:
Gc(z) - sup BB=') (=- z²). x'=
(74)
Z'EC
can be shown that Gc(z) 2 0 and Ge(z) = if and only if a solves 72
However, 74 is
meaningless for most problems, since unless C is compact, Ge(²) is typically equal to +oo for any nonsolution (Diakonikolas 2020). Thus researchers instead focus on the restricted gap function (Nesterov 2007)
Ge,(z) = sup (22')(2-221) S'EC2
(75)
where C2 is arbitrary compact set. However, now the results are only meaningful over the Cz- Thus, C2 must be chosen large enough so that the iterates of the algorithm remain in the interior of C2 (Böhm et al., 2020). Further, the convergence rate bound depends on the diameter of Cz. For some algorithms Mookhtari et al. (020)) valid set is provided which bounds the iterates. However Böhm al. (2020) and and Alacaogiu et al. (202T) do not provide one, although principle it could be done so long the ergodic sequence can be bounded almost-surely. Thus, the convergence rates depending on (75) in Böhh et al. (2020) and Alacaoglu et al. (2021) are somewhat incomplete in that they depend unknown constants.
In contrast, rates based on the approximation residual in the monotone inclusion setting, including ours given in (57) (58). completely avoid this pitfall. There is need to select compact set containing the algorithm's 's iterates and the constants in our rates are all explicit or depend on standard quantities such the initial distance solution.
31

---

Under review as a conference paper at ICLR 2022
H MEMORY-SAVING TECHNIQUE FOR SPS
The variables th. ny, and y on lines 3 5 of SPS are stored variables 2 and y. Another two variables I and y keep track of Σi= 1 and Σi= y² The dual variables are stored as w, for i E I..n and the primal variable as 2. Once I = क computed, the 7th dual variable w; can be partially updated ut; <- W: 0g. Once all the operators have been processed, the update for each dual variable may be completed via Wi; < w; + ax + 1)--r. J. Also, the primal update is computed as f agy. During the calculation loop for the = y/ the terms in approximation residual Rş may also be accumulated one by one. The total total number of vector elements that must be stored is (n 7)d.
ADDITIONAL. INFORMATION ABOUT THE NUMERICAL EXPERIMENTS
We solve the following convex-concave min-max problem:
min
((6 (x0- x) max
m Σ
1
v ((2,,
B))
m Σ
1
(0, - An) + +cll8l1
BER yER" AER
(76)
s.t. 118112 S A/(Lv 1)
111 1.
This model is identical to that of (Yu al. 2021 Thm. 4.3) except for the addition of the Lj regularization term e|| where 2 is given constant. The goal is to learn the model weights B from training dataset of feature vectors é; and corresponding labels D.. Rather than computing the expected loss over the training set, the formulation uses, for each 3, the worst possible distribution within Wasserstein-men metric ball around the empirical distribution of the {( 9.)). with the parameter
5 > 0 giving the diameter of the ball and the parameter 2 O specifying the relative weighting of features and labels. The variables y and parameterize the selection of this worst-case distribution in response the model weights B. Finally, V/ is the logistic loss kernel t + log(e' + e- and Ly 1
is the corresponding Lipschitz constant. In all the experiments, we set å = K = 1 and c 10
We now show how we converted this problem to the form for experiments. Let be shorthand for (A, B, 7)), and define
((=) = X(6 x)
V ((e,, 3)) Σ (in -x)).
The first-order necessary and sufficient conditions for the convex-concane saddlepoint problem in 76) are
0 E +1) (=(=)
(77)
where the vector field (22) is defined as
vx,(((2) v,((2)
B(s) =
(78)
with
8 8- x(1 + 1 Σm 7:)
V Vx,a((=)=
1 m
V V'(a,, B)) +
Σm Di=l 7eh
-==
and
1 (01 (01, -xx)
m
v,((2)=
(Im (8m, B3 AR)
is readily confirmed that B defined this manner is Lipschitz. The monotonicity of follows from its being the generalized gradient of convex-concave saddle function (Rockafellar 1970).
32

---

Under review as a conference paper at ICLR 2022
For the set-valued operators, A1 corresponds to the constraints and A2(2) to the nonsmooth & regularizer, and are defined as
A1(2) Ne, (2, Nc,
where
C1 = ((A |811 \/(L + 1)} and C2 = 17: 1
and
A2(2) = (01x1) x c0I {0mx1).
Here, the notation 0px1 denotes the p-dimensional vector of all zeros. C₁ is a scaled version of the second-order cone, well known to be closed convex set, while C2 is the unit ball of the foo. norm, also closed convex. Since A₁ a normal cone map a closed convex set and A2 the subgradient map of closed proper convex function (the scaled 1-norm), both of these operators maximal monotone and problem (77) a special case of (I) for n
Stochastic oracle implementation be written as
The operator B pm+d+1 + Rm+d+1 defined in 78). can
B(z) = m Σ B2(2)
where
x(1 7))
V (( 3)) + Wib
=+
((-1))x1
(Ut (f.,, B) - Axs)
(m--)
In our SPS experiments, the stochastic oracle is simply B(x) = B + Eien B²(=) for some minibatch B S (1,....,m) We used a batchsize of 100.
Resolvent computations The resolvent A1 is readily constructed from the projection maps of the simple sets C₁ and C2, while the resolvent Ag involves the proximal operator of the l norm. Specifically.
01x1
[2),(2)= projc, B) (7)
and J0A2(=)=
prox (B)
0 0mx1
The constraint C1 is a scaled second-order cone and C2 is the &go ball, both of which have closed-form projections. The proximal operator of the E norm is the well-known soft-three offtthressholdig operator (Parikh & Boyd, 2013,, Section 6.5.2). Therefore all resolvents in the formulation may be computed quickly and accurately.
SPS stepsize choices For the stepsize in SPS, we ordinarily require Pk S P < 1/L for the global Lipschitz constant L B. However, since the global Lipschitz constant may pessimistic, better performance can often be achieved by experimenting with larger stepsizes. If divergence is observed, then the stepsize can be decreased. This type of strategy common SGD and similar stochastic methods. Thus, for SPS-decar
set ag Cak-0.5 and Pk Cak-0.25 and performed grid search to select the best C. from {0.1, 0.5, 1, 5, 103. arriving at C₁ = for epsilon and SUSY, and we used p = K 1/4 and a = Cyp?, and performed grid search select Cý over {0.1, 0.5, 1, 5, 10), arriving Cy 1 for epsilon and real-sim, and C for SUSY. The total number of iterations for SPS-fixed was chosen as follows: For the epsilon dataset, used K 5000, for SUSY used K 200, and for real-sim used K 1000.
Ca = 0.5 for real-sim. For
33

---

Under review as a conference paper at ICLR 2022
SPS decay lours)
approximaton resioul
approxieeetto residlul
SPS fixed (ouns)
307
octerministic
Iseng's method
Stoch. Tren''s mechod
opoch
egach
epoch
Figure 2: Approximation residual versus epoch for three LIBSVM benchmark datasets. Left: epsilon, middle: SUSY, right: real-sim.
Parameter choices for the other algorithms All methods are initialized at the same random point. For Tseng's method, we used the backtracking linesearch variant with initial stepsize of 1, 0 0.8, and stepsize reduction factor of 0.7. For FRB, we used the backtracking linesearch variant with the same settings as for Tseng's method. For deterministic PS, we used fixed stepsize of 0.9/ For the stochastic Tseng's 's method of Böhm et al. (2020), the stepsize ag must satisfy: Σk=1 O2 = oo and Exe k= og < co. So we set 0ş Ck and perform grid search over {C, d] in the range
[10- 1,00 [0.51, 1]. checking 5 x values to find the best setting for each of the three problems.
The selected values are in [
epsilon
SUSY
real-sim
C
0.56
0.56
0.77
d
0.6
0.6
0.55
Table 1: Parameter Values for S-Tseng
The work of Böhm et al. (2020) also introduced FBFp, a stochastic version of Tseng's 's method that reuses a previously-computee
gradient and therefore only needs one additional gradient calculation per iteration. In experiments, the performance of the two methods was about the same, only report the performance of stoch. Tseng's method.
For variance-reduced FRB, the main parameter is the probability p. We hand-tuned p.arriving = 0.01 for all problems. We set the stepsize to its maximum allowed value
VT-P 2L
7
Plots versus Epoch Floure the performance of each method versus epoch (i.e. data pass). This shows an even more dramatic benefit for the stochastic methods than the plots versus time, since at each iteration the stochastic methods only need to process small amounts of data, whereas deterministic methods must process all of it. We believe these benefits do not fully manifest themselves in the plots versus time due to overheads in each iteration of the stochastic methods, multithreading providing boost for the deterministic methods, memory access patterns, and other practical considerations.
Fraction of Nonzero Entries versus Running time Figure 3 plots the fraction of nonzero entries in the iterates of each method versus running time. For each method, we used output of prox oI We observe that our methods produce sparse intermediate iterates for two the three problems. This one of the benefits of proximal splitting algorithms in general, including our method. For the other problem, SUSY, no method produces sparse iterates, suggesting that c should be increased sparse solutions desired.
34

---

Under review as a conference paper at ICLR 2022
Frectoon non-20ro
2010
6.0%
Fresiion nor vato
ven OC Tuegy PRaVT
0:00
running time (s)
running time (s)
running time (s)
Figure 3: Fraction of nonzero entries versus running time for the three datasets. Left: epsilon, middle: SUSY, right: real-sim.
J LOCAL CONVERGENCE ON NON-MONOTONE PROBLEMS
The work by Hsieh et al. 20200) provides a local convergence analysis for DSEG applied to locally monotone problems. Recall that DSEG is equivalent to the special case of SPS for which 0. While extending this result to the more general setting of SPS is beyond the scope of this manuscript, we next provide preliminary sketch of how the analysis of HHsHhhhh al. (2020) might be generalized to our setting. We leave formal proof to future work.
Sketch of assumptions and main result The first assumption needed is the existence of isolated solution p² = (2", ....... w ) S. We then require that there exists a ball (2*),,,, centered at 2", throughout which the operator B is "well-behaved", meaning that it satisfies monotonicity and Lipschitz continuity. In addition, we need each A,, for i 1..n, to be maximal monotone within this ball. Outside of the ball, the operators do not need to be monotone or Lipschitz.
Following (Hsieh et al. 20200] Assumption 2'), the noise variance assumptions are slightly stronger than in the monotone case. In particular, we require that [[[]=~1[9]]] S N4 and 19 S No for some > 2. As before, the noise must be zero-mean. Finally, the stepsize requirements are also slightly stronger than (T2). having the added assumption that Σx= p% co.
With these assumptions, the goal is to show that, so long as the initial point p is sufficiently close to p", then with high probability p² converges to p".
Proof strategy The initial strategy is to develop the following recursion, satisfied by SPS, that does not (yet) utilize local monotonicity Lipschitz continuity:
1p ++1 1'1 < + +
p" 21 c2axph(Tx + 4 + rk) crau(rk + qx) + cjaz 111e + 1| + ci) czaugh
(79)
for appropriate constants
cs...cs 2 0. In this inequality,
n
n
TVd
lut w pr Σ || 1.113
p
n
4. (2
x * : v + (2 - = wi - B(x
2k (e B(T**) - 1 1)+
r (2' - ;,,
a (PF) -1 d/2)||²** - -/122 || ((a) - B(=*)]
de 1le |11| Bx - B || + 2d
1 11
where
d - 1 - PL.
** = pp (B(xt) w
(80)
+ p/2'
35

---

Under review as a conference paper at ICLR 2022
with L being the local Lipschitz constant of B (x*). The iterate i² is the analog of the iterate X x+112 used in Hsieh al. (202)).
The recursion (79) is derived by once again starting from 13 and following the arguments leading to (35). but this time not taking conditional expectations. In partieular, the upper bounds || and | w. |P&ll contribute the terms c1a2 || + ||=1| + eq) and q p'11 For i E 1..7t, the "Pi,A-gap term, (p.x((")) Pi, (p"( dealt with in similar manner Section C.5 but this time not using monotonicity as in (36). This contributes TV and the first term in 4g.. Finally, as we
sketch below, the ",n+1,A-- term contributes rhe Tee qks Th and the last term in 4.
For the ",a+1, that is, (p+1,<(p²)) *n+1,*(p")) ), we have depart from the analysis in
Section C.6 and use alternative argument involving ã* We provide some details of this argument: in the following, we use Bz as shorthand for B(z) for any vector 2 E Rd, We begin the analysis with
Pn+1**(p*) = (2 xt 1 Buti 1 - w
= -2 2 Br wh+1) 1) + (2 c.
(81)
part of
The final term will combine with the term (a 2", et) coming from
-P+11(("") = (="
k
n+1 wh+1 - yn+t)
#n wh+1 Brn+1) + (2 -2", e
(82)
to yield r above. Equation 82 also yields the second term in 4. Using that āt 2 = PkEk. we rewrite the first term in (8I)
(2 21 Brx
w11 (2/ 2h. Br Bxn+1 w w + (5th 2 Br w
(z 5hh Br n+1 w + pklc Bx w whtt)
(at Th Bra+1 n+1 w + px Br - Bāt
(83)
+ (et, Bō w wht))
Next, the terms in (83) admit the lower bound
(2 - 2/ B whtn) + pa (e Ba - B
(2 ahh Bur w wht pkele*
Bu
BE
first part of dh
Considering the first term on right-han hand side of this bound, we also have
(2 88, Bur wh (** 2h B wh+t) ) + (2* Iht Bu B
2 (= - th Bic
# wh+1) $1 z*
2d Ba
Br 1
second part of 9/2
for any > O, using Young's inequality, Finally, for the first two terms of the right-hand side of the above relation, may write
d
(2k - 2 B w
2 -1
=1 -
d
= (2 xhh B² 1) + +(2² - i:h Bith k - -B²*)
1|
111
2
(pr -1 d/2)) 1| x
1| 1 Bi*
B
44
36

---

Under review as a conference paper at ICLR 2022
where in the final inequality use the Pk (= z*), from the definition of z in 80 We have now accounted for all the terms appearing in
inequality and substitute Bz w
The recursion 79 is analogous equation (F.7) on page 24 of Hsieh al. 2020) and provides the starting point for the local convergence analysis. The next step would be to derive an analog of
Theorem F.1. Hfieh et al. (2020) using (79). The following translation the notation of Theorem
F.1. could be used (note that Hsieh et al. 2020) uses / for iteration counter):
D = 1pp p211"
CA = C20xPk (T + 1x) cz0uol,
EK -2aupphk c3art
Xk = cia (Ile* + 11 1p -p--ppl -p"11 + ca) + czardh
and the event Es is translated to
E = f- B,(²",, it I (pr(2").pp Bpr((") for all k = 1.2......
An analog of Theorem 2 of Hsieh et al. (2020) could then be developed based on this result.
37


Reviews:
[{"review_id": "ss4k5FAWYJV", "reviewer": "Reviewer_H9EN", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written and the main contributions are clear. To the best of my knowledge this is the first paper that provides a stochastic variant of the projected splitting algorithm for solving monotone problems with convergence guarantees.\n\nBelow i provide some pointers for further clarification and improved presentation.\n\nI believe that the broader audience of the ML community is not very familiar with the monotone inclusion problems. I would suggest the authors to expand further in the updated version the section 2 of the background on monotone inclusions. Have a proper statement of how these problems can formulate classical problems appearing in ML. For example the authors mentioned maximal operator without a proper definition. they also refer the interested reader to Ryu and Boyd (2016) for proper definitions. I think include all the necessary information in the main paper will be make this work self-contained and could reach broader audience. \n\nAlso i notice that there are few places that the authors could do better job in the presentation. \n\n1) Add a reference for the equation (4) on first order necessary conditions for solving Nash-equilibrium problems and provide a bit more details of what this means.\n\n2) More details required to be given on how one obtains the update rule (8) by projection step for a half space. What is the close form expression of $\\nabla \\phi_k$ and how this is computed relative to $\\cal{P}$.\n\n3) In theorems 1 and 2 add all assumptions on problem 1. Are the $A_i(z)$ and $B(z)$ monotone and L-Lipschitz? do you assume something beyond this and the noise assumptions for the proof to go through?\n\n4) In the intro the authors mentioned that their algorithm includes the update rule of the algorithms proposed in Hsieh et al. 2020 as special case. However when they SPS method presented no more details are provided. can you elaborate more on this? how the method can be obtained as special case and how the convergence guarantees of the proposed method (Theorem 2) can be used in the setting of Hsieh et al. 2020? \n\n5) On experiments: I would suggest instead of only comparing running time to also include 3 more plots where the horizontal axis will be computational complexity (how many gradient/operator evaluations are required by each method). this would be a fair comparison as the implementations might vary and not be optimal between the algorithms (this will affect the running time but not the computational complexity).\n\nSome Missing References:\nFour recent papers on the convergence analysis of stochastic algorithms for solving stochastic games and stochastic variational inequalities (special cases of monotone problems):\n\n[1] Loizou, Nicolas, Hugo Berard, Alexia Jolicoeur-Martineau, Pascal Vincent, Simon Lacoste-Julien, and Ioannis Mitliagkas. \"Stochastic hamiltonian gradient methods for smooth games.\" In ICML 2020.\n\n[2] Loizou, Nicolas, Hugo Berard, Gauthier Gidel, Ioannis Mitliagkas, and Simon Lacoste-Julien. \"Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity.\" NeurIPS 2021 (to appear).\n\n[3] Mishchenko, Konstantin, Dmitry Kovalev, Egor Shulgin, Peter Richtárik, and Yura Malitsky. \"Revisiting stochastic extragradient.\" In AISTATS 2020.\n\n[4] Li, Chris Junchi, Yaodong Yu, Nicolas Loizou, Gauthier Gidel, Yi Ma, Nicolas Le Roux, and Michael I. Jordan. \"On the convergence of stochastic extragradient for bilinear games with restarted iteration averaging.\" arXiv preprint arXiv:2107.00464 (2021).\n", "summary_of_the_paper": "The paper presents a stochastic variant of the projective splitting family of algorithms for solving monotone inclusion problems. In particular, it explains how the monotone inclusion problems can formulate several popular machine learning tasks like min-max optimization problems, game formulation and variational inequality problems and provides convergence guarantees of the proposed algorithm for solving monotone problems.\n", "summary_of_the_review": "As i mentioned in my main review i find that the paper is well written and the main contributions are clear. To the best of my knowledge this is the first paper that provides a stochastic variant of the projected splitting algorithm for solving monotone problems with convergence guarantees.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "pE_QsTewiJF", "reviewer": "Reviewer_vqpx", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This manuscript is ambitious in tackling the problem of multiple operators with a stochastic oracle. This can be seen as a natural generalization of stochastic gradient algorithms for more than one regularizers to the setting monotone inclusion, and can find potential applications in min-max problems and so on.  The motivation is more or less just replacing the deterministic oracle in Johnstone & Eckstein (2020b) with a stochastic one and applying a different stepsize scheduling, but surely this is of importance in large-scale machine learning applications such that accessing all data points could be prohibitively expensive.  However, with the given stepsize scheduling, although being able to achieve optimality asymptotically by driving a certain proxy measure to  zero, the proposed algorithm does not honor the specific structure induced by the resolvents, and therefore can fail to achieve the original purpose of adding multiple operators.\n\nMy detailed comments are as follows.\n\n1. In comparison with the product space reformulation, a clear issue is that multiple existing approaches generate iterates that honor the structure induced by the resolvents of the maximally monotone operators because the final step is the resolvent, while the proposed algorithm does not. In the context of optimization, this means that the specific structure (like sparsity, boundedness, low rank) enforced by the proximal operators will not be kept by the proposed algorithm. This is problematic from the application point of view (although probably not easily visible from the monotone inclusion angle), as usually the regularizers are added exactly because the users need specific structures in the final output.\n\n2. The setting is interesting, but it looks like the authors did not really find a relevant application in practice and therefore needed to invent one of their own and therefore ignored a key part of such a regularizer. As mentioned above, addition of a regularization term is usually for the purpose to enforce or promote a desired structure in the solution, and for the case of the L1 norm, the purpose is usually sparsity, as mentioned by the authors. Therefore, an important aspect to show is the sparsity level and how it changes with time for these algorithms being compared. I can actually imagine from the algorithm forms that probably the proposed algorithm does not generate any sparsity, while Tseng's method, FRB, and FRB-VR will provide stable sparsity levels. This greatly reduces the usefulness of the proposed algorithm.\n\n3. Given the slow convergence and the issue of not honoring the structure from the resolvents, I wonder if one could just apply (stochastic) subgradient methods or ideas similar to that, at least to a narrower range of problems that still include most the interesting cases. In such a case, likely the convergence speed will not be too different, thus from a theoretical angle, the proposed algorithm is probably not of very great contribution.\n\n4. Another concern I have with the experiment is that it seems like the proposed algorithm is fast only in the beginning, and after reaching a mild precision, the optimality measure stalls. From the result on real-sim, it seems like that deterministic algorithms are superior and the proposed method is beneficial only at the beginning for going through more iterations within the same amount of time. If the algorithm is more useful in large-scale problems, for presentation purposes, the authors should indeed present more results on larger datasets and probably skip small scale ones like the one for real-sim.\n\n5. Moreover, although the authors argued in the appendix that the product space formulation can lead to a much smaller step size that slows the convergence, it does not seem so in the comparison between deterministic PS and FRB or Tseng's method. It seems like that the deterministic PS is faster only in one case, thus diminishing the claimed contributions.\n\n6. Judging from the tickers, it also seems to me that some of the advantages of the proposed algorithms is actually from the better time efficiency, in comparison with other methods. (Interestingly, usually one would expect deterministic methods to run faster because of the memory access pattern and less for-loops to be called, and the results presented are quite counterintuitive to me.) If the comparison is in terms of epochs (so that implementation difference can be excluded), I wonder if the outcome would be much different.\n\n7. I also find the organization and detailed description quite unsatisfactory. It seems that the length limit of the main text of ICLR is too short for this manuscript to fully articulate, and I'd therefore suggest the authors to consider a journal or a different conference with a longer length limit (such as ICML or AISTATS that uses a two-column format). In particular, the authors spent quite a length in introducing fundamentals that might not be directly relevant to the rest parts of the main text and are actually well-known to most readers interested in this topic (those who decided to check the paper after viewing the title and abstract). On the other hand, key issues like how existing algorithms work, what the experiment is about, and how the residuals are estimated are all skipped in the main text. This essentially requires everyone to go back and forth between the appendices and the main text, which kind of violates the meaning of the appendices.\nIn essence, appendices are for things that do not affect the reader's grasp of the whole story, but clearly the authors are simply treating the appendices as places to implicitly increase the length of the main text and the readers are unable to skip any of the appendices without losing understanding of the main idea.\n", "summary_of_the_paper": "This manuscript proposes a stochastic algorithm for monotone inclusion with more than two operators, where one is Lipschitz and the rest are maximally monotone and possibly set-valued.  Under standard noise conditions for a stochastic estimation for the Lipschitz operator, the authors showed almost sure convergence for step sizes satisfying some mild conditions, and provided convergence rates of O(k^{-1/4}) for an optimality measure if the number k is pre-specified.", "summary_of_the_review": "The problem considered is of interest, but the proposed algorithm does not fully address the need of the applications. The manuscript presentation also has a great room for improvement. The current organization seems to be incomplete given the length of the main paper.\n\nAfter reading the revision and the responses of the authors, and discussing with the authors, my recommendation moves to weak rejection. The idea is indeed interesting, but there are still unclear parts in the text and organization, and the motivation for the algorithm seems more like finding extensions for an existing work, instead of a real need for the considered problem.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "4by4yaUBHKU", "reviewer": "Reviewer_LTCL", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "One of the drawbacks of this paper is that the main idea of the algorithm is somehow based on several works in literature. Specifically, the algorithm SPS is a stochastic variant of the recently proposed projective splitting (PS) [Johnstone & Eckstein, 2020b]. Also, the Double Stepsize Extragradient Method (DSEG) [Hsieh et al., 2020] is a special case of SPS when removing all regularizers and constraints. To address this issue, the authors discussed the comparisons of their results with other related works and explains the significance of this work lies in the general applicability of their convergence rate, which is one of the advantages of this work. When compared with the preexisting PS framework, SPS enables computational efficiency on large datasets. When compared with other stochastic methods on special cases of monotone inclusions, SPS enables a strong ability to deal with constraints and regularizations. \n\nHowever, the theoretical convergence rate derived in this paper is no better than previous results when constrained to specific problems in other works. While the problem setting is indeed more general, I feel confused about the possible technical difficulties that have caused the $\\mathcal{O}(K^{-1/4})$ convergence rate. In [Hsieh et al., 2020] they proved a $1/K^{1/3}$ last iterate convergence rate for the stochastic case, although Theorem 2 seems directly applicable to this setting, the convergence rate is $\\mathcal{O}(K^{-1/4})$. From my viewpoint, a good convergence result under the general framework should not only be adaptive to the special cases but also obtain a sharp rate when specified to traditional settings. \n\nWith this consideration, the contribution of this piece of work is a little weak. Moreover, why does the experimental result seem to outperform previous works, when the theory does not? In the first figure the pink FRB-VR curve seems to be descending at the right boundary, is it possible that FRB-VR reaches better solutions under some circumstances?\n", "summary_of_the_paper": "The paper focuses on the stochastic variant of the projective splitting (PS) algorithm. With a specific focus on monotone inclusion problems, the authors propose a novel separable algorithm featured by the ability to handle multiple constraints and non-smooth regularizers. Compared with similar approaches on variational inequality which is a special case of monotone inclusions, this paper uses a more direct error metric than the restricted gap function. Moreover, although with a slower convergence rate, this paper is the first discussion under the general discontinuous monotone inclusion case. ", "summary_of_the_review": "Overall, the paper is well written with each part of the results clearly explained and well supported. This is a highly interesting piece of work for the SPS problem, but the significance of its contribution is vague to me.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The submission considers a stochastic variant of the projective splitting algorithm, with a focus on monotone inclusion problems, and it proposes a novel separable algorithm with the ability to handle multiple constraints and non-smooth regularizers.  All reviewers felt that there were merits to the submission and that the submission was borderline.  Public and non-public discussion concluded that the paper would be of greater value to the community if the suggestions of the reviewers and related issues were addressed.
Decision: Reject