On Penalty-based Bilevel Gradient Descent Method

1 Introduction

• Bilevel optimization couples upper- and lower-level problems through S(x), while implicit-gradient methods cannot handle the absence of lower-level strong convexity.The introduction notes that the implicit-gradient approach has mainly been studied for strongly convex lower-level objectives.Source: §1 · p. 2

1.1 Related works

• Iterative differentiation differentiates through lower-level optimization trajectories, but is typically restricted to unconstrained problems and can incur high memory and computational costs.The cited examples include (Franceschi et al., 2017; Liu et al., 2021c).Source: §1 · p. 2

1 Introduction

• In the motivating example, a local solution of the gradient-norm penalized problem is neither a global nor local solution of the original bilevel problem.The example shows why minimizing a lower-level optimality metric alone may fail to recover a solution of the original problem.Source: §1 · p. 2
• The paper proposes a penalty reformulation and PBGD, proving approximate solution recovery under generic conditions and finite-time convergence without lower-level convexity.The convergence analysis covers unconstrained and constrained lower-level problems, and the paper also develops a nonsmooth-penalty setting.Source: §1 · p. 3

1.1 Related works

• Earlier penalty-based methods include log-barrier and gradient-norm approaches with asymptotic convergence, while BOME's KKT guarantee relies on CRCQ and restrictive assumptions.Under lower-level nonconvexity, the introduction says it is difficult to establish when the KKT point is a bilevel solution.Source: §1.1 · p. 4

• Because the distance to the lower-level solution set is non-differentiable, the reformulation uses upper bounds on that distance in the penalty.The reformulated constraint uses a penalty bound, with the squared-distance-bound property supplying the approximation guarantee.Source: §2 · pp. 4–5
• BP_ε with ε = 0 recovers BP, while positive ε gives an approximate problem when p is a squared-distance bound and the upper-level objective is Lipschitz in y.The approximation relation is established in Lemma 1 under Assumption 1.Source: §2 · p. 5
• For γ > γ*, an approximate global solution of BPγp is an approximate solution of BP_εγ, with ε_γ ≤ (ε1 + ε2)/(γ − γ*).Conversely, any global solution of BP is an ε1-global minimum of BPγp under the stated squared-distance-bound and Lipschitz assumptions.Source: §2 · p. 6
• For any γ > 0, the penalized problem can have local solutions that are meaningless for the original problem, so local recovery requires additional conditions.The section contrasts this issue with the conditional local-solution guarantee.Source: §2 · p. 7
• Under the theorem’s continuity, squared-distance-bound, and local Lipschitz assumptions, a local solution of BPγp is a local solution of BP_εγ when either of two additional conditions holds.The alternatives are an approximate minimizer of p over U(xγ), or convexity of U(xγ) and p(xγ, ·); the remark says these essentially require global solvability of min_U(x) p(x, ·).Source: §2 · p. 7

3.1 Candidate penalty terms

• Under PL-based assumptions, the function-value gap and squared gradient norm are squared-distance bound penalties, with smoothness required for the gap penalty.The section uses these bounds to construct penalty reformulations for the unconstrained lower-level problem.Source: §3.1 · pp. 7–8

3.2 Penalty reformulation and its optimality

• With γ = Ω(δ^-0.5), global or local penalized solutions yield corresponding δ-approximate bilevel solutions, and this penalty order is tight.The global and local solution relations require their respective conditions on the candidate penalty; the lower bound on γ is tight for achieving ϵγ = O(δ).Source: §3.2 · pp. 8–9
• An δ-stationary point of the penalized problem is an ϵγ-stationary point of the original problem with ϵγ = O(δ), without requiring bilevel constraint qualifications.The stated stationary relation applies under Assumption 1, the conditions in Lemma 2, and either specified penalty choice.Source: §3.2 · p. 10
• Projected gradient descent solves the penalized problem, but the squared-gradient penalty can require costly second-order information; the function-value-gap variant avoids it.The function-value-gap algorithm instead uses first-order updates.Source: §3.2 · p. 10, §3.3 · p. 11

3.3 Fully first-order PBGD with function value gap

• Under the PL inequality and smoothness, ∇v(x) equals ∇xg(x, y*) at any lower-level optimum, enabling function-value-gap PBGD to use only first-order information.The method approximates a lower-level optimum with inner gradient-descent steps to estimate the penalized gradient.Source: §3.3 · p. 11

3.4 Analysis of PBGD with function value gap

