Three Operator Splitting with Subgradients, Stochastic Gradients, and Adaptive Learning Rates
Authors: Alp Yurtsever
Alex Gu
Suvrit Sra
Venue: NeurIPS 2021 Poster (2021)
Keywords: three operator splitting
nonsmooth optimization
stochastic optimization
adaptive step-size

Abstract: Three Operator Splitting (TOS) (Davis & Yin, 2017) can minimize the sum of multiple convex functions effectively when an efficient gradient oracle or proximal operator is available for each term. This requirement often fails in machine learning applications: (i) instead of full gradients only stochastic gradients may be available; and (ii) instead of proximal operators, using subgradients to handle complex penalty functions may be more efficient and realistic. Motivated by these concerns, we analyze three potentially valuable extensions of TOS. The first two permit using subgradients and stochastic gradients, and are shown to ensure a $\mathcal{O}(1/\sqrt{t})$ convergence rate. The third extension AdapTOS endows TOS with adaptive step-sizes. For the important setting of optimizing a convex loss over the intersection of convex sets AdapTOS attains universal convergence rates, i.e., the rate adapts to the unknown smoothness degree of the objective. We compare our proposed methods with competing methods on various applications. 


Three Operator Splitting with Subgradients, Stochastic Gradients, and Adaptive Learning Rates
Alp Yurtsever* Umeå University uep.yuutteeerruee
Alex Gu & Suvrit Sra
Massachusetts Institute of Technology {gua, suvrit) cowrittCmit...... edu
Abstract
Three Operator Splitting (TOS) (Davis & Yin, 2017) can minimize the sum of multiple convex functions effectively when an efficient gradient oracle or proximal operator is available for each term. This requirement often fails in machine learning applications: (i) instead of full gradients only stochastic gradients may be available; and (ii) instead of proximal operators, using subgradients to handle complex penalty functions may be more efficient and realistic. Motivated by these concerns, we analyze three potentially valuable extensions of TOS. The first two permit using subgradients and stochastic gradients, and are shown to ensure (1/vil) convergence rate. The third extension ADAPTOS endows TOS with adaptive step- sizes. For the important setting of optimizing a convex loss over the intersection of convex sets ADAPTOS attains universal convergence rates, i.e., the rate adapts to the unknown smoothness degree of the objective function. We compare our proposed methods with competing methods on various applications.
Introduction
We study convex optimization problems of the form
min
(xx) = f(x) + 9(x) h(x),
(1)
ZER"
where RRR + R and g, h: : R R are proper, lower semicontinuous and convex func- tions. Importantly, this template captures constrained problems via indicator functions. To avoid pathological examples, we assume that the relative interiors of dom(f), dom(g) and dom(h) have nonempty intersection.
Problem (1) is motivated by number of applications in machine learning, statistics, and signal processing, where the three functions comprising the objective á model data fitting, structural priors, decision constraints. Examples include overlapping group lasso (Yuan al., 2011), isotonic regression (Tibshirani et al., 2011), dispersive sparsity (El Halabi & Cevher, 2015), graph transduction (Shivanna al., 2015), learning with correlation matrices (Higham & Strabié, 2016), and multidimensional total variation denoising (Barbero & Sra, 2018).
An important technique for addressing composite problems is operator splitting (Bauschke et al., 201 1). However, the basic mruimmll(suu)gradicn method may be unsuitable for Problem (1) since
Alp Yurtsever and Alex Gu contributed equally to this paper. The paper based primarily on the work done while Alp Yurtsever was Massachusetts Institute of Technology.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

requires the prox-operator of g + h. computing which may be vastly more expensive than individual prox-operators of g and h. An elegant, recent method, Three Operator Splitting (TOS, Davis & Yin (2017), see Algorithm 1) offers a practical choice for solving Problem (1) when f is smooth. Importantly, at each iteration, TOS evaluates the gradient of f and the proximal operators of g and h only once. Moreover, composite problems with more than three functions can be reformulated as an instance of Problem (1) in a product-space and solved by using TOS. This is an effective method as long each function has an efficient gradient oracle or proximal operator (see Section 2).
Unfortunately, TOS is not readily applicable to many optimization problems that arise in machine learning. Most important among those are problems where only access to stochastic gradients is feasible, e.g., when performing large-scale empirical risk minimization and online learning. Moreover, prox-operators for some complex penalty functions are computationally expensive and it may be more efficient to instead use subgradients. For example, proximal operator for the maximum eigenvalue function that appears in dual-form semidefinite programs (e.g., see Section 6.1 in (Ding et al., 2019)) may require computing a full eigendecomposition. In contrast, we can form a subgradient by computing only the top eigenvector via power method or Lanczos algorithm.
Contributions. With the above motivation, this paper contributes three key extensions of TOS. We tackle nonsmoothness in Section 3 and stochasticity in Section 4. These two extensions enable us to use subgradients and stochastic gradients of f (see Section 2 for a comparison with related work), and satisfy a O (T) error bound in function value after T iterations. The third main contribution ADAPTOS in Section 5. This extension provides an adaptive step-size rule in the spirit of AdaGrad (Duchi et al., 2011; Levy, 2017) for an important subclass of Problem (1). Notably, for optimizing convex loss over the intersection of two convex sets, ADAPTOS ensures universal convergence rates. That is, ADAPTOS implicitly adapts to the unknown smoothness degree of the problem, and ensures a (LI/VI) convergence rate when the problem is nonsmooth but the rate improves to Ö(l/t) if the problem is smooth and solution lies in the relative interior of the feasible set.
In Section 6, we discuss empirical performance of our methods by comparing them against present established methods on various benchmark problems from COPT Library (Pedregosa et al., 2020) including the overlapping group lasso, total variation deblurring, and sparse and low-rank matrix recovery. We also test our methods on nonconvex optimization by training a neural network model. We present more experiments on isotonic regression and portfolio optimization in the supplements.
Notation. We denote a solution of Problem (1) by I. and Φ. == ((xx). The distance between point x E R" and closed and convex set 9 IR" is dist(r, 9) min ||æ yll: the projection of æ onto G is given by projg (x) ;= arg minyeg ||x- The prox-operator of a function
g: R" + RR U { {+oo} is defined by prox, := arg x (o(v) + åll 3 The indicator function of & gives for all x e ② and too otherwise. Clearly, the prox-operator of an indicator
function is the projection onto the corresponding set.
2 Background and related work
TOS, proposed recently by Davis & Yin (2017), can be seen as a generic extension of various operator splitting schemes, including the horward-backwatd splitting. Douglas-Rachiee Rachford splitting, splitting (Briceño-Ariat 2015), and the generalized splitting (Raguet et al., 2013). It covers these aforementioned approaches as special instances when the terms f.g and h in Problem (1) are chosen appropriately. Convergence of TOS is well studied when f has Lipschitz continuous gradients. It ensures (1/L)) convergence rate in this setting, see (Davis & Yin, 2017) 1) and (Pedregosa, 2016) for details.
Other related methods that can be used for Problem (1) when is smooth are the primal-dual hybrid gradient (PDHG) method (Condat, 2013; Vü, 2013) and the primal-dual three operator splitting methods in (Yan, 2018) 1) and (Salim et al., 2020). These methods can handle more general template where g or h is composed with a linear map, however, they require ff to be smooth. The convergence rate of PDHG is studied in (Chambolle & Pock, 2016).
Nonsmooth setting, We are unaware of any prior result that permits using subgradients TOS (or in other methods that can use the prox-operator of y and i separately for Problem (1)). The closest match is the proximal subgradient method which applies when & is removed from Problem (1), and is covered by nonsmooth TOS as special case.

