Bilevel optimization problems arise when an outer objective depends on the solution of an inner optimization problem, as in hyperparameter tuning and meta-learning. When both levels involve sums over many components, existing first-order methods often scale linearly with the number of components or require higher-order information. The new paper introduces SICBO, which uses only gradient information while avoiding such drawbacks.

SICBO combines a penalty approximation with variance-reduced corrections for the lower-level variables. Under componentwise lower strong convexity, the authors prove that the method finds an ε-accurate stationary point in Õ(N + √N κ^{7/2} ε^{-2}) component-gradient calls. This achieves square-root finite-sum dependence, a notable improvement over naive approaches, while preserving the best known deterministic condition-number exponent for smooth problems.

The key technical insight is a curvature-dependent bound on nonlinear correction errors, which permits epochs of length Õ(√(N/κ)) with batches of size Õ(√(Nκ)). A single-level reduction argument further shows that the dependence on N and ε is optimal up to logarithmic factors for fixed κ, indicating that SICBO is near-optimal in those parameters.