Thank you for supporting our paper. We answer your questions as follows.

Q1. “The early-stopping time is oracle-based and lacks explicit bounds, which will limit the practical utility of the results.”

A1. Our aim is to understand the benefits of early stopping. We believe designing a practical criterion for early stopping, despite being an important question, is beyond the scope of this paper.

Q2. “What are the insights of selecting $k$ in the main theorems? How the "variance" and the "bias" are connected to $k$?”

A2. Intuitively, $k$ determines the number of dimensions in which early stopped GD is able to learn the true parameter $w\^\*$. Moreover, early stopped GD ignores the remaining dimensions and pays an “approximation” error. We choose $k$ to minimize the upper bounds.

In Theorem 3.1, the stopping time is relatively small, at which point GD first hits an empirical risk of $\\hat L(w\_{0:k}\^\*)$. Thus, the total parameter movement is relatively small, and the bias error tends to be large. In Theorem 3.2, the stopping time is relatively large, at which point GD hits an empirical risk of $\\hat L(w\^*)$. Thus, the total parameter movement is large, and the variance error tends to be large.

We will clarify these in the revision.

Q3. “Can the results in this paper be extended to generalized linear models or M-estimators?”

A3. We believe that part of our results can be extended beyond logistic regression. For example, the proof of Theorem 3.1 can be adapted to other loss functions that are convex, smooth, and Lipschitz. We will comment on this as a future direction.

We thank the reviewer for their comments. We address your questions below.

Q1. “The technique used to derive the logistic risk upper bounds relies heavily on the prior work of Telgarsky (2022).”

A1. While our Lemma 3.3 appears in [Telgarsky 2022] (and other prior works as mentioned), it seems unfair to call it a “weakness”, as new research builds upon existing results. We would also like to point out that our logistic risk upper bounds require careful statistical control around the population optimum since we work in an overparameterized regime, which is beyond [Telgarsky 2022]. Besides, we show how early stopped GD separates from asymptotic GD and how it explicitly connects to $\ell_2$-regularization. None of these results appears in [Telgarsky 2022].

Q2. “...It would be beneficial to present results that explicitly depend on the stopping time or provide an example of a stopping time for which the bounds hold.”

A2. One can compute an upper bound on the stopping time using standard optimization and concentration tools. Specifically, $\\hat L$ is smooth and convex, so GD converges in $O(1/t)$ rate. Moreover, we can compute $\\hat L(w\^*\_{0:k})$ using concentration bounds. In this way we can compute a stopping time upper bound.

Once we obtain the upper bound on the stopping time, we can state the theorem as “there exists a $t$ no larger than XX, such that…”. This gives examples of stopping time for our bounds to hold. We will comment on this in the revision. However, we prefer to maintain our original theorem statement as it is cleaner.

Q3. “In cases where the results are comparable to prior work, the bounds obtained in this paper are sometimes weaker.”

A3. As discussed in Lines 397-425, no prior results strictly dominates our results; the work that obtained sharper rates also needs stronger assumptions than ours. While there is still room to improve our upper bounds (as discussed in the end of Section 3.2), we believe our contribution is already very significant by establishing the benefits of early stopping in logistic regression.

Q4. “Are there scenarios where the optimal stopping time is impractically large, such as exponential in $d$ or $n$? If so, what happens to the risk of GD when it is stopped after $\mathsf{poly}(d,n)$ iterations? Does it still benefit from early stopping in such cases?”

A4. Note that our results allow $d=\infty$, but the optimal stopping time is always finite as hinted by our negative results for asymptotic GD. Therefore, the stopping time is generally small compared to $d=\infty$, and it is meaningless to discuss “exponential or polynomial in $d$”, which is infinite.

Moreover, as discussed in A2, the stopping time is at most polynomial in $n$ by optimization and concentration arguments. Note that the hidden constant factors might be instance-dependent. Again, there is no exponential dependence.

Thank you for your comments. We address your concerns as follows.

Q1. “My current score is primarily due to the exists of $t$ such that $\\hat L(w\_t) \\le \\hat L(w\_\{0:k\}\^\*)$. I believe that the existence of such a $t$ needs to be proven to complete the story.”

A1. The existence of a $t$ such that $\\hat L(w\_t) \\le \\hat L(w\_\{0:k\}\^\*)$ is guaranteed because

• GD converges to a minimizer of the empirical risk $\\hat L(\\cdot)$;
• and $\\min \\hat L(\\cdot) < \\hat L(w\_\{0:k\}\^\*)$.

So there exists a $t$ such that $\\hat L(w\_t) \\le \\hat L(w\_\{0:k\}\^\*)$. The second bullet is clear. We explain the first bullet as follows.

Note that $\\hat L(\\cdot)$ is smooth and convex. Classical optimization theory guarantees the global convergence of GD in this case. Specific to logistic regression, this is proved in, for example, Theorem 1.1 in [Ji & Telgarsky 2018], with a precise convergence rate. We also see this by applying Lemma 3.3 with suitable $u$ and large enough $t$.

This explanation should address your concerns. But let us know if you have further questions regarding this. We will add these discussions in the revision.

Q2. “I think the paper [A] is an important recent paper that is quite relevant to many of the ideas discussed in the paper (early stopping, implicit regularisation, connection to explicit regularization) is missing”

A2. Thanks for pointing out the missing reference. We will cite and discuss it in the revision.

Q3. “I think the theorem statements could be sharper. Words like - thus should not appear in a theorem statement.”

