betaFeedback

WorksMathematics

On Generalization in Bilevel Least Squares with Overparameterized Neural Networks

Abstract

Bilevel optimization addresses machine learning problems in which the outer objective is a value function implicitly defined through the solution of an inner problem. While its algorithmic aspects are well developed, its generalization properties remain much less understood. In this paper, we study the generalization of inexact gradient methods when both objectives are least-squares regression problems and when the estimator of the value function's gradient, or hypergradient, is obtained by implicit differentiation in function space. This approach allows us to derive stationarity bounds for these methods in terms of the uniform generalization errors of the two regression functions needed to estimate the hypergradient. When these regression functions are defined as overparameterized two-layer ReLU networks trained by gradient flow with early stopping, we obtain explicit finite-sample bounds on these generalization errors in the Neural Tangent Kernel (NTK) regime. Combining these with our general inexact gradient analysis shows the effect of sample size on the overall convergence of the bilevel method. Numerical experiments on synthetic data illustrate our results. Beyond the NTK regime, further experiments reveal an initialization-dependent implicit bias induced by the bilevel structure, which can lead to feature learning at the inner level and overall performance improvements.

Introduction

Bilevel optimization is a class of hierarchical optimization problems in which the solution to an outer problem depends on the solution of an inner problem [28]. These methods naturally arise in numerous machine learning applications, including hyperparameter optimization [68, 37, 40], meta-learning [41, 38], neural architecture search [65], and reinforcement learning [51, 74]. The main challenge in bilevel problems is that the outer objective is defined implicitly through the solution of the inner problem, making both gradient computation and generalization analysis nontrivial [77].

Bilevel optimization poses two intertwined challenges: numerically, one must approximate not only the inner-level solution but also its sensitivity to outer variables in order to compute hypergradients [31, 13, 42]; and statistically, one must understand how the outer solution generalizes as the sample size grows [33, 54, 6]. A large body of work in the well-specified setting with a unique inner level solution addresses the numerical difficulty. Crucially, they typically require the inner objective to be strongly convex, which ensures a unique, smoothly varying inner solution and is therefore amenable to stability and convergence analyses [43, 1, 20]. Modern machine learning applications, however, usually employ neural networks as inner models [11, 92, 65]; the resulting inner problems are nonconvex and often overparameterized, so multiple inner solutions can exist and their dependence on the outer variables becomes ambiguous [90, 4]. This dependence can lead to instability, both because inner solutions may be non-unique and because small perturbations in the lower-level problem can induce large changes in the hypergradient [66, 7, 21]. As a consequence, strong generalization guarantees in the nonconvex setting are still largely limited, and the behavior of the resulting solutions on unseen data is still poorly understood. On the statistical side, most generalization results adopt a fixed finite-dimensional parametric viewpoint [29, 52]. This perspective becomes restrictive for overparameterized networks and nonparametric methods, where the effective parameter space (or feature map) can grow with the sample size and the parameters obtained at different sample sizes are not directly comparable. Bridging this gap therefore requires analytical tools that can handle (i) nonconvex inner landscapes with possibly multiple solutions arising from overparameterization, and (ii) nonparametric function spaces, such as a Reproducing Kernel Hilbert Space (RKHS), in order to obtain meaningful stability and generalization guarantees for bilevel learning in modern settings.

To address these challenges, the functional bilevel optimization framework, introduced in [78], provides a principled framework that shifts focus from parameter-centric approaches to a function-space perspective. By formulating the inner problem as an optimization over an infinite-dimensional Hilbert space of functions, such as an RKHS [33], this approach naturally accommodates multiple inner solutions, which frequently arise in overparameterized neural networks. A crucial advantage of this functional perspective is that it only requires strong convexity in the function space, rather than with respect to the parameter vector, the latter being rarely satisfied by modern neural networks [64]. This ensures the uniqueness of the inner solution for any outer variable, providing a well-defined dependency of the inner problem on the outer parameters and making stability and generalization analyses tractable in practice. In a related line of work, El Khoury et al. [33] provided generalization guarantees for functional bilevel optimization where the considered space is an RKHS. However, these results remain restrictive in the deep learning setting, as they do not accommodate highly expressive models such as overparameterized networks, leaving the question of generalization in bilevel optimization in such settings largely open.

In the present paper, we address this gap by studying Overparameterized Bilevel Optimization (OBO) problems in which the lower-level model is overparameterized, i.e., it contains more parameters than training samples and thus may have multiple global minimizers for the inner problem [90]. Formally, we consider problems of the form:

