PaperlayerView exact revision on arXiv

Source-linked AI summary

BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach

Mao Ye, Bo Liu, Stephen Wright, Peter Stone, Qiang Liu

arXiv:2209.08709v1cs.LGcs.AImath.OC

TL;DR

Bilevel optimization is useful but difficult because conventional methods require expensive differentiation through inner optimization, while existing first-order approaches can be impractical at scale. BOME addresses this with a fully first-order value-function and dynamic-barrier method, reporting strong efficiency and convergence behavior while retaining a theoretical inner-loop scaling requirement.

  • Problem

    Bilevel optimization supports important machine-learning tasks, but existing methods can require Hessian-related implicit differentiation or have practical limitations for non-convex large-scale problems.

  • Method

    BOME reformulates bilevel optimization through a value function and applies stopped-gradient dynamic barrier descent using only first-order gradients.

  • Results

    BOME achieves better or comparable performance with greater computational efficiency, consistently outperforming BVFSM in converged results and efficiency across experiments.

  • Takeaways & Limitations

    BOME provides a simple fully first-order approach with non-asymptotic convergence guarantees for non-convex bilevel objectives, including settings relevant to deep learning.

  • Takeaways & Limitations

    The current theory requires inner-loop iterations to scale logarithmically with outer-loop iterations, although this scaling was not observed empirically.

Abstract

from arXiv · show

Bilevel optimization (BO) is useful for solving a variety of important machine learning problems including but not limited to hyperparameter optimization, meta-learning, continual learning, and reinforcement learning. Conventional BO methods need to differentiate through the low-level optimization process with implicit differentiation, which requires expensive calculations related to the Hessian matrix. There has been a recent quest for first-order methods for BO, but the methods proposed to date tend to be complicated and impractical for large-scale deep learning applications. In this work, we propose a simple first-order BO algorithm that depends only on first-order gradient information, requires no implicit differentiation, and is practical and efficient for large-scale non-convex functions in deep learning. We provide non-asymptotic convergence analysis of the proposed method to stationary points for non-convex objectives and present empirical results that show its superior practical performance.

1 Introduction

Bilevel optimization supports several machine-learning tasks but is difficult because outer optimization depends on an inner solution. Existing approaches can require expensive Hessian-related calculations or suffer practical limitations, motivating BOME’s simple fully first-order design.

  • The bilevel problem minimizes an outer objective whose variables include the solution of an inner minimization problem.
  • Bilevel optimization applies to hyperparameter, meta-, continual, reinforcement, and adversarial learning.
  • Nested dependence makes bilevel optimization challenging, especially because differentiating the inner solution can require Hessian-based implicit differentiation.
  • BSG-1 uses a non-vanishing approximation, while BVFSM is hyperparameter-sensitive at scale and lacks complete non-asymptotic analysis for its practical algorithm.
  • BOME reformulates bilevel optimization as a constrained problem and combines stopped gradients with dynamic barrier descent using only first-order information.

2 Background

Traditional hypergradient methods differentiate through the inner optimum and can be computationally expensive. Stationarity-based reformulations avoid some differentiation but are generally valid only under convexity, limiting their use for non-convex deep-learning objectives.

  • Hypergradient Descent: Hypergradient descent assumes a unique inner minimizer and optimizes the outer objective through the resulting solution function.
  • Hypergradient Descent: Computing the derivative of the inner solution requires solving an implicit linear system, creating a major computational bottleneck.
  • Hypergradient Descent: Automatic-differentiation approximations still require many Hessian-vector or Jacobian-vector products and are slow for large problems.
  • Approximation methods: Neural-surrogate and Newton-Gaussian approximations introduce non-vanishing errors that are difficult to control, while neural surrogates add training cost.
  • Stationary-Seeking Methods: Replacing the inner argmin with a stationarity constraint is equivalent only when the inner objective is convex; otherwise, solutions may be maxima or saddle points.

3 Method