---

Stochastic setting. There are multiple attempts to devise stochastic TOS in the literature. Yurtsever al. (2016) studied Problem (1) under the assumption that f smooth and strongly convex, and an unbiased gradient estimator with bounded variance is available. Their stochastic TOS has a guaranteed (1/tt) convergence rate. In (Cevher et al., 2018), they drop the strong convexity assumption, instead they assume that the variance is summable. They show asymptotic convergence with no guarantees on the rate. Later, Pedregosa et al. (2019) proposed a stochastic variance-reduced TOS and analyzed its non-asymptotic convergence guarantees. Their method gets (11/t) convergence rate when is smooth. The rate becomes linear if f is smooth and strongly convex and g (or h) is also smooth. Recently, Yurtsever et al. (2021) studied TOS problems where can be nonconvex and showed that the method finds a first-order stationary point with O /V) convergence rate under a diminishing variance assumption. They increase the batch size over the iterations to satisfy this assumption.
None of these prior works cover the broad template we consider: f is smooth or Lipschitz continuous and the stochastic first-order oracle has bounded variance. To our knowledge, our paper gives the first analysis for stochastic TOS without strong convexity assumption or variance reduction.
Other related methods are the stochastic PDHG in (Zhao & Cevher, 2018), the decoupling method in (Mishchenko & Richtárik, 2019), the stochastic primal-dual method in (Zhao al., 2019), and the stochastic primal-dual three operator splitting in (Salim et al., 2020). The method in (Zhao et al., 2019) can be viewed as an extension of stochastic ADMM (Ouyang et al.. 2013: Azadi & Sra, 2014) from the sum of two terms to three terms in the objective. Similar to the existing stochastic TOS variants, these methods either assume strong convexity or require veriance-reduction..
Adaptive step-sizes. The standard writings of TOS and PDHG require the knowledge of the smooth- ness constant of f for the step-size. Backtracking line-search strategies (for finding suitable step-size when the smoothness constant is unknown) are proposed for PDHG in (Malitsky & Pock, 2018) and for TOS in (Pedregosa & Gidel, 2018). These line-search strategies are significantly different than our adaptive learning rate. Importantly, these methods work only when f is smooth. They require extra function evaluations, and are thus not suitable for stochastic optimization. And their goal is to estimate the smoothness constant. In contrast, our goal is to design an algorithm that adapts to the unknown smoothness degree. Our method does not require function evaluations, and it can be used in smooth, nonsmooth, or stochastic settings.
At the heart of our method lie adaptive online learning algorithms (Duchi al., 2011; Sridharan, 2013) together with online to offline conversion techniques (Levy, 2017; Cutkosky, 2019). Similar methods appear in the literature for other problem templates with constraint a single constraint in (Levy, 2017; Levy et al., 2018; Kavis et al., 2019; Cutkosky, 2019; Bach & Levy, 2019). Our method extends these results optimization over the intersection of convex sets. When f is nonsmooth, ADAPTOS ensures a Ó(1/V)) VL) rate, whereas the rate improves to Ó(1(() if f is smooth and there is a solution in the relative interior of the feasible set.
Rakhlin &
TOS for more than three functions. TOS can be used for solving problems with more than three convex functions by product-space reformulation technique (Briceño-Ai Arias, 2015). Consider
min EER
(x))).
where each component dy IRd + RU [ is a proper, lower semicontinuous and convex function. Without loss of generality, suppose $1.... ..... , Op are prox-friendly. Then, can reformulate (2) in the product-space dR (p+1) as
min (xo, (++
(x:)) + Σ
(b( subject to 2o = I1 =
Tpp
(3)
i=p+1
This is an instance of Problem (1) with d (p 1) and = (zo, II.... I. ).). We choose g(x) as the indicator of the equality constraint, f(x) = Si @z( and h(x) = Σ (1,))) Then, the (sub)gradient of f is the sum of (sub)gradients of 0pt1..... dg: prox, is a mapping that averages To. Ii,..., Tpi and prox, is the concatenation of the individual prox-operators of Φ1. $1..... Óp.
To our knowledge, TOS has been studied only for problems with smooth S, and this forces us to assign all nonsmooth components Φ; in (2) to the proximal term h in (3). In this work, by enabling subgradient steps for nonsmooth f, we provide the flexibility to choose how to process each nonsmooth component d; in (3), either by its proximal operator through f or by its subgradient via f.
3

---

Algorithm Three Operator Splitting (TOS)
Input: Initial point yo IR.", step-size sequence (7x (>=)==
for ( -= 0, 0, 2,.,..... , do
2t = --proox,. (3t))
Choose an update direction un E R=
[ue V (ze) captures the standard version of TOS)
2y = proxx (2zz - yt (
Mr+1 = Zt + 2₁
end for
Return: Ergodic sequence v, and ā, defined in (5)
3 TOS for Nonsmooth Setting
Algorithm presents the generalized TOS for Problem (1). recovers the standard version in (Davis & Yin, 2017) if we choose u, = (=x) when / is smooth. For convenience, we define the mapping TOS, (y, u) == y g
(v) + prox,,A (2 prox (3) y yu)
(4)
which represents one iteration of Algorithm 1.
The first step of the analysis is the fixed-point characterization of TOS. The following lemma is a straightforward extension of Lemma 2.2 in (Davis & Yin, 2017) to permit subgradients. The proof is similar to (Davis & Yin, 2017), we present it in the supplementary material for completeness.
Lemma (Fixed points of TOS). Let y > 0. Then, there exists a subgradient u E 0f (prox. (v)) that satisfies TOS, u) if and only if prox..g (t) is solution of Problem (1).
When smoothh, with 4n f2)) is known be an averaged operator' if E (0. Lg)) (see Proposition 2.1 in (Davis & Yin, 2017)) and the analysis in prior work is based on this property. In particular, averagedness implies Fejér monotonicity, i.e., that 11y. y-ll is non-increasing, where y+ denotes fixed point of TOS. However, when i' nonsmooth and is replaced with subgradient, TOS operator is no longer averaged and the standard analysis fails. One of our key observations that l/ye y+1 remains bounded even-though we loose averagedness and Fejér monotonicity in this setting, see Theorem S.6 in the supplements.
Ergodic sequence. Convergence of operator splitting methods are often given in terms of ergodic (averaged) sequences. This strategy requires maintaining the running averages of 2 and Zy.
and
(5)
T=0
Clearly, we do not need to store the history of I, and 2, to maintain these sequences. In practice, the last iterate often converges faster than the ergodic sequence. We can evaluate the objective function at both points and return the one with the smaller value.
We are ready to present convergence guarantees of TOS for the nonsmooth setting. Theorem 1. Consider Problem (1) and employ TOS (Algorithm 1) with the update directions and step-size chosen
70
Ut E 0f(z) and 7tt VT for some "/o > 0, for = 0, 1,.....,7
(6)
Assume that ||uil| $ G for all t. Then, the following guarantees hold:
(De
D
f(Er) g(Er) + h(Tr) 0. S 2T+II %
+ 7007
(7)
2
and | - 2T| < T +1
(D+r00y)) where D = max
xx xx11:11u0 1=l1).
(8)
An operator T _ + Rn is w-avergeed if Te - Tyll s || yll 1- [1x Tx) (y Ty)1 for
E (0, 1) for all 2, R..