• Under Assumptions 1–3, V-PBGD limit points are stationary for the penalized problem, and penalized local or global solutions correspond to approximate bilevel solutions.The stated solution relation has ϵγ ≤ δ.Source: §3.4 · p. 12
• O~(γϵ^-1) iterations find an ϵ-stationary point of the penalized problem; setting δ = ϵ and γ = O(ϵ^-0.5) gives O~(ϵ^-1.5) iterations.The first complexity recovers projected gradient descent’s iteration complexity with smoothness Θ(γ).Source: §3.4 · p. 14
• V-PBGD finds a local or global solution of the approximate upper-level problem under no stronger conditions than projected gradient descent needs for meaningful solutions.Source: §3.4 · p. 14
• Theorem 3 guarantees stationary-point convergence, but convergence to local or global minima requires additional assumptions, including arguments for escaping saddle points.Random initialization or perturbations during projected gradient descent can, according to cited recent work, almost surely ensure convergence to local minima.Source: §3.4 · p. 14

3.5 Extension to the stochastic version of PBGD

• V-PBSGD extends the method by using SGD for the lower-level problem and an approximate stochastic gradient of Fγ for the outer update.Source: §3.5 · p. 15
• The stochastic convergence result assumes unbiased stochastic gradients with bounded variance and the assumptions of Theorem 3.Theorem 4 is stated for V-PBSGD; the supplied passage does not provide its full bound.Source: §3.5 · p. 15

4 Solving Bilevel Problems with Lower-level Constraints

• The constrained method has finite-time convergence under assumptions weaker than the commonly used strong-convexity assumption.The section considers a fixed lower-level constraint set and assumes C and U are convex and compact.Source: §4 · p. 18

4.1 Penalty reformulation

• Under Proposition 4's conditions, a local or global solution of the penalized problem is a local or global solution of an approximate bilevel problem.The section uses the lower-level function-value gap g(x, y) − v(x) as its penalty.Source: §4.1 · pp. 18–19

4.2 PBGD under lower-level constraints

• Proposition 5 makes v(x) differentiable under specified assumptions, with its gradient evaluable using any lower-level solution.V-PBGD approximates that gradient by running projected gradient descent on the lower-level problem, then updates over C × U.Source: §4.2 · pp. 20–21
• With δ = ϵ, iteration complexity is Õ(ϵ^-1.5) under Condition (b) or Õ(ϵ^-2) under Condition (a) of Proposition 4.The general bound is Õ(γϵ^-1), matching projected gradient descent with smoothness Θ(γ).Source: §4.2 · p. 22

5.1 Penalty reformulation

• For γ > L√µ, global solutions of the nonsmooth penalized problem are global solutions of the original bilevel problem; if ∥∇_y g(x, y)∥ is convex in y, the same holds locally.The penalty uses γ∥∇_y g(x, y)∥ and can use a constant γ = O(1), independent of ϵ.Source: §5.1 · pp. 22–23

5.2 The Prox-linear algorithm

• PBPL applies Prox-linear optimization to the composite objective by linearizing f and ∇_y g and retaining the Euclidean norm penalty.It solves each subproblem to a specified accuracy.Source: §5.2 · p. 23

5.3 Convergence analysis of PBPL

• The convergence analysis assumes smoothness of f, g, and ∇_y g, while developing efficient solvers for PBPL's subproblem is outside the paper's scope.For special lower-level structure, the subproblem's nonsmooth component may have a closed-form proximal operator, allowing proximal gradient descent.Source: §5.3 · pp. 24–25

6 Simulations

• The simulations verify V-PBGD and PBPL on toy bilevel problems before comparing PBGD with baselines on data hyper-cleaning.The section introduces these as its two experimental aims.Source: §6 · p. 25

6.1 Numerical verification

• V-PBGD consistently finds local solutions from 1,000 random starts; its iteration complexity is Θ(γ), while lower-level accuracy is Θ(1/γ^2).The numerical test uses γ = 10 and reports the complexity and accuracy scaling as consistent with Theorem 3.Source: §6.1 · p. 25
• PBPL converges to local solutions from 1,000 random starts and reaches zero lower-level optimality gap with γ ≥ 0.3 in the example.The text notes that PBPL may be hard to implement when its subproblem lacks a closed-form solution.Source: §6.1 · pp. 25–26

6.2 Data hyper-cleaning