min⁡ω∈ΩF(ω):=Lout(ω,hω⋆)such thathω⋆=argmin⁡h∈H Lin(ω,h),\min_{\omega\in\Omega} \mathcal{F}(\omega) := L_{\mathrm{out}}(\omega,h_\omega^\star) \quad\text{such that} \quad h_\omega^\star= \underset{h \in\mathcal{H}}{\operatorname{argmin}}\ L_{\mathrm{in}}(\omega,h),

where Ω⊂Rd\Omega\subset\mathbb{R}^{d} is nonempty, compact, and convex, H\mathcal{H} is a Hilbert space of functions on X⊂Rp\mathcal{X} \subset\mathbb{R}^{p} taking values in Y⊂R\mathcal{Y} \subset\mathbb{R}, and Lin,Lout:Ω×H→RL_{\mathrm{in}},L_{\mathrm{out}}:\Omega\times\mathcal{H} \to\mathbb{R} denote the inner and outer objective functions, respectively. Throughout this work, both LinL_{\mathrm{in}} and LoutL_{\mathrm{out}} take the form of expected squared losses, a choice motivated by its practical relevance in machine learning [41, 77] and its ubiquity as a theoretical framework [23, 9].

Contributions. We study generalization in bilevel least squares, i.e., bilevel optimization problems where both levels are least-squares regressions. This setting is advantageous, as it expresses the hypergradient ∇F\nabla\mathcal{F} in terms of two regression functions, the inner solution and the outer regression function. The latter does not depend on the outer variable and can thus be estimated once and for all, which simplifies both the analysis and the algorithmic complexity. Our contributions are as follows.

  • (i) Convergence under inexact hypergradients. We bound the near-stationarity measure of a projected mini-batch stochastic gradient descent (SGD) method driven by a plug-in hypergradient estimator, in terms of the two estimators’ generalization errors (Theorem 2.4).

  • (ii) Generalization rates in the NTK regime. When these two estimators are two-layer ReLU networks with bias in both layers trained by gradient flow with early stopping, we derive finite-sample generalization bounds in the neural tangent kernel (NTK) regime (Proposition 3.1). These bounds hold in expectation, and uniformly over the outer variable for the inner estimator. To obtain them, we truncate the trained networks, i.e., set them to zero, on a rare event outside of which they provably remain in the NTK regime.

  • (iii) End-to-end sample complexity. Plugging the rates of (ii) into the bound of (i) yields the sample complexity of the bilevel method in the NTK regime (Corollary 3.2): the statistical error is governed by the slower of the two regression rates, so the inner and outer sample sizes should be balanced to prevent either level from becoming a bottleneck.

  • (iv) Implicit bias beyond the NTK regime. Synthetic experiments suggest an initialization-dependent implicit bias of the bilevel structure, which promotes inner-level feature learning and improves performance over the NTK regime.

Overparameterized bilevel optimization with squared losses

In this section, we introduce the problem under consideration, derive the expression of its hypergradient, and present the gradient-based algorithm we analyze along with its convergence guarantee.

Problem formulation

In many machine learning problems with a bilevel structure, the inner and outer objectives LinL_{\mathrm{in}} and LoutL_{\mathrm{out}} are typically expectations of pointwise losses over some data distributions. In this work, we instantiate both as squared losses, a choice that arises widely in regression [46] and causal inference [93, 56], and that allows us to develop our theoretical analysis in a simplified setting. Specifically, we consider:

Lin(ω,h)=12E(x,z)∼PXZ[∣h(x)−gω(z)∣2],Lout(h)=12E(x,y)∼PXY[∣h(x)−y∣2],(1)L_{\mathrm{in}}(\omega,h)=\frac{1}{2}\mathbb{E}_{(x,z)\sim\mathbb{P}_{XZ}}\left[\lvert h(x)-g_{\omega}(z)\rvert^{2}\right],\qquad L_{\mathrm{out}}(h)=\frac{1}{2}\mathbb{E}_{(x,y)\sim\mathbb{P}_{XY}}\left[\lvert h(x)-y\rvert^{2}\right], \tag*{(1)}

