PaperlayerView exact revision on arXiv

Source-linked AI summary

A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singleton

Risheng Liu, Pan Mu, Xiaoming Yuan, Shangzhi Zeng, Jin Zhang

arXiv:2006.04045v2cs.LGcs.CVmath.DSmath.OCstat.ML

TL;DR

Existing gradient-based first-order methods for bi-level optimization rely on a singleton lower-level solution set, limiting their theoretical scope. The paper proposes BDA, an optimistic and modular framework with convergence guarantees without that assumption, and reports superiority across applications while improving existing LLS-based analyses.

  • Problem

    Existing bi-level first-order methods require the lower-level solution set to be a singleton, although non-singleton cases make the optimization challenging and the assumption can be restrictive.

  • Method

    BDA formulates bi-level programs from the optimistic viewpoint as a single-level upper-level problem coupled with a simple bi-level lower-level problem, with aggregated hierarchical objective information.

  • Results

    BDA has convergence guarantees without the LLS assumption, while existing bi-level first-order schemes receive improved convergence results under LLS; experiments show BDA's superiority across applications.

  • Takeaways & Limitations

    The framework supports generic bi-level optimization beyond lower-level singleton settings and is compatible with different first-order computation modules.

  • Takeaways & Limitations

    Conventional first-order schemes may converge to incorrect limiting points when the lower-level solution set is not a singleton.

Abstract

from arXiv · show

In recent years, a variety of gradient-based first-order methods have been developed to solve bi-level optimization problems for learning applications. However, theoretical guarantees of these existing approaches heavily rely on the simplification that for each fixed upper-level variable, the lower-level solution must be a singleton (a.k.a., Lower-Level Singleton, LLS). In this work, we first design a counter-example to illustrate the invalidation of such LLS condition. Then by formulating BLPs from the view point of optimistic bi-level and aggregating hierarchical objective information, we establish Bi-level Descent Aggregation (BDA), a flexible and modularized algorithmic framework for generic bi-level optimization. Theoretically, we derive a new methodology to prove the convergence of BDA without the LLS condition. Our investigations also demonstrate that BDA is indeed compatible to a verify of particular first-order computation modules. Additionally, as an interesting byproduct, we also improve these conventional first-order bi-level schemes (under the LLS simplification). Particularly, we establish their convergences with weaker assumptions. Extensive experiments justify our theoretical results and demonstrate the superiority of the proposed BDA for different tasks, including hyper-parameter optimization and meta learning.

1. Introduction

Bi-level optimization couples upper- and lower-level problems, but existing first-order methods generally rely on a restrictive singleton lower-level solution set. BDA removes that requirement through an optimistic formulation, a modular algorithmic framework, and a general convergence analysis.

  • Problem: Bi-level programs couple an upper-level objective and constraint with a parameterized lower-level solution set, making optimization challenging when multiple lower-level solutions exist.The lower-level solution mapping S(x) may be set-valued rather than single-valued.
  • Applications: Bi-level optimization has been applied to meta learning, hyper-parameter optimization, reinforcement learning, generative adversarial learning, and image processing.
  • Existing methods: Existing first-order methods hierarchically compute lower-level gradients and upper-level gradients, but their theory requires the Lower-Level Singleton condition and often strong lower-level convexity.These requirements can be too restrictive for complex machine learning tasks.
  • BDA: BDA is a flexible, modularized first-order framework that formulates the upper-level variable through a single-level problem and the lower-level variable through a simple bi-level problem.The formulation uses the optimistic bi-level viewpoint and supports gradient-aggregation modules.
  • Contributions: A counter-example shows that existing bi-level first-order methods may produce incorrect solutions without the singleton condition.The example motivates analyzing non-singleton lower-level solution sets directly.
  • Theory: The paper proves BDA convergence without the LLS assumption and improves convergence results for existing methods in the LLS scenario.

2. First-Order Methods for BLPs

Conventional first-order methods approximate the lower-level solution by unrolling gradient updates and differentiating the resulting upper-level objective. A counter-example shows that this strategy can fail when the lower-level solution is non-singleton.

  • Lower-Level Singleton: Existing methods assume a unique lower-level solution for each upper-level variable and replace the lower-level problem with a single-valued mapping.This is the Lower-Level Singleton simplification.
  • Lower-Level optimization: The lower-level approximation uses gradient updates y_k+1 = y_k − s_l∇_y f(x, y_k) from an initialization y_0.The step size s_l is chosen appropriately and the procedure runs for K iterations.
  • Upper-Level optimization: After K lower-level updates, y_K(x) is inserted into the upper-level objective, producing the single-level approximation min_x∈X F(x, y_K(x)).Automatic differentiation through the unrolled updates computes the derivative with respect to x.
  • Counter-example: The counter-example uses x ∈ [−100, 100] and y ∈ R^2 to show that the singleton assumption is too restrictive for conventional gradient-based schemes.
  • Counter-example: The counter-example has true solution x*=1, y*=(1,1), but the conventional scheme with y_0=(0,0) cannot converge to x*=1.The resulting limiting points may therefore be incorrect.
  • Limitation: Without LLS, the lower-level iterates may fail to converge to the true solution even when the iterates can minimize both lower- and upper-level objectives under singleton behavior.

