Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper shows that gradient descent with early stopping in the context of Generalized Linear models has an optimal sample and iteration complexity.
strengths_and_weaknesses: I am not an expert in the specific field of this paper, so it is hard for me to assess if this paper is not missing some important related work. However, to the extent of my knowledge, it seems that this paper is not missing any critical related work. 

1. (Pro and con) On the one hand, the result seems new and interesting as it contrasts previous results on generalization of GD and SGD with early stopping. On the other hand, it seems that SGD is superior to GD even in that setting (since an iteration is significantly cheaper for SGD.) Thus we may consider that this result is not groundbreaking.  However, I still think this paper is in the interest of the community (assuming that its results are correct)

2. (Pro) The core of the technical contribution (Thm 3.1) is very well explained. 

3. (Con) I found the exposition of some of the results not 100% clear. I have some serious doubts about some results mentioned in this paper (mainly equation (4) and its consequences). I am hopeful that the authors can clarify this during the rebuttal. (see my questions) 

questions: 1. Some emphasis is put on the fact that this work is dealing with Gradient descent without projection, but the generalization guarantees are obtained with respect to the best classifier in a constrained ball $\mathcal{W}^B$. (see, for instance, Theorem 3.1). (in comparison, [2] uses projections).

2. In the same vein, I am a bit confused with some statements that compare the output of GD (unconstrained) and the solution of the constrained problem. For instance in (4) if we assume that the optimum is at $w=0$ and we take $B=\eta \approx 0$, we get that $F_S(\bar w^S) \leq \min_w F_S(w)$ which is not possible if we initialize at $w_0 \neq 0$ because we would have $\bar w^S \approx w_0$ and thus  $F_S(\bar w^S) \gg \min_w F_S(w)$. Can you comment on that and/or provide a precise citation/proof for equation (4)? I read [17] and the closest statement to (4) in [17] is Theorem 3.1 about online gradient descent where there is a projection step for the iterates. If we considered GD with projection, it would not be a problem since one projection step would bring us to the optimum. It seems to me that usually, in the proof of (4) the quantity $\|x^* - x^t\|$ appears and is upper bounded by $2B$ because $x^*$ and $x^t$ **belong to the constraint set.** 
3. By reading the statement of Theorem 3.1, I was not 100% sure how you would go from the constrained to the penalized formulation. I got it by reading the proof of Thm 3.4. You use the fact that the constrained statement is valid for any $B$. Thus it is critical to make sure that (4) is valid and precise that the first statement of Theorem 3.1 is valid for any $B$.

4. In any case,  you could also assume that the optimum is achieved and use the fact that $$F_S(\bar w^S) \leq \min_{w \in \mathbf{R}^d} F_s(w) + \eta L^2 + \frac{\|w^*-w_0\|^2}{\eta T}$$ 
 ? Another alternative for (4) to be true would be to use $\mathcal{W}^B$ with $B$, and $u$ picked such that we know that $\bar w^S$ belongs to $\mathcal{W}^B$, but you would not get the penalized version of the result. 


Overall, I may change my grade depending on the answers to these questions. (mainly question 2.) Precisely, I am currently leaving them the benefit of the doubt, but if the statement in Eq.4 is not clarified, I may decrease my score to 4. On the other hand, if all my questions are correctly addressed, I may increase my score to 7.

limitations: The iteration complexity is maybe optimal, but the oracle complexity is n * iteration complexity which is $ O(1/\epsilon^4)$. So still worse than SGD. It is briefly addressed by the authors.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors study the problem of excess risk minimization of convex Lipschitz Generalized Linear Models (GLMs) over euclidean norm balls.

They consider the classical setting of minimization of the empirical risk as a surrogate for the excess risk.
They consider the Gradient Descent (GD) algorithm to optimize the empirical risk, except they _do not_ rely on projections and simply run plain GD.

Using the uniform convergence of GLMs, the authors show that plain GD with early stopping outputs an $\epsilon$-accurate solution (compared to the best solution contained in a euclidean norm ball) in $O(1/\epsilon^2)$ iterations with $O(1/\epsilon^2)$ samples.

This contrasts with the performance of GD under the more general setting (i.e. non-GLM) where the complexity is $O(1/\epsilon^4)$.

Finally, the authors show through a lower bound and matching upper bound a non-distribution-dependent convergence is possible for GD without projections, but the resulting is then $O(1/\epsilon^4)$.

 
strengths_and_weaknesses: # Strength

The paper is well-written and easy to follow. 
The problem at hand is well described, and even though I am not an expert in the field, the related work section seems complete.
The proofs are kept simple and arguments follow each other nicely.

I particularly appreciate part 5 which gives an overview of the main arguments of the proofs, and make diving in the proofs easier.

# Weaknesses
I am wondering about the relevance of the result. 
Namely, as the authors mention, rates of $O(1/\epsilon^2)$ are already known for SGD, and SGD is the go-to method in practice as iterations are much cheaper than GD.
So is the main contribution that GD reaches that rate without projections ? or is it the distribution dependent uniform convergence argument ? or a mix of both ? I know the authors discuss this at the end of the introduction, but it would be great if they could clarify.

Also, the authors often refer to the notion of stability, especially at the end of section 5, but I believe that they never actually define it. Could the authors clarify this ?
questions: Apart from the above questions, here are some more minor remarks:

* I did not fully understand the last part of the sentence line 126.
* In the second equation of Theorem 3.1, I believe $\norm{w}^2$ should be $B^2$
* Supplemental material, equation after line 503: the $c>0$ is refered to as $t$ and then $c$.
* Supplemental material, to apply Theorem line 509 to the current problem, I believe $c_i= 4L$, while the authors use $c_i = L$. This has no major impacts, but it changes the constants in the rest of the proof and in the theorem statement.
* Equation 10: $g(a) = ...$
* line 284: "the" -> "that"

limitations: NA
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper studies the gradient descent for a stochastic convex optimization problem for a generalized linear model. With excess error at most $\epsilon$, sample complexity and number of iterations of $\tilde{O}(1/\epsilon^{2})$ is needed in contrast to the general stochastic convex optimization, where $\Omega(1/\epsilon^{4})$ is needed.  
strengths_and_weaknesses: The logic and contributions of the paper are clear. To the best of my knowledge, the results are novel. 

In terms of weakness, I think although the results are new, they are not that surprising because one knows that there is dimension-independent uniform convergence bounds for generalized linear models and it is reasonable to expect that sample complexity and number of iterations for a stochastic convex optimization problem for a generalized linear model will be better than the general stochastic convex optimization. In addition, I think the presentations can be improved here and there, and some points can be made more clear which I will detail in the questions below.
questions: (1) In the abstract, and introduction, you mentioned ''early stopped'' gradient descent, but when you introduce your gradient descent algorithm in (2) and afterwards, it seems to me (I hope I didn't miss anything) that you never talk about ''early stopped'' again. Where did you use ''early stopped'' in your analysis?

(2) In equation (3), should it be from $t=1$ to $T$?

(3) In equation (11), what is the space you are taking supremum over for $D$ and $f$?

(4) In line 478 in the supplementary material, it is better to use '','' instead of ''.'' to end the last equation and write ''where'' instead of ''Where'' here. Same can be said about line 495.

(5) Cauchy-Schwartz should be Cauchy-Schwarz.

(6) In the proof of Theorem 3.1, for the equation between line 494 and line 495, what do you mean by $P(w\notin\mathcal{W}_{u}^{K})$? The previous term involves taking sup over $w$, but here, it is for some arbitrary $w$? Also in the same line, what do you mean by $\sup_{S}$? What is the space of the supremum taken over? Can you explain in more detail how do you get the next inequality?

(7) Line 509. In the statement of Theorem, instead of ''Boucheron, Lugosi and Massart 7'' write ''Boucheron, Lugosi and Massart [7]''.

(8) In line 522, I am confused with the notation $u=\frac{1}{T}\sum_{t=1}^{T}u_{t}$. In the equation between line 262 and 263, you had $\bar{u}$. So both $u$ and $\bar{u}$ denote average?

(9) In line 528, can you provide a reference to McDiarmid or perhaps even state what it is?

(10) In line 531, line 538, what is ''union bound''? 

(11) In line 533, ''set $w^{\ast}$'', do you mean ''set $w^{\star}$''? 

(12) In line 545, maybe you can define Rademacher random variables for the convenience of the readers.

(13) In line 578, ''with the same probability'', I just want to know whether this is indeed with the same probability, or with at least the same probability?

(14) In line 600, what is ''reverse triangle inequality''? I know what triangle inequality is, but I am not familiar with reverse triangle inequality. Plus in the second line below, you wrote (triangle inequality) instead of (reverse triangle inequality).
limitations: It seems the author(s) did not include a discussions on the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: metareview: This work is concerned with an analysis of early-stopped gradient descent in a stochastic setting, and shows improved complexity, by relying on an assumption of a distribution-dependent ball for the parameter.

The reviewers all think that this is an interesting submission that should be accepted, and I agree with them.
confidence: Certain
Decision: Accept