PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards Gradient-based Bilevel Optimization with Non-convex Followers and Beyond

Risheng Liu, Yaohua Liu, Shangzhi Zeng, Jin Zhang

arXiv:2110.00455v2cs.LG

TL;DR

Bilevel optimization methods often rely on restrictive lower-level assumptions, while many applications have non-convex followers. IAPTT-GM combines an optimizable initialization with pessimistic trajectory truncation; the paper establishes convergence without lower-level convexity and justifies an accelerated variant under that condition.

  • Problem

    Many bilevel methods require lower-level singleton, convexity, or strong-convexity assumptions, despite non-convex followers appearing in applications.

    Source: §1.1 · p. 2, §1 · p. 2

  • Method

    IAPTT-GM jointly optimizes an auxiliary lower-level initialization and uses pessimistic trajectory truncation to approximate the bilevel problem.

    Source: §1.1 · p. 3, §2.1 · pp. 3–4

  • Results

    The authors establish convergence of IAPTT-GM for non-convex followers and justify its Nesterov-accelerated variant under lower-level convexity.

    Source: §1.1 · p. 3, §5 · p. 10

  • Takeaways & Limitations

    The framework provides a gradient-based approach to bilevel problems with non-convex followers without requiring lower-level convexity.

    Source: §1.1 · p. 3, §5 · p. 10

    The formulation assumes the lower-level solution set S(x) is nonempty for every upper-level x.

    Source: §2 · p. 3

Abstract

from arXiv · show

In recent years, Bi-Level Optimization (BLO) techniques have received extensive attentions from both learning and vision communities. A variety of BLO models in complex and practical tasks are of non-convex follower structure in nature (a.k.a., without Lower-Level Convexity, LLC for short). However, this challenging class of BLOs is lack of developments on both efficient solution strategies and solid theoretical guarantees. In this work, we propose a new algorithmic framework, named Initialization Auxiliary and Pessimistic Trajectory Truncated Gradient Method (IAPTT-GM), to partially address the above issues. In particular, by introducing an auxiliary as initialization to guide the optimization dynamics and designing a pessimistic trajectory truncation operation, we construct a reliable approximate version of the original BLO in the absence of LLC hypothesis. Our theoretical investigations establish the convergence of solutions returned by IAPTT-GM towards those of the original BLO without LLC. As an additional bonus, we also theoretically justify the quality of our IAPTT-GM embedded with Nesterov's accelerated dynamics under LLC. The experimental results confirm both the convergence of our algorithm without LLC, and the theoretical findings under LLC.

1 Introduction

Bilevel optimization is used across machine-learning tasks, but existing methods often rely on restrictive lower-level assumptions that do not fit non-convex followers. The paper proposes IAPTT-GM and analyzes its convergence without lower-level convexity.

1 Introduction

  • Existing bilevel methods often require lower-level singleton, lower-level convexity, or strong-convexity assumptions, although non-convex followers arise in applications.The introduction also notes limited convergence analysis for approaches that avoid the singleton assumption.Source: §1.1 · p. 2, §1 · p. 2

1.1 Our Motivations and Contributions

  • Initialization Auxiliary (IA) jointly optimizes the upper-level variables and dynamical initialization, while Pessimistic Trajectory Truncation (PTT) adaptively reduces backward recurrent propagation complexity.Source: §1.1 · p. 3
  • The authors report a first strict convergence guarantee for gradient-based methods on bilevel problems with non-convex followers, and justify an IAPTT-GM variant with Nesterov acceleration under lower-level convexity.Source: §1.1 · p. 3
  • Experiments evaluate IAPTT-GM on challenging bilevel tasks with non-convex follower losses and coupled network structures.Source: §1.1 · p. 3

2 The Proposed Algorithmic Framework

The framework approximates bilevel optimization without requiring convexity in the lower-level problem. It combines an optimizable initialization with a pessimistic choice among trajectory points.

2 The Proposed Algorithmic Framework

  • The proposed bilevel formulation assumes the lower-level solution set is nonempty for each upper-level variable, but requires no lower-level convexity.Source: §2 · p. 3

2.1 Initialization Auxiliary

  • Initialization Auxiliary adds an optimizable initial point z to the lower-level dynamics, allowing the upper-level variable and initialization to be updated together.The auxiliary addresses the possibility that a fixed, unsuitable initial point misses a desired lower-level solution while optimizing the upper-level objective.Source: §2.1 · pp. 3–4

2.2 Pessimistic Trajectory Truncation

  • Pessimistic Trajectory Truncation selects the trajectory point with the worst upper-level objective, avoiding the need to identify a specific convergent selection.The maximum over trajectory points can yield a truncation shorter than K, reducing the cost of hypergradient backpropagation.Source: §2.2 · p. 4

3 Theoretical Investigations

The section analyzes IAPTT-GM’s convergence without lower-level convexity (LLC) and the accelerated IA-GM(A) variant under LLC. Its results cover global and local solution behavior in the non-convex-follower setting, and convergence guarantees for accelerated dynamics under LLC.

3.1 Convergence Analysis of IAPTT-GM for BLO with Non-convex Followers

  • The pessimistic truncation minimizes the worst case across lower-level trajectories, and the resulting approximate optimal-value gap eventually vanishes.The argument combines the uniform convergence result with continuity of the residual mapping.Source: §3.1 · p. 5
  • Without LLC, every limit point of the approximate problems’ global solutions is a solution to the original bilevel optimization problem.The analysis uses standing assumptions including compact convex variable sets and a nonempty lower-level solution set.Source: §3.1 · pp. 5–6
  • Limit points of uniformly local minima of the approximated problems are local minima of the bilevel problem over lower-level stationary points.The result assumes a shared neighborhood modulus and identifies a corresponding neighborhood for the limiting point.Source: §3.1 · p. 6

3.2 Theoretical Findings of IA-GM (A) for BLO with LLC

  • Under LLC, the residual may converge uniformly to zero, allowing the pessimistic truncation to be removed and the approximation objective to simplify to F(x, yK(x, z)).The accelerated variant uses an initialization auxiliary while minimizing the simplified approximation objective.Source: §3.2 · p. 6
  • Under LLC, IA-GM(A) has a convergence guarantee for accelerated dynamics, and Nesterov’s dynamics satisfy the theorem’s required assumptions when α = 1/Lf.The general convergence theorem also applies to other dynamics meeting its assumptions.Source: §3.2 · pp. 6–7

4 Experimental Results

The experiments test IAPTT-GM on a non-convex numerical problem, few-shot classification, and data hyper-cleaning, then evaluate accelerated IA-GM under LLC. They report convergence from varied initializations, performance comparisons on application tasks, and runtime and memory trade-offs.

4.2 BLO with Non-convex Followers in Different Application Scenarios

  • The application experiments cover non-convex followers arising from non-convex regularization and neural network architectures, including few-shot classification and data hyper-cleaning.For application settings, the feasible set can be treated as sufficiently large so that projection is ignored in practical computations.Source: §4 · p. 7, §4.2 · p. 8

4.1 Numerical Verification

  • With distant initializations, IAPTT-GM reaches the optimal UL solution and objective value, while other compared methods fail to converge to the true solution.Different initializations only slightly affect IAPTT-GM's convergence speed; IA-GM also fails to converge to the true solution without LLC.Source: §4.1 · p. 7
  • IAPTT-GM uses less memory than NS, LS, and BDA, matches RHG, runs slower than RHG and NS, and runs faster than BDA.Its adaptive PTT step count shortens the backward recurrent propagation trajectory for UL-gradient computation.Source: §4.1 · p. 8, Table 1 · p. 8

4.2.1 Few-Shot Classification: Non-convex LL Objective

  • IAPTT-GM outperforms state-of-the-art methods on both 5-way 1-shot and 5-way 5-shot tasks across miniImageNet and tieredImageNet.Table 2 reports mean test accuracy with 95% confidence intervals over tasks.Source: §4.2.1 · p. 9, Table 2 · p. 9

4.2.2 Data Hyper-Cleaning: Non-convex LL Architecture Structure

  • IAPTT-GM achieves better test accuracy and F1 score than IG and EG methods on MNIST and FashionMNIST data hyper-cleaning tasks.Table 3 defines Acc. as test accuracy and F1 as the harmonic mean of precision and recall.Source: §4.2.2 · p. 10, Table 3 · p. 10

4.3 Evaluations of IA-GM (A) for BLOs under LLC

  • IA-GM (A) improves UL- and LL-variable convergence speed under LLC and performs better than IA-GM on convex data hyper-cleaning.The convergence-speed comparison is reported for a problem under LLC; the real-world task uses a single fully connected layer.Source: §4.3 · p. 10, Figure 3 · p. 10

5 Conclusion

The conclusion presents IAPTT-GM as a first-order framework for bilevel problems with non-convex followers, using initialization and pessimistic trajectory truncation to support convergence without LLC.

5 Conclusion

  • IAPTT-GM is a generic first-order framework for bilevel optimization with non-convex followers.The conclusion identifies initialization auxiliary and pessimistic trajectory truncation as its two features.Source: §5 · p. 10
  • The framework is designed to guarantee convergence without the LLC hypothesis and to achieve better performance on various applications.Source: §5 · p. 10
  • Under LLC, the paper validates performance and speed improvement for IAPTT-GM.Source: §5 · p. 10

A.1 Proof of Lemma 3.1

The proofs bound residuals along the follower trajectory and show that an approximate solution in the specified set remains fixed under the follower iterations.

A.1 Proof of Lemma 3.1

  • The residual at step k is bounded by the residual using step size αy, for αy in the stated interval.Source: §A.1 · p. 14
  • Summing the inequalities and using m ≤ f(x, yk(x, z)) ≤ M yields an aggregate bound over K+1 iterations.Source: §A.1 · p. 14

A.2 Proof of Lemma 3.2

  • For any ε-approximate minimizer yε in Ŝ(x), the residual is zero and the follower iterates remain equal to yε.Source: §A.2 · p. 14

A.3 Proof of Theorem 3.1

The proof shows that selected follower-trajectory limits lie in the specified solution set, and uses this to establish convergence of approximate optimal values and original-problem minimizers.

A.3 Proof of Theorem 3.1

  • A limit of the selected follower-trajectory points has zero residual and therefore belongs to Ŝ at the limiting upper-level point.Source: §A.3 · p. 14
  • Continuity of F is used to compare its values along the selected subsequence with the limiting point.Source: §A.3 · p. 15
  • The limiting upper-level point minimizes ϕ, and the associated pair minimizes F subject to y ∈ Ŝ(x).Source: §A.3 · p. 15
  • As K grows, the infimum of ϕK over (x, z) converges to the infimum of ϕ over x.Source: §A.3 · p. 15

A.4 Proof of Theorem 3.2

The proof follows limit points of approximate local minima and uses their uniform neighborhood condition to pass a local comparison to the limit.

A.4 Proof of Theorem 3.2

  • Along a subsequence, the upper-level points and selected follower iterates converge, with the follower limit in Ŝ at the upper-level limit.Source: §A.4 · p. 15
  • The local-minimum condition with uniform neighborhood modulus δ supplies a comparison on a neighborhood of the limit point.Source: §A.4 · p. 16
  • The proof applies the same arguments as Lemma 3.2 to nearby feasible pairs, then takes the subsequence limit and ε → 0.Source: §A.4 · p. 16

B Proof of results in Section 3.2

The proof compares the approximate problem’s minimizer with lower-level solutions that remain fixed under the auxiliary dynamics, yielding an upper bound by the original objective.