where gω:Z⊂Rr→Rg_{\omega}:\mathcal{Z}\subset\mathbb{R}^{r}\to\mathbb{R} is a model parameterized by ω\omega. Note that we omit the explicit dependence of LoutL_{\mathrm{out}} on ω\omega, as it occurs only implicitly through hω⋆h_{\omega}^{\star}. The distributions PXZ\mathbb{P}_{XZ} and PXY\mathbb{P}_{XY} are the marginals of a joint distribution P\mathbb{P} over triplets (x,y,z)(x,y,z) in X×Y×Z\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}, sharing the same marginal PX\mathbb{P}_{X} over elements x∈Xx\in\mathcal{X}. A natural space of functions H\mathcal{H} in this context is L2(X)L^{2}(\mathcal{X}), the space of square-integrable functions with respect to PX\mathbb{P}_{X}, defined on X\mathcal{X} and taking values in Y\mathcal{Y}. Provided that z↦gω(z)z\mapsto g_{\omega}(z) is square integrable, this problem is guaranteed to admit a unique solution to the inner problem, which takes the simple form of a conditional expectation, i.e., hω⋆(x)=EP[gω(z)∣x]h_{\omega}^{\star}(x)=\mathbb{E}_{\mathbb{P}}[g_{\omega}(z)\mid x], for any ω∈Ω\omega\in\Omega. In practice, such conditional expectation is only estimated, typically using a neural network, and thus requires careful analysis of the generalization error, which is a central challenge in this study. Typical applications of this problem in machine learning include instrumental variable regression and value function fitting in reinforcement learning, as further discussed in Appendix § 9. In what follows, ∥⋅∥\lVert\cdot\rVert denotes the Euclidean norm, ∥⋅∥L2(X)\lVert\cdot\rVert_{L^{2}(\mathcal{X})} denotes the L2L^{2} norm with respect to PX\mathbb{P}_{X}, and ⟨⋅,⋅⟩L2(X)\langle\cdot,\cdot\rangle_{L^{2}(\mathcal{X})} denotes the corresponding inner product. For notational simplicity, we will write P\mathbb{P} without subscript in the remainder of the paper whenever the meaning can be inferred from context.

Throughout the paper, we assume that the model gωg_{\omega} is uniformly smooth with bounded values and gradients, that the target space is bounded, that the input space is compact, and that PX\mathbb{P}_{X} admits a density pPp_{\mathbb{P}} with respect to the Lebesgue measure on X\mathcal{X} that is bounded above and bounded away from zero on some open ball. These assumptions are formalized below.

Assumption A. (Parameterization properties of gωg_{\omega}) There exist an open convex set U⊃ΩU\supset\Omega such that, for all z∈Zz\in\mathcal{Z}, the map (ω,z)↦gω(z)(\omega,z)\mapsto g_{\omega}(z) is differentiable on UU with respect to ω\omega and its partial derivative ∂ωgω(z)∈Rd\partial_{\omega}g_{\omega}(z)\in\mathbb{R}^{d} is LL-Lipschitz on UU. Moreover, there exist constants G,D>0G,D>0 such that:

sup⁡ω∈U,z∈Z∥∂ωgω(z)∥≤Gandsup⁡ω∈U,z∈Z∣gω(z)∣≤D.\sup_{\omega\in U,z\in\mathcal{Z}}\lVert\partial_{\omega}g_{\omega}(z)\rVert\le G \qquad\text{and}\qquad \sup_{\omega\in U,z\in\mathcal{Z}}\lvert g_{\omega}(z)\rvert\le D.

Assumption B. (Boundedness of Y\mathcal{Y}) The target space Y⊂R\mathcal{Y}\subset\mathbb{R} is bounded, i.e., there exists a constant B>0B>0 such that ∣y∣≤B\lvert y\rvert\le B for any y∈Yy\in\mathcal{Y}.

Assumption C. (Compactness of X\mathcal{X}) The input space X⊂Rp\mathcal{X}\subset\mathbb{R}^{p} is compact with a constant A>0A>0 such that ∥x∥≤A\lVert x\rVert\le A for any x∈Xx\in\mathcal{X}.

Assumption D. (Bounded density) There exists a constant MP>0M_{\mathbb{P}}>0 such that pP≤MPp_{\mathbb{P}}\le M_{\mathbb{P}}. Moreover, pPp_{\mathbb{P}} is bounded below by a positive constant on some open ball contained in X\mathcal{X}.

These are relatively mild conditions introduced mainly to simplify the analysis as further discussed in Appendix § 10. Additional assumptions will be introduced in later sections whenever needed.

Optimization algorithm for solving (OBO)

We aim to solve (OBO) with a gradient-based algorithm, driven by the hypergradient ∇F\nabla\mathcal{F}. The following result establishes the differentiability of F\mathcal{F} and provides an explicit expression for ∇F\nabla\mathcal{F}, by applying the functional implicit differentiation theorem [78 Proposition 2.2].

