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}\|\nabla\Phi(x)\|^2\le\varepsilon^2$ within $\tilde{O}(N+\sqrt{N}\kappa^{7/2}\varepsilon^{-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 $\varepsilon$ is optimal up to logarithmic factors for fixed $\kappa$.

Optimization and Control (math.OC); Machine Learning (cs.LG); Machine Learning (stat.ML)

arXiv:2610.24538 [math.OC]

(or arXiv:2610.24538v1 [math.OC] for this version)

https://doi.org/10.48550/arXiv.2610.24538 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.