PaperlayerView exact revision on arXiv

Source-linked AI summary

First-order penalty methods for bilevel optimization

Zhaosong Lu, Sanyou Mei

arXiv:2301.01716v2math.OCcs.LGcs.NAmath.NAstat.ML

TL;DR

The paper addresses the difficulty of obtaining implementable approximate solutions for bilevel optimization. It uses first-order penalty methods whose subproblems are structured minimax problems. The methods have stated operation-complexity guarantees for unconstrained and constrained cases, while explicitly constrained upper-level problems are left for future work.

  • Problem

    A double penalty approach for bilevel optimization is typically not implementable because no general method is available for approximately solving its subproblems.

    Source: §1 · p. 2

  • Method

    The paper develops first-order penalty methods that reformulate bilevel problems as structured minimax problems solvable by a first-order method.

    Source: §1 · p. 2

  • Results

    The operation complexities for finding ε-KKT solutions are O(ε^-4 log ε^-1) when ˜g ≡ 0 and O(ε^-7 log ε^-1) otherwise.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The paper presents an implementable method with complexity guarantees and demonstrates that bilevel optimization can be approximately solved as minimax optimization.

    Source: §1 · p. 2

    The proposed first-order methods address problem (3), excluding the explicit upper-level constraint g(x, y) ≤ 0; extending them to problem (1) is left for future research.

    Source: §6 · p. 21

Abstract

from arXiv · show

In this paper we study a class of unconstrained and constrained bilevel optimization problems in which the lower level is a possibly nonsmooth convex optimization problem, while the upper level is a possibly nonconvex optimization problem. We introduce a notion of $\varepsilon$-KKT solution for them and show that an $\varepsilon$-KKT solution leads to an $O(\sqrt{\varepsilon})$- or $O(\varepsilon)$-hypergradient based stionary point under suitable assumptions. We also propose first-order penalty methods for finding an $\varepsilon$-KKT solution of them, whose subproblems turn out to be a structured minimax problem and can be suitably solved by a first-order method recently developed by the authors. Under suitable assumptions, an \emph{operation complexity} of $O(\varepsilon^{-4}\log\varepsilon^{-1})$ and $O(\varepsilon^{-7}\log\varepsilon^{-1})$, measured by their fundamental operations, is established for the proposed penalty methods for finding an $\varepsilon$-KKT solution of the unconstrained and constrained bilevel optimization problems, respectively. Preliminary numerical results are presented to illustrate the performance of our proposed methods. To the best of our knowledge, this paper is the first work to demonstrate that bilevel optimization can be approximately solved as minimax optimization, and moreover, it provides the first implementable method with complexity guarantees for such sophisticated bilevel optimization.

1 Introduction

Bilevel optimization is widely studied, but many existing methods address only special cases, and a double penalty approach lacks a generally available solver for its subproblems. The paper develops implementable first-order penalty methods with complexity guarantees and introduces notation and terminology for approximate minimax solutions.

1 Introduction

  • Bilevel optimization appears in applications including adversarial training, hyperparameter tuning, meta-learning, neural architecture search, and Stackelberg games.Source: §1 · p. 1
  • The double penalty method is typically not implementable because no general method is available for finding approximate solutions of its subproblems.The subproblems penalize constraints associated with both upper- and lower-level feasible sets.Source: §1 · p. 2
  • The paper recasts bilevel optimization approximately as structured minimax optimization and develops an implementable first-order penalty method with complexity guarantees.The proposed subproblems can be solved using a first-order method from [41, Algorithm 2].Source: §1 · p. 2
  • The method has operation complexity O(ε^-4 log ε^-1) when ˜g ≡ 0 and O(ε^-7 log ε^-1) otherwise for finding an ε-KKT solution.Operation complexity counts evaluations of gradients and proximal operators.Source: §1 · p. 2
  • The approach applies to cases with nonsmooth f and ˜f and with ˜f and ˜g nonconvex in x, which the authors say existing methods do not suitably handle.Source: §1 · p. 2

1.1 Notation and terminology

  • The notation section defines conventions for norms, distances, proximal operators, and subdifferentials, and introduces approximate optimality and stationarity for minimax problems.The supplied passages state the definitions’ setup but not their full conditions.Source: §1.1 · pp. 2–3

2 Unconstrained bilevel optimization

For unconstrained bilevel optimization, the paper constructs penalty subproblems as structured minimax problems and proposes ideal and practical methods. Under stated assumptions, the practical method has a complexity guarantee, and ε-KKT solutions imply approximate hypergradient stationarity.

2 Unconstrained bilevel optimization

  • The practical method assumes continuous objectives with smooth components and a convex lower-level objective in y; it also requires exactly evaluable proximal operators and compact domains.Source: §2 · p. 4
  • The penalty function Pρ(x, y, z) = f(x, y) + ρ(˜f(x, y) − ˜f(x, z)) yields a minimax problem that is nonconvex in (x, y) and concave in z.Its smooth component has Lipschitz-continuous gradient, while its possibly nonsmooth component has an exactly computable proximal operator.Source: §2 · p. 4
  • The ideal method solves a sequence of minimax problems, while the practical method finds an approximate stationary point of a single problem with a suitable penalty parameter.Source: §2 · p. 4
  • Any accumulation point of the ideal method’s iterates is an optimal solution, assuming Assumption 1 holds.Source: §2 · p. 4
  • Under Theorem 2’s smoothness and strong-convexity assumptions, an ε-KKT solution gives an O(√ε) hypergradient-based stationary point, improved to O(ε) when ρ ≥ cε^-1.The constant c is positive and independent of ε.Source: §2 · p. 6
  • O(ε^-4 log ε^-1) operation complexity finds an O(ε)-KKT solution using gradient and proximal-operator evaluations.The bound is for Algorithm 2 and counts evaluations of ∇f1, ∇˜f1, and proximal operators of f2 and ˜f2.Source: §2 · p. 7

3 Constrained bilevel optimization

The constrained bilevel problem is reformulated through lower-level penalties as a structured minimax problem, yielding ideal and practical first-order penalty methods. Under stated assumptions, the practical method has an operation-complexity guarantee for finding an approximate KKT solution.

3 Constrained bilevel optimization

  • The lower-level penalty adds μ times squared constraint violation, and the resulting minimax objective Pρ,µ is nonconvex in (x, y) but concave in z.Its smooth component has Lipschitz continuous gradient, while its possibly nonsmooth component has an exactly computable proximal operator.Source: §3 · pp. 7–8
  • The authors propose an ideal sequence-of-minimax method and a practical single-minimax method for the constrained problem.The ideal method is generally not implementable because finding an ε-optimal solution of its nonconvex-concave minimax subproblem is typically hard.Source: §3 · p. 8
  • Under Assumptions 1–3, every accumulation point of Algorithm 3's (xk, yk) iterates is an optimal solution of (25).Source: §3 · p. 8
  • The ε-KKT notion characterizes approximate solutions through stationarity, lower-level optimality, constraint feasibility, and complementarity conditions.The stated residual bounds include ε for lower-level objective gap, constraint violation, and complementarity.Source: §3 · p. 9
  • Under Assumptions 1–2, Algorithm 4 finds an O(ε)-KKT solution of (25) with O(ε^-7 log ε^-1) operation complexity.The complexity is measured by evaluations of ∇f1, ∇f̃1, ∇g̃ and proximal operators of f2 and f̃2.Source: §3 · p. 10

4 Numerical results

Preliminary experiments evaluate dynamic-parameter variants of Algorithms 2 and 4 on randomly generated unconstrained and constrained bilevel problems. In both settings, the reported approximate solutions significantly reduce objective value relative to their initial points.

4 Numerical results

  • The preliminary experiments use Matlab implementations and run on a desktop with a 3.60 GHz Intel i7-12700K 12-core processor and 32 GB RAM.Source: §4 · p. 10
  • For problems (52) and (53), the reported algorithm variants significantly reduced objective values: average final values were below average initial values over 10 random instances for each listed parameter setting.Source: Table 1 · p. 11, §4.1 · p. 11, Table 2 · p. 12

4.1 Unconstrained bilevel optimization with linear upper level and quadratic lower level

  • For unconstrained problem (52), the Algorithm 2 variant significantly reduces objective value versus the initial point across the tested dimension pairs.Table 1 reports average initial and final objective values over 10 random instances for each pair (n, m).Source: Table 1 · p. 11, §4.1 · p. 11