---

Remark 1. The boundedness of subgradients is standard assumption in nonsmooth optimization. is equivalent assuming that is --ipschittz contimuous on dom(g).
If D and Gy are known, we can optimize the constants in (7) by choosing "o D/Gy. This gives f(zr) + ((rr) + h(zr) - Φ. z ((D)) and [r žrll & (DD/T).
Proof sketch. We start by writing the optimality conditions for the proximal steps for 2 and 2t- Through algebraic modifications and by using convexity of f. and h. we obtain
f(z)) + g(2)) + h(x)) - o.
1 2
11:
=.
2 Ilu++1 11l1+11-xx11 =.11 2 + 2 211u
(9)
||u || S. Gy by assumption. Then, we average this inequality over t = 0, ,,, T and use Jensen's inequality get (7).
The bound in (8) is an immediate consequence the boundedness of ||r+1 y. that we show in Theorem S.6 in the supplementary material:
||ut+1
y.ll S | y~ll + 270Gr..
(10)
By definition, ||- žr| + +luT++1 - woll S + (1lu++1 v~ll
11le voll). l).
Theorem does not immediately yield convergence to solution of Problem (1) because f + and are evaluated at different points in (7). Next corollary solves this issue.
Corollary 1. We are interested in two particular cases of Theorem 1: (i). Suppose Gi-Lipschttz continuous. Then,
D2
2Gh (D+ mG
((T)) -b+ 2
10G9
+
(11)
(ii). Suppose h is the indicator function of a convex set H C R". Then,
1
D2
f(2r) + g(Zr) - 0. -
+1007
(12)
2 +
70
2
and dist(ET, H) S +
(D + m0G
(13)
Proof. (i). Since h Gip-iihhh d(2)) S f(rr) + g(rr) + h(TT) + GnlleT - Er|1-
(ii). h(āT) = since ãr E H. Moreover, dist(Er, H) == infach h || xll S | Zr||-
Remark 2. We fix time horizon for the ease of analysis and presentation. practice, we use Tt -
Theorem covers the case in which is the indicator of a convex set G RR. By definition, žτ E G and x. E G. hence g(ăr) = g(x.) = 0. If both g and are indicator functions, TOS gives an approximately feasible solution, in G. and close to H. We can also consider a stronger notion of approximate feasibility, measured by dist(Er, & n H). However, this requires additional regularity assumptions on G and H. to avoid pathological examples, see Lemma in (Hoffmann, 1992) and Definition 2 in (Kundu et al., 2018).
Problem (1) captures unconstrained minimization problems when h = 0. Therefore, the convergence rate in Theorem optimal in the sense that matches the information theoretical lower bounds for first-order black-box methods, see Section 3.2.1 in (Nesterov, 2003). Remark that the subgradient method can achieve ((1/t) rate when f is strongly convex. We leave the analysis of TOS for strongly convex nonsmooth as open problem.
5

---

4 TOS for Stochastic Setting
In this section, we focus on the three-composite stochastic optimization template:
min RER
=(x)= fx) g(x) + h(x) where f(x) := Exf(x
(14)
and is random variable. The following theorem characterizes the convergence rate of Algorithm 1 for Problem (14).
Theorem 2. Consider Problem (14) and employ TOS (Algorithm with a fixed step-size Yt = 7 70/ + for some Yoo > O. Suppose we are receiving the update directions un from an unbiased stochastic first-order oracle with bounded variance, i.e.,
út = E [u E (f{))) and El[lu - àn = < for some a < +oc.
(15)
Assume that ||ū l1 S G for all t. Then, the following guarantees hold:
(De
[[) + ((T)) + M(TT)) 0+ S 2/T (70 + + and
(16)
2 ElllT ærill - T+1 ( (G,+g)) where = max - x.11, 11y0 - vall3. (17)
Remark 3. Similar rate guarantees hold with some restrictions on the choice of to we replace bounded subgradients assumption with the smoothness of f. We defer details to the supplements.
If we can estimate D, f and then can optimize the bounds by choosing To D max max OG This gives f(žr) - (अT) + h(āT) - 6. S ODD max{Gr: /// //VT)) and - - žr| S ODD/T).
Analogous to Corollary 1, from Theorem we derive convergence guarantees when h is Lipschitz continuous or an indicator function. As in the nonsmooth setting, the rates shown in this section are optimal because Problem (14) covers ((x) h(x) 0 special case.
5 TOS with Adaptive Learning Rates
In this section, we focus on an important subclass of Problem (1) where g and are indicator functions of some closed and convex sets:
min
f(x) subject to x E n...
(18)
#ER
TOS is effective for Problem (18) when projections onto and H are easy but the projection onto their intersection is challenging. Particular examples include transportation polytopes, doubly nonnegative matrices, and isotonic regression, among many others.
We propose ADAPTOS with an adaptive step-size in the spirit of adaptive online learning algorithms and online to batch conversion techniques, see (Duchi et al., 2011; Rakhlin Sridharan, 2013; Levy, 2017: Levy et al., 2018; Cutkosky, 2019; Kavis et al., 2019; Bach & Levy, 2019) and the references therein. ADAPTOS employs the following step-size rule:
a
n
for some 3 > 0.
(19)
BB Σ |1
9 in the denominator prevents to become undefined. = Ilvo -x, and Gy are known, theory suggests choosing = D) and 3 = G? for a tight upper bound, however, this choice affects only the constants and not the rate convergence as we demonstrate in the rest of this section. Importantly, do not assume any prior knowledge on D Gy. In practice, often discard 3 and use % at the first iteration.
For ADAPTOS, in addition to (5), we will also use a second ergodic sequence with weighted averaging:
By
and
1ة =
(20)
ΣT=
7T
T=0
Σt=
TT
This sequence was also considered for TOS with line-search in (Pedregosa & Gidel, 2018).

---

Theorem 3. Consider Problem (18) and TOS (Algorithm 1) with the update directions E (z()) and the adaptive step-size (19). Assume that ||ulll S y for all Then, the estimates generated by TOS satisfy
- -
D2 v++1 da2
2aG,
+1+ G/ ) and
(21)
(2s H) 06
Vt++1 ( (1+ v3)) ) where D == 1190 x.ll-
2a
(22)
If D and Gy are known, we can choose a = D and 3 = G3. This gives f(2)) - f f. and (2, H) O(D/Vt).
The next theorem establishes a faster rate for the same algorithm when f smooth and a solution lies in the interior of the feasible set.
Theorem 4. Consider Problem (18) and suppose I is Lyysmooth on G. Use TOS (Algorithm 1) with the update directions u, = v f(2)) and the adaptive step-size (19), Assume that ||wel| S G for all t. Suppose Problem (18) has solution in the interior of the feasible set. Then, the estimates generated by TOS satisfy
f(z)) f. So (
2
+1+ -) +av
D2 + +1+ +)))
(a
Ly
and (23)
t++
dist(2,, H) < 0 2x D +1+ ) where D = =1190- - x+11- -x+11
(24)
t+1
If D and G are known, This gives f(2)) f. s D +
choose D and 8 G7.
D)/) and dist(z H) - Ō(D/t).
Remark 4. When f is smooth, the boundedness assumption ||ue| S Gy holds automatically with G5 S Dy if has bounded diameter Dg.
We believe the assumption on the location of the solution is a limitation of the analysis and that the method can achieve fast rates when is smooth regardless of where the solution lies. Remark that this assumption also appears in (Levy, 2017; Levy et al., 2018).
Following the definition in (Nesterov, 2015), we say that an algorithm is universal it does not require to know whether the objective smooth not yet it implicitly adapts to the smoothness of the objective. ADAPTOS attains universal convergence rates for Problem (18). It converges to solution with (L)V/t rate (in function value) when is nonsmooth. The rate becomes O(Ltt) if is smooth and the solution is in the interior of the feasible set.
Finally, the next theorem shows that ADAPTOS
successfully handle stochastic (sub)gradients.
Theorem 5. Consider Problem (18). Use TOS (Algorithm 1) with the update directions un from an unbiased stochastic subgradient oracle such that B[u,) 2 02(2) almost surely. Assume that l|uell < G5 for all I. Suppose Problem (18) has solution in the interior of the feusible set. Then, the estimates generated by TOS satisfy
2aG, (D² +1+ ++)) and vt+I 1aa
E E[f(2) f.]
(25)
E(dist(E, H)] S Ō 2a D +1+ ())) where D 1130 x.Il-
(26)
t+1
1++100
6 Numerical Experiments
This section demonstrates empirical performance of the proposed method on a number of convex optimization problems. We also present an experiment on neural networks. Our experiments are performed in Python 3.7 with Intel Core 19-9820X CPU @ 3.30GHz. We present more experiments on isotonic regression and portfolio optimization in the supplementary materials. The source code for the experiments is available in the supplements.
7

