Tight Risk Bounds for Gradient Descent on Separable Data

Summary

This paper considers training a convex linear model with gradient descent on linearly separable data. The paper improves the upper bound of the population risk and proves a matching lower bound.

Strengths

The paper closes the gap for training convex linear models with smooth loss functions on linearly separable data, by showing matching upper and lower risk bounds. I believe this can be an important work in this field. Also, the paper is well-written and the logic is easy to follow. The proof is a bit heavy but the authors managed to make it accessible.

Weaknesses

I didn't find a major flaw in this paper. The proof looks correct to me. My only concern is that there seems to have little novelty in techniques as a theoretical work. Especially the improvement on the upper bound of the test risk relies on the results in Srebro et al. [15]. But I believe the proof of the lower bound has some nice intuition, which probably should be further explained.

Questions

1. For the lower bound in Theorem 1, is there a way you can derive the minimum of the RHS with respect to the epsilon? 2. In the proof of Theorem 2, you consider two different regimes where $T \gg n$ and $n \gg T$. How to see that in Lemma 3 and 4?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

As a theory paper, I think it's fine to consider linear models. Therefore, I don't see an important limitation.

Summary

This paper examines the problem of learning linearly separable data with margin using gradient descent (GD) and focuses on establishing a population risk bound on the GD output. Previous research in this area has primarily concentrated on understanding the implicit bias and population error associated with solving this task using logistic regression. In contrast, this study introduces a broader class of loss functions known as C_{\pi,\beta}, which are non-negative smooth loss functions that converge to zero more rapidly than a reference loss function, \pi. The main contribution of this paper is the derivation of both upper and lower bounds on the population risk of GD (including stochastic gradient descent, SGD) for this class of loss functions. The authors employ a straightforward and elegant proof technique that revolves around controlling the norm of the GD output and its empirical risk. In order to establish a population error guarantee, the authors rely on uniform convergence results specifically tailored for linear models.

Strengths

This paper is extremely well-written and easy to follow. Also, this paper shows that bounds on the empirical error of (S)GD and the norm of the solution suffice to provide a sharp analysis of the population error. Compared to other work in this line, proofs in this work are more straightforward. Also, the population risk guarantee in this paper can be seen as an algorithmic-dependent uniform convergence which is also interesting.

Weaknesses

In classification tasks, the ultimate goal is often to minimize the 0-1 loss function, which directly measures the accuracy of classification. However, when employing gradient descent (GD) optimization, it is common to use surrogate loss functions such as logistic loss or hinge loss. These surrogate loss functions approximate the 0-1 loss and are more amenable to optimization. In this paper, all the results focus on controlling the population risk of the surrogate loss functions. It is important to note that many surrogate loss functions can provide an upper bound on the 0-1 loss function. However, for the specific case of logistic loss, there appears to be a discrepancy between the upper bound on the logistic loss presented in this paper and the upper bound on the 0-1 loss. This discrepancy suggests that overfitting may occur, and the concept of early stopping becomes relevant. Something that I fail to understand is why the authors do not focus on providing classification error bound for C_{pi,beta}.

Questions

1- In Corollary 1, the authors instantiate their result for the logistic regression. It shows that when T is exponentially large in the number of samples, then we have overfitting. How does this result compare to Shamir 2021? 2- Can the lower bound be extended to the case that it holds for every phi and “every” loss in C_{\pi,beta}? The current statement is different.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

One of the limitations is that this paper does not provide any evidence of "implicit bias".

Summary

This paper studies the generalization properties of gradient methods for convex, smooth and decreasing losses (e.g., logistic and polynomial losses) over linearly separable data distributions. The contributions are 1) a generalization bound based on Rademacher complexity which does not require the self-boundedness assumption for the loss and 2) a lower bound on the test loss which nearly matches the upper-bound. Overall, the results indicate that Rademacher complexity (or algorithmic stability) analyses for data-dependent generalization of GD are rate-optimal, as the lower bounds match the upper bounds in $n,T,\gamma$.

Strengths