BOME uses a value-function reformulation and dynamic barrier gradient descent to solve bilevel optimization without Hessian computation. It approximates the inner optimum with a short gradient-descent run and applies stopped-gradient first-order updates.

  • Value-function reformulation: The value-function formulation replaces the bilevel argmin with q(v, θ) := g(v, θ) − g*(v) ≤ 0 and remains equivalent for non-convex inner objectives.
  • Value-function reformulation: Danskin’s theorem removes the need to differentiate the inner solution when differentiating the value function, avoiding implicit derivatives and Hessian computation.
  • Dynamic Barrier Gradient Descent: Dynamic barrier descent updates the variables to reduce the objective while controlling constraint decrease whenever the constraint is positive.
  • Practical approximation: The algorithm runs T inner gradient steps, treats the resulting inner iterate as constant in the gradient, and uses it to estimate the value-function constraint.
  • Algorithm 1: BOME updates (v, θ) using the outer gradient plus a constraint-gradient correction, with a barrier control based on η and the constraint gradient norm.
  • Practical approximation: The method offers two barrier-control choices, with η ∥∇q∥2 used by default, and can use standard optimizers or separate outer and inner step sizes.

4 Analysis

The analysis develops KKT conditions and convergence guarantees for the proposed method under both unique-minimizer and multimodal lower-level objectives. It obtains non-asymptotic stationarity rates under PL-type, smoothness, boundedness, and attraction-basin assumptions.

  • 4.1 KKT Conditions: The direct value-function constraint violates the usual KKT condition because feasible points have zero constraint gradient, so CRCQ generally fails.If KKT held, the outer and inner objectives would both need to be stationary, which is rare.
  • 4.1 KKT Conditions: Replacing the value-function constraint with the lower-level stationarity condition enables a KKT characterization under CRCQ with ∇θq.The condition can also be obtained by relaxing q(v, θ) ≤ 0 to q(v, θ) ≤ c_k and taking c_k to zero.
  • 4.2 Convergence with unimodal g: Under the PL, smoothness, and boundedness assumptions, Algorithm 1 achieves a non-asymptotic stationarity bound for the unique-minimizer case.The theorem requires ξ, α ≤ 1/L, φ_k = η∥∇q̂(v_k, θ_k)∥^2, and sufficiently large T.
  • 4.2 Convergence with unimodal g: With q(v_0, θ_0) = O(1), choosing ξ = O(K^-1/2) gives min_k≤K K(v_k, θ_k) = O(K^-1/4 + exp(−bT)).A better initialization q(v_0, θ_0) = O((ξK)^-1) and ξ = O(K^-2/3) yields O(K^-1/3 + exp(−bT)).
  • 4.3 Convergence with multimodal g: For multimodal g, the analysis uses attraction points and assumes a local PL inequality within each attraction basin.The attraction point is the limit of lower-level gradient descent from the current initialization.
  • 4.3 Convergence with multimodal g: Under the multimodal assumptions and differentiability along the iterates, Algorithm 1 retains a non-asymptotic convergence guarantee, while attraction-basin boundaries remain a technical limitation.At such boundaries, the attraction point and q⋄ can be discontinuous and K⋄ is not well defined; random initialization almost surely avoids them.

5 Related Works

The paper positions its value-function method as a practical alternative to hypergradient-based bilevel optimization. It emphasizes the gap between classical value-function theory and practical nonconvex algorithms, and claims a first non-asymptotic rate for a purely first-order method under broad lower-level assumptions.

  • 5 Related Works: Value-function formulations are classical in bilevel optimization but have been used much less for practical algorithms than hypergradient methods, especially for deep-learning-scale nonconvex problems.Prior practical approaches include interior-point, smoothed, pessimistic trajectory-truncation, and sequential-minimization methods.
  • 5 Related Works: The proposed method builds on dynamic control barriers and extends an approach previously applied to simple bilevel optimization without an outer variable.Its analysis must control the error between the exact lower-level solution θ*(v_k) and the T-step approximation θ^(T)(v_k).
  • 5 Related Works: The paper claims the first non-asymptotic rate for a purely first-order bilevel method under general assumptions allowing the lower-level problem to be convex or non-convex.The cited stochastic and minimax methods use hypergradient descent and require Hessian-vector products in implementation.