3. Bi-level Descent Aggregation

BDA reformulates generic bi-level programs from an optimistic viewpoint and aggregates upper- and lower-level descent information through a modular first-order framework. The resulting approximations reduce the problem to single-level optimization while allowing varied iterative modules, including nonsmooth lower-level objectives.

  • Optimistic formulation: BDA adopts the optimistic viewpoint, selecting a lower-level solution that also minimizes the upper-level objective for each fixed upper-level variable.This yields a single-level value-function formulation in x, with a bi-level subproblem in y.
  • Hierarchical updates: The lower-level sequence is updated by a schematic module y_k+1(x) = T_k+1(x, y_k(x)), whose output approximates the value function.After K iterations, F(x, y_K(x)) replaces the exact value function in a single-level approximation.
  • Hierarchical updates: Each approximation subproblem is a standard single-level optimization problem whose descent direction implicitly incorporates the lower-level solution strategy.Automatic differentiation techniques can be used to optimize these approximation problems.
  • Gradient aggregation: BDA constructs T_k by aggregating descent information from the upper- and lower-level objectives with separate step sizes and an aggregation parameter.The framework explicitly combines both hierarchical objectives rather than treating them as independent single-level problems.
  • Modularity: The framework can incorporate multiple numerical schemes, including a proximal module for nonsmooth lower-level objectives while retaining guaranteed convergence within the framework.The paper describes gradient aggregation as one choice of T_k rather than the only compatible module.

4. Theoretical Investigations

The theoretical analysis develops a general convergence recipe based on lower-level solution-set and upper-level objective convergence properties. Applying this recipe establishes BDA convergence without LLS under continuity and regularity assumptions, while also weakening assumptions for existing LLS methods.

  • General proof recipe: The general proof recipe separates convergence analysis into lower-level solution-set and upper-level objective properties.Theorem 1 connects these two properties to convergence of limit points and optimal value approximations.
  • General proof recipe: Any limit point of the sequence {x^K} belongs to arg min_x∈X ϕ(x), and inf_x∈X ϕ^K(x) converges to inf_x∈X ϕ(x).The same framework also gives a local-minimum result under a uniform neighborhood modulus.
  • BDA convergence: The analysis establishes boundedness and convergence of lower-level iterates toward the solution set, then derives upper-level objective convergence through lower semicontinuity.The intermediate results use level-boundedness, inner and outer semicontinuity, and uniform convergence of lower-level objective values.
  • BDA convergence: Under Assumption 1 and continuity of S(x) on X, BDA satisfies both required convergence properties.Assumption 1 requires Lipschitz continuity, smoothness, and strong convexity for F in y, and smooth convexity for f in y.
  • Extensions: BDA's theory extends to nonsmooth lower-level objectives through proximal iterations within the same framework.The paper states that the corresponding convergence proofs are highly similar.
  • Existing LLS methods: For existing LLS methods, convergence can be established under level-boundedness, bounded iterates, and uniform objective-value convergence instead of strong convexity.Theorem 3 and Proposition 5 provide the weaker-condition route when S(x) is single-valued.

5. Experimental Results

Experiments evaluate BDA on synthetic bi-level problems, data hyper-cleaning, and few-shot meta learning. Across these settings, BDA converges reliably without the LLS condition and generally outperforms or matches the compared first-order methods.

  • Synthetic BLPs: On synthetic BLPs, RHG struggled to obtain the correct solution across initialization points, whereas BDA converged under the non-singleton lower-level solution setting.The evaluations used objective gaps and normalized upper- and lower-level variable errors.
  • Synthetic BLPs: BDA converged for K = 8, 16, and 64 lower-level iterations, with numerical performance improving as K increased; RHG did not improve by increasing K.The experiments used α_k = 0.5/k.
  • Synthetic BLPs: Adaptive α_k produced favorable convergence for both upper- and lower-level variables, while α_k = 0 provided insufficient upper-level guidance and fixed α_k = 0.5 converged slowly.The adaptive strategy used α_k = 0.9/k.
  • Hyper-parameter Optimization: In MNIST data hyper-cleaning, BDA achieved the highest accuracy among the compared methods across different lower-level iteration counts, and more lower-level iterations usually improved performance.The comparison included RHG and truncated RHG with K = 50, 100, 200, 400, and 800.
  • Meta Learning: In few-shot meta learning, BDA achieved the highest classification accuracy except on the 5-way 5-shot Omniglot task, where it was slightly below MAML.On MiniImageNet, BDA outperformed RHG and truncated RHG and required the fewest upper-level iterations to reach approximately 44% accuracy.