A3. We will polish our theorem statements according to your suggestions. Thanks.

Q4. “All of the current analyses are for the case when we initialize at zero. What if we initialized somewhere else, or did it have a random initialization?”

A4. When the initialization $w\_0$ is nonzero, in the bounds, $w\^\*$ should be replaced by $w\^\* - w\_0$. This can be seen from the proof of the theorems. We will clarify this in the revision.

Q5. “just to confirm the probabilities in Theorems 3.1 and 3.2 agree with respect to the sampling of the data?”

A5. Yes.

Thank you for your detailed comments. We address your questions below.

Q1. “...Lines 266-273, discuss application of these bounds to a trivial, under-parameterized case. How do these bounds perform in the overparameterized case?... For a meaningful comparison with the negative results in Section 4 on asymptotic GD, it would be useful to determine when Thm 3.1 and Thm 3.2 provide non-vacuous bounds and how common these settings are.”

A1. In Lines 205-214 of the right column and Lines 272-274, we discuss our bounds in an overparameterized setting satisfying the standard source and capacity conditions, where our bounds are non-vacuous.

Our comparison holds in general and common settings. In what follows, we explain this using Theorems 3.1 and 4.1 as examples. For every well-specified logistic regression problem (see Assumption 1), Theorem 3.1 yields a vanishing excess risk for early stopped GD as discussed in Lines 190-203 right. For the same set of problems, Theorem 4.1 implies GD without early stopping is inconsistent for logistic loss and poorly calibrated, as discussed in Lines 279-283 of the right column. Note that this comparison is agnostic to dimension and holds in the overparameterized regime as well.

Q2. “For Thm 4.2, what role does the $k$-sparsity condition play? Is this the key condition needed to prove inconsistency? Please provide some intuition based on the proof. … can you provide an example (or a class of examples based on data covariance) where Thm 3.1 and Thm 3.2 yield non-vacuous bounds while the negative results in Thm 4.2 still hold?”

A2. The $k$-sparsity is a sufficient condition to establish the sample complexity lower bound in Theorem 4.2. Note that Theorem 4.2 provides a lower bound on the excess zero-one error, but this does not imply inconsistency. For the inconsistency results in Theorem 4.1, we do not need the $k$-sparsity condition.

The intuition behind Theorem 4.2 is that there are $k$ informative dimensions and a lot more uninformative dimensions. Since $n\gg k$, the training set cannot be separated purely using the $k$ informative dimensions. Thus, interpolators must use the uninformative dimensions to separate the data, leading to the risk lower bound. This explains the role of the $k$-sparsity in Theorem 4.2.

We discuss in Lines 313-319 for situations where Theorems 3.1 and 3.2 yield non-vacuous bounds while the negative results in Thm 4.2 still hold. Moreover, the example discussed in Lines 205-214 of the right column and Lines 272-274 also suffices. We will make this clear in the revision.

Q3. “Regarding conjectures at the end of page 6 and page 8 (left column end)—what justifies these claims? For the first, do you have any empirical results supporting it? For the second, Thm 5.2 and Thm 5.3 merely represent convergence under a sufficient condition and a counter example, the conjecture seems strong—do you have additional reasoning to support it?”

A3. We discuss evidence/intuitions for the two conjectures as follows.

For the first one, note that in Figure 1(b), the test zero-one error keeps increasing even after reaching interpolation (training zero-one error becomes zero). This suggests that the zero-one error of the maximum $\\ell\_2$-margin interpolator (this is when $t\to\\infty$) should be higher than an oblivious interpolator. Our conjecture is partly motivated by this observation.

The reasoning behind the second conjecture is as follows. Note that Assumption 2 implies that the dataset projected perpendicular to the max-margin directions (called “projected dataset”) is strictly nonseparable (see Lemma 3.1 in Wu et al., 2023). This is the only property used in Theorem 5.2. Moreover, in Theorem 5.3, the “projected dataset” is nonseparable but with margin zero – we conjecture this property is sufficient for Theorem 5.3 to hold. Now for a generic separable dataset, we check the “projected dataset”:

• if it is strictly non-separable, Theorem 5.2 holds;
• if it is non-separable but with margin zero, we conjecture Theorem 5.3 holds;
• otherwise it is separable (with positive margin), we decompose the dataset recursively. This is the reasoning behind our conjecture.

We will add these discussions in the revision.

We appreciate your support! We address your concerns as follows.

Q1. “Though the settings are different, I am not sure if the authors ignored the line of work on logistic regression by E. Candes et al.”

A1. We will cite and discuss these works you pointed out in the revision. They focused on the existence of MLE and its behavior if it exists, which is quite apart from our focus where MLE never exists (see paragraph “Noise and overparameterization.” in Section 2 and Proposition 2.2).

Q2. “...it would be better if the author could provide a more concrete comparison between their work and those from linear regression using square loss. This would help readers better understand the key differences between square loss and logistic loss.”

A2. Risk bounds for logistic regression and linear regression are not directly comparable, as these two problems are different in nature: they have different data assumptions and different risk measurements.

In Lines 244-257 of the right column, we provide a high level comparison on the techniques for analyzing GD in logistic regression and linear regression. One immediate issue is that we cannot directly use tools from linear regression, which relies on the chains of equalities that needs the Hessian to be constant.

We will make these discussions more detailed in the revision to better clarify the key difference between squared loss and logistic loss.