6 Experiment

Experiments evaluate BOME on toy bilevel problems and machine-learning applications, comparing correctness, robustness, performance, and computational efficiency against bilevel baselines and continual-learning methods.

  • Experimental setup: The experiments cover three toy problems and three machine-learning applications, using state-of-the-art bilevel methods and other continual-learning algorithms as baselines.The applications include hyperparameter optimization and continual learning; the baseline suite includes first-order, stationary-seeking, explicit/implicit, and reverse-mode methods.
  • Machine-learning applications: Replacing the continual-learning bilevel optimizer with BOME yields a substantial performance boost, while BOME consistently outperforms BVFSM in converged results and computational efficiency.The continual-learning evaluation reports mean accuracy, negative backward transfer, and forward transfer, with results averaged over five independent runs.
  • Toy problems: BOME converges to the optima of the toy bilevel problems, including the mini-max and degenerate low-level cases, while competing methods can fail to reach the true optimum.In the mini-max problem, naive gradient descent-ascent diverges, whereas BOME works and other first-order methods fail.
  • Toy problems: Across the toy examples, BOME’s proxy for inner-problem optimality decreases to 0.This proxy is denoted ˆq in the reported experiments.
  • Machine-learning applications: BOME achieves comparable or better hyperparameter-optimization performance than state-of-the-art bilevel methods and is especially computationally efficient on the twenty newsgroup dataset.The hyperparameter experiments include data hyper-cleaning on MNIST and learnable regularization on 20 Newsgroup.
  • Robustness and efficiency: BOME is robust to choices of its control coefficient, inner-loop iteration count, and inner step size; T = 1 works well in many cases.The reported default setting is η = 0.5, T = 10, and α = ξ, while varying these parameters produces almost identical performance.

7 Conclusion and Future Work

The paper presents BOME as a fully first-order bilevel method with non-asymptotic convergence guarantees, while identifying a gap between the theory’s inner-loop requirement and empirical behavior.

  • Conclusion and Future Work: BOME has a non-asymptotic convergence guarantee, but the current theory requires inner-loop iterations to grow logarithmically with outer-loop iterations.The authors report that this logarithmic scaling is not observed empirically and identify understanding the discrepancy as future work.

Societal Impacts

The paper reports no significant negative societal impact from its theoretical work, while noting that bilevel optimization can be instantiated in potentially harmful applications. Its experiments compare BOME with other methods on toy bilevel problems.

  • The authors state that specific bilevel applications such as adversarial learning and data attacking might harm real-world machine-learning systems.
  • The authors report no significant negative societal impact from their theoretical work.
  • A.1 Toy Coreset Problem: The toy coreset experiment compares trajectories from three initial points for BOME, BSG-1, BVFSM, and Penalty.
  • A.1 Toy Coreset Problem: BOME converges to the optimal solution regardless of the initial θ0, whereas BSG-1, BVFSM, and Penalty converge to non-optimal points.
  • A.3 Without LLS assumption: The low-level-singleton-violating experiment compares convergence of f(vk, θk), g(vk, θk), θk, and vk toward their optimal values over training time.

A.4 Data Hyper-cleaning

The appendix describes bilevel experiments for data hyper-cleaning, learnable regularization, and continual learning, including dataset setups, model details, and baseline-evaluation caveats. Results are averaged over independent runs where specified.

  • Data Hyper-cleaning: Data hyper-cleaning uses validation loss as the outer objective and a weighted training loss over 50,000 training examples as the inner objective.The validation set contains 5,000 examples, and the model is linear with W ∈ R10×784 and b ∈ R10.
  • Data Hyper-cleaning: Figure 5 reports data hyper-cleaning results on MNIST and FashionMNIST and learnable-regularization results on 20 Newsgroup.Each method’s results are averaged over 5 independent runs.
  • Baseline limitations: The authors could not find hyperparameters making BSG-1 work on the data hyper-cleaning problems, and VRBO was observed to learn slowly in practice.The VRBO observation is attributed to requiring multiple Hessian-vector products per step.
  • Learnable Regularization: The learnable-regularization experiment uses a linear model with θ ∈ R20×130107 and v ∈ R130107, with data split into training, validation, and test portions.
  • Continual Learning: The continual-learning setup trains a quickly updated backbone and a slowly updated controller through bilevel optimization across current-task data and memory data.The inner objective uses training data and episodic memories, while the outer objective uses held-out semantic memory.