Proposition 2.1 (Hypergradient of F\mathcal{F}). Under Assumptions A\mathbf{A} and B\mathbf{B}, F\mathcal{F} is differentiable on UU, and its hypergradient is given, for any ω∈U\omega\in U, by:

∇F(ω)=−EP[∂ωgω(z)aω⋆(x)]∈Rd,(2)\nabla\mathcal{F}(\omega)=-\mathbb{E}_{\mathbb{P}}\left[\partial_{\omega}g_{\omega}(z)a_{\omega}^{\star}(x)\right]\in\mathbb{R}^{d}, \tag*{(2)}

where aω⋆=−hω⋆+b⋆∈L2(X)a_{\omega}^{\star}=-h_{\omega}^{\star}+b^{\star}\in L^{2}(\mathcal{X}) is the adjoint function, hω⋆:x↦EP[gω(z)∣x]h_{\omega}^{\star}:x\mapsto\mathbb{E}_{\mathbb{P}}[g_{\omega}(z)\mid x] is the inner solution, and b⋆:x↦EP[y∣x]b^{\star}:x\mapsto\mathbb{E}_{\mathbb{P}}[y\mid x] is the regression function, defined as the minimizer of LoutL_{\mathrm{out}} over L2(X)L^{2}(\mathcal{X}). Moreover, F\mathcal{F} is L\mathcal{L}-smooth on UU, in particular on Ω\Omega, with L:=G2+L(D+B)\mathcal{L}:=G^{2}+L(D+B) where the constants GG, LL, DD and BB are defined in Assumptions A\mathbf{A} and B\mathbf{B}.

While the expression in Equation (2) is exact, it requires full knowledge of P\mathbb{P}, hω⋆h_{\omega}^{\star}, and b⋆b^{\star}, which are unavailable in practice, making it necessary to estimate ∇F(ω)\nabla\mathcal{F}(\omega) from data. Its structure is particularly appealing: since ∂ωgω(z)\partial_{\omega}g_{\omega}(z) is known, the statistical difficulty reduces entirely to approximating the adjoint function aω⋆a_{\omega}^{\star}, which itself decomposes into two regression functions b⋆b^{\star} and hω⋆h_{\omega}^{\star}. This structure is key to our analysis, as it allows us to approximate hω⋆h_{\omega}^{\star} and b⋆b^{\star} independently and combine their estimates to obtain an approximation of the hypergradient using finite-sample estimates.