---

6.1 Experiments on Convex Optimization with Smooth
In this subsection, we compare ADAPTOS with TOS, PDHG and their line-search variants TOS-LS and PDHG-LS. Our experiments are based on the benchmarks described in (Pedregosa & Gidel, 2018) and their source code available COPT Library (Pedregosa et al., 2020) under the new BSD License. We implement ADAPTOS and investigate its performance on three different problems:
Logistic regression with overlapping group lasso penalty:
N
min JER
log(1 + exp( x)). x))) + N
E GEG
VIG +
EVHl MEH
(27)
where {(11, by)..... ............ (aN; by is given set of training examples, 9 and H. are the sets of distinet groups and |. denotes the cardinality. The model we use (from COPT) considers groups of size 10 with 2 overlapping coefficients. In this experiment, we the benchmarks on synthetic data (dimensions n 1002, N = 100) and real-sim dataset (Chang & Lin, 2011) 1) (n = 20958, N 72309).
p Image recovery with total variation penalty:
m-1
min X km
A(X)IE + A E X15+1 - X X
+
Σ
X - -ogb (28)
where is given blurred image and A : _=xx + R is a linear operator (blur kernel). The benchmark in COPT solves this problem for an image of size 153 x 115 with provided blur kernll.
> Sparse and low-rank matrix recovery via l and muclear- regularizations:
N
min X
huber(b; - (A;, + X|| + A||XI|1-
(29)
N
We use huber loss. bi),, (AN, bx)} } is a given set of measurements and |||] is the vector -n-rrmm of X. The benchmark in COPT considers a symmetric ground truth matrix X E 20x00 and noisy synthetic measurements (N 100) where A; has Gaussian iid entries. = (A, X²) + w; where is generated from a zero-mean unit variance Gaussian distribution.
At each problem, we consider two different values for the regularization parameter A. We use all methods with their default parameters in the benchmark. For ADAPTOS, we discard |3 and tune a by trying the powers of 10. See the supplementary material for the behavior of the algorithm with different values of a. Figure shows the results this experiment. In most cases, the performance of AAAPTOS is between TOS-LS and PDHG-LS. Remark that TOS-LS is using the extra knowledge of the Lipschitz constant of h.
6.2 Experiments on Convex Optimization with Nonsmooth f
We examine the empirical performance of ADAPTOs for nonsmooth problems on an image impainting and denoising task from (Zeng & So, 2018; Yurtsever et al., 2018). 8). We are given an occluded image (i.e., missing some pixels) of size 517 x 493, contaminated with salt and pepper noise of 10% density. We use the following template where data fitting is measured in terms of vector -n-nrm::
min BERWX
||A(X) - Yllp subject to
|| X, X
(30)
where is the observed noisy image with missing pixels. This is essentially a matrix completion problem, A _ - mx* is linear map that samples the observed pixels in Y. In particular, we consider (30) with p = 1 and p = 2. The fosloss is common in practice for matrix completion (often in the least-squares form) but it is not robust against the outliers induced by the salt and pepper noise. -oss is known to be more reliable for this task.
The subgradients in both cases have fixed norm at all points (note that the subgradients are binary valued for & loss and unit-norm for Eg-loss), hence the analytical and the adaptive step-sizes are same up to a constant factor.
8

