Improving bilevel optimization speed using only gradient information

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

Machine Learning

Summary

This work addresses a type of complex two-level optimization problem where the top level is nonconvex and the bottom level is strongly convex, occurring in many machine learning tasks. The authors propose a new algorithm, SICBO, that uses only gradient information (first-order oracles) to solve these problems faster than previous methods, especially when dealing with large datasets composed of many components. Their method balances corrections to the lower-level variables and achieves nearly optimal efficiency in how work scales with problem size and accuracy targets. This means fewer calculations are needed to reach good solutions while only relying on simpler and more accessible gradient data.

What this means in practice

Authors

Qihao Zhou, Shanshui Niu

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Φ(x)\|^2\le\varepsilon^2$ within $\tilde{O}(N+\sqrt{N}κ^{7/2}\varepsilon^{-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 $\tildeΘ(\sqrt{N/κ})$ with batches of size $\tildeΘ(\sqrt{Nκ})$. A single-level reduction shows that the dependence on $N$ and $\varepsilon$ is optimal up to logarithmic factors for fixed $κ$.
View PDFOpen arXiv