References

  1. [1]P. Ablin, G. Peyré, and T. Moreau. Super-efficiency of automatic differentiation for functions defined as a minimum. In International Conference on Machine Learning (ICML), 2020.arxiv.org/abs/2002.03722
  2. [2]R. A. Adams and J. J. Fournier. Sobolev Spaces, volume 140. Elsevier, 2003.
  3. [3]M. S. Agranovich. Sobolev Spaces, Their Generalizations, and Elliptic Problems in Smooth and Lipschitz Domains. Springer Monographs in Mathematics. Springer, Cham, 2015.DOI
  4. [4]Z. Allen-Zhu, Y. Li, and Z. Song. A Convergence Theory for Deep Learning via Over-Parameterization. In International Conference on Machine Learning (ICML), 2019.
  5. [5]J. D. Angrist and G. W. Imbens. Two-stage least squares estimation of average causal effects in models with variable treatment intensity. Journal of the American Statistical Association, 90 (430):431–442, 1995.DOI
  6. [6]M. Arbel and J. Mairal. Amortized Implicit Differentiation for Stochastic Bilevel Optimization. In International Conference on Learning Representations (ICLR), 2022.arxiv.org/abs/2111.14580
  7. [7]M. Arbel and J. Mairal. Non-convex bilevel games with critical point selection maps. In Advances in Neural Information Processing Systems (NeurIPS), 2022.arxiv.org/abs/2207.04888
  8. [8]N. Aronszajn. Theory of reproducing kernels. Transactions of the American Mathematical Society, 68(3):337–404, 1950.
  9. [9]S. Arora, S. S. Du, W. Hu, Z. Li, R. R. Salakhutdinov, and R. Wang. On Exact Computation with an Infinitely Wide Neural Net. In Advances in Neural Information Processing Systems (NeurIPS), 2019.arxiv.org/abs/1904.11955
  10. [10]K. Atkinson and W. Han. Spherical harmonics and approximations on the unit sphere: an introduction. Lecture Notes in Mathematics, volume 2044. Springer Heidelberg, 2012.DOI
  11. [11]F. Bao, C. Li, K. Xu, H. Su, J. Zhu, and B. Zhang. Bi-level score matching for learning energy-based latent variable models. In Advances in Neural Information Processing Systems (NeurIPS), 2020.arxiv.org/abs/2010.07856
  12. [12]J. A. Barceló, T. Luque, and S. Pérez-Esteva. Characterization of Sobolev spaces on the sphere. Journal of Mathematical Analysis and Applications, 491(1):124240, 2020.arxiv.org/abs/1907.01571
  13. [13]A. G. Baydin, B. A. Pearlmutter, A. A. Radul, and J. M. Siskind. Automatic differentiation in machine learning: a survey. Journal of Machine Learning Research (JMLR), 18(153):1–43, 2018.
  14. [14]A. Beck. First-order methods in optimization. SIAM, 2017.DOI
  15. [15]A. Behzadan and M. Holst. Sobolev-Slobodeckij Spaces on Compact Manifolds, Revisited. Mathematics, 10(3):522, 2022.arxiv.org/abs/1704.07930
  16. [16]M. Belkin, D. Hsu, S. Ma, and S. Mandal. Reconciling modern machine-learning practice and the classical bias–variance trade-off. Proceedings of the National Academy of Sciences, 116 (32):15849–15854, 2019.DOI
  17. [17]J. Bergh and J. Löfström. Interpolation Spaces: An Introduction, volume 223 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag, Berlin, 1976.
  18. [18]A. Bietti and J. Mairal. On the inductive bias of neural tangent kernels. In Advances in Neural Information Processing Systems (NeurIPS), 2019.arxiv.org/abs/1905.12173
  19. [19]G. Blanchard and N. Mücke. Optimal Rates for Regularization of Statistical Inverse Learning Problems. Foundations of Computational Mathematics, 18(4):971–1013, 2018.arxiv.org/abs/1604.04054
  20. [20]M. Blondel, Q. Berthet, M. Cuturi, R. Frostig, S. Hoyer, F. Llinares-López, F. Pedregosa, and J.-P. Vert. Efficient and modular implicit differentiation. In Advances in Neural Information Processing Systems (NeurIPS), 2022.arxiv.org/abs/2105.15183
  21. [21]J. Bolte, Q.-T. Lê, E. Pauwels, and S. Vaïter. Geometric and computational hardness of bilevel programming. Mathematical Programming, 215(1):539–574, 2026.arxiv.org/abs/2407.12372
  22. [22]S. Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4):231–357, 2015.arxiv.org/abs/1405.4980
  23. [23]A. Caponnetto and E. De Vito. Optimal Rates for the Regularized Least-Squares Algorithm. Foundations of Computational Mathematics, 7(3):331–368, 2007. doi: 10.1007/s10208-006-0196-8.DOI
  24. [24]G. Chen, Y. Li, and Q. Lin. On the Impacts of the Random Initialization in the Neural Tangent Kernel Theory. In Advances in Neural Information Processing Systems (NeurIPS), 2024.arxiv.org/abs/2410.05626
  25. [25]Z. Chen, A. Nitanda, A. Gretton, and T. Suzuki. Towards a Unified Analysis of Neural Networks in Nonparametric Instrumental Variable Regression: Optimization and Generalization. arXiv preprint arXiv:2511.14710, 2025.arxiv.org/abs/2511.14710
  26. [26]L. Chizat, E. Oyallon, and F. Bach. On Lazy Training in Differentiable Programming. In Advances in Neural Information Processing Systems (NeurIPS), 2019.arxiv.org/abs/1812.07956
  27. [27]Y. Cho and L. Saul. Kernel Methods for Deep Learning. In Advances in Neural Information Processing Systems (NIPS), 2009.
  28. [28]B. Colson, P. Marcotte, and G. Savard. An overview of bilevel optimization. Annals of Operations Research, 153:235–256, 2007.DOI
  29. [29]M. Dagréou, P. Ablin, S. Vaïter, and T. Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. In Advances in Neural Information Processing Systems (NeurIPS), 2022.arxiv.org/abs/2201.13409
  30. [30]D. Davis and D. Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 29(1):207–239, 2019.arxiv.org/abs/1803.06523
  31. [31]J. Domke. Generic methods for optimization-based modeling. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2012.
  32. [32]D. E. Edmunds and H. Triebel. Function spaces, entropy numbers, differential operators, volume 120. Cambridge University Press Cambridge, 1996.
  33. [33]F. El Khoury, É. Pauwels, S. Vaiter, and M. Arbel. Learning Theory for Kernel Bilevel Optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2025.arxiv.org/abs/2502.08457
  34. [34]F. El Khoury, H. Zenati, N. Kallus, M. Arbel, and A. Bibaut. Parametric Rates for Nonparametric Conditional-Moment Bilevel Optimization. arXiv preprint arXiv:2605.21341, 2026.arxiv.org/abs/2605.21341
  35. [35]O. Elkabtz and N. Cohen. Continuous vs. Discrete Optimization of Deep Neural Networks. In Advances in Neural Information Processing Systems (NeurIPS), 2021.arxiv.org/abs/2107.06608
  36. [36]L. C. Evans and R. F. Gariepy. Measure Theory and Fine Properties of Functions. CRC Press, Boca Raton, FL, revised edition, 2015. ISBN 9781482224393.
  37. [37]M. Feurer and F. Hutter. Hyperparameter Optimization. In Automated Machine Learning: Methods, Systems, Challenges, The Springer Series on Challenges in Machine Learning, pages 3–33. Springer International Publishing, 2019.DOI
  38. [38]C. Finn, P. Abbeel, and S. Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In International Conference on Machine Learning (ICML), 2017.arxiv.org/abs/1703.03400
  39. [39]S. Fischer and I. Steinwart. Sobolev Norm Learning Rates for Regularized Least-Squares Algorithms. Journal of Machine Learning Research (JMLR), 21(205):1–38, 2020.
  40. [40]L. Franceschi, M. Donini, P. Frasconi, and M. Pontil. Forward and reverse gradient-based hyperparameter optimization. In International Conference on Machine Learning (ICML), 2017.arxiv.org/abs/1703.01785
  41. [41]L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International Conference on Machine Learning (ICML), 2018.
  42. [42]S. Ghadimi and M. Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02246, 2018.arxiv.org/abs/1802.02246
  43. [43]S. Gould, B. Fernando, A. Cherian, P. Anderson, R. S. Cruz, and E. Guo. On differentiating parameterized argmin and argmax problems with application to bi-level optimization. arXiv preprint arXiv:1607.05447, 2016.arxiv.org/abs/1607.05447
  44. [44]P. Grisvard. Elliptic Problems in Nonsmooth Domains, volume 24 of Monographs and Studies in Mathematics. Pitman (Advanced Publishing Program), Boston, 1985.
  45. [45]M. Haas, D. Holzmüller, U. von Luxburg, and I. Steinwart. Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimension. In Advances in Neural Information Processing Systems (NeurIPS), 2023.arxiv.org/abs/2305.14077
  46. [46]T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning. Springer, 2009.
  47. [47]T. Hastie, A. Montanari, S. Rosset, and R. J. Tibshirani. Surprises in High-Dimensional Ridgeless Least Squares Interpolation. Annals of Statistics, 50(2):949–986, 2022.DOI
  48. [48]D. Hendrycks and K. Gimpel. Gaussian Error Linear Units (GELUs). arXiv preprint arXiv:1606.08415, 2016.
  49. [49]D. P. Hewett and A. Moiola. A note on properties of the restriction operator on Sobolev spaces. Journal of Applied Analysis, 23(1):1–8, 2017.DOI
  50. [50]S. Hofmann, M. Mitrea, and M. Taylor. Geometric and transformational properties of Lipschitz domains, Semmes-Kenig-Toro domains, and other classes of finite perimeter domains. The Journal of Geometric Analysis, 17(4):593–647, 2007.
  51. [51]M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 33(1):147–180, 2023.DOI
  52. [52]Y. Hu, J. Wang, Y. Xie, A. Krause, and D. Kuhn. Contextual Stochastic Bilevel Optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2023.arxiv.org/abs/2310.18535
  53. [53]A. Jacot, F. Gabriel, and C. Hongler. Neural Tangent Kernel: Convergence and Generalization in Neural Networks. In Advances in Neural Information Processing Systems (NeurIPS), 2018.arxiv.org/abs/1806.07572
  54. [54]K. Ji, J. Yang, and Y. Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning (ICML), 2021.arxiv.org/abs/2010.07962
  55. [55]K. Karhadkar, M. Murray, and G. Montúfar. Bounds for the smallest eigenvalue of the NTK for arbitrary spherical data of arbitrary dimension. In Advances in Neural Information Processing Systems (NeurIPS), 2024.arxiv.org/abs/2405.14630
  56. [56]J. Kim, D. Meunier, A. Gretton, T. Suzuki, and Z. Li. Optimality and Adaptivity of Deep Neural Features for Instrumental Variable Regression. In International Conference on Learning Representations (ICLR), 2025.arxiv.org/abs/2501.04898
  57. [57]T. Kumar, B. Bordelon, S. J. Gershman, and C. Pehlevan. Grokking as the transition from lazy to rich training dynamics. In International Conference on Learning Representations (ICLR), 2024.arxiv.org/abs/2310.06110
  58. [58]J. Lai, M. Xu, R. Chen, and Q. Lin. Generalization Ability of Wide Neural Networks on ℝ. arXiv preprint arXiv:2302.05933, 2023.arxiv.org/abs/2302.05933
  59. [59]J. Lee, L. Xiao, S. Schoenholz, Y. Bahri, R. Novak, J. Sohl-Dickstein, and J. Pennington. Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent. In Advances in Neural Information Processing Systems (NeurIPS), 2019.DOI
  60. [60]J. M. Lee. Introduction to Smooth Manifolds. Springer, 2 edition, 2013.
  61. [61]S. Li. Concise Formulas for the Area and Volume of a Hyperspherical Cap. Asian Journal of Mathematics and Statistics, pages 66–70, 2011.DOI
  62. [62]Y. Li, Z. Yu, G. Chen, and Q. Lin. On the Eigenvalue Decay Rates of a Class of Neural-Network Related Kernel Functions Defined on General Domains. Journal of Machine Learning Research (JMLR), 25(82):1–47, 2024.arxiv.org/abs/2305.02657
  63. [63]J. Lin, A. Rudi, L. Rosasco, and V. Cevher. Optimal rates for spectral algorithms with least-squares regression over Hilbert spaces. Applied and Computational Harmonic Analysis, 48(3):868–890, 2020.
  64. [64]C. Liu, L. Zhu, and M. Belkin. Loss landscapes and optimization in over-parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59:85–116, 2022.arxiv.org/abs/2003.00307
  65. [65]H. Liu, K. Simonyan, and Y. Yang. DARTS: Differentiable architecture search. In International Conference on Learning Representations (ICLR), 2019.arxiv.org/abs/1806.09055
  66. [66]R. Liu, Y. Liu, S. Zeng, and J. Zhang. Towards gradient-based bilevel optimization with non-convex followers and beyond. In Advances in Neural Information Processing Systems (NeurIPS), 2021.arxiv.org/abs/2110.00455
  67. [67]K. Lyu, J. Jin, Z. Li, S. S. Du, J. D. Lee, and W. Hu. Dichotomy of Early and Late Phase Implicit Biases Can Provably Induce Grokking. In International Conference on Learning Representations (ICLR), 2024.arxiv.org/abs/2311.18817
  68. [68]D. Maclaurin, D. Duvenaud, and R. Adams. Gradient-based hyperparameter optimization through reversible learning. In International Conference on Machine Learning (ICML), 2015.DOI
  69. [69]M. A. Mohamadi, Z. Li, L. Wu, and D. J. Sutherland. Why Do You Grok? A Theoretical Analysis on Grokking Modular Addition. In International Conference on Machine Learning (ICML), 2024.arxiv.org/abs/2407.12332
  70. [70]J.-J. Moreau. Proximité et dualité dans un espace hilbertien. Bulletin de la Société mathématique de France, 93:273–299, 1965.DOI
  71. [71]R. Munos and C. Szepesvári. Finite-Time Bounds for Fitted Value Iteration. Journal of Machine Learning Research (JMLR), 9(27):815–857, 2008.DOI
  72. [72]Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Springer Science & Business Media, 2013.
  73. [73]W. K. Newey and J. L. Powell. Instrumental Variable Estimation of Nonparametric Models. Econometrica, 71(5):1565–1578, 2003. doi: 10.1111/1468-0262.00459.DOI
  74. [74]E. Nikishin, R. Abachi, R. Agarwal, and P.-L. Bacon. Control-oriented model-based reinforcement learning with implicit differentiation. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 7886–7894, 2022.
  75. [75]A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, et al. PyTorch: An Imperative Style, High-Performance Deep Learning Library. In Advances in Neural Information Processing Systems (NeurIPS), 2019.arxiv.org/abs/1912.01703
  76. [76]D. Patel and E.-V. Vlatakis-Gkaragkounis. Solving Neural Min-Max Games: The Role of Architecture, Initialization & Dynamics. In Advances in Neural Information Processing Systems (NeurIPS), 2025.arxiv.org/abs/2512.00389
  77. [77]F. Pedregosa. Hyperparameter optimization with approximate gradient. In International Conference on Machine Learning (ICML), 2016.arxiv.org/abs/1602.02355
  78. [78]I. Petrulionytė, J. Mairal, and M. Arbel. Functional Bilevel Optimization for Machine Learning. In Advances in Neural Information Processing Systems (NeurIPS), 2024.arxiv.org/abs/2403.20233
  79. [79]A. Power, Y. Burda, H. Edwards, I. Babuschkin, and V. Misra. Grokking: Generalization beyond overfitting on small algorithmic datasets. arXiv preprint arXiv:2201.02177, 2022.arxiv.org/abs/2201.02177
  80. [80]A. Rahimi and B. Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems (NIPS), 2007.
  81. [81]P. Ramachandran, B. Zoph, and Q. V. Le. Searching for activation functions. arXiv preprint arXiv:1710.05941, 2017.arxiv.org/abs/1710.05941
  82. [82]G. Raskutti, M. J. Wainwright, and B. Yu. Early Stopping and Non-Parametric Regression: An Optimal Data-Dependent Stopping Rule. Journal of Machine Learning Research (JMLR), 15 (1):335–366, 2014.arxiv.org/abs/1306.3574
  83. [83]R. T. Rockafellar and R. J.-B. Wets. Variational Analysis, volume 317 of Grundlehren der mathematischen Wissenschaften. Springer, Berlin, 1998.DOI
  84. [84]T. Runst and W. Sickel. Sobolev Spaces of Fractional Order, Nemytskij Operators, and Nonlinear Partial Differential Equations. De Gruyter, Berlin, New York, 1996. ISBN 9783110812411. doi: 10.1515/9783110812411.DOI
  85. [85]E. M. Stein. Singular Integrals and Differentiability Properties of Functions, volume 2. Princeton University Press, 1970.
  86. [86]I. Steinwart and A. Christmann. Support Vector Machines. Information Science and Statistics. Springer New York, New York, NY, USA, 2008.
  87. [87]I. Steinwart and C. Scovel. Mercer’s theorem on general domains: On the interaction between measures, kernels, and RKHSs. Constructive Approximation, 35(3):363–417, 2012.DOI
  88. [88]H. Triebel. Theory of Function Spaces II, volume 84 of Monographs in Mathematics. Birkhäuser, Basel, 1992. ISBN 978-3-7643-2639-5. doi: 10.1007/978-3-0346-0419-2.DOI
  89. [89]R. Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2 edition, 2026.
  90. [90]P. Vicol, J. P. Lorraine, F. Pedregosa, D. Duvenaud, and R. B. Grosse. On Implicit Bias in Overparameterized Bilevel Optimization. In International Conference on Machine Learning (ICML), 2022.arxiv.org/abs/2212.14032
  91. [91]B. Woodworth, S. Gunasekar, J. D. Lee, E. Moroshko, P. Savarese, I. Golan, D. Soudry, and N. Srebro. Kernel and Rich Regimes in Overparameterized Models. In Conference on Learning Theory (COLT), 2020.
  92. [92]Q. Xiao, H. Yuan, A. Saif, G. Liu, R. Kompella, M. Wang, and T. Chen. A First-order Generative Bilevel Optimization Framework for Diffusion Models. In International Conference on Machine Learning (ICML), 2025.arxiv.org/abs/2502.08808
  93. [93]L. Xu, Y. Chen, S. Srinivasan, N. De Freitas, A. Doucet, and A. Gretton. Learning Deep Features in Instrumental Variable Regression. In International Conference on Learning Representations (ICLR), 2021.arxiv.org/abs/2010.07154
  94. [94]G. Yang and E. J. Hu. Tensor Programs IV: Feature Learning in Infinite-Width Neural Networks. In International Conference on Machine Learning (ICML), 2021.
  95. [95]Y. Yao, L. Rosasco, and A. Caponnetto. On Early Stopping in Gradient Descent Learning. Constructive Approximation, 26(2):289–315, 2007.DOI
  96. [96]H. Zhang, Y. Li, and Q. Lin. On the Optimality of Misspecified Spectral Algorithms. Journal of Machine Learning Research (JMLR), 25(188):1–50, 2024.arxiv.org/abs/2303.14942

Paper details

vlnc:W_9gxa7g7h
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents