On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation

1 Introduction

• Direct implicit-gradient methods typically assume an unconstrained, strongly convex lower-level problem, leaving nonconvex or constrained cases difficult to handle.The paper also notes that weak lower-level curvature can make these problems highly ill-conditioned.Source: §1 · p. 2

1.1 Overview of Main Results

• The paper studies how the penalty formulation approximates the original bilevel landscape, a relationship needed because the penalty problem is only an approximation.The resulting algorithmic problem also retains nested optimization and may require a small penalty parameter.Source: §1.1 · p. 3
• Under proximal-EB and regularity conditions, penalty and hyper-objective values and derivatives are O(σ)-close, including settings with multiple lower-level solutions.The analysis relies on continuity of lower-level solution sets; the multiple-solution case uses mild solution-set continuity and constraint regularity assumptions.Source: §1.1 · p. 3
• The algorithm avoids directly computing exact lower-level minimizers by using an alternative saddle-point formulation to find an approximate stationary point.The approach is designed for a proximal-EB condition that need only hold near lower-level solutions, including points with O(δ) proximal error.Source: §1.1 · p. 4
• O(ε^-7) stochastic oracle complexity is achieved by polynomially decreasing the penalty parameter, saving an O(ε^-1) order of complexity.The stated O(ε^-8) stochastic bound for a plug-in min-max method provides a comparison point.Source: §1.1 · p. 4
• Under mean-squared smoothness of stochastic gradients, a fully single-loop version uses O(1) oracle calls per iteration and achieves O(ε^-5) stochastic oracle complexity.The paper reports that its results match best-known fully first-order stochastic bilevel complexity for strongly convex, unconstrained lower-level problems and also apply under a PL condition [67].Source: §1.1 · p. 4

1.2 Related Work

• For nonconvex or constrained lower-level problems, Hessian inversion may be unstable and boundary solutions can require unknown dual variables, motivating methods that avoid explicit implicit gradients.Projection operations can also obstruct iterative differentiation when the lower-level feasible set is constrained.Source: §1.2 · pp. 5–6
• Earlier penalty analyses focused on equivalence near minimizers, while this work targets landscape relations beyond such infinitesimal neighborhoods and includes stochastic implementations.The related work [52] connects the penalty problem to an ε-relaxed constrained formulation and studies only deterministic double-loop algorithms.Source: §1.2 · pp. 5–6

• The objectives are twice continuously differentiable and jointly smooth, and are assumed bounded below and coercive in the lower-level variable.Source: §2 · p. 6
• The domains are closed and convex; Y is bounded and described by convex inequality constraints and linear equality constraints, while f is bounded on X × Y.Source: §2 · p. 6
• The notation includes projections onto sets, normal cones, matrix kernels and images, and the pseudoinverse of a symmetric matrix.Source: §2 · pp. 6–7
• Solution-set continuity is measured using Hausdorff distance, with local Lipschitz continuity bounding distances between solution sets at nearby inputs.Source: §2 · pp. 6–7
• For constrained problems, active inequalities are identified by equality at the feasible point, and LICQ requires active inequality and equality constraint gradients to be linearly independent.Source: §2 · p. 7

3 Landscape Analysis and Penalty Method

• The penalty formulation perturbs the lower-level objective to h_σ(x, y) = σf(x, y) + g(x, y), enabling analysis of its landscape against the original problem.Source: §3 · p. 7

3.1 Sufficient Conditions for Differentiability

• Locally Lipschitz solution sets alone may not suffice under constraints; the analysis adds lower-level constraint regularity, including LICQ and strict complementarity at a solution.Source: §3.1 · p. 9

3.2 Asymptotic Landscape

• With locally Lipschitz solution sets and a regular lower-level solution, Theorem 3.1 gives an explicit mixed derivative formula, including when multiple lower-level solutions exist.Source: §3.2 · p. 10

3.2.1 Special Case: Unique Solution and Invertible Hessian

• For a unique lower-level solution, Assumption 6 and an invertible Lagrangian Hessian imply local Lipschitz continuity of the solution set and an explicit mixed derivative formula.Source: §3.2.1 · p. 11

3.3 Landscape Approximation with σ > 0 ∂

• When the mixed derivative is well-defined and uniformly Lipschitz over the penalty interval, the gradient gap between ψ_σ and ψ is O(σ); ε-stationarity also yields an O(ε + σ)-KKT point.Source: §3.3 · pp. 11–12

4.1 Stationarity Measures

• An ε-stationary point of the saddle formulation maps to an (1 + l_g, 1/μ)ε-stationary point of ψ_σ, and additional assumptions yield an ((1 + l_g, 1/μ)ε + L_σ σ)-stationary point of ψ.Source: §4.1 · p. 13

4.2 First-Order Method with Large Batches

• Because the proximal error bound holds only at small proximal errors, the analysis cannot guarantee improving lower-level distance when iterates leave that region; σ_k is decreased gradually to avoid an overly conservative start.Source: §4.2 · p. 14
• The double-loop method uses proximal envelopes to obtain a strongly convex inner minimization, then chooses increasing inner iterations or batch sizes while gradually decreasing σ_k.Source: §4.2 · pp. 14–15

4.3 A Fully Single-Loop First-Order Algorithm

• With mean-squared-smooth stochastic oracles that allow two-point queries, momentum-assisted estimators support a fully single-loop algorithm with O(1) oracle calls before each outer-variable update.Source: §4.3 · pp. 15–16

5.1 Analysis of Algorithm 1

• Algorithm 1’s step-size relations keep y_k and z_k relatively close to their solution sets and permit approximate proximal operations without restarting each outer iteration.The relations between α_k and β_k support solution-set tracking; the relation between α_k and T_kγ_k supports proximal evaluation.Source: §5.1 · p. 17
• For E[∥∇ψϵ(xR)∥] = O(ϵ), sample-complexity upper bounds are O(ϵ−7), O(ϵ−5), and O(ϵ−3) for fully stochastic, only upper-level stochastic, and deterministic cases, respectively.Source: §5.1 · p. 17
• A single-loop design for Algorithm 1 may worsen the overall complexity unless momentum assistance is used.Algorithm 2’s momentum-assisted version uses O(1) samples per iteration and improves the fully stochastic complexity bound.Source: §5.1 · p. 17, §5.2 · p. 19

5.2 Analysis of Algorithm 2

• Algorithm 2’s convergence analysis requires an additional boundedness assumption on the movement in w_y,k.The assumption is stated as a technical requirement for the momentum-assisted fully single-loop implementation.Source: §5.2 · p. 18
• Algorithm 2 achieves sample complexities O(ε^-5), O(ε^-4), and O(ε^-3) for fully stochastic, only upper-level stochastic, and deterministic cases, respectively.It uses O(1) samples per iteration; in the fully stochastic setting, its stationarity bound includes a log K factor with K^-1/5 scaling, with probability at least 2/3.Source: §5.2 · pp. 18–19

6 Conclusion

• The paper establishes O(σ)-closeness between the penalty function and hyper-objective under a small-error proximal error-bound condition, then analyzes first-order algorithms for penalty-stationary points.The conclusion also describes the algorithms as applicable to double-loop and single-loop methods with explicit stochastic oracle-complexity bounds.Source: §6 · p. 19
• The paper leaves tightness of its first-order oracle-complexity bounds open, particularly for stochastic oracles and constrained formulations.The conclusion contrasts its setting with an O(ε^-2) deterministic bound for unconstrained, strongly convex lower-level problems.Source: §6 · p. 19
• When lower-level constraints depend on x, implicit-gradient formulas require estimating Lagrange multipliers, including for penalty-function stationarity.Developing an efficient first-order algorithm for this case is identified as future work.Source: §6 · p. 19
• For a merely convex lower-level objective, an ε-stationary point of (P_saddle) is also an ε-KKT solution of (P_con), while extending results to stochastic settings remains open.The conclusion identifies [45] as the first investigation of this direction in deterministic settings, to the authors’ knowledge.Source: §6 · p. 19
• Nonsmooth objectives are considered as a future direction when efficient proximal operators are available; whether the analysis must change significantly is left open.Source: §6 · p. 19

Appendix A Auxiliary Lemmas

• A differentiable minimizer value function has gradient ∇_w f(w, θ*) for any minimizer θ* when the solution map is Lipschitz continuous.The cited auxiliary lemma also gives L(1 + L_S)-smoothness when f is L-smooth and the solution map has Lipschitz constant L_S.Source: Appendix A · p. 24

B.1 Proof of Proposition 3.5

• Under uniqueness, regularity, and strict complementary slackness, the lower-level solution remains locally singleton and differentiable by the implicit function theorem.The proof establishes a neighborhood in which the solution map is uniquely given by that theorem.Source: §B.1 · pp. 24–25

B.2 Proof of Theorem 3.6

• The implicit function theorem provides derivatives of y with respect to x and σ in the local region considered by the proof.Source: §B.2 · p. 25
• The proof also considers the derivatives taken in the swapped order.Source: §B.2 · p. 25
• Existence of the mixed derivative at σ = 0+ implies lim_{σ→0} ψ_σ(x) = ψ(x).Source: §B.2 · p. 25

B.3 Proof of Proposition 3.4

• For a smooth objective and sets satisfying Assumption 4, the theorem assumes a locally Lipschitz solution map and regularity and continuity conditions at a minimizer.Under these conditions, the theorem states a necessary condition on the Lagrangian Hessian.Source: §B.3 · p. 25
• A perturbation in the parameter yields a nearby solution under local Lipschitz continuity, while the active-constraint matrix has a positive minimum right singular value.The proof uses the full-rank active-constraint matrix and an O(δ) change in Lagrangian gradients.Source: §B.3 · p. 26
• The proof’s contradiction shows that condition (10) is necessary for the solution map to be locally Lipschitz continuous.A kernel component of the perturbation cannot be canceled by the O(δ) terms, so no feasible optimum exists in the required neighborhood.Source: §B.3 · p. 26

• Theorem B.2 gives ∇^2l*(w) when the solution map is locally uniformly Lipschitz and a solution satisfies the stated regularity and Hessian conditions.The theorem requires continuous differentiability and L-smoothness, with the relevant Hessian locally Lipschitz jointly in w, the active multipliers, and the solution.Source: §B.4 · p. 27
• Theorem 3.1 follows by specializing Theorem B.2 to the mixed derivatives with respect to x and σ.Source: §B.4 · p. 27
• The proof treats a possibly singular lower-level Hessian by separating its nonzero-eigenvalue subspace from its kernel.It fixes a basis for the image and uses the implicit function theorem on the reduced problem.Source: §B.4 · pp. 27–28

B.5 Proof of Theorem 3.8

• The proof bounds the penalized objective’s value error by a term proportional to σ and establishes gradient approximation through Lipschitz continuity in σ.The value comparison uses the nearest lower-level solution; the gradient comparison applies the explicit mixed-derivative formula.Source: §B.5 · pp. 30, 32

B.6 ϵ-Stationary Point and ϵ-KKT Solution

• An ϵ-stationary point of ψσ is an O(ϵ + σ)-KKT solution of (Pcon), for σ ≤ 1 under the stated assumptions.Source: §B.6 · p. 32

C.1 Descent Lemma for wy,k, wz,k

• The inner-iterate analysis establishes per-iteration descent bounds for wy,k and wz,k.Source: §C.1 · pp. 33–34

C.2 Descent Lemma for Φσ,ρ

• The Φσ,ρ analysis splits its change into an iterate-update term and a penalty-parameter-change term, then combines bounds on both.Source: §C.2 · p. 35

C.2.1 Bounding (ii)

• When σ decreases, the proof bounds the contribution labeled (ii) by comparing proximal minimizers under the two penalty parameters.Source: §C.2.1 · pp. 35–36

C.2.2 Bounding (i)

• For contribution (i), the proof uses Assumption 1 to cancel positive proximal-error terms involving z against terms from the other bound.Source: §C.2.2 · p. 38

C.3 Proof of Theorem 5.1

• Combining Proposition C.3, Lemma C.2, and Lemma 3.7 gives, omitting expectations, an upper bound on V_{k+1}−V_k with negative weighted squared-error and distance terms.The displayed terms include −(1/16)σ_kα_k∥x_k−x̂_k∥², −(1/8)σ_kα_k∥x_k−x_{k+1}∥², and −β_k/(4σ_kρ) dist²(z_k,T(x_k,0)), followed by O.Source: §C.3 · p. 39

C.4 Proof of Corollary 5.2

• Substituting the step-size rates makes the right-hand side O(log K), yielding Corollary 5.2.Source: §C.4 · p. 41

Appendix D Analysis for Algorithm 2

• For Algorithm 2, the appendix adds descent lemmas for the noise variances of its momentum-assisted gradient estimators.Source: Appendix D · p. 42, §D.1 · pp. 42–43

D.1 Descent Lemma for Noise-Variances

• The stochastic analysis establishes per-iteration descent bounds for the gradient-estimator noise variances.The proof uses unbiased gradient oracles and Assumption 11 in bounding the variance terms.Source: §D.1 · pp. 42–43

D.2 Descent Lemma for wy,k, wz,k

• The stochastic inner-iterate analysis bounds both proximal progress and expected movements of wy,k and wz,k.Source: §D.2 · p. 44

D.3 Descent Lemma for Φσ,ρ

• The Φσ,ρ descent analysis for Algorithm 2 follows the deterministic analysis with corresponding stochastic-gradient terms.Source: §D.3 · p. 45

D.4 Descent in Potentials

• The stochastic potential analysis combines descent bounds and noise controls to obtain a bound with negative terms for iterate changes.Source: §D.4 · pp. 45–47

D.5 Proof of Theorem 5.4

• Theorem 5.4’s proof sums the potential bound and uses Assumption 12 and compactness of Y to bound the remaining terms.Source: §D.5 · pp. 49–50

• The Corollary 5.5 proof is stated to be almost identical to the proof of Corollary 5.2.Source: §D.6 · p. 50

E.1 Proof of Lemma 3.7

• T(x, σ) is locally O(l_g,1/μ)-Lipschitz in x and O(l_f,0/μ)-Lipschitz in σ.Source: §E.1 · p. 50

E.2 Proof of Lemma 4.1

• An O(ε)-stationary point for ∇ψ_σ(x) is obtained through projection-error control; the proof also bounds ∥∇ψ_σ(x) − ∇ψ(x)∥ by L_σ σ.Source: §E.2 · p. 51

E.3 Proof of Lemma A.3

• One projected gradient-descent step for the strongly convex inner problem contracts the distance to its solution by a factor of 9/10.Source: §E.3 · p. 51

E.4 Proof of Lemma A.4

• The comparison of proximal solutions at different σ values includes a 9/10 contraction term and a term measuring the gradient difference.Source: §E.4 · p. 52

E.5 Proof of Lemma A.5

• The Lemma A.5 argument uses Lipschitz bounds in x and y together with ρ^-1-smoothness of the inner minimization problem.Source: §E.5 · p. 52