4.2 Constrained bilevel linear optimization

  • For constrained problem (53), the Algorithm 4 variant significantly reduces objective value versus the initial point across the tested dimension triples.Table 2 reports average initial and final objective values over 10 random instances for each triple (n, m, l).Source: Table 2 · p. 12, §4.2 · p. 12

5 Proof of the main results

The proofs establish convergence properties for penalty-method iterates in unconstrained and constrained bilevel settings, deriving the conditions behind the main result from an ε-stationary point of the penalized problem and bounding the evaluations needed by Algorithm 4 to find an approximate solution.

5.1 Proof of the main results in Section 2

  • As ρ_k→∞ and ε_k→0, the unconstrained penalty-method iterates converge along a subsequence to an optimal solution of problem (5).The proof uses Lemma 1 and continuity of f and ˜f to show lower-level optimality and attainment of f* at the limit.Source: §5.1 · p. 13
  • An ε-KKT solution yields an O(√ε)- or O(ε)-hypergradient-based stationary point under suitable assumptions.The proof bounds the distance to the lower-level solution and establishes the stated estimates when ε is sufficiently small and ρ sufficiently large.Source: §5.1 · pp. 13–14
  • With α=ˆα, δ=ˆδ, and H, H*, Hlow from (67), Algorithm 2 performs at most b N evaluations of ∇f1, ∇˜f1, and the proximal operators of f2 and ˜f2, respectively, to find an approximate solution (xε, yε) of problem (5) satisfying (23) and (24).Source: §5.1 · p. 15

5.2 Proof of the main results in Section 3

  • As ρ_k, μ_k→∞ and ε_k→0, the constrained penalty-method iterates converge along a subsequence to an optimal solution of problem (25).The limiting point satisfies upper-level optimality, lower-level constrained optimality, and feasibility; the argument uses the stated assumptions and continuity conditions.Source: §5.2 · pp. 17–18
  • Lemma 8 provides the link between an ε-stationary point of problem (33) and the relations used in proving Theorem 5.Its proof derives the required relations from stationarity conditions for the penalized objective under Assumptions 1 and 2.Source: §5.2 · p. 19
  • Setting ρ = ε^-1 and μ = ε^-2 puts problem (33) in structured minimax form, allowing Algorithm 6 to find an ε-stationary point whose conditions imply (45)–(51).The smooth component satisfies the required smoothness condition, and the proof applies Lemma 8 to obtain the stated relations.Source: §5.2 · p. 20
  • Algorithm 4 performs at most eN evaluations to find an approximate solution of problem (25) satisfying relations (45)–(51).The counted operations are evaluations of ∇f1, ∇˜f1, ∇˜g, and proximal operators of f2 and ˜f2.Source: §5.2 · pp. 20–21

6 Concluding remarks

The proposed first-order penalty methods address only problem (3); extending them to constrained problem (1) using a standard constraint-handling technique is left for future research.

6 Concluding remarks

  • The proposed methods address only problem (3), leaving extension to constrained problem (1) for future research.The paper notes that a standard technique could handle the constraint g(x, y) ≤ 0.Source: §6 · p. 21

A A first-order method for nonconvex-concave minimax problem

This appendix presents a first-order method for finding an ε-stationary point of a nonconvex-concave minimax problem. It applies a method for strongly-convex-strongly-concave minimax subproblems under stated assumptions, with iteration and evaluation bounds.

A first-order method for nonconvex-concave minimax problem

  • The method assumes compact domains for proper convex p and q, exactly evaluable proximal operators, and a smooth h that is concave in y.The domain and function assumptions appear in Assumption 4.Source: A A first-order method for… · p. 24
  • AIPP-S generally is not implementable for (99) because it requires an exact maximization, while the method in targets a different stationarity notion.The paper presents [41, Algorithm 2] for the ε-stationarity notion used in (99).Source: A A first-order method for… · p. 24
  • Algorithm 6 uses [41, Algorithm 2] to update iterates by applying a method for strongly-convex-strongly-concave minimax subproblems.The subproblem function is strongly convex in x, strongly concave in y, and smooth on dom p × dom q.Source: A A first-order method for… · pp. 24–25
  • Algorithm 6 terminates with an ε-stationary point in at most K + 1 outer iterations, and performs no more than N evaluations of each of ∇h and proximal operators of p and q.Source: A A first-order method for… · p. 26
Loading 2301.01716v2…