The paper is in general well-written and clear, although few inconsistencies exist throughout the main body. The studied problem is interesting as understanding generalization of GD on separable data is foundational to machine learning. This paper takes a step in this direction by studying linear models. The paper's results imply that the commonly studied margin-based generalization bounds which usually take the form $1/(\gamma^2 n)$ cannot be improved in $\gamma,n$, or other parameters related to tail behavior, unless additional assumptions on data are imposed. The paper's claims are new and are also applicable to a broad class of smooth losses. The main contribution of the paper which is the lower test loss bound for a certain class of convex loss functions involves the construction of a new data distribution which can be useful for future works.

Weaknesses

weaknesses and some questions: 1- The derived upper-bounds are barely an improvement over known results in literature. The authors claim in abstract and also throughout the introduction that their results apply to any smooth loss function. however this is not the case, as the loss in this work must be monotonically decreasing. This excludes the commonly used square-loss whereas previous results by Lei and Ying 2020 can be applied to square loss. I also do not find the condition of self-boundedness existing in previous works limiting as it includes almost all commonly used losses that are also used in this work. Can the authors elaborate on that? 2- Also regarding the training and generalization upper bounds, I am not convinced of the novelty of the approach. The technique based on Srebro et al. is rather simple and well-known. I assume the challenge is in characterizing the rademacher complexity for linearly separable data, but similar analyses have been already done even for more complex models such as neural networks, for example see the papers titled "Feature selection and low test error in shallow low-rotation ReLU networks" and "Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks". Can the authors please comment on the challenges in optimization and generalization analyses and highlight novel steps related to general tail behaviors? 3- How do the bounds look like if $w_1\neq 0$? Particularly, it is interesting to know how the bounds on generalization behave with respect to initialization. 4- It might be helpful if a new column is added to table 2 explaining what $r_{\phi,T}$ looks like for each loss. 5- The specific data distribution used for obtaining the lower bound seems very interesting. It can be helpful for readers if the authors provide more discussion on high-level steps of the proof and the their intuition on the designed distribution. 6- It seems the bound of Theorem 1 contains a $\log ^3(n)$ factor which is missing In Table 2. 7- Table 2 shows that tailes of the form $\exp(x^{-\alpha})$ are slightly better in test loss performance than exponential tails. Does it leads to faster convergence for misclassification test error or generally for real-world experiments? 8- I think the previous works on the lower generalization bounds of SVM can be discussed here. e.g., "Optimality of SVM: novel proofs and tighter bounds" by S Hanneke, A Kontorovich.

Questions

please see the section above.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The paper does not have a conclusions section. It can be insightful if the authors discuss some limitations of the methodology and data assumptions. There is no potential negative societal impact associated with this work.

Summary

This paper establishes tight upper and lower bounds on the population risk of linear models trained with gradient descent (GD) on linearly separable data. In contrast to previous work, the paper's result only requires a smoothness assumption on the loss function, and the upper bounds are adaptive to the loss function's tail decay. Surprisingly, the authors achieve this result using standard techniques, with the generalization bound of [Srebro et al., 2010] based on local Rademacher complexity playing a pivotal role. **References** [Srebro et al., 2010]: Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates. *NIPS* 2010.

Strengths

**Minimal assumptions and standard proof technique.** The only assumptions on the loss function for the population risk upper bound are convexity, monotonicity, and smoothness, which leads to a clean theorem statement. Moreover, the proof only involves standard tools; one shows upper bounds the norm of the GD iterate and the empirical risk, and combines these two using the generalization bound from Srebro et al. (2010). In addition, the authors construct a lower bound which shows that their upper bound is nearly optimal for essentially all tail decay rates of the loss function. The minimality of assumptions, tightness of upper bounds, and simplicity of proof techniques showcases the paper’s strength.

Weaknesses

**Motivation for studying losses with diverse tail decays?** Having a more general theorem is beneficial, especially if it can be achieved without much sophistication. Still, I am curious about the utility of the upper bound’s generality. Were there important examples of losses that previous works failed to capture? Are there examples of loss functions with polynomial tails that have been used in the context of classification?

Questions

- What were some important losses (either from a theoretical or practical point of view) that previous works failed to cover? - When does it make sense to use loss functions with slow (e.g., polynomial) tail decay? It seems that loss functions with slow tails may encourage the predictor to increase the margin of already correct answers at the cost neglecting misclassified samples.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes.