Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methods

We thank the reviewer for their time and their valuable comments on our submission.

The result in [Chen et al. 2021] assumes $\|w^*-w_0\|=O(1)$ which leads to the first-order approximation for the model i.e., $\Phi(w) = \Phi(w_0) + \nabla \Phi(w_0) ^\top (w-w_0)$ being accurate in the constant-radius ball around initialization. On the other hand, our analysis uses second order information and the Hessian’s spectral-norm bound to show that as long as $\|w^*-w_0\|=O(m^{O(1/L)})$, the objective has favorable quasi convex-like properties (see pages 16-17) which ultimately leads to global convergence and good generalization. Moreover, using smoothness of the activation enables us to derive generalization bounds based on algorithmic stability which leads to finer generalization bounds compared to Rademacher complexity based bounds in [Chen et al. 2021] (please also see lines 128-168). Approaches based on Hessian spectral norm of deep nets has been used for obtaining training convergence of GD for square loss (cf. Remark 2.2). In particular, here the self-bounded property of the minimum eigen-value of the Hessian, (i.e., that the lower bound on $\lambda_{min}(\nabla^2 \hat F(w))$ is proportional to $\hat F(w)$) enables us to obtain smaller width lower bounds of poly-logarithmic order compared to the least-squares case which requires polynomial width.

We thank the reviewer for their time and their valuable comments on our submission.

2-The result in (Chen et al. 2021) assumes $\|w^*-w_0\|=O(1)$ which leads to the first-order approximation for the model i.e., $\Phi(w) = \Phi(w_0) + \nabla \Phi(w_0) ^\top (w-w_0)$ being accurate in the constant-radius ball around initialization. On the other hand, our analysis uses the second order information and the fact that Hessian’s minimum eigen-value at any $w$ is larger than $-\frac{\|w-w_0\|^{3L}}{\sqrt{m}} \hat F(w)$ to show that as long as $\|w^*-w_0\|=O(m^{O(1/L)})$, the objective has favorable quasi convex-like properties along the GD path. Moreover, using the Hessian structure of smooth networks enables obtaining the algorithmic-dependent generalization-gap bounds based on algorithmic stability. On the other hand, (Chen et al. 2021) uses Rademacher-complexity based bounds for deep nets which lead to the undesirable terms in the generalization loss. Since for algorithmic stability the generalization is solely dependent on the training loss performance, the generalization loss has the same favorable properties. This ultimately leads to tighter bounds.

3- Similar to the regression tasks, for classification tasks the weights are also close to initialization in the NTK regime. As mentioned earlier, the guarantees hold as long as the distance between the target weights and initialization satisfies $\|w^*-w_0\| = O(m^{1/L})$. We note that the convergent analysis is different from regression tasks using least squares method. Here the objective function has approximately quasi-convex-like properties. In particular, the self-bounded property of the minimum eigen-value of the Hessian, (i.e., that the lower bound on $\lambda_{min}(\nabla^2 \hat F(w))$ is proportional to $\hat F(w)$) enables us to obtain smaller width lower bounds of poly-logarithmic order compared to the least-squares case which requires polynomial width.

4- The goal in section 2.2 was to discuss the benefits of escaping the NTK regime in obtaining smaller width, iteration and sample complexity requirements. Indeed, there is a difference in problem setups between the sections as the proof specifically holds for the XOR dataset and two-layer nets. Extensions of the XOR problem’s results to multi-layer networks or to more general datasets are interesting future directions.

5- The step-size can be chosen such that $\frac{\eta}{m \cdot\text{polylog}(d)} = o_d(1)$. However, for larger step sizes, the noise caused by SGD can dominate the signal (i.e., the expected weights), which makes our test bound invalid.

We thank the reviewer for their time and their valuable comments on our submission.

2- Thanks for bringing up this issue. We will clarify in the revision. $\mathcal{S}$ denotes the training set. The generalization loss is a random variable depending on the choice of training set and the expectation is with respect to the randomness in selecting the training set. There is no condition on the noise generation for Section 2.1.2. Unlike the results in thm 2.1. which holds in the interpolation regime, here for thm 2.3. $F(w^*)$ (that is the optimal test error) can be non-vanishing as it is the case for noisy (nonseparable) data. In fact, the result holds for any such $F(w^*)$.