6. Conclusions

The paper presents BDA as a generic first-order framework for bi-level programs, proves convergence without the LLS assumption, and reports broad empirical superiority. It also gives a general proof recipe and improves convergence results for existing schemes.

  • BDA addresses bi-level programs as a generic first-order algorithmic scheme without requiring the Lower-Level Singleton condition.
  • A counter-example shows that existing bi-level first-order methods may produce incorrect solutions without LLS.
  • BDA reformulates optimistic bi-level programs into a single-level subproblem in x and a simple bi-level subproblem in y.
  • The proposed proof recipe establishes BDA convergence without LLS and improves convergence results for existing schemes.
  • Supplementary results cover local convergence and BDA for bi-level programs with nonsmooth lower-level objectives.

A.1. Proof of Theorem 1

The proof establishes convergence of the approximated upper-level objectives by combining compactness, distance-to-solution-set control, continuity, and lower-level level-boundedness.

  • Compactness of X provides a convergent subsequence xK → x̄ ∈ X for the proof.
  • For sufficiently large K, the distance between yK(x) and S(x) is bounded by ε/(2L0).
  • The proof shows infx∈X ϕK(x) → infx∈X ϕ(x) as K → ∞ by contradiction.
  • Local uniform level-boundedness prevents lower-level solutions from diverging while continuity and inner semicontinuity control objective values.

B.2. Proof of Lemma 2

The proof derives upper semicontinuity of the lower-level value function from continuity and then uses it to establish uniform convergence of approximate lower-level solutions toward the solution set.

  • For xt → x̄, continuity and near-optimality yield lim supk→∞ f*(xt) ≤ f*(x̄).
  • The proof establishes uniform convergence of ỹK(x) toward S(x) through uniform convergence of f(x, ỹK(x)).

B.3. Proof of Proposition 2

The proof establishes convergence properties of the lower-level approximations by combining continuity, inner and outer semicontinuity, compactness, and uniform level-boundedness.

  • A contradiction argument shows that approximate lower-level points converge into S(x) when their distance from S(xt) cannot remain bounded away from zero.
  • Outer semicontinuity and boundedness of lower-level solutions ensure that subsequential limits remain in S(x̄).
  • Continuity and local uniform level-boundedness establish bounded lower-level sequences and the lower semicontinuity of ϕ on X.
  • For sufficiently large K, the approximation error is controlled by choosing K > max{2C/ε, k(ε)}.
  • The resulting approximated value functions satisfy ϕK(x) → ϕ(x) for every x ∈ X as K → ∞.

C.1. Proof of Lemma 3

Under the stated assumptions, the lower-level solution mapping is continuous, and the approximated upper-level objectives converge pointwise to the limiting objective.

  • Continuity of the lower-level solution mapping follows from its single-valuedness, outer semicontinuity, and local boundedness.
  • The limiting upper-level objective is lower semicontinuous on X.
  • ϕK(x) converges to ϕ(x) for every x ∈ X as K →∞.
  • The assumptions include Lf-smoothness and convexity of f(x, ·), with lower-level step size sl ≤ 1/Lf.

C.3. Proof of Proposition 4

The proposition verifies the required convergence assumption for the lower-level iterates even without strong convexity of the lower-level objective.

  • The proposition follows directly from the cited preceding theorem results.
  • The required convergence assumption on {f(x, yK(x))} can be verified without lower-level strong convexity.
  • Local boundedness of S(x) at every point, together with compactness of X, makes the union of lower-level solution sets bounded.

D.1. Local Convergence Results

BDA admits local convergence guarantees for smooth and nonsmooth lower-level objectives: limit points of local minima remain local minima, and the framework extends through proximal updates.

  • D.1. Local Convergence Results: Any limit point of local minima xK of ϕK with uniform neighborhood modulus δ > 0 is a local minimum of ϕ.
  • D.1. Local Convergence Results: The proof uses lower-level solution-set convergence, upper-level objective convergence, local minimality of ϕK, and lower semicontinuity of ϕ.
  • D.2. Nonsmooth LL Objective: BDA can address nonsmooth composite lower-level objectives by replacing the lower-level descent step with a proximal operator.
  • D.2. Nonsmooth LL Objective: Automatic differentiation through the update dynamics can approximate upper-level derivatives when explicit subgradient estimation is computationally infeasible.
  • D.2. Nonsmooth LL Objective: For the nonsmooth case, the analysis derives boundedness, upper semicontinuity, iterate convergence, and the required convergence properties before invoking the main framework.
  • D.2. Nonsmooth LL Objective: Under the nonsmooth assumptions, a limit point of xK is a local minimum of ϕ when the solution mapping S(x) is continuous on X.
Loading 2006.04045v2…