---

Figure 2 shows the results. The empirical rates for 1 roughly match our guarantees in Theorem 1. We observe locally linear convergence rate when Ez-loss is used. Interestingly, the ergodic sequence converges faster than the last iterate for 1 but significantly slower for p = 2. The runtime of the two settings are approximately the same, with 67 msec per iteration on average. Despite the slower rates, we found fllosss more practical on this problem. A low-accuracy solution obtained by 1000 iterations on & flosss yields high quality recovery with PSNR 26.21 dB, whereas the PSNR saturates at 21.15 dB for the fz-formulation. See the supplements for the recovered images and more details.
6.3 An Experiment on Neural Networks
In this section, we train a regularized deep neural network to test our methods on nonconvex optimization. We consider regularized neural network problem formulation in (Scardapane et al., 2017). This problem involves a fully connected neural network with the standard cross-entropy loss function, ReLu activation for the hidden layers, and the softmax activation for the output layer. Two regularizers are added to this loss function: The first one is the standard l regularizer, and the second the group sparse regularizer where the outgoing connections of each neuron is considered as a group. The goal is to force all outgoing connections from the same neurons to be simultancously zero, so that we can safely remove the neurons from the network. This is shown as an effective way to obtain compact networks (Scardapane et al., 2017), which is crucial for the deployment of the learned parameters on resource-constraing devices such as smartphones (Blalock et al., 2020).
We reuse the open source implementation (built with Lasagne framework based on Theano) published in (Scardapane et al., 2017) under BSD-2 License. We follow their experimental setup and instructions with MNIST database (LeCun, 1998) containing 70k grayscale images (28 x 28) of handwritten digits (split 75/25 into train and test partitions). We train a fully connected neural network with 784 input features, three hidden layers (400 /30/ 100) and 10 10-dimensional output layer. Interested readers can find more details on the implementation in the supplementary material or in (Scardapane et al., 2017).
Scardapane et al. (2017) use SGD and Adam with the subgradient of the overall objective. In contrast, methods can leverage the prox-operators for the regularizers. Figure 3 compares the performance in terms of two measures: the sparsity of the parameters and the accuracy. On the left side, we see the spectrum of weight and neuron magnitudes. The advantage of using prox-operators is outstanding: More than 93% of the weights are zero and 68% of neurons are inactive when trained with ADAPTOS. In contrast, subgradient based methods can achieve only approximately sparse solutions.
The third and the fourth subplots present the training and test accuracies. Remarkably, ADAPTOS performs better than the state-of-the-arr (both in train and test). Unfortunately, we could not achieve the same performance gain in preliminary experiments with more complex models like ResNet (He et al., 2016), where SGD with momentum shines. Interested readers can find the code for these preliminary experiments in the supplements. We leave the technical analysis and a comprehensive examination of ADAPTOS for nonconvex problems to future work.
7 Conclusions
We studied an extension of TOS that permits subgradients and stochastic gradients instead of the gradient step and established convergence guarantees for this extension. Moreover, we proposed an adaptive step-size rule (ADAPTOs)) for the minimization of a convex function over the intersection of two convex sets. ADAPTOS guarantees a nearly optimal ((1/Vt) rate on the baseline setting, and it enjoys the faster ((1/t) rate when the problem is smooth and the solution in the interior of feasible set. We present numerical experiments on various benchmark problems. The empirical performance of the method is promising.
We conclude with short list of open questions and follow-up directions: (i) In parallel to the subgradient method, we believe TOS can achieve ((1/t) rate guarantees in the nonsmooth setting if f is strongly convex. The analysis remains open. (ii) The faster rate for ADAPTOS on smooth requires an extra assumption on the location of the solution. We believe this assumption can be removed, and leave this as an open problem. (iii) We analyzed ADAPTOS only for a specific subclass of Problem (1) in which and are indicator functions. Extending this result for the whole class is valuable question for future study.

---

OG Lasso Synth. (A 30
OG Lesso Synth. (A - 10
0G Lasso roaldita (A - 10-1)
OG Lasso roal-ain (A - 10"2)
10
10
abjective sbopttinaiigg
10-3
109
100
10F
10
10-5
10-5
10"4
10
10
10
10-4
10t4
10"
10.7
10"
10-14
10
10
10
20
1.25
25
3.75
75
150
225
330
150
300
Sparse mank (A 10-1)
Spare low-rank (A- 10
Total varlation (A 10
variation (A )
109
10
10
10
abjective mbboptinaligy
10
10
10r4
10
10
10"
10-4
10
10-4
10-
10
10
10a
10
10-10
10-11
20
10111
10-15
10-15
155
30
15
60
0
2.5
7.5
10
0
25
50
75
100
25
50
75
100
Cime (wec)
(see)
Sinee (see)
Sime (see)
Figure/ 1: Empirical comparison of algorithms for Problem (1) with smooth f. Dashed lines represent the line-search variants of TOS and PDHG. The performance of ADAPTOS is between TOS-LS and PDHG-LS. TOS and PDHG require the knowledge of the smoothness constant, and TOS-LS uses the Lipschitz constant for one of the nonsmooth terms.
4 Jloss
E: Joss
Eg Jlsss
Jaass
abjective saboptimmiity
167
objective suboptimaiitt
10-2
109
infeasiilltty
10
Infeasibility
10-2
10
10
10-1_
10-4
30
10-1
10:
10-1
Ergudic
10
10
10:7
20
10F
10
107
107
100
109
30
10a
10
10'
10F
10
Noeation
Iteration
Isceation
Iteration
Figure 2: Performance of ADAPTOS on image impainting and denoising problems with é, and loss functions. The empirical rates for loss match the guaranteed (11/Vl) rate in objective suboptimality and (1/tt) in infeasibility. We observe a locally linear convergence rate for the lo-loss.
0.98
10
magnitude group
10-3
magaiiauii of seeigitt
10
training sccurasy
0.59
validation acouracc
00.97
0.98
10.0
10:9
SGD
0.97
11.96
10-2
10"7
AdaCraa Adam
0.96
10
10-12
TOS
0.95
0.96
Adap/OOS
10-15
10-13
0.94
0.94
3.2
0.4
0.6
0
0.2
0.4
0.6
100
200
300
500
100
200
300
400
500
groups (ordered)
wrights (ardered)
epoch
epoch
Figure 3: Comparison of methods on training neural networks with group lasso regularization. The outgoing connections of each neuron form group. The first plot shows the magnitude of weights after 500 epochs. The second plot shows the absolute sum of outgoing weights from each neuron. x-axes are normalized by the total number of weights and neurons these plots. More than 68% of the neurons are inactive on the network trained by ADAPTOS. The third and fourth plots show the training and validation losses. This experiment is performed with 20 random seeds. The solid lines show the average performance and the shaded area represents + standard deviation from the mean.
10

---

Acknowledgements
The authors would like to thank Ahmet Alacaoglu for carefully reading and reporting an error in the preprint of this paper.
Alp Yurtsever received support from the Swiss National Science Foundation Early Postdoc.Mobility Moobility Fellowship P2ELP2_I 2JEL22_187955, from the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation, and partial postdoctoral support from the NSF-CAREER grant LIS-1846088 Suvrit Sra acknowledges support from an NSF BIGDATA grant (1741341) and an NSF CAREER grant (1846088).
References
Azadi, S. and Sra, S. Towards an optimal stochastic alternating direction method of multipliers. In International Conference on Machine Learning. pp. 620-628. 628. PMLR, 2014.
Bach, F. and Levy, K. Y. A universal algorithm for variational inequalities adaptive to smoothness and noise. In Conference on Learning Theory, pp. 164-194. PMLR, 2019.
Barbero, A. and Sra, S. Modular proximal optimization for multidimensional total variiaiit regular- ization. The Journal of Machine Learning Research, 19(1):2232 2313, 2018.
Bauschke, H. H., Combettes, P. L., et al. Convex analysis and monotone operator theory in Hilbert spaces, volume 408. Springer, 2011.
Blalock, D., Ortiz, J. J. G., Frankle, J., and Guttag, J. What the state of neural network pruning? arXiv preprint arXiv:2003.030333 2020.
Briceño-Arias, L. M. Forward-douglas rachford rachhfro splitting and forward-partial inverse method for solving monotone inclusions. Optimization, 64(5):1239-126) 2015.
Cevher, V., Vū, B. C., and Yurtsever, A. Stochastic forward douglas-rachford splitting method for monotone inclusions. Large-Scale and Distributed Optimization, pp. 149-179. Springer, 2018.
Chambolle, A. and Pock, T. On the ergodic convergence rates of first-order primal-dual algorithm. Mathematical Programming, 159(1):253-285 2016.
Chang, C.-C. and Lin, C.-J. Libsvm: library for support vector machines. ACM Iransactions on intelligent systems and technology (TIST), 2(3):1-27, 2011.
Condat, L. A primal-dual splitting method for convex optimization involving lipschitzian, proximable and linear composite terms. Journal of optimization theory and applications, 158(2):460-479 2013.
Cutkosky, A. Anytime online-to-batch, optimism and acceleration. International Conference on Machine Learning, pp. 1446-14544 PMLR, 2019.
Davis, D. and Yin, W. A three-operator splitting scheme and its optimization applications. Set-valued and variational analysis, 25(4):829-88 8588 2017.
Ding, L., Yurtsever, A., Cevher, V., Tropp. J. A., and Udell, M. An optimal-storage approach to semidefinite programming using approximate complementarity. arXiv preprint arXiv: 2019.
Duchi, J., Hazan, E., and Singer, Y. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
El Halabi, M. and Cevher, V. A totally unimodular view of structured sparsity. In Artificial Intelligence and Statistics, pp. 223-231. PMLR, 2015.
Glorot, X. and Bengio, Y. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256 JMLR Workshop and Conference Proceedings, 2010.

---

Glorot, X., Bordes, A., and Bengio. fourteenth international conference on artificial intelligence and statistics, pp. 315-323. JMLR Workshop and Conference Proceedings, 2011.
Y. Deep sparse rectifier neural networks. In Proceedings of the
Grant, M. and Boyd, S. CVX: Matlab software for disciplined convex programming, version 2.1, 2014.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Higham, N. J. and Strabié, N. Anderson acceleration of the alternating projections method for computing the nearest correlation matrix. Numerical Algorithms, 72(4):1021-1044 2016.
Hoffmann, A. The distance to the intersection of two convex sets expressed by the distances to each of them. Mathematische Nachrichten, 157(1):81 1992.
Kavis, A., Levy, K. Y., Bach, F., and Cevher, V. Unixgrad: A universal, adaptive algorithm with optimal guarantees for constrained optimization. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, 2019.
Kundu, A., Bach, F., and Bhattacharya, C. Convex optimization over intersection of simple sets: improved convergence rate guarantees via exact penalty approach. In International Conference on Artificial Intelligence and Statistics, pp. 958-967. PMLR, 2018.
LeCun, Y. The mnist database of handwritten digits. http://yanm. lecun. com/exdb/nnistl, 1998.
Levy, K. Y. Online to offiin conversions, universality and adaptive minibatch sizes. Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017.
Levy, K. Y., Yurtsever, A., and Cevher, Online adaptive methods, universality and acceleration. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018.
Lewis, D. D., Yang, Y., Russell-Rose, T., and Li, F. Revl: A new benchmark collection for text categorization research. Journal of machine learning research, 5(Apr):361-397, 2004.
Malitsky, Y. and Pock, T. A first-order primal-dual algorithm with linesearch. SIAM Journal Optimization, 28(1):411-435 2018.
Mishchenko, K. and Richtárik, P. A stochastic decoupling method for minimizing the sum of smooth and non-smooth functions. arXiv preprint arXiv: /905. /153, 2019.
Nesterov, Y. Introductory lectures on convex optimization: basic course, volume 87, Springer Science & Business Media, 2003.
Nesterov, Y. Universal gradient methods for convex optimization problems. Mathematical Program- ming, 152(1):381 404, 2015.
Ouyang, H., He, N., Tran, L., and Gray, A. Stochastic alternating direction method of multipliers. In International Conference Machine Learning, pp. 80-88. PMLR, 2013.
Pedregosa, F. On the convergence rate of the three operator splitting scheme. arXiv preprint arXiv:1610.07830, 2016.
Pedregosa, F. and Gidel, G. Adaptive three operator splitting. In International Conference on Machine Learning, pp. 4085-4094, 2018.
Pedregosa, F., Fatras, K., and Casotto, M. Proximal splitting meets variance reduction. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1-10. PMLR, 2019.
Pedregosa, F., Negiar, G., and Dresdner, G. copt: composite optimization in python. 2020. doi: 10.5281/zenodds 283333. URL http://openo pttptp//.t//pp....o.mm
Raguet, H., Fadili, J., and Peyré, G. A generalized forward-backwerr splitting. SIAM Journal on Imaging Sciences, ((3):1199-11) 2013.
12

---

Rakhlin, A. and Sridharan, K. Optimization, learning, and games with predictable sequences. In Proceedings of the 26th International Conference on Neural Information Processing Systems- Volume 2, pp. 3066-3074, 2013.
Salim, A., Condat, L., Mishchenko, K., and Richtárik, P. Dualize, split, randomize: Fast nonsmooth optimization algorithms. arXiv preprint arXiv:2004.0260 02635, 2020.
Scardapane, Comminiello, D., Hussain, A., and Uncini, A. Group sparse regularization for deep neural networks. Neurocomputing, 241:81 1-81889,, 2017.
Shivanna, R., Chatterjee, B., Sankaran, R., Bhattacharyya, C., and Bach, F. Spectral norm regular-
ization of orthonormal representations for graph transduction, In Neural Information Processing Systems, 2015.
Tibshirani, R. J., Hoefling, H.,, and Tibshirani, R. Nearly-isotonic regression. Technometrics, 53(1): 54 61, 2011.
Toh, K.-C., Todd, J., and Tütüncü, R. H. SDPT3-a MATLAB software package for semidefinite programming, version 1.3. Optimization methods and software, 11(1-4):545-581, 1999.
Vū, B. C. splitting algorithm for dual monotone inclusions involving cocoercive operators. Advances in Computational Mathematics, 38(3):667-681, 2013.
Yan, M. A new primal-dua algorithm for minimizing the sum of three functions with a linear operator. Journal of Scientific Computing, 76(3):1698-177 2018.
Yuan, L., Liu, J., and Ye, J. Efficient methods for overlapping group lasso. Advances neural information processing systems, 24:352-360, 2011.
Yuan, M. and Lin, Y. Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 68(1):49-6) 2006.
Yurtsever, A., Vū, B. C., and Cevher, V. Stochastic three-composite convex minimization. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pp. 4329-4337, 2016.
Yurtsever, A., Fercoq, O., Locatello, F., and Cevher, V. A conditional gradient framework for composite convex minimization with applications to semidefinite programming. In International Conference Machine Learning, pp. 5727-5736. PMLR, 2018.
Yurtsever, A., Mangalick, V., and Sra, S. Three operator splitting with nonconvex loss function. In International Conference on Machine Learning, pp. 12267-12277. PMLR, 2021.
Zeng, W.-J. and So, H. C. Outlier-robust matrix completion via f, my-miiimization. IEEE Trans. on Sig. Process, 66(5): 120, 2018
Zhao, R. and Cevher, V. Stochastic three-composite convex minimization with linear operator. In International Conference on Artificial Intelligence and Statistics, pp. 765-774. PMLR, 2018.
Zhao. R., Haskell, W. B., and Tan, V. Y. An optimal algorithm for stochastic composite optimization. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. PMIR, 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We explicitly state limitations of our methods and its analysis in multiple places in the paper.
(c) Did you discuss any potential negative societal impacts of your work? [No] We present a new convex optimization technique and its technical analysis, we do not expect any
direct societal impact.
13

---

(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We listed our assumptions the beginning of each Theorem.
(b) Did you include complete proofs of all theoretical results? [Yes] In the supplementary material.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or as URL)? [Yes] In the supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Some details are deferred to the supplementary material.
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [Yes] We report error bars for experiments neural networks. Or other experiments are on convex and deterministic problems which do involve any randomness.
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes] In the beginning of Section 5.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as URL? [Yes]
We implemented the proposed methods for the openopt/copt Python library.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes] We used standard benchmark datasets with citation synthetic data.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [No] The datasets we use do not contain any personal information to the best of our knowledge.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "wlnFPcw82YG", "reviewer": "Reviewer_eqKr", "summary": "The paper considers three extension of the three operator splitting (TOS) algorithm: sub-gradient instead of gradient, stochastic  gradient and adaptive step-sizes. Convergence rates are established for each extension. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "First of all, the paper missed a recent work “Three Operator Splitting with a Nonconvex Loss Function, A. Yurtsever et al 2021’’ which studied TOS in the non-convex setting and with stochastic gradient. For example, problem of type (15) was studied in this work.\n\nDue to the above missing reference, the main strength of the paper is TOS with sub-gradient. However the proposed algorithm is not what I expected when reading lines 34-36 of the introduction. It appears to me that the authors would replace the computation of one prox-operator with sub-gradient descent. However, the proposed algorithm still needs computing two prox-operators, and gradient descent part is relaxed. \n\nThe convergence results of the paper match existing result of sub-gradient descent and stochastic gradient.\n\nThe proposed AdapTOS is difficult to understand, as the step-size is motivated by adaptive stochastic gradient method, and there is no randomness here.  For problem (27) considered in the numerical experiments, it would be great if the authors comparing the proposed with other methods where no sub-gradient descent, such as ADMM type methods or Primal-Dual splitting. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above for limitations and no negative societal impact.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "oA3V3vUU3Rp", "reviewer": "Reviewer_ofGn", "summary": "This paper proposes to extend the three operator splitting (TOS) algorithm via stochastic gradients, subgradients and adaptive step-sizes respectively. Convergence rates and numerical experiments of these extensions are provided. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "Originality: \n\nThe application of subgradients in a TOS scheme seems to be original to me. The use of stochastic gradients in a TOS scheme is well mentioned in Section 2 of the paper. \n\n\nQuality and significance: \n\nThe quality of this paper is above average. I also believe that the proposed extensions are significant to study. \n\n\nClarity: \n\nI think some statements in the paper require clarifications as they are misleading. For instance, in the abstract, point (ii) has led me to think that the authors are going to replace the functions which we evaluate their proximity operators on (i.e., $g$ and $h$) by their subgradients. But after looking into the paper, the authors are replacing $\\nabla f$ by $\\partial f$ instead, where the smooth function $f$ in the original TOS becomes nonsmooth. The subsection titles of numerical experiments are also misleading: these problems are also nonsmooth because of the nonsmooth regularizers. \n\nTypos: \n* Line 16: $\\mathbb{R}\\cup\\lbrace +\\infty\\rbrace$ instead of $\\mathbb{R}\\cap\\lbrace +\\infty\\rbrace$ \n* Line 120: *splitting* instead of slitting\n* Line 143: redundant *an*\n* Line 233: $X$ instead of X\n* Line 284: 93% instead of %93 \n\n**Post-rebuttal:** \nI have read the author response and decided to keep my evaluation unchanged, given that the authors agree to clarify the misleading notions in the original manuscript. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "While the author have discussed the limitations of their work, I do expect numerical experiments to illustrate the theoretical results in Section 5. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "nrKoBn9IDw", "reviewer": "Reviewer_fPkS", "summary": "This paper provides an extension of the Three Operator Splitting methods for composite optimization, of the form $f + g + h$. Previous work assumed $f$ to be smooth. This work tackles two cases: 1) the case where $f$ is non-smooth, and the case where additionally, only a stochastic estimator of the (sub)gradient of $f$ is available. It can be seen as an extension of (Yurtsever et al 2018) in the non-smooth, non-strongly convex case.\nThe paper provides a theoretical worst-case analysis of convergence, and gives non-asymptotic rates for these two cases. It also proposes an analyses an adaptive variant, where step size depends on the previous observed subgradient magnitudes, a la AdaGrad. It provides experimental validation of the method on a non-smooth problem, and on a non-convex non-smooth problem.", "questions": "", "limitations": "", "rating": 7, "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 clear and well written. Extensions of the TOS method in the non-smooth setting should be interesting to the community.\n\nAdditional experiments in the 1st setting (robust recovery) in the stochastic setting (large images + subsampling pixels to compute the [sub]gradients) would be interesting to evaluate scalability of the stochastic method vs non-stochastic.\n\nQuestion on the Image recovery experiment: I see in the code that the loss is not the squared loss for the L2 case. Why is that? Since the squared L2 is strongly convex, and the two problems are equivalent, the squared loss would always be used in practice. Also, it allows to avoid numerical instability due to dividing by the norm of $\\mathcal A(x) - y$. \n\nQuestion on ResNet experiments: what sparsity structure did you try to enforce in your preliminary experiments ? Using individual convolutional filters as groups for the group LASSO (and not penalizing/regularizing the fully connected layer) may be beneficial in this context. Also, keeping some type of L2 regularization (weight decay) should also be helpful. I would be greatly interested in these results.\n\nThe latest commit on Lasagne was in 2015... Perhaps consider writing the AdapTOS optimizer in PyTorch, Jax or Tensorflow to promote its usage, and reproducibility?\n\nComments on the form:\nTypo: line 115 unnecessary \"a\" \nTypo: line 202: we believe this to be a limitation...", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "ho1wo4Ftvxj", "reviewer": "Reviewer_7qvs", "summary": "In this paper, the authors analyze a variant of the classical three operator splitting algorithm where the smooth gradient (or co-coercive operator) is replaced by a subgradient (which is only a  monotone operator). This enables the minimization of the sum of three functions, two of which have explicit proximity operators and one is accessed through a subgradient. ", "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": "First of all, I would say that the main reason this case has not been covered previously is that with a subgradient, the TOS operator (ie (2) with u as in Lemma 1) is no longer firmly non-expansive which means that most of the usual operator theory for (Fejér monotonous) iterates convergence breaks down. If my intuition is correct maybe a sentence about that would be interesting for the reader.\n\n* I understand the need to have a generic u_t in algorithm 1 but could you give the reader the intuition that it should be a gradient of f (in original TOS) or something related (maybe as a comment).\n\n* In the proof of Lemma 1, you need Assumption 1 (for S.3 to hold) but it is not explicitly put in the lemma or the other theorems. Should this be a blanket assumption? (eg. in Theorem 1, you will need Lemma 1 but only assumption is put explicitly)\n\n\n* I am a bit troubled by the formulation of Lemma 1 since TOS is not R^n to R^n but takes two values. Replacing u directly by its (set-)value and consider the resulting set-valued operator would be in line with standard monotone operator theory. (and the fact that it may not be single valued would show the difference with the usual case).\n\n* I find Theorem 1 slightly deceiving as x_T is present in h while z_T is present in the other, I would be nice to have a warning. It would also be nice to have a sketch of the proof. Basically, I think that Supp. C builds on operator theory to get boundedness which is the only possible out come without smothness of the gradient and then in D, you explicitly use the functions to get a functional convergence.\n\n* I also missed at first read that the adaptive part only focused on indicator functions, maybe the first sentence of Sec 5 should be emphasized. Also, what are the technical limitations that prevent from considering proximity operators there?\n\n* In the numerical experiments, I am a bit dubious about the the smooth case of Figure 1. You use AdapTOS for smooth problems (except the sparse low-rank) which is outside of the theoretical framework right? Also, the LS version seem to perform worse than the vanilla counterparts in some experiments is that normal? In the nonsmooth Sparse Low Rank case, I would have expected to see also the policy of Theorem 1 for comparison.\n\nMinor comments:\n* line 16:  R \\cap \\{\\infty\\} should be  R \\cup \\{\\infty\\}\n* Caption of Fig. 1  \"Lipchitz constant the regularizer\" ?\n* in S.29, you have \\gamma but above, line 80, you have gamma_t\n\nPost-rebuttal: Despite some limitations and clarifications to be made, the paper has merits.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "n/a", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers agree that this paper is worthy of publication. Although some reviewers had initial remarks regarding missing reference, the authors have provided a strong rebuttal that addressed these concerns.

I encourage the authors to take into account the feedback provided by the reviewers, in particular:

  * Reviewers 7qvs, ofGn and eqKr make excellent clarification suggestions on motivation and presentation.

   * Reviewer fPkS suggests some improvements to the experimental section.

   * Reviewer eqKr raises the issue of an important missing reference. This review also raises issues regarding clarity, motivation and comparison with other methods.
Decision: Accept (Poster)