Comparison.  Our result is related to [1]}, which gave an NTK-based generalization bound for overparameterized two-layer ReLU neural networks. This result matches with theirs in the sense that we discover some underlying functions that are provably learnable. Examples of learnable target functions in [1]} include polynomials \(y = (\beta ^\top x)^p\) , non-linear activations \(y = \cos (\beta ^\top x) - 1\) , \(y = \tilde{\phi } (\beta ^\top x)\)  with \(\tilde{\phi } (z) = z \cdot \arctan (z / 2)\) , \(\Vert \beta \Vert  \le 1\) . Our result, furthermore, expands the target function class that is provably learnable since we only require \(\tilde{\phi }\)  to be Lipshcitz. In addition, they set the standard deviation of the initialization to be at most \(\mathcal {O} (1 / n)\) , whereas we use a different initialization with order \(\mathcal {O}(1 / \sqrt{d})\)  that is more often applied in practice.
Our result is also related to [3]}, which proved that overparameterized deep neural networks satisfy the PL condition. Further, we extend this work by analyzing the generalization based on the length of optimization trajectories.
