Bilevel Optimization with Lower-Level Uniform Convexity: Theory and Algorithm

• URL: http://arxiv.org/abs/2603.00027v1
• Date: Wed, 04 Feb 2026 03:09:52 GMT
• Title: Bilevel Optimization with Lower-Level Uniform Convexity: Theory and Algorithm
• Abstract summary: Bilevel optimization is a hierarchical framework where an upper-level problem is constrained by a lower-level problem.<n>Existing bilevel optimization methods assume strong convexity or Polyak-ojasiewicz (PL) conditions for the lower-level function.<n>We show that bilevel optimization is inherently intractable for general convex lower-level functions with the goal of finding small hypergradients.
• Score: 28.40732302523826
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization [68.22688819802622]
  We propose a new state-of-the-art complexity of $O(/epsilon)$ for finding an (nearly) $'level KKT solution.<n>By applying our hinge-of-the-art complexity of $O(/epsilon)$ for finding an (nearly) $'level KKT solution, we achieve a new state-of-the-art complexity of $O(/epsilon)$ for finding an (nearly) $'level KKT solution.
  arXiv  Detail & Related papers  (2025-06-03T06:31:59Z)
• Adaptive Mirror Descent Bilevel Optimization [25.438298531555468]
  We propose a class of efficient adaptive bilevel methods based on mirror descent for non bifraclevel optimization. We provide an analysis for methods under some conditions, and prove that our methods have a fast number of iterations.
  arXiv  Detail & Related papers  (2023-11-08T08:17:09Z)
• Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditions [9.518010235273785]
  We present a novel fully Liploop Hessian-inversion-free algorithmic framework for bilevel optimization. We show that by a slight modification of our approach our approach can handle a more general multi-objective robust bilevel optimization problem.
  arXiv  Detail & Related papers  (2023-06-21T07:32:29Z)
• A Generalized Alternating Method for Bilevel Learning under the Polyak-{\L}ojasiewicz Condition [63.66516306205932]
  Bilevel optimization has recently regained interest owing to its applications in emerging machine learning fields. Recent results have shown that simple alternating iteration-based iterations can match interest owing to convex lower-level objective.
  arXiv  Detail & Related papers  (2023-06-04T17:54:11Z)
• On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis [18.08351275534193]
  Bilevel optimization reveals the inner structure of otherwise oblique optimization problems.<n>A common goal in bilevel optimization is to a hyper-objective that implicitly depends on the solution of the set of factors.
  arXiv  Detail & Related papers  (2023-01-02T15:09:12Z)
• Alternating Implicit Projected SGD and Its Efficient Variants for Equality-constrained Bilevel Optimization [41.10094500516342]
  This paper considers the bilevel optimization problems both in the equality constraints and constrained upper-level problems. By leveraging the equality constraints approach, first, an alternating implicit projection SGD approach is used for unconstrained bilevel problems.
  arXiv  Detail & Related papers  (2022-11-14T03:47:43Z)
• A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem [18.15207779559351]
  We present a novel bilevel optimization method that locally approximates the solution set of the lower-level problem via a cutting plane. Our method achieves best-known assumption for the considered class of bilevel problems.
  arXiv  Detail & Related papers  (2022-06-17T16:12:47Z)
• A Constrained Optimization Approach to Bilevel Optimization with Multiple Inner Minima [49.320758794766185]
  We propose a new approach, which convert the bilevel problem to an equivalent constrained optimization, and then the primal-dual algorithm can be used to solve the problem. Such an approach enjoys a few advantages including (a) addresses the multiple inner minima challenge; (b) fully first-order efficiency without Jacobian computations.
  arXiv  Detail & Related papers  (2022-03-01T18:20:01Z)
• Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
  Bilevel optimization is one of the problems in machine learning. Recent developments in bilevel optimization converge on the first fundamental nonaptature multi-step analysis.
  arXiv  Detail & Related papers  (2022-02-08T07:10:06Z)
• Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
  We propose a bilevel optimization method based on Bregman Bregman functions. We also propose an accelerated version of SBiO-BreD method (ASBiO-BreD) by using the variance-reduced technique.
  arXiv  Detail & Related papers  (2021-07-26T16:18:43Z)
• Lower Bounds and Accelerated Algorithms for Bilevel Optimization [62.192297758346484]
  Bilevel optimization has recently attracted growing interests due to its wide applications in modern machine learning problems. We show that our results are more challenging than that of minimax applications.
  arXiv  Detail & Related papers  (2021-02-07T21:46:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.