A LOCAL POLYAK-ŁOJASIEWICZ AND DESCENT LEMMA OF GRADIENT DESCENT FOR OVERPARAMETERIZED LINEAR MODELS

To [7VmP], we thank the reviewer for the thoughtful comments. We address the questions below.

1. Verification of $\alpha_1>0$. Please see our response to all reviewers.
2. Missing experimental validation for the linear convergence rate. Please see Appendix G.2 where we numerically verify that Problem(2) trained via gradient descent achieves linear convergence under different choices of the hyperparameters. Moreover, we show numerically the theoretical upper bound follows the actual loss well.
3. How to estimate \eta_\max? In Appendix E, we show \eta_\max=\min(\eta_0^{(1)}, \eta_0^{(2)}, \log(1+\frac{\alpha_1}{2\alpha_2}))^{1/c}. Thus, \eta_\max depends on initial weights, $c, d, \mu, K$, and $L(0)$. One can see that if $L(0), K, \beta_2$and $c, d$ increase or $\mu, \frac{\alpha_1}{\alpha_2}$ decrease, then \eta_\max will decrease accordingly. To numerically solve for \eta_\max, one can use existing equation solver to solve eq(87) and eq(88) to get $\eta_0^{(1)}, \eta_0^{(2)}$. Then, \eta_\max can be estimated by the minimum value by its definition.
4. Novelty compared with existing literature. We thank the reviewer for pointing us to these results (Nguyen et al., 2020; Radhakrishanan et al., 2020). We have added (Nguyen et al., 2020) in the "Related Work" section. In (Radhakrishanan et al., 2020), the authors study the convergence of autoencoder which is less relevant to our work. Thus, we won't cite it in the paper. We clarify the novelty of this work compared to existing results as follows. Existing results that study the convergence of deep linear networks (Arora et al., 2018; Du et al., 2018a) or deep nonlinear networks (Nguyen et al., 2020; Du et al., 2018; Jacot et al., 2018; Liu et al., 2022; Lee et al., 2019) all make unrealistic assumptions. Specifically, the NTK analysis[1,5,6,7,8] is done under rather unrealistic assumptions such as extremely large width and large Gaussian initialization. Further, (Chizat et al., 2019) show that the performance of neural networks degrades when trained in the NTK regime, thus the NTK analysis does not capture the behavior of neural networks used in practice. On the other hand, (Arora et al., 2018; Du et al., 2018a) focus on deep linear networks under the assumption that there is sufficient margin at initialization. This requires the initialization to be close to optimal, which is rarely seen in practice. Therefore, both lines of work make some unrealistic assumptions. The goal of our work is precisely to relax these unrealistic assumptions by considering general initializations with either sufficient margin or sufficient imbalance, which subsumes NTK initialization, mean-field initialization and spectral initialization. Moreover, our work assumes the width is larger than or equal to the input and output dimensions, which can be considered as a "mild-overparameterization" compared with the NTK analysis. Therefore, our work is an important stepping stone to analyzing deep networks of finite width under general initialization, which is not covered by existing results.

[1]Nguyen, Quynh N., and Marco Mondelli. "Global convergence of deep networks with one wide layer followed by pyramidal topology." Advances in Neural Information Processing Systems 33 (2020): 11961-11972.

[2]Radhakrishnan, Adityanarayanan, Mikhail Belkin, and Caroline Uhler. "Overparameterized neural networks implement associative memory." Proceedings of the National Academy of Sciences 117.44 (2020): 27162-27170.

[3]Arora, Sanjeev, et al. "A convergence analysis of gradient descent for deep linear neural networks." arXiv preprint arXiv:1810.02281 (2018).

[4]Du, Simon S., Wei Hu, and Jason D. Lee. "Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced." Advances in neural information processing systems 31 (2018).

[5]Du, Simon S., et al. "Gradient descent provably optimizes over-parameterized neural networks." arXiv preprint arXiv:1810.02054 (2018).

[6]Jacot, Arthur, Franck Gabriel, and Clément Hongler. "Neural tangent kernel: Convergence and generalization in neural networks." Advances in neural information processing systems 31 (2018).

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

[8]Lee, Jaehoon, et al. "Wide neural networks of any depth evolve as linear models under gradient descent." Advances in neural information processing systems 32 (2019).

[9]Chizat, Lenaic, Edouard Oyallon, and Francis Bach. "On lazy training in differentiable programming." Advances in neural information processing systems 32 (2019).

To [m2Ce], we thank the reviewer for the thoughtful comments. We address the questions below.

1. Incremental w.r.t. (Xu et al., 2023). Please see our response to all reviewers.
2. Verification of $\alpha_1>0$. Please see our response to all reviewers.
3. Missing reference: we thank the reviewer for pointing us to this work. We have added the reference to Karimi et. al. 2016 in the "Related Work" section.
4. Cosmetics: we thank the reviewer for the suggestions. We have modified the paper accordingly. For Descent lemma, we treated it as a noun and that's why we cite it as "Descent lemma" instead of "the Descent lemma".