B Proof of the Result in Section 4.1

The proof establishes convergence properties by showing that the relevant constraint quantities and augmented-gradient conditions meet the assumptions of an external proposition. It uses continuity, lower boundedness, and a constraint qualification at limit points.

  • The proof verifies that λk remains finite, ∇q(vk, θk) tends to zero, and q is lower bounded because q ≥ 0.
  • Continuity of ∇q is used to derive the limiting behavior required by the proof.
  • At the optimum, q(v∗, θ∗) = 0 implies ∇q(v∗, θ∗) = 0.
  • Under these verified conditions, Proposition 6.3 of Gong et al. is used to obtain the desired result.
  • The invoked proposition assumes continuous differentiability of f, q, and ∇q, convergence of two gradient conditions, and CRCQ at a limit point.

C Proof of the Result in Section 4.2

The proof develops smoothness, approximation, descent, and boundedness lemmas for the value-function constraint and its stopped-gradient approximation. These lemmas support bounds on constraint reduction and the augmented objective during the algorithm’s iterations.

  • The analysis assumes q is Lq-smooth and restricts the outer stepsize to ξ ≤ 1.
  • The stopped-gradient approximation depends on T inner gradient steps, with θ(T) treated as constant when differentiating q-hat.
  • The proof defines the dual solution λ∗ and the combined direction δ∗ = λ∗ q-hat-gradient + ∇f.
  • Under the stated assumptions, gradient approximation error is bounded by L times the distance between θ(T) and θ∗(v).
  • When α < 2/L, inner gradient steps reduce q geometrically at a rate determined by α, L, and κ.
  • The main lemmas require sufficiently large T and, in one result, r and ξ no larger than 1/L.
  • The proof combines smoothness, approximation, descent, and bounded-gradient bounds to control successive changes in q and f.

D Proof of the Result in Section 4.3

The proof develops bounds for the approximate lower-level solution and uses them to control changes in the auxiliary objective q during the bilevel updates. It combines smoothness, assumptions, lemmas, and a telescoping inequality to establish the required convergence bound.

  • Notation: The proof defines θ(T) as T gradient steps on g(v, ·), and uses q as shorthand for q⋄.The notation is introduced to connect finite lower-level optimization with the proof's auxiliary objective.
  • Lower-level bounds: Lemma 13 shows that, for α ≤ 1/L, the lower-level objective at θ⋄(v, θ) is no larger than at θ.The proof explicitly concludes g(v, θ⋄(v, θ)) ≤ g(v, θ).
  • Descent analysis: The proof decomposes q(vk+1, θk+1) − q(vk, θk) into changes in g caused by the upper-level update and the lower-level approximation.The decomposition introduces an intermediate term using θ⋄(vk+1, θk), separating the two sources of change.
  • Descent analysis: Using Lemma 14, the change in q is bounded by a descent term, a quadratic step-size term, and the residual χk.The stated inequality is q(vk+1, θk+1) − q(vk, θk) ≤ −ξ⟨∇q(vk, θk), δ∗(vk, θk)⟩ + Lqξ2||δ∗(vk, θk)||2/2 + χk.
  • Conditions: The argument relies on Assumption 4 and a sufficiently large lower-level iteration count T, with constants and auxiliary bounds supplied through earlier lemmas.The proof invokes Assumption 4, chooses T above a bound involving b7, and uses bounds such as ||δ∗(vk, θk)|| ≤ b2.
  • Convergence bound: Summing the bounds yields a relation between the accumulated gradient norms, the initial and final q values, the approximation term K∆, and the residual terms χk.The proof defines ∆ and presents the resulting telescoping inequality over k = 0 to K − 1.
Loading 2209.08709v1…