Fast convergence of stochastic subgradient method under interpolation
Authors: Huang Fang
Zhenan Fan
Michael Friedlander
Venue: ICLR 2021 Poster (2021)
Keywords: Optimization
stochastic subgradient method
interpolation
convergence analysis

Abstract: This paper studies the behaviour of the stochastic subgradient descent (SSGD) method applied to over-parameterized nonsmooth optimization problems that satisfy an interpolation condition. By leveraging the composite structure of the empirical risk minimization problems, we prove that SSGD converges, respectively, with rates $O(1/\epsilon)$ and $O(\log(1/\epsilon))$ for convex and strongly-convex objectives when interpolation holds. These rates coincide with established rates for the stochastic gradient descent (SGD) method applied to smooth problems that also satisfy an interpolation condition. Our analysis provides a partial explanation for the empirical observation that sometimes SGD and SSGD behave similarly for training smooth and nonsmooth machine learning models. We also prove that the rate $O(1/\epsilon)$ is optimal for the subgradient method in the convex and interpolation setting.

Published as a conference paper at ICLR 2021
FAST CONVERGENCE OF STOCHASTIC SUBGRADIENT METHOD UNDER INTERPOLATION
Huang Fang, Zhenan Fan & Michael P. Friedlander Department of Computer Science University of British Columbia Vancouver, BC, Canada {hgfang, zhenanf, mcs .uc.
ABSTRACT
This paper studies the behaviour of the stochastic subgradient descent (SSGD) method applied to over-parameterized nonsmooth optimization problems that satisfy an interpolation condition. By leveraging the composite structure of the empirical risk minimization problems, we prove that SSGD converges, respectively, with rates ((1/e) and ([lo(L//e) for convex and strongly-conve objectives when interpolation holds. These rates coincide with established rates for the stochastic gradient descent (SGD) method applied to smooth problems that also satisfy an interpolation condition. Our analysís provides partial explanation for the empirical observation that sometimes SGD and SSGD behave similarly for training smooth and nonsmooth machine learning models. We also prove that the rate (1/e)) is optimal for the subgradient method in the convex and interpolation setting.
INTRODUCTION
Gradient descent (GD) and subgradient descent (subGDD) methods are simple and effective first-order optimization algorithms for training machine learning models. The convergence- analyses for these methods depend crucially on the smoothness of the objective function. is well understood that there is a fundamental gap between the convergence rates of gradient-like methods for smooth and nonsmooth problems (Shor, 1984; Nemirovski Yudin, 1983; Nesterov, 2005; Bubeck, 2015; Beck, 2017). Table summarizes the rates for the main problem classes.
However, in the practice of training machine learning models, the nonsmootheness from the model is not causing much trouble (Glorot et al., 2011: Goodfellow et al., 2016). Neural networks with nonsmooth activation function such as ReLU activation can usually be trained as fast as the one with smooth activation function such softplus, see Figure 1.1 motivating experiment from to compare the convergence of gradient and subgradient based methods for smooth and nonsmooth neural networks the MNIST dataset' to classify digits 0 and We can see that the gradient and subgradient based methods, either batch or stochastic version, has similar convergence behaviour for smooth and nonsmooth neural networks. Therefore there is discrepancy between theory and practice.
The success of overparameterized models such as deep and wide neural networks has instigated a trend in the analysis of stochastic variants of gradient descent in the interpolation setting, in which the model achieves zero training loss, and therefore fits of the training data (Schmidt & Le Roux, 2013; Bassily et al., 2018; Ma et al., 2018b; Jain et al., 2018; Vaswani et al., 2019a;b; Wu et al., 2019; Liu Belkin, 2020). This recent series of papers offer insight into the fast convergence of SGD and new approaches for algorithm design. This line of analysis, however, focus exclusively smooth objective function, and cannot explain the effectiveness SSGD for training nonsmooth neural networks.
We present a formal analysis showing that SSGD for nonsmooth objectives could converge as fast as smooth objectives in the interpolation setting. Our contributions include:
hhttp://yam/ lecun. com/ /ttp//xxdmmm//m st./

---

Published as a conference paper at ICLR 2021
Convergence comparison, learning rate 0.01
0.7
5500 with ReLU act.
Taining loss
0.5-
GD with sofples act
with act.
objective f(x)
smooth (1/e)) (1gg(1)))
nonsmooth
convex
(11/²)
0.2-
strongly convex
O(1/e)
0.0
Table 1: Worst-case iteration complexity of batch gradient and subgradient methods.
Figure 1.1: The convergence gradient- based (GD and SGD) and subgradient- based (subGD and SSGD) methods for smooth and nonsmooth neural networks
A description of semi-smoothness properties of a function useful for the iteration complexity analysis of convex objectives in the interpolation context. Under mild conditions, semi- smoothness under interpolation allows us to prove that SSGD has iteration complexity (11/e) for convex objectives, and (log((1/c) for strongly-conver objectives. These rates improved the classic bounds O (e2 and ((1/c) for convex and strongly-convex objectives and match the convergence rates SGD for convex and smooth objective under interpolation.
Proof that the iteration bound (1/cc) is optimal in the convex and interpolation setting. In contrast to the case with smooth objective function, subgradient-basee methods cannot be further accelerated for nonsmooth model-even with the interpolation assumption.
RELATED WORK
2.1 FIRST-ORDER METHODS FOR NONSMOOTH OPTIMIZATION
The subgradient method and its convergence analysis for general convex and nonsmooth problems was first described by Shor in the late 1960s and 70s; see Shor (1984). Nemirovski & Yudin (1983) subsequently established that the iteration complexity (11/²²) described by Shor (1984) is optimal for methods that can only access subgradient oracle. Subsequent works for minimizing general convex and nonsmooth problems include stochastic subgradient methods (Polyak, 1987; Shalev- Shwartz et al., 2007; Shamir & Zhang, 2013), dual averaging (Nesterov, 2009), and acceleration via smoothing (Nesterov, 2005; Beck & Teboulle, 2012). More recently, Zhang et al. (2020) and Shamir (2020), among others, described the tractability and complexity of getting an approximate stationary point for general nonsmooth and nonconvex problems.
related line of work involves analysis of optimization algorithms for partially nonsmooth objectives that take the form fxx) + g(x), where the function f is smooth, and the function g, which usually represents a regularizer, is convex and nonsmooth. Many models in feature selection and compressed sensing fall into this category of problems, which are usually solved by variations of the proximal-gradient method (Nesterov, 2007; Beck & Teboulle, 2009; Xiao, 2010; Parikh & Boyd, 2014; Defazio et al., 2014; Allen-Zhu, 2017). These approaches typically use special properties of the regularization function which generally do not apply in the context we consider in this paper.
Another related line of works focus on compositional optimization (Drusvyatskiy & Paquette, 2019; Davis & Drusvyatskiy. 2018; Duchi & Ruan, 2018). These works consider the objective as the compositions of convex functions and smooth maps. which different from the objective formulation in this work, see section 3 for details.
2.2 INTERPOLATION HELPS OPTIMIZATION
The interpolation condition implies that the residual between the prediction of the model and data vanishes. In the context of nonlinear least-squares, for example, it is known that interpolation
2

---

Published as a conference paper at ICLR 2021
Algorithm 1 Stochastic subgradient descent. The learning rate function oz N R. returns the learning rate at iteration L.
1: Initialize: w()) E R
2: for t. = 1, .... do
3: select i .1,2....,n1 uniformly at random
4: compute (() E (f((w())
5: we((+1) w(() ang(t)
6: end for
allows the Gauss-Newton method converge at local superlinear rate, although in general it can only achieve a local linear rate (Bertsekas, 1997). Conditional gradient method can also enjoy a linear convergence rate for least square objective when interpolation holds (Beck & Teboulle, 2004). Recent interest in over-parameterized models for machine learning problems makes interpolation (or near interpolation) relevant assumption for the analysis and development of algorithms. Under interpolation, stochastic gradient descent enjoys the same convergence rate as its deterministic counterpart, gradient descent (Schmidt & Le Roux, 2013; Ma al., 2018a; Bassily al., 2018). Some techniques that originally developed for gradient descent, such as line-search and Nesterov acceleration, are proven also hold for SGD when interpolation is satisfied (Vaswani et al., 2019b;a; Liu & Belkin, 2020; Jain et al., 2018) Related work in this vein includes improved analysis of stochastic second-order optimization algorithms (Meng et al., 2020) and adaptive stochastic gradient descent (Loizou et al., 2020; Vaswani et al., 2020) under interpolation. Another line of work (Qian et al., 2019; Khaled & Richtárik, 2020) in this direction aims to explore assumptions other than the classic bounded noise assumption for the optimization theory of training over parameterized model, such as the expected growth condition (Schmidt & Le Roux, 2013), expected smoothness (Qian et al., 2019; Gower al., 201 8), etc. All of the work just mentioned involves differentiable and smooth objective functions, and cannot explain the fast convergence of SSGD for nonsmooth objectives that often observed practice.
PROBLEM SETTING
We consider the unconstrained empirical risk-minimizatie problem
minimize wERd
f(w) = Σ f((w) where each
fi(w) = (w,(
(3.1)
and n is the number of data points. Throughout the paper, we use w" to denote any solution of eq. (3.1), and thus f = f(w") is the optimal objective value. We assume that the 1-dimensional loss function & TR + Rzo is nonnegative, inf = 0, convex, and is 1-smooth, i.e.,
(a((a) (3) S aa
Va, 3e.BEl
Without loss generality, we also assume {0) Common examples for loss function include the 2-norm, logistic loss, and the 2-norm hinge loss function. The functions hy are Lipschitz continuous with respect to the fixed parameter L:
[h,(w1) - hx(ww) S L||w1 w22l Vwi, W2 E Rd, Vi [n].
We make no assumption on their smoothness properties. Many key machine learning tasks can be formulated 13. including training deep neural networks with nonsmooth activations, such the ReLU function. Here and throughout, the function is the 2-norm of vector, unless otherwise specified.
Our analysis relies on the Clark generalized gradient (Clarke, 1990) of the nonconvex and nonsmooth function h, defined as the convex hull of all valid limiting gradients:
ah(w) conv uu t
lim Vh(wa), wa - w
This definition additionally requires to be almost everywhere differentiable by Rademacher's theorem. We refer readers to Clarke (1990), and more recently, to Zhang et al. (2020), who use this generalized gradient in a related analysis. These properties of the generalized gradient are needed for analysis:
3

---

Published as a conference paper at ICLR 2021
(chain rule)
@f((w) (h((w) ah(w), [[h,(w)]l S L, Ae E R., Vi [n].
(gradient bound)
The second property follows from the L-Lipschitz continuity of each function h4. We define the norm of the generalized gradient at vector
[[),,w)]l = sup || 2 E ah,(w))
Algorithm describes the stochastic subgradient descent (SSGD) method. Interpolation means that our model has the ability to fit all training samples perfectly and therefore we can obtain zero training loss at the solution e.g., f(w") O. The interpolation assumption holds for overparameterizee neural networks and is gaining increasing interest in recent years Jacot et al. (2018).
MAIN RESULTS
4.1 BOUNDS AND LIPSCHITZ PROPERTIES THE GENERALIZED GRADIENT
Our analysis hinges on establishing that the objective function f is differentiable at all of its minimiz- ers, i.e., at all vectors such that f(w O. This is implied by the following proposition, which holds even without the interpolation condition.
Proposition 4.1 (Generalized growth condition). For all d-vectors w,
< 21 fww)
Vi [n].
(4.1)
Consequently,
|()(w))] < - Σ
(4.2)
Equation (4.2) implies that if the objective value f(w) O. then the generalized gradient contains only the origin: (w( = {0). It thus follows from Clarke (1981, Property 10) that f is differentiable at any point with zero objective value. This means that if there is solution with a zero value, then it must be a fixed point of the subgradient method. This property stands in contrast to a solution where the function is nonsmooth and makes it possible for the subgradient method to converge to solution with constant learning rate.
Proof of Proposition 4.1. Fix an arbitrary d-vector w. The subdifferential 0f:(w) (h;((w)) (h;(w). Because each function h; is L-Lipschitz continuous, we can then deduce that
[0f((w)) < L2 [E(((()()))))))
(e((h(()))) - E(
21 2T?((((((w)) E(O))
(4.3)
21 f((w).
Step (i) follows from the assumption that {(0) = minxeR {(A) = 0, which implies (' = 0. Step (ii) follows from the fact that any convex L-smooth function E= + R satisfies the bound
m(y) u(x)) (Vu(x), y x)
Vulyy) vu(x)]
2L
see Nesterov (2014, Theorem 2.1.5). Make the identifications
u y = hw(w), x
to immediately obtain eq. (4.3) and thus the proof for eq. (4.1). Equation (4.2) can be obtained directly from Jensen's inequality:
[ = 1 3 af((w) < [(ff(w))l < Σ 2I f(w)) =2
4

---

Published as a conference paper at ICLR 2021
The composite structure of the functions fi allows develop semi-Lipschizz bound their generalized gradients. Moreover, we show that it is possible to provide a global convex majorant for each function f.. which holds without assuming convexity. Interestingly, eq. (4.5) overlaps with the "semi-smooohness" property of over-parameterizer neural networks derived by Allen-Zhu et al. (2019, Theorem 4). In contrast to that result, however, do not use any special properties of over-parameterized neural networks, Proposition 4.2 may thus be of more general interest.
Proposition 4.2 (Semi- smoothness... For all vectors w1 and W2, and each E [md].
[[ - 0f((w1))l - L2 will + 2L 2L (in
(4.4)
and
1,2
f((w2) S ((fi w2 -w1) +
w2 wi w1l1 +2 wr (Ill2ff((w)))
2
(4.5)
See Appendix A for the proof of this result.
4.2 CONVERGENCE RATE OF STOCHASTIC SUBGRADIENT DESCENT
We now present global convergence analysis for the SSGD algorithm under the additional assump- tion that the objective I' of eq. (3.1) is convex. We develop a bound on the expected progress of the objective value that depends function itself, which is the usual bound in the literature. Our proof is based on a simple modification of the classical proof of subgradient descent method.
the minimizing value f* rather than the Lipschitz bound on the
Theorem 4.3 (Global convergence rate of SSGD). Assume f is convex. Then for any positive
integer T and any learning rate function 0r that satisfies Σt=1(0 (0= - 12a > 0,
min (l) - -5 ||w(1]) w=1 + +1,2 l Σt=1 a? 2 2Σ (0t - 1,2
(4.6)
(E[T]
Proof. Let g00 E @)((((())). Then each iterate w(() satisfies the bound
E|]lo((++1 -0²1 w(
1w ang; (8)
w w=1 1
(1) w01112 1112- 112--204 -204
Σ
(t)
w²
1
9
12
n
(1) w w²1 - -20 -
f(ww)) -
+
1
(t)
(4.7)
1=1
(t) w011 - - 2a L f(w
- f(w"))
(4.8)
where (i) follows from the convexity of f, and (ii) follows from Proposition 4.1. Take expectations on both sides of the inequality (4.8) and rearrange to obtain
(2a,- - 2L'a7) B[(f(w(()) - f*)] s "I]lu( w11 - (1]l w0 w012]+222a
(4.9)
Summing inequality (4.9) over & E (1,2...., T) yields
T
2 (2a: - 2L ([f((( fo $ (1 -1112 2L2 Σ
1=1
Divide both sides by 2 2 T.2of) obtain the required result.
5

---

Published as a conference paper at ICLR 2021
This proof mirrors closely the classical proof of SSGD, which assumes that the subdifferential of each ft is bounded, i.c., (w)] I G for some constant G. We use Proposition 4.1 in eq. (4.7) to avoid the bounded subgradient assumption and to express the convergence rate using the minimal value S* This modification allows us to leverage the interpolation assumption that f = 0. We use Theorem 4.3 to immediately deduce the following convergence rate result.
Corollary 4.4 (Global convergence rate of SSGD with constant learning rate). Assume that I is
convex and that the learning rate a = (2L2)) is constant for all t >> O. Then for any positive integer T, the SSGD iterates w' satisfy
min E (f - fl (21)(22)))))) (212/T)]lo0)) -w---w"- 12 1E[2
Furthermore, when f = (interpolation holds),
min rE(T)
(w) - ( (22L//)) ==112
Corollary 4.4 indicates that the SSGD method converges rate (L/e)) when interpolation holds. This rate matches the convergence rate of SGD for smooth objective functions under interpolation (Schmidt Le Roux, 2013). When interpolation does not hold, Corollary 4.4 implies that SSGD, on expectation, could obtain objective value lower than 2 + in O(1/c) time, which could be close to f" when f" close to 0 (interpolation nearly holds).
Next, we derive convergence rate under the stronger assumption that f is strongly convex, which means that
P [0 w2 2 Vwn, w2 Rd Vg E Of(w))
[(w1) f(w2) + (g, Wi (22 +
(4.10)
for some constant μ > 0. Note that recent works indicated that in order to prove linear convergence rate, the strong convexity assumption can be relaxed other weaker assumptions that could hold even for some nonconvex functions (Karimi et al., 2016; Qian et al., 2019). For simplicity, we assume strong convexity in our analysis.
Theorem 4.5 (Global convergence rate SSGD under strong convexity). Assume that f is 1/L²² L22 is constant for all L >> O. Then for any
p-sttrongy convex and that the learning rale 04 positive integer T, the SSGD iterates (t) satisfy
[T]l -w=1
(1
11
T-1
2 - -w'12 +
(4.11)
T
Proof. Use the definition of the SSGD iteration to obtain
E Elllw (1+1) w= [
( Σ 1=1
i ( - w²11 2ar
w(() - w
+ Σ
a |1,
1=1
( [| - 111 20 20((5(1(1) - f²) - -masllw" - w011 -maylll'-w((1p
Σ
n
a
l1gg
(4)
12
1=1
(1))
(1 (aa)) (1) -=1l²= 225-200 2az
(( - +202+ 20 (w
(4.12)
(iv)
/1 [1) - 11
T 1
2
(4.13)
where (i) follows from the same argument of the proof of Theorem 4.3; (ii) follows from the j-stroogg convexity of ff (see eq. (4.1 (iii) follows from eq. (4.1); and (iv) follows from the definition the learning rate a+ 1/1.2.

---

Published as a conference paper at ICLR 2021
Taking expectation to both sides of eq. (4.13) and recursively apply to E (1,2....,T) to deduce
Bill w0 ==1
112
S
1
T-1
w w011 +
Σ
11
2
L
2
L
1
T-1
|| - w -w112
2 -
(4.14)
T,2
1
1² = 1.2/u. where (i) follows from the fact that Et=0(
Theorem 4.5 indicates that the SSGD can converges to the ball centered at w" with radius 2 f linear rate. If additionally interpolation holds, SSGD converges the solution linearly. Again, this rate matches the convergence rate of SGI) for smooth and strongly convex objectives in the interpolation setting (Schmidt Le Roux, 2013; Ma et al., 2018a). Similar to Corollary 4.4, when interpolation is nearly satisfied, SSGD converges linearly to an 2/ /paapproximate solution.
Corollary 4.4 and Theorem 4.5 also provide insight into the effect of learning rate schedules on the performance of SSGD. A learning rate schedule a that decays as t t-1/ is optimal because it causes the algorithm to exhibit a complexity bound of O(1/e²). which is the theoretical lower bound (Nemirovski & Yudin, 1983). However, the learning rate schedule Ot is slow in practice. Corollary 4.4 and Theorem 4.5 partially explain the discrepancy between the theory and practice: many machine learning models exhibit interpolation or near interpolation, and an aggressive constant learning-rate schedule works better than the conservative worst-case optimal learning rate 0g = (tt
Other than the learning rate scheduling a, = 1/12, we can adopt more carefully tuned learning rate scheduling (Stich, 2019) to obtain refined convergence rate, see more details in Appendix.
4.3 LOWER BOUNDS
We have proven that, under interpolation, SGD for smooth problems and SSGD for nonsmooth problems exhibit the same convergence rates. This causes us to consider the following questions:
Is it possible induce momentum-type acceleration for SSGD under interpolation? Vaswani et al. (2019a) and Liu & Belkin (2020) showed recently that acceleration is possible for SGD under interpolation. It seems plausible that similar techniques could be used for nonsmooth problems.
Can the composite structure fi = to ho, which is central to our analysis, be used to establish improved convergence rate for SSGD without interpolation? In other words, we know the lower bound on the iteration complexity for any subgradient method for nonsmooth functions is ((1/e²). What, then, is the lower bound for minimizing the structured nonsmooth function o h?
Unfortunately, the answer these questions is "no", show below. First, derive the lower iteration bound for any algorithm with access only to a subgradient oracle in the interpolation setting.
Theorem 4.6 (Lower bound with interpolation). Given
and positive constants L and R, and an initial vector (1) Let ( (.) Then there exists an funntichit,uunciion h such that f f= o convex, f = min. f(w) = 0, [I - wIll < R such that
f(w(o))- - - L² 15a5e
min
(4.15)
2(1 +
Proof.
With out loss of generality, we assume the initial point (1) = 0. Let h(w)) L|l - w* lloo
and
R
R
R
0 ].
w
Vt+1
V
2'
V++1
20
+ entries
(d
1) entries
7

---

Published as a conference paper at ICLR 2021
where is some arbitrary constant greater than O. It is easy to check that is 1-smooth, h is L-Lipschitz, f = h convex, and f
We follow Nemirovski & Yudin (1983) and assume that any algorithm that uses only subgradient infor- for all s S t. By our construction, we can further obtain w(+) span(e1, ..,..., ...,...., ex) for all S L. Therefore, for all S 4,
mation generates iterates w(+) E span span(0f(u())) @f(w(())
LR
Le 2 2--1
f(((+)) - f vt+1
Note that the above holds Ve > 0. Taking + 0+, we completes the proof.
Theorem 4.6 established (2(1/c) iteration complexity for subgradient method under interpolation. Combining this result with the ((1/e) iteration complexity in Corollary 4.4, we can conclude that the rate (11/e) is optimal the interpolation setting and no acceleration possible for subgradient- based methods. Then proceed to the lower bound with assuming interpolation.
Theorem 4.7 (Lower bound without interpolation). Given d, L, R > 0 and an initial point w(1) Let E(-) (.)2, and there exist L. L-Lipschitz functiooi satisfying == o h is convex, [|u w" || z such that
min Ssst f(((())- fr LRR
(4.16)
V++I
Proof. Similar to the proof of Theorem 4.6, we set w(()) = 0. But we change the construction of l(w) to h(w) T[llw w=
loc R),, and wn is defined in the same way as in the proof of Theorem 4.6:
R
R
R
0 O..... 0 ]
w"
V+++
Vt
2'
V++1
2
+
entries
(d (d-t- 1) entries
where is some arbitrary constant greater than Following the same analysis of the proof of Theo- rem 4.6, w(s) E span(fe1 (2,,,,,,.... ......... e,} Vs < and
2
R
L2R
L2R
f(w(s)) - - 2
+ 2- + R
Stt
vt+1
Vt +1
By taking 0+, we have || w*ll s and completes the proof.
Theorem 4.7 provides 12(1/e2) iteration complexity for subgradient-baxe methods for solving the structured function &. a h. This matches the lower bound for solving general nonsmooth objective function with subgradient-based method, and implies that the structure foh itself without interpolation cannot give us an improved iteration complexity of subgradient-biin based methods.
5 NUMERICAL EXPERIMENTS
The smoothness of the loss function is crucial to our analysis. We now present some numerical experiments compare the convergence of SSGD for training ReLU neural networks with smooth and nonsmooth loss functions. We denote {=: as training samples and {y {yr) as training labels. d stands for the prediction of the i-th sample 2; from the trained model.
5.1 TEACHER-STUDENT STUDENT SETUP
We randomly generate small one hidden layer neural network with 16 neurons and ReLU activation as the teacher network, the network takes 16 dimensional vectors as inputs and outputs scalar. Then generate 128 random vectors from the Gaussian distribution and get their corresponding labels {y: 122 as the output the teacher network. In order to ease the training and satisfy the interpolation assumption, overparameteriize the student neural network
training data {a, 1228 R
8

---

Published as a conference paper at ICLR 2021
Training curve: MSE and L1 loss
Logistic vs. L1hinge Loss
2.0
MSE 1==1e.3
Logistic 1r=0.1
objective value
1.5
MSE 1r-1e-4
objective value
Logistic Ir-0.01
L1ooss In=1e-4
L]Hinge In-0.1
Ir=1e-5
L1Hinge 1r=0.01
1.0
0.5
0.0
200
400
600
800
1000
10
20
30
40
50
epoch
eepochs
(a) Teacher-student training
(b) Classify 4's and 9's on MINST dataset.
Figure 5.1: The performance of SSGD with smooth and nonsmooth loss functions.
and set to be a one hidden layer network with 512 neurons and ReLU activation. We train the student network with different loss functions: squared loss e.g.. : - (yi 0z)² and absolute loss e.g.. 1 Er= [y Ds with different learning rates. The training curves shown in Figure 5. We can observe that the training curve with squared loss is smoother than the curve with absolute loss. For absolute loss, the performance of SSGD more sensitive to the change of learning rate and we need to decrease the learning rate to obtain a lower objective value. These observations validate the importance of the smoothness of loss function under the interpolation setting.
5.2 CLASSIFY 4's AND 9's ON MNIST DATASET
We train the LeNet (Lecun et al., 1998) on the MNIST dataset to classify 4's and 9's. To convert this task to a binary classification problem, we transform the labels {yr ). to (-1,+11) Then we run SSGD to train the model with difference loss functions: logistic loss # Σx= log(1 (10-e1ee(ppppp and LI-hinge loss e.g.. 1 Σi= max 1- y and with different learning rates. The training curves are presented in Figure 5.1b. Different from the teacher-student experiment, SSGD in this task perform similarly with smooth and nonsmooth loss functions. We conjecture that this is because the objective function with Li-hinge loss almost satisfies Proposition 4.1 locally at the solution, namely eq. (4.1) 1) holds for most training samples in a neighbourhood of the solution. Our observation supports this conjecture. We observe that more that 95% of our final predictions ÿ. 's satisfy the condition [ > 2. Since the Ll-hinge loss is locally smooth when [ > 2, we can thus say that most training samples satisfy eq. (4.1) locally at the solution. While for the teacher-student training problem, its objective is nonsmooth at solution (when zero residual is attained) since the absolute value function {(x) == |x] is nonsmooth at O. Therefore the objective of the teacher-student training problem does not satisfy Proposition 4.1 locally as solution and running SSGD to solve it could suffer from slow convergence.
CONCLUSION AND DISCUSSION
An empirical minimization problem based on composite functions has sufficient structure to allow for tight convergence analysis that explains the effectiveness of stochastic subgradient descent methods on nonsmooth problems with interpolation. Surprisingly, the complexity bounds O11/e) and O(log (1))) that we prove under interpolation match those of stochastic gradient descent for smooth functions.
Our convergence analysis is based on the convexity properties of As mention in connection with Theorem 4.5, the strong convexity assumption can be relaxed to weaker conditions, but even these exclude important nonconvex models that appear in neural networks. It is still open problem as to whether linear convergence rate for subgradient methods under a weaker assumptions, such as the restricted secant inequality (RSI). In Section 4.3 we proved that the rate O(1/e) is optimal for subgradient-banl -hased methods under interpolation. However, this lower bound holds only for subgradient- based algorithms. Smoothing techniques based on Moreau envelopes (Nesterov, 2005) can sometimes lead to acceleration for nonsmooth optimization, which may be further avenue to explore for obtaining an accelerated SSGD method.
9

---

Published as a conference paper at ICLR 2021
REFERENCES
Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. Journal of Machine Learning Research, 18:221:1-221:51, 2017.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via parameterization. In Proceedings of ICML, pp. 242-252, 2019.
Raef Bassily, Mikhail Belkin, and Siyuan Ma. On exponential convergence of sgd in non-convex over-parametrized learning. arXiv e-prints, art. arXiv:1811.02566 Nov 2018.
Amir Beck. First-order methods in optimization, volume 25. SIAM, 2017.
Amir Beck and Mare Teboulle. A conditional gradient method with linear rate of convergence for solving convex linear systems. Mathematical Methods of Operations Research, 59(2):235-247, 2004.
Amir Beck and Mare Teboulle. A fast iterative thinshog algorithm for linear inverse problems. SIAM J. Imaging Sci., 2 2009.
Amir Beck and Mare Teboulle. Smoothing and first order methods: A unified framework. SIAM Journal Optimization, 22(2):557-58)) 2012.
Dimitri P Bertsekas. Nonlinear programming. Journal of the Operation Research Society, 48(3), 1997.
Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundation and Trends in Machine Learning, 8(3-4):231-3577 2015.
Frank H Clarke. Generalized gradients of lipschitz functionals. Advances in Mathematics, 40(1):
52-67, 1981.
Frank H. Clarke. Optimization and nonsmooth analysis, volume 5. SIAM, 1990.
Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 29(1), 2018.
Aaron Defazio, Francis R. Bach, and Simon Lacoste-Julics SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In Proceedings of NeurlPS, pp. 1646-1654, 2014.
Dmitriy Drusvyatskiy and Courtney Paquette. Efficiency of minimizing compositions of convex functions and smooth maps. Mathematical Programming, 1 178:503-558, 2019.
John Duchi and Feng Ruan. Solving (most) of a set of quadratic equalities: composite optimization for robust phase retrieval. Information and Inference: Journal the IMA, 8:471-529, 2018.
Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep sparse rectifier neural networks. In Proceedings of AISTATS, pp. 315-323, 2011.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. The MIT fPress, 2016. ISBN 0262035618.
Robert M. Gower, Peter Richtárik, and Francis Bach. Stochastic quasi- gradient methods: Variance reduction via jacobian sketching. arXiv e-prints, art. MrXiv:1805.0266 May 2018.
Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kernel: Convergence and generalization in neural networks. In Proceedings of NeurlPS, pp. 8580 85890,859,.000 2018.
Prateck Jain, Sham M. Kakade, Rahul Kidambi, Pranceth Netrapalli. and Aaron Sidford. Accelerating stochastic gradient descent for least squares regression. In Proceedings of COLT, pp. 545-604, 2018.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the tojjaaa-ojasiwwizz condition. In Proceedings of ECML PKDD, pp. 795-811, 2016.
10

---

Published as a conference paper at ICLR 2021
Ahmed Khaled and Peter Richtárik. Better theory for sgd in the nonconvex world. arXiv e-prints, art. arXiv:2002.03329, Feb 2020.
Yann Lecun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. In Proceedings of the IEEE, pp.
1998.
Chaoyue Liu and Mikhail Belkin. Accelerating SGD with momentum for over-parameterrized learning. In Proceedings of ICLR, 2020.
Nicolas Loizou, Sharan Vaswani, Issam Laradji, and Simon Lacoste-Julien. Stochastic polyak step- size for sgd: An adaptive learning rate for fast convergence. arXiv e-prints, art. arXiv:2002. Feb 2020.
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of SGD in modern wer-paaametrrizd learning. In Proceedings of ICML, pp. 3325- 3334, 2018a.
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of SGD in modern wer-parametrized learning. In Proceedings of ICML, pp. 3331- 3340, 2018b.
Si Yi Meng, Sharan Vaswani, Issam Hadj Laradji, Mark Schmidt, and Simon Lacoste-Julien, Fast and furious convergence: Stochastic second order methods under interpolation. In Proceedings of AISTATS, pp. 1375-1386, 2020.
Arkadi Nemirovski and David Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley Interscience, 1983.
Yu. Nesterov. Gradient methods for minimizing composite objective function. CORE Discussion Pa- pers 2007076, Université catholique de Louvain, Center for Operations Research and Econometries (CORE), 2007.
Yurii Nesterov. Primal-dual subgradient methods for convex problems. Mathematical programming. 120(1):221-259, 2009.
Yurii Nesterov. Introductory Lectures Convex Optimization: A Basic Course. Springer Publishing Company, Incorporated, edition, 2014. ISBN 1461346916
Yurii H. Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103 (1):127-152, 2005.
Neal Parikh and Stephen Boyd. Proximal algorithms. Foundation and Trends in Optimization, 1(3): 127-239, 2014.
Boris T Polyak. Introduction to optimization. translations series in mathematics and engineering. Optimization Software, 1987.
Xun Qian, Peter Richtárik, Robert M. Gower, Alibek Sailanbayev, Nicolas Loizou, and Egor Shulgin. SGD with arbitrary sampling: General analysis and improved rates. In Proceedings of ICML, pp. 5200-5209, 2019.
Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under a strong growth condition. arXiv e-prints, art. arXiv:1308.60
Aug 2013.
Shai Shalev-Shwartz, Yoram Singer, and Nathan Srebro. Pegasos: Primal estimated sub-gradient solver for sym. In Proceedings of ICML, pp. 807-814, 2007.
Ohad Shamir. Can we find heaar-pproximmaelyy-staaonnn points of nonsmooth nonconvex functions? arXiv e-prints, art. arXivv2002.11962, Feb 2020.
Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: convergence results and optimal averaging schemes. In Proceedings of ICML, 2013.
Naum Z Shor. Minimization methods for non-differentiable functions. funcciioo Springer Series in Computa- tional Mathematics, Springer, 1984.
11

---

Published as a conference paper at ICLR 2021
Sebastian U. Stich. Unified optimal analysis of the (stochastic) gradient method. arXiv e-prints, pp. arXiv:1907.04232, 2019.
Sebastian U. Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for sgd with delayed gradients and compressed communication. arXiv e-prints, pp. 2019.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of SGD for over- parameterized models and an accelerated perceptron. In Proceedings of AISTATS, pp. 1195-1204, 2019a.
Sharan Vaswani, Aaron Mishkin, Issam H. Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste-Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. In Proceedings of NeurlPS, 2019b.
Sharan Vaswani, Frederik Kunstner, Issam Laradji, Si Yi Meng, Mark Schmidt, and Simon Lacoste- Julien. Adaptive gradient methods converge faster with ver-parameterization (and you can do line-search). arXiv e-prints, art. arXiv:2006.06835, Jun 2020.
Xiaoxia Wu, Simon S. Du, and Rachel Ward. Global convergence of adaptive gradient methods for an over-parameterized neural network. arXiv e-prints, art. 1rXiv:1902.07111..60 Feb 2019.
Lin Xiao. Dual averaging methods for regularized stochastic learning and online optimization. Journal of Machine Learning Research, 0122543-2596. 2010.
Jingzhao Zhang, Hongzhou Lin, Suvrit Sra, and Ali Jadbabaie. On complexity of finding stationary points of nonsmooth nonconvex functions. In Proceedings of ICML. 2020.
APPENDIX
A THE PROOF OF PROPOSITION 4.2
Proof of Proposition 4.2. Given w1, w2 Rd Vi E [n).
[05i(w2) - -
[1((h((w2))@00 - (1)
(h((()))))) - (4kcehh-DDikkii------hhhhhhhhh--
(Ohh)((
1e" ((h_(aa2)))ll0hh((x))) - (/0p()))))l--((///m/o)e0ddddd/dd
2 [ (w:) X
2L 2222) + _ w| wills
(A.1)
where (1) follows the same argument as the proof of Proposition 4.1:
[e((h(w22) = 1e' (w²) - E' (0) < v2(E(h+(w2)) E(O) = 2ff()22)
Exchange Wi and u/2 we can also get
[[])( ( )l < 2L 2f((wi) L 1 wi
(A.2)
Combining Equation (A.2) and Equation (A.1), finished the proof for Equation (4.4).
Given W1, W2 E Rdd note that f.(w) is almost every differentiable by Rademacher's Theorem, thus f((22) = f((w)) + S' (0f((u1 T(22 wr)), w2 w2)drr
=f(w)) + (0f((w;), w2 wi)+ + ( (0f((u + T(22 w1)) -ff(ww), u2 - wi)dr
(A.3)
12

---

Published as a conference paper at ICLR 2021
Note that
(0s((1r + + wi)) afi(wi), w2 - wi)dr
10s((11 -u(w2 ((w))w))) 05i(wn )|l ||][ w wil
/ /2L/2f((w)) 1 - w1
|00 w ||dr
L
2L| w2 wi
w 22((wi)
|| wi
(A.4)
2
Plug Equation (A.4) into Equation (A.3), we finished the proof for Equation (4.5).
B ANOTHER CHOICE OF LEARNING RATE SCHEDULING
The following theorem is based the result of Stich (2019)'s analysis refined learning rate scheduling. Note that the refined learning rate scheduling depends not only on the Lipschitz constant L, but also rely on the number of iteration I' (we need the number of iterations an input of our algorithm).
Theorem B.1. Assume that f is p-strongly convex for some μ 2 O. For all positive integer T, there exist constant learning rate scheduling at = 1/(2L²), such that the SSGD iterates w satisfy
μT 4T2
72L? 8r
B[ - f*1 - w01 64L ==112exp
min 1E[T+1]
(B.1)
for μ > 0, and
4L2 ww (1)
w0 112
4L f ((( (1) w'1
min
Blf(((()) - fr]
(B.2)
[E[T]
T
VT
for μ = O.
Proof. We start with eq. (4.12),
eq. (4.12)
(1 - ,aa)) l| - "" w²1 2ar(f(w()) - + +2?222
(1 ,aai) (|) - w²1 2- - -( (f(x)) - -f) - 120
(1 (aat [l w² w01 ar(((w(()) - +2,
(B.3)
where (i) is from the fact that 2(a, 12) 2 a given that ar S 1/(2L2). Note that eq. (B.3) in the same form as Eq. (8) from Stich (2019)'s work, then Lemma 2, Lemma 3): there exist a learning rate scheduling such that
directly apply (Stich, 2019,
n 4
72L2 f
min (0) f*1 + W (T+) - w*1l < 64L +E[T+]]
w=1l2 exp
+
μT
(B.4)
Then we can obtain eq. (B.2) by applying (Stich & Praneeth Karimireddy. 2019, Lemma 13) and therefore completes the proof. Note that our proof is mostly based on the recurrence relation eq. (B.3) and Stich (2019)'s analysis, we refer interested readers to Stich (2019)'s 's work for more technical details.
13


Reviews:
[{"review_id": "v83xKzjRzDE", "reviewer": "AnonReviewer2", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies SSGD method to nonsmooth optimization problems with interpolation condition. It has proven that SSGD converges with rate O(1/epsilon) for convex problem and O(log(1/\\epsilon)) for strongly-convex problems. What is more, it is proven that O(1/\\epsilon) is optimal for the subgradient method in convex and interpolation setting.\n\nOverall, I vote for accepting. The rate and lower bound results are solid theoretic results. It helps to explain the empirical observation that nonsmooth machine learning models are not necessarily more difficult to optimize than smooth models in practice.\n\nPros: \n\n1. The results can be helpful to explain some observations in practice.\n\n2. This would be a helpful result to investigate interpolation models, which has attracted attention recently.\n\nCons: \n\n1. This paper only considers convex and strongly-convex problems, while over-parameterized models are usually nonconvex model, e.g., DNN.\n\n2. The authors did not give empirical results to verify that (S)SGD do have similar performance in smooth and nonsmooth problems.\n\n3. I have a minor concern regarding the reason of nonsmoothness. It seems that the authors blame the nonsmoothness in neural networks to the nonsmooth activation function. Even if the activation is smooth, the neural network is not L-smooth when w is unbounded, e.g., considering f(w)=w1*w_2*w_3.\n\nQuestions:\n1. It is assumed that \\ell(.) is 1-smooth. Fundamentally, is this crucial and why? I am not clear about this, especially considering that the inner function of the composite, i.e., h_i, is nonsmooth.\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "bvXTgHba0wi", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\nThe paper focuses on the empirical risk minimization problem when summands have a form of composition of smooth non-negative convex and non-smooth functions under interpolation condition, i.e. when the loss is zero in the solution. In this setting, authors derived convergence rates $O\\left(\\frac{1}{\\varepsilon}\\right)$ and $O\\left(\\log\\left(\\frac{1}{\\varepsilon}\\right)\\right)$ for Stochastic Subgradient Descent (SSGD) for convex and strongly convex objectives respectively. Up to the difference in factors hidden in $O(\\cdot)$, these rates match the rate of SGD in the convex and strongly convex cases under interpolation assumption, which partially explains why neural networks with non-smooth activations can usually be trained as fast as ones with smooth activations. Moreover, the authors derived lower complexity bounds for this particular class of problems showing that SSGD is optimal in the convex case under interpolation.\n\nOverall, the contributions are quite impressive and solid, the paper is clearly written, and the proofs are simple and short (which is actually one of the biggest advantages of this paper). However, there are also some technical issues in the proofs of lower bounds. Fortunately, these issues can be easily fixed (see the Weaknesses part for further details).\n\n## Strengths\n1. **Clarity, motivation, and related work.** The paper is reader-friendly: the results are presented clearly and explained well, the problem is well-motivated, the literature review is very concrete and covers the most relevant papers, to the best of my knowledge.\n2. **Lower bounds and tight rates for SSGD.** Authors proposed lower bounds showing that $O(1/\\varepsilon)$ is the best convergence rate one can hope for in this setting. These lower bounds are tighter than standard lower bounds for non-smooth convex optimization, and they rely on a particular structure of function $f$. Moreover, the authors show that SSGD complexity bounds match the proposed lower bounds.\n3. **Simple proofs.** I have checked all proofs: they are mathematically correct **(except the proofs of lower bounds; see the weaknesses part)**, clearly written, and short. Taking into account the novelty and importance of the proposed results, simple and solid proofs are a nice bonus making the paper easy to read.\n\n## Weaknesses\n1. **Experiments.** There are almost no experiments in the paper. While the contribution of the paper is primarily theoretical, I believe the paper would benefit from adding some numerical study justifying the proposed theory on different problems.\n2. **Inaccuracies in the proofs of lower bounds.** Formally speaking, the proof of Theorem 4.6 is incorrect. Indeed, if $w^{(0)} = 0$, then $w^{(1)} \\not\\in \\text{span}(e_1,\\ldots, e_t)$, but $w^{(1)} \\in \\text{span}(e_1,\\ldots, e_t, {\\color{red}e_{t+1}})$, because the subgradient of $\\partial f(w^{(0)}) = \\frac{2L^2R^2}{t+1}\\cdot\\text{conv}(e_1,\\ldots,  e_t, {\\color{red}e_{t+1}})$ . Since the proof of Theorem 4.7 relies on the following technique, it is mathematically incorrect too. However, it can be easily fixed without changing the main idea; see my version of the proof below.\n - **Proof of Theorem 4.6.** Let us consider the same function $f$, the same starting point $w^{(0)} = 0$, but change the definition of $w^{\\star}$ in the following way: $w^{\\star}=\\left[\\frac{R}{\\sqrt{t+1}} + \\varepsilon, \\frac{R}{\\sqrt{t+1}} + \\frac{\\varepsilon}{2}, \\ldots, \\frac{R}{\\sqrt{t+1}} + \\frac{\\varepsilon}{2^t}, 0, \\ldots, 0\\right]^\\top$, where $\\varepsilon > 0$ is some small number. We have $\\partial f(w) = 2L^2||w - w^{\\star}||_{\\infty}\\cdot \\text{conv}( \\partial(|w_i - {w_i}^{\\star}|) \\quad|\\quad  i: \\quad i\\in I(w) )$, where $i\\in I(w)$ means that  $|w_i-{w_i}^{\\star}|$ equals $\\ell_\\infty$-norm of $w-w^*$. Therefore, one can easily check via induction that $w^{(s)}$ lies in the span of first $s$ coordinate vectors for all $s \\leq t$ since coordinates $w_i^*$ of $w^*$ are decreasing when $i$ increases (see also the formula for $\\partial f(w)$). Using this we derive $f(w^{(s)}) - f(w^*) \\geq \\left(\\frac{LR}{\\sqrt{t+1}} + \\frac{L\\varepsilon}{2^s}\\right)^2$ for all $s \\leq t$. Taking the limit w.r.t. $\\varepsilon \\downarrow 0$ we get the result.\n\n## Questions and Comments\n1. page 1, Abstract, \"By leveraging ...\": The sentence is incomplete and should be rewritten.\n2. page 4, \"$f$ is differentiable ...\": I guess, this sentence is slightly misleading: $f(w) = 0$ means that $w$ is a minimizer and interpolation condition is satisfied, while in general if $w$ is a minimizer, then it is not necessary that $f(w) = 0$ (unless we have an interpolation). Consider rewriting of the sentence.\n3. page 11, inequality between (A.1) and (A.2): $\\sqrt{2\\left(l(h_i(w_2) - l(0)\\right)}$ $\\to$ $\\sqrt{2\\left(l(h_i(w_2){\\color{red})} - l(0)\\right)}$\n4. page 11, ineq. (A.3): $\\langle \\partial f_i(w_1 + \\tau(w_2-w_1)) - \\partial f(w_1), w_2 - w_1 \\rangle$ $\\to$ $\\langle \\partial f_i(w_1 + \\tau(w_2-w_1)) - \\partial f_{\\color{red}i}(w_1), w_2 - w_1 \\rangle$\n5. page 5, proof of Theorem 4.3: The notation $g_i^{(t)}$ is not introduced, while can be recovered from the context. Anyway, authors should add a formal definition.\n6. page 6, Theorem 4.5: Actually, one can extend the result using the recurrence (4.12) for the general choice of $\\alpha_t$ and applying some standard stepsize schedules for SGD; e.g., see\n - Stich, Sebastian U. \"Unified optimal analysis of the (stochastic) gradient method.\" arXiv preprint arXiv:1907.04232 (2019).\n\n## Final Remarks\nTo conclude, the paper makes an important contribution to the theory of stochastic optimization under interpolation. There are small issues in the proofs for lower bounds that can be easily fixed (see my comment in the Weaknesses part). I encourage the authors to apply the needed corrections. **If the authors fix the issues mentioned above, I will increase my score.**", "extra_scores": {}, "extra_text": {}}, {"review_id": "ahiJx6axFvo", "reviewer": "AnonReviewer1", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe paper considers stochastic finite-sum minimization with a special structure of composition of a smooth univariate loss with a non-smooth Lipschitz function. A generalized gradient bound is proved for this setting as well semi-smoothness. Using the former bound, sublinear 1/k rate is proved for stochastic subgradient method under convexity and interpolation conditions. With additional assumption of strong convexity, a linear convergence rate is proved.  Further, a lower complexity bound is claimed for the considered class of functions, which proves that the obtained bounds for the SSGD are optimal.\n \nEvaluation:\nIn my opinion, the paper is a borderline, slightly on the acceptance side. The obtained convergence rates are interesting. On the other hand, the convex setting is not well motivated by applications, and the lower bounds are obtained under quite restrictive assumption on the possible algorithms.\n\nPros:\n1. Faster convergence rates for SSGD under interpolation condition, which match the non-accelerated bounds for the smooth case.\n2. This can shed some light on why SSGD works quite fast in practice.\n3. Proposition 4.1 shows that this setting is very close to the smooth optimization case.\n\nCons:\n1. It is not clear what could be particular real examples of problems in the convex case which are covered by the considered framework. \n2. Since there is almost sure differentiability, it may happen that SSGD visits only points of smoothness and, thus, generates the same trajectory as SGD. This could be a simpler explanation of why SSGD works very similarly to SGD in practice.\n3. The lower bounds are proved under a restrictive assumption that $w^{(s)} \\in span \\{e_1, e_2,...,e_t\\}$. This is not what assumed in Nemirovski & Yudin (1983). Instead, standard way is to assume that $w^{(s)}$ belongs to the span of previous subgradients. Then, with a special construction of resisting oracle, it is proved that only one non-zero component can be added per iteration.\n4. No numerical experiments to support the theoretical findings.\n\nMinor comments:\n1. Some related literature is not mentioned. There is a set of works on so-called compositional optimization. See https://link.springer.com/article/10.1007/s10107-018-1311-3 , references therein and also papers which cite this paper.\n2. There are some misprints.\na. Last but one line of the first paragraph of Sect. 2.1. \"complexity of get\" -> \"complexity of getting an\"\nb. Last but one line of the first paragraph of Sect. 3.  \"2-norm a vector\" -> \"2-norm of a vector\"\nc. First line of the second paragraph of Sect. 5. extra \"the\".\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "_YioEvjnHwz", "reviewer": "AnonReviewer4", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper considers the behavior of the stochastic subgradient descent method under the interpolation condition. They provide convergence rates for both convex and strongly-convex objectives. \n\nReasons for score: \n\nThis paper is well-written. My major concern is the novelty. In terms of both methodology and theory, the paper seems to be an extension of classical results. While the theoretical results are interesting and useful, they are fairly straightforward. The authors should also provide comparisons between their method and previous approaches both theoretically and numerically. Some detailed comments are listed below. Hopefully, the authors can address my concern in the rebuttal period. \n\nHere are my main comments:\n\n1) The authors need to claim clearly what are their theoretical contributions. The main results Theorem 4.3 and Theorem 4.5 seem to be easy extensions of traditional SGD convergence analysis.\n\n2) Interpolation condition is a core concept in this paper. However, there is no clear statement of it. It only appears in some comments after theorems. I suggest the authors provide a formal condition at the beginning of their main results and offer some intuition behind it. \n\n3) The assumption that f is convex is not very intuitive. Could the author give some examples to illustrate that? Moreover, the term \"overparameterized\" has been brought up several times in the abstract and the introduction part. It would be better to give an example of an overparameterized model, which also helps to explain the convexity assumption. \n\n4) Some numerical experiments would be preferred to better illustrate the theoretical results. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proves new rates of convergence for stochastic subgradient under an interpolation condition. The analysis is rather simple but it produces better rates than previously known, which all reviewers agree is interesting. As pointed out by the reviewers, this work has the potential to help the community better understand optimization with over-parametrized neural networks (where convexity or other related assumptions play a role).

To the authors, please add a citation to Pegasos as requested by the reviewers.


Decision: Accept (Poster)