B Proof of results in Section 3.2

  • Thus, for every x and ε > 0, the approximate minimum is at most ϕ(x) + ε.This comparison uses the fixed-point property for lower-level solutions and the approximate problem’s minimization over x and z.Source: B Proof of results in Section 3.2 · p. 16
  • For any x and ε > 0, a lower-level solution yε can be chosen with F(x, yε) ≤ ϕ(x) + ε.Because yε is a lower-level solution, the auxiliary dynamics leave it unchanged for every iteration.Source: B Proof of results in Section 3.2 · p. 16
  • Evaluating the approximate objective at z = yε bounds its minimizer by φK(xK, zK) ≤ F(x, yε).The inequality follows by comparing the minimizer with the feasible choice (x, yε).Source: B Proof of results in Section 3.2 · p. 16

B.1 Proof of Theorem 3.3

The proof uses convergent subsequences to show that limit points satisfy lower-level solution conditions, then establishes convergence of the approximate optimal values to the original optimum.

B.1 Proof of Theorem 3.3

  • For condition (a), continuity and upper semi-continuity imply that each relevant subsequential limit satisfies the lower-level solution condition.The proof takes a convergent subsequence of upper-level and inner-iterate variables before applying these continuity properties.Source: §B.1 · p. 16
  • For condition (b), continuity of Rα and vanishing residuals likewise imply that the subsequential limit is a lower-level solution.The residual bound is taken to zero along the subsequence.Source: §B.1 · pp. 16–17
  • The approximate optimal values converge to the original BLO optimal value as K tends to infinity.The proof uses the upper bound from Lemma B.2 and rules out a subsequence staying below the original infimum by a fixed δ.Source: §B.1 · p. 17

B.2 Proof of Theorem 3.4

The proof verifies the convex, smooth inner-iteration conditions required by Theorem 3.3; the accompanying experiments describe numerical-example and few-shot setups.

B.2 Proof of Theorem 3.4

  • Under convexity and Lf-smoothness with α = 1/Lf, the inner iterates meet Theorem 3.3’s required conditions.Compactness bounds the distance to the solution set, and the update keeps iterates in Y and fixes solutions when initialized there.Source: §B.2 · p. 17

C Experiments

  • The experiments ran on a 64-bit Ubuntu 18.04.5 system with two RTX 3090 GPUs.The reported machine also had an Intel Core i9-10900KF CPU and 128GB RAM.Source: C Experiments · p. 18

C.1 Non-convex Numerical Example

  • For the non-convex numerical example, IAPTT-GM and EG use general hyperparameter settings, while IG methods use method-specific settings.SGD updates the upper-level variables and initialization auxiliary; T is the IG inner-iteration count, and μ weights the BDA gradient aggregation.Source: §C.1 · p. 18, Table 4 · p. 18

C.2 Few-Shot Classification

  • Few-shot evaluation uses miniImageNet and TieredImageNet with ConvNet-4 and ResNet-12 architectures.TieredImageNet is described as more challenging because its training and testing sets are more dissimilar.Source: §C.2 · p. 18

C.3 Data Hyper-Cleaning

The supplied passages describe data hyper-cleaning datasets and parameter tables, plus an acceleration evaluation setup for convex numerical examples.

C.3 Data Hyper-Cleaning

  • Data hyper-cleaning uses MNIST and FashionMNIST, each randomly split into three disjoint subsets of 5,000, 5,000, and 10,000 examples.Adam updates x and z for the proposed method and x for the comparison methods.Source: §C.3 · p. 18, Table 6 · p. 19

C.4 Details for Evaluation of IA-GM (A)

  • The IA-GM (A) acceleration experiments use SGD to update x and z, with hyperparameters reported for convex numerical examples.The parameter settings are identified as Table 7.Source: §C.4 · p. 19, Table 7 · p. 19
Loading 2110.00455v2…