Estimation error of gradient descent in deep regressions

A few minor weaknesses hinders the clarity of this paper.

1. The title is misleading, in my point of view. Better state as "Estimation Error of Gradient Descent in 3-layer sigmoidal neural network". I would expect the result could extend to multiple layer L of NN when one states "deep" regression. Also, since this paper deals with 3-layer NN. I wonder if there is already similar result for 2-layer NN, which I cannot find this paper citing.

2. I understand there are many constants and symbols in the paper due to the circumstances of the paper, but I find it confusing to have $L,L_n,L_\sigma$ all representing different things.

3. There is no experimental result supporting the claim.

The proof is based on neural tangent kernel theory which is used in a few NN theory papers, and the proof is similar to the idea that the local landscape of the objective function is almost linear and the optimal points are dense when the NN is overparameterized. Although the paper is thorough and comprehensive, I’m not sure how much novelty it provides compared to previous work technically, and whether the bound, for example, the lower bound of the widths of each layer, is optimal compared with previous papers.

Is the novelty about constraints? Does the optimization path interact with the boundary of feasible set, or the feasible set is so large that once the initial point is far from boundary, since it moves a small distance, the constraints are never hit?

The NN structure is quite special that each layer has to be some sort of shape and the architecture is simple. As practical NN is developing, it would make more sense to present a generic method or discussion that can be applied to many types of NNs.

It is fine that the bound terms are complicated and not intuitive, but it makes the paper readable if we see more discussions, like which term is bottleneck, how to insert some intermediate values (such as $B$ with different sub/superscripts) to get the bound in informal Thm.

It is better to give lower bound of $n$ rather saying “sufficiently large”.

I am not sure if any practical NN applications have "iterates moving locally" so that one can use kernels, and people usually use regularizers. Is there an experiment or practical observation that verifies the phenomenon in this paper in practice?

• The detailed comparison with previous results is missing. For example, for the optimization result, this paper proves a result that in the overparameterization regime, the loss function satisfies the PL condition along the gradient descent dynamics. This result is also stated in [1], so how does the current result differ with [1]? Also, for the generalization result, there are some generalization bounds for three-layer neural networks (or more general deep neural networks), e.g., [2,3,4]. What is the difference between this generalization result to these previous bounds? From my understanding, the generalization bound in this paper is based on the distance $|w_t-w_0|$, and there are many existing results for distance-based generalization bounds, e.g., [5]. What is the difference for the techniques on the distance-based generalization bound between the two works?

• For the generalization result, I think it would be more convincing if the authors could provide numerical experiments on the tightness of the generalization bound.

[1] Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over-parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59: 85–116, 2022.

[2] Gatmiry, Khashayar, Stefanie Jegelka, and Jonathan Kelner. "Adaptive Generalization and Optimization of Three-Layer Neural Networks." The Tenth International Conference on Learning Representations (ICLR). 2022.

[3] Ju, Peizhong, Xiaojun Lin, and Ness Shroff. "On the generalization power of the overfitted three-layer neural tangent kernel model." Advances in Neural Information Processing Systems 35 (2022): 26135-26146.

[4] Wang, Puyu, et al. "Generalization Guarantees of Gradient Descent for Multi-Layer Neural Networks." arXiv preprint arXiv:2305.16891 (2023).

[5] Arora, Sanjeev, et al. "Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks." International Conference on Machine Learning. PMLR, 2019.

1. The main Theorem (either Theorem 1 or Theorem 5) requires much more discussion. At least two aspects of discussion are missing: (i) what the results indicate, and (ii) how the results are compared to previous results quantitatively.
2. There are a lot of notations in Section 3.2, and I would be happy to see more explanations about what how these notations mean. For example, $L$ looks like a Lipschitz constant and $\mu$ looks like the coefficient of strong convexity. If the use of these notations are too technical, I would recommend putting them in the appendices, and the author could just mention the existence of these requirements in the main text.
3. The notations of $I_{k_1}^{(1)}$ $I_{k_2}^{(2)}$ are a bit confusing to me. I failed to find $I_{k_1}^{(1)}$ used anywhere in the main text. Also, the definition of the neural networks in Eq. (2) and how $I_{k_2}^{(2)}$ is used look a bit strange to me
4. The comments after Theorem 3 claims that Theorem 3 is a result of constrained optimization. However, boundedness is hardly enforced in practice, and I am skeptical about whether this is a contribution.
5. The motivation of the authors studying a 3-layer network is a bit unclear to me. I am expecting to see the technical contributions if the analysis of three-layer networks embodies some intrinsic difficulties (and the proof sketch should probably highlight the technical contributions). I am also curious about the method in this work can be extended to networks of arbitrary depth.