Bilevel Optimization with Lower-Level Uniform Convexity: Theory and Algorithm
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911474361827328 |
|---|---|
| author | Wu, Yuman Gong, Xiaochuan Hao, Jie Liu, Mingrui |
| author_facet | Wu, Yuman Gong, Xiaochuan Hao, Jie Liu, Mingrui |
| contents | Bilevel optimization is a hierarchical framework where an upper-level optimization problem is constrained by a lower-level problem, commonly used in machine learning applications such as hyperparameter optimization. Existing bilevel optimization methods typically assume strong convexity or Polyak-Łojasiewicz (PL) conditions for the lower-level function to establish non-asymptotic convergence to a solution with small hypergradient. However, these assumptions may not hold in practice, and recent work~\citep{chen2024finding} has shown that bilevel optimization is inherently intractable for general convex lower-level functions with the goal of finding small hypergradients.
In this paper, we identify a tractable class of bilevel optimization problems that interpolates between lower-level strong convexity and general convexity via \emph{lower-level uniform convexity}. For uniformly convex lower-level functions with exponent $p\geq 2$, we establish a novel implicit differentiation theorem characterizing the hyperobjective's smoothness property. Building on this, we design a new stochastic algorithm, termed UniBiO, with provable convergence guarantees, based on an oracle that provides stochastic gradient and Hessian-vector product information for the bilevel problems. Our algorithm achieves $\widetilde{O}(ε^{-5p+6})$ oracle complexity bound for finding $ε$-stationary points. Notably, our complexity bounds match the optimal rates in terms of the $ε$ dependency for strongly convex lower-level functions ($p=2$), up to logarithmic factors. Our theoretical findings are validated through experiments on synthetic tasks and data hyper-cleaning, demonstrating the effectiveness of our proposed algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_00027 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Bilevel Optimization with Lower-Level Uniform Convexity: Theory and Algorithm Wu, Yuman Gong, Xiaochuan Hao, Jie Liu, Mingrui Optimization and Control Machine Learning Bilevel optimization is a hierarchical framework where an upper-level optimization problem is constrained by a lower-level problem, commonly used in machine learning applications such as hyperparameter optimization. Existing bilevel optimization methods typically assume strong convexity or Polyak-Łojasiewicz (PL) conditions for the lower-level function to establish non-asymptotic convergence to a solution with small hypergradient. However, these assumptions may not hold in practice, and recent work~\citep{chen2024finding} has shown that bilevel optimization is inherently intractable for general convex lower-level functions with the goal of finding small hypergradients. In this paper, we identify a tractable class of bilevel optimization problems that interpolates between lower-level strong convexity and general convexity via \emph{lower-level uniform convexity}. For uniformly convex lower-level functions with exponent $p\geq 2$, we establish a novel implicit differentiation theorem characterizing the hyperobjective's smoothness property. Building on this, we design a new stochastic algorithm, termed UniBiO, with provable convergence guarantees, based on an oracle that provides stochastic gradient and Hessian-vector product information for the bilevel problems. Our algorithm achieves $\widetilde{O}(ε^{-5p+6})$ oracle complexity bound for finding $ε$-stationary points. Notably, our complexity bounds match the optimal rates in terms of the $ε$ dependency for strongly convex lower-level functions ($p=2$), up to logarithmic factors. Our theoretical findings are validated through experiments on synthetic tasks and data hyper-cleaning, demonstrating the effectiveness of our proposed algorithm. |
| title | Bilevel Optimization with Lower-Level Uniform Convexity: Theory and Algorithm |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2603.00027 |