Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.

Overall, 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.

Pros: 

1. The results can be helpful to explain some observations in practice.

2. This would be a helpful result to investigate interpolation models, which has attracted attention recently.

Cons: 

1. This paper only considers convex and strongly-convex problems, while over-parameterized models are usually nonconvex model, e.g., DNN.

2. The authors did not give empirical results to verify that (S)SGD do have similar performance in smooth and nonsmooth problems.

3. 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.

Questions:
1. 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.




review_title: Summary 

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: ## Summary
The 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.

Overall, 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).

## Strengths
1. **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.
2. **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.
3. **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.

## Weaknesses
1. **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.
2. **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.
 - **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.

## Questions and Comments
1. page 1, Abstract, "By leveraging ...": The sentence is incomplete and should be rewritten.
2. 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.
3. 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)}$
4. 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$
5. 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.
6. 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
 - Stich, Sebastian U. "Unified optimal analysis of the (stochastic) gradient method." arXiv preprint arXiv:1907.04232 (2019).

## Final Remarks
To 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.**
review_title: New complexity bounds for stochastic non-smooth (with a certain structure) optimization under interpolation

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:

This 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. 

Reasons for score: 

This 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. 

Here are my main comments:

1) 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.

2) 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. 

3) 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. 

4) Some numerical experiments would be preferred to better illustrate the theoretical results. 

review_title: Convergence analysis of stochastic subgradient descent

final_score: rating: 7: Good paper, accept
review_content: Summary:
The 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.
 
Evaluation:
In 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.

Pros:
1. Faster convergence rates for SSGD under interpolation condition, which match the non-accelerated bounds for the smooth case.
2. This can shed some light on why SSGD works quite fast in practice.
3. Proposition 4.1 shows that this setting is very close to the smooth optimization case.

Cons:
1. It is not clear what could be particular real examples of problems in the convex case which are covered by the considered framework. 
2. 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.
3. 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.
4. No numerical experiments to support the theoretical findings.

Minor comments:
1. 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.
2. There are some misprints.
a. Last but one line of the first paragraph of Sect. 2.1. "complexity of get" -> "complexity of getting an"
b. Last but one line of the first paragraph of Sect. 3.  "2-norm a vector" -> "2-norm of a vector"
c. First line of the second paragraph of Sect. 5. extra "the".

review_title: A borderline paper, closer to acceptance

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)