On Generalization in Bilevel Optimization with Overparameterized Models

Bilevel optimization provides a general framework for machine learning problems where an outer objective depends implicitly on the solution of an inner problem. While significant attention has been devoted to its algorithmic aspects, its generalization properties remain far less understood. In this paper, we address this gap by studying the case where the inner solution is approximated by an overparameterized two-layer ReLU neural network trained by gradient flow. Under the Neural Tangent Kernel (NTK) regime, we derive non-asymptotic generalization bounds that characterize how statistical accuracy depends jointly on the inner and outer sample sizes, as well as on the regularity of the target function and the complexity of the hypothesis space. We further establish convergence guarantees for a gradient-based bilevel algorithm, where the inner level is approximately solved by applying an early stopping strategy to the gradient flow training. Finally, we complement our theoretical analysis with numerical experiments showing that the bilevel structure induces an initialization-dependent implicit bias that enables feature learning at the inner level and yields performance improvements beyond NTK predictions.