• V-PBGD achieves the best solution quality among the baselines, while PBGD shows no steep increase in memory or runtime versus ITD baselines.The comparison reports solution quality in Table 3 and GPU memory and runtime to highest test accuracy in Table 4.Source: Table 3 · p. 27, Table 4 · p. 27, §6.2 · p. 27
• On MNIST, the algorithms are compared for speed, memory usage, and solution quality against IAPTT-GM, BOME, RHG, and T-RHG, using linear and MLP models with 50% training-label pollution.The data are split into 5,000 training, 5,000 validation, and 10,000 test examples; polluted labels are drawn uniformly.Source: §6.2 · p. 27

7 Conclusions

• The penalty reformulation approximately recovers original bilevel solutions under generic conditions verifiable with commonly made assumptions.The paper considers lower-level problems that may be nonconvex and constrained.Source: §7 · p. 28
• PBGD has established finite-time convergence for both unconstrained and constrained lower-level problems.The paper also proposes fully first-order and stochastic PBGD versions for some settings.Source: §7 · p. 28
• Experiments verify the effectiveness of the proposed algorithm.Source: §7 · p. 28

A Omitted Proof in Section 2

• Restricted α-sublinearity requires a bound relative to the projection onto a function’s minimum-point set.Continuous convex or star-convex functions on a closed convex set with a nonempty minimum set satisfy it for every α in [0, 1].Source: §A.1 · pp. 31–32
• The stronger Theorem 2 version shows that a local solution of the penalized problem is a local solution of an approximate bilevel problem under its stated assumptions.The theorem assumes continuity of p, a ρ-squared-distance-bound property, local optimality of the penalized point, and Lipschitz continuity of f in y.Source: §A.1 · p. 32
• The stronger theorem replaces a condition from Theorem 2 with restricted α-sublinearity, a weaker requirement in the stated comparison.The proof establishes feasibility of the approximate problem before transferring local optimality from the penalized problem.Source: §A.1 · p. 32

B Omitted Proof in Section 3

• With p(x, y) = ∥∇_y g(x, y)∥^2, penalized stationary points imply ε-stationary points of the unconstrained problem without additional assumptions.The proof chooses γ = Ω(δ^-0.5) to satisfy the feasibility condition.Source: §B.3 · pp. 34–35
• For the alternative penalty g(x, y) − v(x), the proof uses a PL condition to relate lower-level gradient norm and objective gap.The gap penalty vanishes exactly on the lower-level solution set.Source: §B.1 · pp. 33–34, §B.3 · p. 35
• The proof constructs a multiplier-like vector w from the distance to a lower-level solution to establish the stationarity conditions for the gap penalty.It uses w = γ(y − y*(x)) and the bound γ = Ω(δ^-0.5).Source: §B.3 · p. 35

C Proof of Proposition 5

• Under either Assumption 5(ii) or Assumptions 5(i) and 5(iii), solutions can be selected across x values with Lipschitz constant L_S.The stated constants are L_S = L_g μ̄ in case (a) and L_S = L_g(μ+1)(L_g+1) in case (b).Source: C Proof of Proposition 5 · p. 36
• For the generalized lower-level objective g₂(x,y) = g(x,y) + g₁(y), the value function v₂ is L_v-smooth with L_v = L_g(1 + L_S).The proof also obtains ∇v₂(x) = ∇ₓg(x,y*) for every y* in S₂(x).Source: C Proof of Proposition 5 · pp. 36–37
• Choosing g₁ as the indicator of U makes v₂ equal v and S₂ equal S, so Proposition 5 follows from Proposition 7 and Lemma 6.The indicator is zero on U and infinite elsewhere.Source: C Proof of Proposition 5 · p. 36

D Proof for Proposition 6

• For γ ≥ Lρ, every global BP solution is globally optimal for BPγp; for γ > Lρ, an ε₂-global penalty solution yields an approximate BP solution with ε_γ ≤ ε₂/(γ−Lρ).The theorem assumes p is a ρ-distance-bound function and f(x,·) is L-Lipschitz continuous on U(x).Source: D Proof for Proposition 6 · p. 38
• A local solution of BPγp is a local solution of BP when γ > Lρ and the stated continuity, Lipschitz, and convexity conditions hold.These include convexity of U(xγ) and p(xγ,·), continuity of p(x,·), and local Lipschitz continuity of f(xγ,·).Source: D Proof for Proposition 6 · p. 38
• The proof applies the theorems to Proposition 6 by showing that ∥∇ᵧg(x,y)∥ is a √μ-distance-bound function and using the unconstrained- U special cases.It derives Proposition 6's two conditions from Theorems 8 and 9.Source: D Proof for Proposition 6 · p. 38