Accelerating Finite-Sum Bilevel Optimization with Fully First-Order Oracles

We study nonconvex--strongly-convex bilevel optimization with finite-sum objectives and fully first-order oracles. We propose Sampled Implicit Corrections for Bilevel Optimization (SICBO), which combines a penalty approximation with variance-reduced corrections for the lower-level variables. Under componentwise lower strong convexity, SICBO finds a point x satisfying E| gradΦ(x)| 2 epsilon squared within (N+ sqrt N κ 7/2 epsilon-2) component-gradient calls, where N is the total number of components and κ is the normalized lower-level condition number. The bound achieves square-root finite-sum dependence using only gradients and preserves the best known deterministic fully first-order condition-number exponent for smooth problems. Our improvement follows from a curvature-dependent bound for nonlinear correction errors, which permits epochs of length Θ(sqrt N/κ) with batches of size Θ(sqrt Nκ). A single-level reduction shows that the dependence on N and epsilon is optimal up to logarithmic factors for fixed κ.