3- Indeed, assumption 1 holds with high-probability and a width lower bound is implicit for this assumption to hold. However, this assumption is standard in literature and used in several recent works in deep learning theory [Ji and Telgarsky 2020, Chen et al. 2021]. Alternatively, one could assume the infinite width NTK separability condition and derive the finite width NTK separability from that.

Q1- The results for generalization loss in Thm 2.1 hold if the conditions of the theorem (that is Eq. 2 and Eq. 3) are true for ‘every n samples’ from the distribution. For the case in your question, with $w_0$ being fixed, this can only happen if $w^*$ is the minimizer of the loss on the entire distribution. We also note that this justifies the fact that the generalization loss in Eq. 5 holds in expectation over the randomness of the training set rather than for a fixed training set. We apologize for the confusion and we’ve now added a sentence in Thm 2.1. clarifying this.

Q2- In fact, our training loss guarantees hold for the averaged training loss $\frac{1}{T} \sum F(w_t)$ (cf. Thm B.1 in the appendix) and the last iterate guarantee stems from the descent lemma as $F(w_T)\le F(w_t)$ for all $t\le T.$ Thus, the logarithmic term can be avoided by using the averaged training loss guarantee. Thanks for bringing this up; we have now clarified in the revision.

Q3- We apologize for the confusion and have fixed the theorem reference in the revision (we are referring to Thm 2 in [Lei and Ying 2020]). The reviewer is correct that their notion of stability requires replacing the i’th sample rather than deleting it. However, the statement of our lemma 5 is correct and the proof is similar (e.g., see Lemma 6 in [1])

[1] Schliserman, Matan, and Tomer Koren. "Stability vs implicit bias of gradient methods on separable data and beyond." Conference on Learning Theory. PMLR, 2022.

Thank you very much for your insightful feedback, which has greatly contributed to improving the clarity and quality of our paper! We are happy that our response addressed most of your concerns and we agree with the reviewer about the remaining limitation regarding the dependency of overparameterization on the depth. Thank you again for your detailed review and for your recognition of our work's contribution to the field.

We thank the reviewer for their time and their valuable comments on our submission.

-We refer the reviewer to Remark 2.2 and lines 301-310 for a proof comparison of Thm. 2.1 with previous results. In summary, for the results in NTK regime, we used an induction-based argument to show that both $\|w_t-w_0\|$ and $\|w_t-w^*\|$ remain sufficiently small during training. This is essential to show that the bounds for the objective’s Hessian spectral-norm and the objective’s minimum eigenvalue remain valid.

-The improvements mainly come from using an algorithmic-dependent analysis which bounds the generalization loss based on training performance whereas previous works used Rademacher-complexity bounds (Bartlett et al 2017,chen et al 2021) which captures the distance in L2,1 norm (please also see lines 128-168 in the Prior Works section). Whether the algorithmic-stability framework can be extended to neural nets with non-smooth activations is unknown and a possible direction for future studies. We believe such an extension is possible, although it requires new proof techniques as our current analysis relies on the smoothness assumption for both convergence and generalization.

Q1- please see the last paragraph.

Q2- In addition to our response in paragraph 1 above, the other problem that we study, learning the XOR, also goes beyond using known techniques. Let us give a brief proof overview for Theorem 2.4 on the XOR problem. We first derive a generic expression for the expected weights at any iteration. We then decompose the error terms (due to SGD noise) in two components where the first one is the deviations of the empirical gradient around its expected value and the other is the deviations of the empirical gradient at true weights compared to expected weights. The calculations of error terms lead to the system of equations in section E.7. The most challenging part of the proof is in simplifying this system of equations as done in Section E.7. This needs careful treatment in order for the final noise strength (i.e., noise resulting from SGD) to be sufficiently small. For simplifying the error terms first we derive the $\ell_\infty$ norm of error terms and replace the resulting term in the third equation for obtaining the $\ell_2$ norm of the noise resulting from coordinates $k\in[3,d].$ To the best of our knowledge, the derivations and the approach above are novel.