[1]Xu, Ziqing, et al. "Linear Convergence of Gradient Descent for Finite Width Over-parametrized Linear Networks with General Initialization." International Conference on Artificial Intelligence and Statistics. PMLR, 2023.

To [KJ6o]: we thank the reviewer for the thoughtful comments. We address the questions below.

1. Incremental contribution compared with (Arora et al., 2018). We respectfully disagree that our work is an incremental contribution compared with (Arora et al., 2018). In the work of (Arora et al., 2018), the authors provide the convergence rate of deep linear networks trained with gradient descent. While deep linear networks are indeed more general, (Arora et al., 2018) focus on deep linear networks under the assumption that there is sufficient margin and small imbalance at initialization. This requires the initialization to be close to optimal, which is rarely seen in practice. Moreover, standard Gaussian initialization, Xavier initialization, and He initialization all have large imbalance at initialization. Therefore, the convergence in (Arora et al., 2018) is proved under some unrealistic assumptions that cannot be satisfied by practical initialization schemes. The goal of our work is precisely to relax these unrealistic assumptions by considering general initialization with either sufficient margin or sufficient imbalance. Therefore, our work is an important stepping stone to analyzing deep networks of finite width under general initialization.
2. Generalizability to deep linear networks. Extending the results of this work to deep linear networks trained via gradient descent is the next step, and the analysis can be done in the same spirit as it was done in this work. In the case of two-layer linear networks, we present a framework showing that one can use the imbalance and margin to bound the singular values of \mathcal{T} during the training. In the case of deep linear networks, $\mathcal{T}$ takes a different form depending on all layer weights which is more complicated than the two-layer case. On the other hand, we have $L-1$ imbalances for L-layer deep linear networks. As long as one can bound the $\mathcal{T}$ for deep linear networks using $L-1$ imbalances and the margin, the convergence rate of deep linear networks is derived. We refer the reviewer to (Min et al., 2023) which proves the convergence of deep linear networks trained via gradient flow in a similar spirit as described above.
3. Verification of $\alpha_1>0$. Please see our response to all reviewers.

[1]Arora, Sanjeev, et al. "A convergence analysis of gradient descent for deep linear neural networks." arXiv preprint arXiv:1810.02281 (2018).

[2] Min, H., Vidal, R. and Mallada, E., 2023. On the Convergence of Gradient Flow on Multi-layer Linear Models.

To [PUum]: we thank the reviewer for the thoughtful comments. We address the question below.

1. Is Lemma 3.1 the main contribution of this work? We respectfully disagree that Lemma 3.1 is the main (technical) contribution of this work compared with (Xu et al., 2023). The main technical contributions of this work consist of (a) a novel local smoothness inequality and Descent lemma (See Theorem 3.1), (b) a tighter convergence rate for overparametrized models with a general loss (See Theorem 3.2), and (b) novel spectral bounds for $\mathcal{T}$ (See Lemma 3.1). Specifically, Theorem 3.1 presents a novel local Descent lemma and PL inequality of the overparametrized model to characterize the local rate of decrease, while prior results (Arora et al., 2018; Du et al., 2018a; Xu et al., 2023) are based on Descent lemma and PL inequality of the non-overparametrized model. In Appendix C, we show that Theorem 3.1 leads to a faster rate of decrease compared with the results in (Arora et al., 2018; Du et al., 2018a; Xu et al., 2023). Based on Theorem 3.1, it suffices to bound the singular values of \mathcal{T} and W to derive the linear convergence of the overparametrized model. Lemma 3.1, which is the second main contribution of this work, shows when the step size satisfies certain constraints that allow the step sizes to grow during the training, one can present uniform spectral bounds for $\mathcal{T}$ and W using the initial weights and initial step size. In (Xu et al., 2023), the authors show that the uniform spectral bounds not only depend on initial weights but also on some auxiliary constants $c_1, c_2$ under constant upper bound on the step sizes. Thus, the requirement in Lemma 3.1 admits a wider choice of the step sizes. Moreover, (Xu et al., 2023) show linear convergence under restrictive assumptions on $c_1$ and $c_2$, which leads to looser uniform spectral bounds on $\mathcal{T}$ compared with this work. Finally, Theorem 3.2, which is based on Theorem 3.1 and Lemma 3.1, shows linear convergence of the adaptive step size scheme. In Appendix G, we numerically verify that the adaptive step size scheme proposed in this work is almost ten times faster than the one proposed in (Xu et al., 2023) and the backtracking line search.

2. Significance of studying matrix factorization. Please see our response to all reviewers.

3. Improvement of the presentation of the prior work. We thank the reviewer for the suggestion. We modified the "Related Work" section to highlight that (Xu et al., 2023) also designed an adaptive step size scheme to accelerate the convergence, and the convergence rate of the adaptive step size scheme heavily relies on two auxiliary constants which is a slower rate compared with this work.

[1]Xu, Ziqing, et al. "Linear Convergence of Gradient Descent for Finite Width Over-parametrized Linear Networks with General Initialization." International Conference on Artificial Intelligence and Statistics. PMLR, 2023.