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

Abstract

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 $\mathbb{E}\Vert \nabla \Phi (x){\Vert }^2\le {\epsilon }^2$ within $\tilde{O}(N+\sqrt{N}{\kappa }^{7/2}{\epsilon }^{-2})$ component-gradient calls, where $N$ is the total number of components and $\kappa$ 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 $\tilde{\Theta }(\sqrt{N/\kappa })$ with batches of size $\tilde{\Theta }(\sqrt{N\kappa })$. A single-level reduction shows that the dependence on $N$ and $\epsilon$ is optimal up to logarithmic factors for fixed $\kappa$.

arXiv comment23 pages, 2 figures, 1 table