SGHA: A Single-Loop Fully First-Order Algorithm for Nonconvex-Strongly-Convex Bilevel Optimization

SGHA: A Single–Loop Fully First-Order Algorithm for Nonconvex–Strongly-Convex Bilevel Optimization Zhihao Gu1*

arXiv:2608.23211v1 [math.OC] 24 Aug 2026

1

Qilong Wu2*

Junchi Yang2†

Department of Industrial and Manufacturing Engineering The Pennsylvania State University 2 School of Data Science The Chinese University of Hong Kong, Shenzhen zbg5155@psu.edu qilongwu@link.cuhk.edu.cn yangjunchi@cuhk.edu.cn

August 25, 2026

Abstract In this work, we study the oracle complexity of finding an ϵ-stationary point for nonconvex– strongly-convex (NC–SC) bilevel optimization using only first-order oracles. Existing methods achieving the best-known complexity guarantees typically rely on double-loop, penalty-based procedures. We propose a novel single-loop algorithm based on a constrained reformulation in which lower-level stationarity is imposed as a constraint. Specifically, we construct a regularized Lagrangian by introducing a quadratic regularizer and restricting the dual variable to a bounded domain, and then apply Smoothed Gradient Descent Ascent [Zhang et al., 2020], with Hessian-vector products approximated via finite differences of gradients. We refer to the resulting deterministic and stochastic algorithms as SGHA and Stoc–SGHA, respectively. In the deterministic setting, SGHA achieves an oracle complexity of O(κ̄5y ϵ−2 ), where κ̄y denotes the relevant condition
number. In the stochastic setting, Stoc–SGHA achieves an oracle complexity −6 −3 of O κ̄17 with probability at least 1 − ρ for any ρ ∈ (0, 1), and an oracle complexity of y ϵ
ρ −6 O κ̄17 ϵ in expectation under an additional bounded-iterate assumption. Moreover, under y an additional stochastic smoothness assumption imposed only on the lower-level objective, the
11 −4 −2 stochastic oracle complexity of Stoc–SGHA improves to O κ̄ ϵ ρ with high probability y
−4 and O κ̄11 ϵ in expectation, matching the ϵ-dependence of the lower bounds. y

Keywords: Bilevel optimization; fully first-order methods; finite-difference approximation; oracle complexity

1

Introduction

Bilevel optimization [Colson et al., 2007] is a fundamental framework for modeling hierarchical decision-making problems with two nested levels. It originates from the two-player general-sum ∗

Equal contributions. The corresponding author. Also affiliated with Shenzhen Research Institute of Big Data and Shenzhen International Center for Industrial and Applied Mathematics. †

1

Stackelberg game [Von Stackelberg, 2010], and reflects the sequential nature of the decision process of two players. Recently, it has found broad applications in machine learning and related areas, including meta-learning [Rajeswaran et al., 2019], hyperparameter optimization [Franceschi et al., 2018, Bao et al., 2021], model selection [Giovannelli et al., 2021, Kunapuli, 2008], adversarial learning [Goodfellow et al., 2020], and reinforcement learning [Hong et al., 2023, Konda and Tsitsiklis, 1999, Zeng et al., 2024]. In its canonical form, bilevel optimization can be written as the following problem: min F (x) = f (x, y ∗ (x)),

s.t.

x∈Rdx

y ∗ (x) ∈ arg min g(x, y).

(P)

y∈Rdy

The hyper-objective F depends on the upper-level variable x both directly through f and indirectly through the lower-level solution y ∗ (x). We consider the smooth nonconvex–strongly-convex (NC–SC) setting [Ghadimi and Wang, 2018, Hong et al., 2023, Ji et al., 2021], in which the lower-level objective g(x, y) is strongly convex in y, while the upper-level objective f (x, y) may be nonconvex. Under this assumption, the lower-level solution y ⋆ (x) is unique, and the resulting hyperobjective F is well defined and smooth. By the implicit function theorem [Krantz and Parks, 2002], the gradient of the hyperobjective can be characterized as follows: i−1

h

∇F (x) = ∇x f (x, y ∗ (x)) − ∇2xy g(x, y ∗ (x)) ∇2yy g(x, y ∗ (x))

∇y f (x, y ∗ (x)).

(1)

This motivates methods that estimate ∇y ∗ (x) and substitute it into the gradient expression [Gould et al., 2016, Domke, 2012, Ghadimi and Wang, 2018, Dagréou et al., 2022]. However, they typically rely on the Hessian of g. To avoid costly Hessian–vector products (HVPs), fully first-order methods have recently received increasing attention in bilevel optimization [Kwon et al., 2023b, Liu et al., 2022]. A prominent line of work adopts the penalty formulation Fλ (x, y) = f (x, y) + λ g(x, y) − g ⋆ (x) , 

with g ⋆ (x) = min g(x, y) = g x, y ⋆ (x) ,



y

where λ > 0 is the penalty parameter and g(x, y) − g ⋆ (x) measures lower-level suboptimality. Chen et al. [2025b] and Chen et al. [2025a] analyze this penalty-based approach with the choice λ = Θ(ϵ−1 ). e −2 ) In particular, F2 BA and F2 BA+ achieve a nearly optimal fully first-order oracle complexity of O(ϵ in the deterministic NC–SC setting, while F2 BSA and F3 BSA attain the best-known complexity of e −6 ) in the stochastic NC–SC setting. O(ϵ However, these complexity guarantees rely crucially on double-loop procedures. Specifically, the algorithms introduce two auxiliary variables, z and y, and solve the corresponding inner subproblems to prescribed accuracies in order to approximate g ⋆ (x) and arg miny Fλ (x, y). A key observation in Chen et al. [2025b] is that, when the inner iterates remain sufficiently close to their exact minimizers, the outer update in x can use a relatively large stepsize because the value function Fλ⋆ (x) := miny Fλ (x, y) has a smoothness constant of order Θ(1), independent of the large penalty parameter λ. In contrast, if the inner loops are removed directly, the tracking errors in y and z evolve simultaneously with the upper-level variable x, while the large penalty parameter deteriorates the conditioning of the penalized problem. As a result, algorithms and analyses that cannot exploit the λ-independent smoothness of Fλ⋆ typically yield worse complexity guarantees [Liu et al., 2022, Shen and Chen, 2023, Kwon et al., 2023b]. Therefore, a direct single-loop implementation of the penalty-based approach does not retain the best-known dependence on ϵ. 2

Can a single-loop, fully first-order algorithm match the best ϵ-dependence achieved by double-loop penalty methods? We answer this question by proposing a novel single-loop algorithm, SGHA (Smoothed GDA with Hessian Approximation), together with its stochastic counterpart, Stoc-SGHA. Our approach builds on the Smoothed Gradient Descent Ascent (GDA) framework [Zhang et al., 2020] and adapts it to NC–SC bilevel optimization through a regularized Lagrangian reformulation, combining a first-order approximation for Hessian–vector products. The starting point of our approach is to reformulate Problem (P) as an equality-constrained problem. Since the lower-level objective g(x, ·) is strongly convex, the lower-level solution is uniquely characterized by the first-order optimality condition ∇y g(x, y ∗ (x)) = 0. Therefore, Problem (P) can be equivalently written as min

x∈Rdx , y∈Rdy

f (x, y),

s.t.

∇y g(x, y) = 0.

(R)

We then introduce the associated Lagrangian function L(x, y, λ) := f (x, y) + λ⊤ ∇y g(x, y),

(L)

where λ ∈ Rdy is the multiplier. The Lagrangian (L) is generally nonconvex in the primal variables (x, y) and affine in the dual multiplier λ. Although the equality-constrained problem can be formally expressed as minx,y maxλ L(x, y, λ), the inner maximization is unbounded whenever ∇y g(x, y) ̸= 0, since λ is unconstrained. Consequently, the resulting formulation is not a finite-valued smooth minimax problem, and many standard minimax algorithm analyses cannot be applied directly. Moreover, our goal is to exploit the particular structure of this Lagrangian to obtain sharper complexity guarantees. To this end, we apply Smoothed GDA with three key modifications. First, we restrict the multiplier λ to a sufficiently large bounded domain. Second, we introduce a small concave quadratic regularizer in λ, which renders the inner maximization strongly concave with well-controlled conditioning. Third, because the primal gradients of L involve Hessian–vector products of g, we approximate these terms using finite differences of first-order gradients. These modifications yield a well-conditioned minimax surrogate amenable to Smoothed GDA analysis while preserving the fully first-order nature of SGHA. Our main complexity results are summarized in Table 1. Here, κy and κ̄y denote the condition numbers defined in Definition 1. In the deterministic setting, Theorem 4 shows that SGHA (Algorithm 1) finds an ϵ-stationary point of the NC–SC bilevel problem with oracle complexity O(κ̄5y ϵ−2 ). In the stochastic setting, Theorems 8 and 9 show that Stoc-SGHA (Algorithm 2) achieves 







−6 −3 with probability at least 1 − ρ for any ρ ∈ (0, 1), and O κ̄17 ϵ−6 in oracle complexity O κ̄17 y ϵ ρ y expectation under an additional bounded-iterate assumption. These bounds remove the logarithmic factors appearing in the best-known complexities of Chen et al. [2025b]. Moreover, when the lower-level objective g satisfies the  stochastic smoothness condition in Assumption 3, Theorems    10 −4 ρ−2 with probability at least 1 − ρ, and O κ̄11 ϵ−4 in and 11 improve these bounds to O κ̄11 ϵ y y expectation. They match the lower bound in [Arjevani et al., 2023] in the dependence on ϵ.

3

Table 1: Oracle complexity for finding an ϵ-stationary point in deterministic and stochastic NC–SC bilevel optimization. Shaded cells denote our methods. Problem Class

Algorithm

Oracle

# Loops

Det. NC–SC BiO

F2 SA [Kwon et al., 2023b] MEHA [Liu et al., 2024] V-PBGD [Shen and Chen, 2023] F2 BA [Chen et al., 2025b] F2 BA+ [Chen et al., 2025a] SGHA (Theorem 4) Lower Bound [Chen et al., 2025a]

FO FO FO FO FO FO FO

single–loop single–loop double–loop double–loop double–loop single–loop –

e 7 ϵ−3 ) O(κ̄ y O(poly(κ̄y )ϵ−4 ) O(poly(κ̄y )ϵ−3 ) e 4 ϵ−2 ) O(κ̄ y e 3.5 ϵ−2 ) O(κ̄ y O(κ̄5y ϵ−2 ) −2 Ω(κ2.5 y ϵ )

F2 SA [Kwon et al., 2023b] F2 BSA [Chen et al., 2025b] F3 BSA [Chen et al., 2025b]

SFO SF O SF O

double–loop double–loop double–loop

Stoc-SGHA (Theorem 8/Theorem 9)

SFO

single–loop

−7 e O(poly(κ̄ y )ϵ ) e 12 ϵ−6 ) O(κ̄ y e 11 ϵ−6 ) O(κ̄ y 

Stoc. NC–SC BiO

Stoc-SGHA (Theorem 10/Theorem 11)

SFO + Assumption 3

single–loop

Lower Bound [Chen et al., 2025a]

FO for f + SFO for g

–

Oracle Complexity









−6 −3 /O κ̄17 ϵ−6 O κ̄17 y ϵ ρ y





−4 −2 /O κ̄11 ϵ−4 O κ̄11 y ϵ ρ y −4 Ω(κ4.5 y ϵ )

Table Notes. Det. and Stoc. stand for “deterministic" and “stochastic", respectively. NC–SC BiO stands for nonconvex–strongly-convex bilevel optimization. FO denotes an exact first-order oracle. SFO denotes a stochastic first-order oracle. The analysis of F2 SA covers both single-loop and nested-loop variants with the −4 same complexity rate. The Ω(κ4.5 ) lower bound is proved for zero-respecting SFO algorithms on a bounded y ϵ constrained nonconvex–quadratic problem. The displayed condition-number rates treat the initial Lyapunov gap ∆V and the remaining problem-dependent variance and bounded-gradient constants as fixed; the theorem statements retain their explicit dependence on these quantities.

2

Related Work

We organize the related work around two themes: bilevel optimization and minimax optimization. For bilevel optimization, we review the best-known deterministic and stochastic first-order oracle complexities for NC–SC problems. We then discuss minimax optimization, motivated by the nonconvex–concave (linear) Lagrangian formulation (L). Bilevel Optimization with Hessian The implicit-differentiation formula in (1) shows that computing the hypergradient requires estimating the sensitivity ∇y ∗ (x), or equivalently applying the inverse lower-level Hessian to ∇y f . One line of work uses Iterative Differentiation (ITD) [Gould et al., 2016, Franceschi et al., 2017, Shaban et al., 2019, Bolte et al., 2021], which approximates y ∗ (x) by a finite lower-level trajectory and differentiates through its iterations. Another line, known as Approximate Implicit Differentiation (AID) [Domke, 2012, Ghadimi and Wang, 2018, Pedregosa, 2016, Franceschi et al., 2018, Grazzi et al., 2020, Ji et al., 2021, Dagréou et al., 2022, Arbel and Mairal, 2021], approximates the inverse-Hessian action by solving the associated linear system. These ideas also underlie several single-loop stochastic NC–SC bilevel algorithms. TTSA [Hong et al., 2023], SUSTAIN [Khanduri et al., 2021], and STABLE [Chen et al., 2022] construct implicit-differentiation-based hypergradient estimators using Hessian-vector products, Jacobianvector products, or related second-order information. SOBA/SABA [Dagréou et al., 2022] and MA-SOBA [Chen et al., 2024] avoid explicit Hessian inversion by recursively tracking the solution of the linear system, but still require second-order oracle information and an auxiliary linear-system variable. Consequently, these methods fall outside the fully first-order oracle model considered in this paper.

4

Fully First-order Bilevel Optimization. Methods based on the hypergradient typically require Hessian information, which has motivated the development of fully first-order approaches [Liu et al., 2022, Shen and Chen, 2023, Kwon et al., 2023b]. Most of these methods are double-loop and penalty-based: they incorporate lower-level optimality into a penalized upper-level objective whose gradients can be evaluated using only first-order information. In particular, Kwon et al. [2023b] e 7 ϵ−3 ) and a stochastic oracle proposed F2 SA, which achieves a deterministic oracle complexity of O(κ̄ y −7 e complexity of O(poly(κ̄ y )ϵ ) for NC–SC bilevel optimization using an increasing penalty parameter. By instead fixing the penalty parameter at λ = Θ(ϵ−1 ), Chen et al. [2025a] improved the deterministic −6 e 3.5 ϵ−2 ), while the stochastic complexity was improved to O(poly(κ̄ e complexity to O(κ̄ y )ϵ ) [Kwon y et al., 2024, Chen et al., 2025b]. Without additional assumptions, no known fully first-order method improves these dependencies on ϵ. −2 On the lower-bound side, Chen et al. [2025a] establish Ω(κ2.5 y ϵ ) in the deterministic setting 4.5 −4 and Ω(κy ϵ ) in the stochastic setting for fully first-order methods. These results show that the deterministic complexity of F2 BA/F2 BA+ is nearly optimal in its dependence on ϵ. In contrast, the best-known stochastic upper bound still exhibits an extra factor of ϵ−2 relative to the Ω(ϵ−4 ) lower bounds. We note that Kwon et al. [2024] also establish an Ω(ϵ−4 ) lower bound under the stochastic smoothness assumption on the lower-level objective, using a y ⋆ -aware oracle, which additionally returns an estimate ŷ satisfying a prescribed accuracy guarantee relative to the exact lower-level solution y ⋆ (x). Most of the methods discussed above are double-loop. While the analysis of Kwon et al. [2023b] permits a single-loop variant by setting the inner-loop length to one, it has strictly worse complexity guarantees. The best-known bounds of Chen et al. [2025b], by contrast, rely essentially on inner-loop updates, as discussed in Section 1. A closely related single-loop method is FdeHBO [Yang et al., 2023], which avoids iteratively solving linear-systems and uses finite-difference approximations for Hessian–vector products. However, its guarantees require variance reduction and stronger assumptions, including stochastic smoothness in the upper-level function, stochastic Hessian, and higher-order smoothness. Other methods, such as F3 SA [Kwon et al., 2023b], also operate under similar stronger assumptions. We therefore omit these methods from Table 1. Minimax optimization.

Minimax optimization problems take the form min max f (ω, λ),

ω∈W λ∈Λ

where W ⊆ Rdω and Λ ⊆ Rdλ are nonempty closed convex sets. Motivated by the structure of (L), we focus on the nonconvex–concave (NC–C) setting, where f : Rdω × Rdλ → R is nonconvex in ω and concave in λ. There is a vast literature on nonconvex–concave (NC–C) minimax optimization [Rafique et al., 2022, Nouiehed et al., 2019, Kong and Monteiro, 2021, Boţ and Böhm, 2023]. In the deterministic e −2.5 ) under the f -stationarity measure [Lin et al., setting, the best-known gradient complexity is O(ϵ −3 e 2020], and O(ϵ ) under stationarity of the Moreau envelope of the value function [Yang et al., 2020]. In the stochastic setting, SAPD+ achieves the best-known stochastic oracle complexity of O(ϵ−6 ) [Zhang et al., 2022]. However, most of these results assume a compact dual domain Λ, and thus do not apply directly to our original unbounded Lagrangian formulation. Moreover, by exploiting the special structure of the bilevel problem, our method achieves sharper complexity guarantees than those available for generic NC–C minimax optimization.

5

In contrast, existing single-loop algorithms generally have worse complexity than the best-known rates discussed above [Lin et al., 2025, Xu et al., 2023, Boţ and Böhm, 2023]. Our algorithm builds on Smoothed GDA [Zhang et al., 2020, Yang et al., 2022], which introduces a Moreau-envelope-type smoothing mechanism via an auxiliary primal sequence. In the deterministic setting, Zhang et al. [2020] establish a complexity of O(ϵ−4 ) for general NC-C minimax problems, which improves to O(ϵ−2 ) when the objective is linear in λ and additional regularity conditions hold, including strict complementarity and bounded level sets of maxλ∈Λ f (·, λ). Their analysis does not directly apply to our setting, as we seek an O(ϵ−2 ) complexity without these additional assumptions. In both deterministic and stochastic settings, Yang et al. [2022] obtain complexities of O(κϵ−2 ) and O(κ2 ϵ−4 ), respectively, under a Polyak–Łojasiewicz condition, where κ denotes the condition number. These results do not directly apply to our setting: imposing strong concavity via a quadratic regularizer of order Θ(ϵ∥λ∥2 ) will lead to a worse ϵ-dependence than ours. Moreover, the gradients of (L) requires HVPs, which must be approximated in our first-order framework.

3

Preliminaries and Technical Background

Notations. For a vector v and a matrix A, we use ∥v∥ and ∥A∥ to denote the Euclidean norm of v and the spectral norm of A, respectively. For a closed convex set C, we denote by PC its Euclidean projection. For a differentiable function h, we write ∇h for its gradient, and use ∇x h and ∇y h to denote the partial gradients with respect to x and y. Similarly, ∇2xy h and ∇2yy h denote the corresponding Hessian blocks. Throughout the paper, E[·] denotes expectation with respect to all randomness in the stochastic oracle and the algorithm, and Ek [·] denotes conditional expectation given the history up to iteration k. a ≍ b means that a/b is bounded above and below by positive constants. The notation O(·), Ω(·), and Θ(·) hides absolute constants independent of the target accuracy, condition number, and failure probability, while Õ(·), Ω̃(·), and Θ̃(·) additionally hide logarithmic factors.

3.1

Basic Assumptions and Definitions

We consider the nonconvex–strongly–convex (NC–SC) bilevel optimization problem min F (x) = f (x, y ∗ (x)),

x∈Rdx

s.t.

y ∗ (x) ∈ arg min g(x, y). y∈Rdy

(P)

We first state the basic assumptions used throughout the paper. These assumptions are standard in the literature and, to the best of our knowledge, are among the weakest commonly imposed for smooth NC–SC bilevel optimization [Chen et al., 2025a,b, Kwon et al., 2023a,b]. Assumption 1. We have the following assumptions: 1. ∥∇y f (x, y)∥ ≤ lf,0 for all x and y. 2. g(x, y) is µg -strongly convex w.r.t. y for every x. 3. f and g are lf,1 and lg,1 -smooth, respectively. 4. The Hessians of f and g are lf,2 – and lg,2 –Lipschitz, respectively. 5. For all x and y, f (x, y) is bounded from below by some finite constant f > −∞. 6

Next, we introduce the condition-number notation and the stationarity measure used throughout the paper. Definition 1. Under Assumption 1, we define the lower-level condition number κy := lg,1 /µg , and the global condition number κ̄y := L̄/µg with L̄ := max{lf,0 , lf,1 , lg,1 , lf,2 , lg,2 }. Since lg,1 ≥ µg , these definitions imply κ̄y ≥ κy ≥ 1. Definition 2. Given a differentiable function φ(x) : Rd → R, we call x an ϵ–first–order stationary point of φ(x) if ∥∇φ(x)∥ ≤ ϵ.

3.2

Equality–constrained Reformulation

Since g(x, ·) is differentiable and strongly convex for every fixed x, the lower-level minimizer y ∗ (x) is unique. Moreover, the first-order optimality condition is both necessary and sufficient, and hence ∇y g(x, y ⋆ (x)) = 0. Therefore, the graph of the lower-level solution map x 7→ y ⋆ (x) is exactly the feasible set described by the equality constraint ∇y g(x, y ⋆ (x)) = 0. Equivalently, any feasible pair (x, y) of this reformulated problem satisfies y = y ⋆ (x), and hence f (x, y) = F (x). Thus, it preserves the objective values and minimizers of the original bilevel formulation. Consequently, the NC–SC bilevel problem can be equivalently written as min

x∈Rdx , y∈Rdy

f (x, y),

s.t.

∇y g(x, y) = 0.

(R)

The Lagrangian associated with this equality-constrained bilevel problem is L(x, y, λ) := f (x, y) + λ⊤ ∇y g(x, y),

λ ∈ Rdy .

(L)

The next lemma shows that the equality constraint in the equality-constrained bilevel problem is regular. In other words, lower-level strong convexity implies the LICQ condition for ∇y g(x, y) = 0. This regularity ensures that local solutions of the (R) admit KKT multipliers, and hence justifies the Lagrangian stationarity system introduced below. Lemma 1 (LICQ for the lower-level optimality constraint). Suppose g(x, ·) is µg -strongly convex for every x. Then, the Jacobian of the constraint mapping ∇y g(x, y) has full row rank at every (x, y). In particular, LICQ holds at every feasible point of the equality-constrained reformulation. We note that several works also impose the lower-level first-order optimality condition as a constraint, either designing algorithms based on the KKT system of the resulting constrained problem [Liu et al., 2023] or applying penalty methods [Kim et al., 2020, Mehra and Hamm, 2021]. Our approach differs in that we construct a regularized Lagrangian reformulation and develop a specific single-loop, fully first-order method for finding an approximate stationary point of L.

3.3

From Lagrangian Stationarity to Bilevel Stationarity

The following theorem shows that the equality-constrained reformulation allows us to reduce the analysis of stationarity for the hyperobjective F to that of the Lagrangian L. 7

Theorem 2. Suppose Assumption 1 holds. Then ∥∇F (x)∥ ≤ ∥∇x L(x, y, λ)∥ + κy ∥∇y L(x, y, λ)∥ +

LF̄ ,y ∥∇λ L(x, y, λ)∥. µg

with LF̄ ,y = lf,1 (1 + κy ) + lf,0 lg,2

1 lg,1 + 2 µg µg

!

.

The following theorem shows that for any pairs of (x∗ , y ∗ , λ∗ ) satisfying the KKT conditions of the equality-constrained bilevel problem, λ∗ is always bounded by a constant determined by the problem itself. This provides one motivation for studying stationarity of the Lagrangian associated with the lower-level first-order optimality constraint, rather than penalizing the lower-level value gap as in [Kwon et al., 2023b]. Theorem 3 (Boundedness of λ∗ ). Under Assumption 1, the optimal Lagrangian multiplier λ∗ satisfying the KKT conditions is bounded with ∥λ∗ ∥ ≤

4

lf,0 . µg

Deterministic NC–SC Bilevel Optimization

In this section, we aim to solve deterministic nonconvex-strongly-convex (NC–SC) bilevel optimization problems. We first introduce SGHA and establish its main complexity guarantees, and then present the key analytical tools together with a proof sketch. The algorithm-specific notation used in the analysis of SGHA is summarized in Table 2.

4.1

Algorithm

We first note that L is generally nonconvex in the primal variables x and y, and affine in the multiplier λ. Because the maximization over an unconstrained multiplier is unbounded whenever the constraint is violated, (L) does not define a standard finite-valued minimax problem. Instead, we use it as a Lagrangian stationarity model for the equality-constrained reformulation. However, Theorem 3 shows that every KKT multiplier of Problem (R) is bounded by a problemdependent constant. Therefore, we restrict the dual variable to Λ = {λ : ∥λ∥ ≤ Cλ }, where Cλ is chosen sufficiently large to contain all KKT multipliers of Problem (R). This bounded domain provides uniform smoothness control of L along the algorithmic trajectory. We further add a small quadratic regularization term to λ with a sufficiently small regularization parameter pλ > 0. This term turns the projected affine dual maximization into a strongly concave one, avoiding boundarysaturating or nonunique multiplier responses, while only introducing a controllable perturbation to the original Lagrangian stationarity. This leads to the regularized surrogate min

x∈Rdx ,y∈Rdy

max f (x, y) + λ⊤ ∇y g(x, y) − λ∈Λ

pλ ∥λ∥2 . 2

(2)

We then apply Smoothed Gradient Descent Ascent (GDA) [Zhang et al., 2020]. Specifically, we introduce auxiliary smoothing variables x̂ and ŷ, together with quadratic proximal terms on the primal variables using a regularization parameter pw > 0. With an appropriate choice of pw , the 8

resulting surrogate is strongly convex in w = (x, y) and strongly concave in λ. We then perform gradient descent on the primal variables w, and projected gradient ascent on the dual variable λ, for the problem min

x∈Rdx ,y∈Rdy

max f (x, y) + λ⊤ ∇y g(x, y) + λ∈Λ

pw pw pλ ∥x − x̂∥2 + ∥y − ŷ∥2 − ∥λ∥2 . 2 2 2

(3)

Furthermore, we note that the gradients induced by (3) involve Hessian-vector product terms associated with g, namely ∇2xy g(x, y)λ and ∇2yy g(x, y)λ. To retain a fully first-order method, we approximate these Hessian-vector products by central finite differences. Specifically, we use ˜ 2xy gλ (x, y) := ∇x g(x, y + τ λ) − ∇x g(x, y − τ λ) ≈ ∇2xy g(x, y)λ, ∇ 2τ and

˜ 2 gλ (x, y) := ∇y g(x, y + τ λ) − ∇y g(x, y − τ λ) ≈ ∇2 g(x, y)λ, ∇ yy yy 2τ where τ > 0 is the finite-difference radius, whose value will be specified later. The complete procedure is summarized in Algorithm 1, which we call SGHA (Smoothed GDA with Hessian Approximation). In the convergence analysis, we use a common stepsize for the primal updates, namely γx,k = γy,k =: γw,k , while the dual stepsize γλ,k is chosen separately and may scale differently. After each primal–dual update, the auxiliary variables x̂ and ŷ are updated by an averaging step with parameter β ∈ (0, 1). Algorithm 1 SGHA (Smoothed GDA with Hessian Approximation) Input: Total iterations K, step sizes {γx,k }k , {γy,k }k , {γλ,k }k , initialization points x0 , x̂0 ∈ Rdx , y 0 , ŷ 0 ∈ Rdy , λ0 ∈ Λ. τ > 0, pw , pλ > 0, 0 < β < 1, Λ := {λ : ∥λ∥ ≤ Cλ } with Cλ > 0. 1: for k = 0, . . . , K − 1 do  ˜ 2 gλk (xk , y k ) + pw (xk − x̂k ) 2: xk+1 ← xk − γx,k ∇x f (xk , y k ) + ∇ xy   ˜ 2 gλk (xk , y k ) + pw (y k − ŷ k ) 3: y k+1 ← y k − γy,k ∇y f (xk , y k ) + ∇ yy

x̂k+1 = x̂k + β(xk+1 − x̂k ) 5: ŷ k+1 = ŷ k + β(y k+1 −ŷ k )  6: λk+1 = PΛ λk + γλ,k ∇y g(xk , y k ) − pλ λk 7: end for 4:

4.2

Complexity Guarantees

We are now ready to state the oracle complexity of Algorithm 1 for solving deterministic nonconvexstrongly-convex bilevel optimization problems. Theorem 4. Suppose that Assumption 1 holds. Fix any target accuracy 0 < ϵ ≤ 1. Let Λ :=  ϵ {λ : ∥λ∥ ≤ Cλ } with Cλ := 2κ̄y . Choose pw = 16L̄κ̄y and pλ = 18 min µg , 211 (1+ . For every L̄)κ̄4 y

k ≥ 0, use the constant stepsizes γx,k = γy,k =

1 28 L̄κ̄y

9

,

γλ,k =

κ̄y . 28 L̄

Table 2: Notations in algorithms and analysis Notation

Definition

w ŵ L(w, λ) γw γλ K(w, ŵ, λ) Ψ(ŵ, λ) Φ(w, ŵ) P (ŵ) Vt w∗ (ŵ, λ) w∗ (ŵ) λ̂∗ (ŵ) w+ (ŵ, λ) λ+ (ŵ) ϵL ϵ

(x, y) (x̂, ŷ) f (w) + λ⊤ ∇y g(w) Common stepsize for the update of x and y Stepsize for the update of λ L(w, λ) + p2w ∥w − ŵ∥2 − p2λ ∥λ∥2 minw K(w, ŵ, λ) maxλ∈Λ K(w, ŵ, λ) minw maxλ∈Λ K(w, ŵ, λ) K(wt , ŵt , λt ) − 2Ψ(ŵt , λt ) + 2P (ŵt ) arg minw K(w, ŵ, λ) arg minw Φ(w, ŵ) arg maxλ∈Λ Ψ(ŵ, λ) w − γw ∇K(w, ŵ, λ) PΛ (λ + γλ (∇y g(w∗ (ŵ, λ)) − pλ λ)) Target accuracy for L Target stationarity accuracy for F

Choose the averaging parameter and finite-difference radius as β=

1 230 κ̄2y

,

τ=

ϵ . 224 (1 + L̄)κ̄4y

Let ∆V := V0 − f , where V0 is the initial Lyapunov value defined below, and run Algorithm 1 for (

&

252 (1 + L̄)2 ∆V 5 −2 κ̄y ϵ K := max 1, L̄

')

.

Then there exists an index k⋆ ∈ {0, . . . , K − 1} such that ∇F (xk⋆ ) ≤ ϵ. −2 The resulting dependence on ϵ matches the lower bound Ω(κ2.5 y ϵ ) established in Chen et al. [2025a]. To the best of our knowledge, SGHA is the first single-loop method for deterministic −2 NC–SC bilevel optimization to  achieve  the optimal ϵ dependence. Compared with the best-known 3.5 −2 e double-loop upper bound O κ̄y ϵ [Chen et al., 2025a], our result also removes the logarithmic factor. We note, however, that the dependence on κ̄y remains worse than that of existing double-loop methods; improving the condition-number dependence of single-loop methods is left for future work.

4.3

Analysis and Proof Sketch

We now provide a proof sketch of Theorem 4. The same analysis framework will later be extended to the stochastic settings. We use the notation summarized in Table 2. Following Zhang et al.

10

[2020], we introduce the following Lyapunov function: Vt = K(wt , ŵt , λt ) − 2Ψ(ŵt , λt ) + 2P (ŵt ). The following lemma shows that the Lyapunov function is lower bounded. Lemma 5. Under Assumption 1, the Lyapunov function satisfies Vt ≥ f By analyzing the one-step progress bounds for K(w, ŵ, λ), Ψ(ŵ, λ) and P (ŵ), we obtain the following one-step descent inequality for the Lyapunov function: l

Proposition 6. Suppose that Assumption 1 holds, and let Λ := {λ : ∥λ∥ ≤ Cλ } with Cλ > µf,0 . Let g √
lL,1 be any constant satisfying lL,1 ≥ 2 lf,1 + Cλ lg,2 and let the primal regularization parameter pw = 2lL,1 . Introduce the auxiliary constants γ1 :=

pw = 2, pw − lL,1

lΨ,1 := pλ + lg,1 γ2 ,

γ2 :=

γ3 := r

lg,1 lg,1 = , pw − lL,1 lL,1 −1 lΨ,1 + γλ,k

(pw −l )2 µ2g 2(pw − lL,1 )pλ + (pw +lL,1 2 L,1 )

.

Choose positive stepsizes γw,k and γλ,k such that (

γw,k ≤ min

γλ,k ≤ min

1 1 , 8pw β 8(pw + lL,1 )

   

)

,

1 

2 lg,1    2 2lΨ,1 + pλ + p +l w

,

L,1

   

2 lL,1 1 γw,k , , . 2 16lg,1 1536pw βγ22   

Suppose that parameter β ∈ (0, 1) satisfies (√

β ≤ min

1 5−1 , 48γ1 3072pw γλ,k γ32

)

.

Then, we have Vk − Vk+1 ≥



where Cτ,k :=

2 2 1 1 wk − w+ (ŵk , λk ) + λ+ (ŵk ) − λk 32γw,k 64γλ,k 2 pw β + wk − ŵk − Cτ,k τ 2 , 8

2 pw βγw,k γw,k 2 4 + (pw + lL,1 )γw,k + 4



(4)

2 C 4. lg,2 λ

The proposition also remains valid if lL,1 is replaced consistently by any deterministic upper bound on the smoothness of L(·, λ) over λ ∈ Λ. This is the form used in Theorem 4, with L0 = 8L̄κ̄y .

11

It follows from (4) that the one-step Lyapunov decrease controls three nonnegative stationarity and tracking residuals, up to the finite-difference error Cτ,k τ 2 . For a target Lagrangian stationarity accuracy ϵL , choosing constant stepsizes and a finite-difference radius τ = Θ(κ̄−1 y ϵL ), and telescoping −2 −1 2 (4) over K = Θ(κ̄y ϵL ) iterations yields residuals of order ϵL . The full proof is deferred to the appendix. A key ingredient is the special structure of the regularized surrogate (2), which allows us to retain the coupled primal–dual coercivity in Lemma 24 rather than bounding the dual error first. Then, the following lemma shows that three residual terms controlled by the one-step Lyapunov inequality are sufficient to guarantee ϵL -stationarity of the original Lagrangian. Lemma 7. Under the same assumption and hyperparameter setting as Proposition 6, suppose further that ϵL is sufficiently small such that 

−1 γw,k + κ̄y pw



lf,0 Cλ − µg

µg ϵL ≤ 4

!

,

lf,0 1 κ̄y ϵL ≤ Cλ − 4 µg

!

.

Then, if ∥wk − w+ (ŵk , λk )∥ ≤ ϵL , we have

∥λ+ (ŵk ) − λk ∥ ≤ κ̄y ϵL , 

∥wk − ŵk ∥ ≤ κ̄y ϵL ,



−1 ∥∇w L(wk , λk )∥ ≤ γw,k + κ̄y pw ϵL ,

!

k

k

∥∇λ L(w , λ )∥ ≤

lg,1 −1 + κ̄y γλ,k ϵL + pλ Cλ . (pw − lL,1 )γw,k

Lemma 7 establishes the bridge between the residual terms in the one-step Lyapunov inequality (4) and the stationarity of the Lagrangian function. Finally, by Theorem 2, the convergence of ∇L can be further translated into the convergence of the hypergradient in the original bilevel problem (P).

5

Stochastic NC–SC Bilevel Optimization

We now extend SGHA to the stochastic setting, where exact gradients of f and g are not directly available. We first specify the stochastic first-order oracle (SFO) used throughout this paper. Assumption 2. We access the gradients of f and g via unbiased estimators ∇f (x, y; ξ) and ∇g(x, y; ζ) such that Eξ [∇f (x, y; ξ)] = ∇f (x, y),

Eζ [∇g(x, y; ζ)] = ∇g(x, y).

Moreover, the variance of stochastic gradients is bounded: h

i

h

Eξ ∥∇f (x, y; ξ) − ∇f (x, y)∥2 ≤ σf2 ,

i

Eζ ∥∇g(x, y; ζ) − ∇g(x, y)∥2 ≤ σg2 .

We propose Stoc-SGHA, stated in Algorithm 2, for solving NC-SC bilevel optimization. Algorithm 2 has the same single–loop structure as Algorithm 1. The only change is that the exact gradients used in SGHA are replaced by mini-batch stochastic estimators. In particular, the gradients of f are estimated using a mini-batch Bf , while the finite-difference approximations of the Hessian-vector products of g are computed using a mini-batch Bg . For simplicity, we take

12

|Bf | = |Bg | = B. With Bf = {ξ1 , . . . , ξB }, we use ∇x f (xk , y k ; Bfk ) =

B 1 X ∇x f (xk , y k ; ξi ), B i=1

∇y f (xk , y k ; Bfk ) =

B 1 X ∇y f (xk , y k ; ξi ). B i=1

With Bg = {ζ1 , . . . , ζB }, we use B X

∇x g(x, y + τ λ; ζi ) − ∇x g(x, y − τ λ; ζi ) ˜ 2 gλ (x, y; Bg ) := 1 ∇ ≈ ∇2xy g(x, y)λ, xy B i=1 2τ and

B X

∇y g(x, y + τ λ; ζi ) − ∇y g(x, y − τ λ; ζi ) ˜ 2 gλ (x, y; Bg ) := 1 ≈ ∇2yy g(x, y)λ. ∇ yy B i=1 2τ The same sample ζi is used for the two gradient evaluations in each central difference. This coupling is essential for the sharper variance bound under Assumption 3. Under the bounded-variance oracle in Assumption 2, the stochastic finite-difference approximation introduces an additional variance term of order σg2 /(Bτ 2 ) relative to the deterministic setting. With τ ≍ κ̄−1 y ϵL , controlling −4 −2 −1 this term requires B ≍ ϵL . Combined with K ≍ κ̄y ϵL , this yields an overall sample complexity −6 of order κ̄−1 y ϵL . This additional variance also prevents a direct combination of existing minimax analyses with finite-difference approximations, as such an approach would generally lead to worse complexity guarantees. Algorithm 2 Stoc-SGHA (Stochastic Smoothed GDA with Hessian Approximation) k }, B k = {ζ k , . . . , ζ k }, stepsizes Input: Total iterations K, mini-batch set Bfk = {ξ1k , . . . , ξB g 1 B {γx,k }k , {γy,k }k , {γλ,k }k , initialization points x0 , x̂0 ∈ Rdx , y 0 , ŷ 0 ∈ Rdy , λ0 ∈ Λ. τ > 0, pw , pλ > 0, 0 < β < 1, Λ := {λ : ∥λ∥ ≤ Cλ } with Cλ > 0. 1: for k = 0, . . . , K − 1 do  ˜ 2 gλk (xk , y k ; B k ) + pw (xk − x̂k ) 2: xk+1 ← xk − γx,k ∇x f (xk , y k ; Bfk ) + ∇ xy g   k+1 k k k k 2 k k k ˜ 3: y ← y − γy,k ∇y f (x , y ; B ) + ∇ gλk (x , y ; B ) + pw (y k − ŷ k ) f

yy

g

x̂k+1 = x̂k + β(xk+1 − x̂k ) 5: ŷ k+1 = ŷ k + β(y k+1 − ŷ k )  6: λk+1 = PΛ (λk + γλ,k ∇y g(xk , y k ; Bgk ) − pλ λk ) 7: end for

4:

The stochastic analysis follows the same general framework as the deterministic case, with Proposition 30 establishing a one-step Lyapunov descent bound in expectation. A subtle difference, however, arises in translating the residual bounds into Lagrangian stationarity. In the deterministic setting, Lemma 7 applies pathwise: if the three residuals in (4) are sufficiently small at an iterate, then that iterate is approximately stationary for L. In the stochastic setting, the telescoping argument only controls these residuals in expectation, which does not directly imply expected stationarity of L. We therefore use Markov’s inequality to convert the expected residual bound into a high-probability bound, and then apply Lemma 7 pathwise on this event. This yields the following high-probability oracle complexity guarantee for Algorithm 2. Theorem 8. Suppose that Assumptions 1 and 2 hold. Fix any target accuracy 0 < ϵ ≤ 1 and failure probability ρ ∈ (0, 1), and define σ̄ 2 := 1 + σf2 + σg2 . Let Λ := {λ : ∥λ∥ ≤ Cλ } with Cλ := 2κ̄y . 13

√ ϵ ρ





Choose pw = 16L̄κ̄y and pλ = 18 min µg , 212 (1+L̄)κ̄4 . For every k ≥ 0, use the constant stepsizes y

γx,k = γy,k =

1 28 L̄κ̄y

,

γλ,k =

κ̄y . 28 L̄

Choose the averaging parameter, finite-difference radius, and batch size as 1 β = 30 2 , 2 κ̄y

√ ϵ ρ τ = 25 , 2 (1 + L̄)κ̄4y

&

'

298 σ̄ 2 (1 + L̄)4 12 −4 −2 B= κ̄y ϵ ρ . L̄2

Let ∆V := E[V0 ] − f , and run Algorithm 2 for (

&

5 · 253 (1 + L̄)2 ∆V 5 −2 −1 K := max 1, κ̄y ϵ ρ L̄ 

')

.



Then there exists k⋆ ∈ {0, . . . , K −1} such that P ∥∇F (xk⋆ )∥ ≤ ϵ ≥ 1−ρ. Therefore, the stochastic first-order oracle complexity is   −6 −3 O κ̄17 ϵ ρ . y We can also establish an in-expectation guarantee under the additional assumption that the iterates are almost surely bounded, i.e., ∥wk ∥ ≤ Dw almost surely for all k. This condition is weaker than that typically imposed in analyses of Smoothed–GDA–type methods [Zhang et al., 2020], which require both the primal and dual iterates to remain bounded. We use a good-event decomposition directly at the level of the bilevel hypergradient. On the event where the residuals are small, Lemma 7 and Theorem 2 give a small hypergradient. On the complementary event, boundedness of wk , lower-level strong convexity, and global smoothness provide a uniform bound on ∥∇F (xk )∥. This sharper treatment avoids an unnecessary condition-number loss from separately bounding the Lagrangian-gradient components on the bad event. It leads to the following stochastic first-order oracle complexity guarantee in expectation for Algorithm 2. Theorem 9. Suppose that Assumptions 1 and 2 hold. Further assume that there exists Dw > 0 such that the iterates generated by Algorithm 2 satisfy ∥wk ∥ ≤ Dw almost surely for all k ≥ 0. Fix any target accuracy 0 < ϵ ≤ 1, and let Λ := {λ : ∥λ∥ ≤ Cλ } with Cλ := 2κ̄y . Let G be a  problem-dependent 

constant, and denote σ̄ 2 := max{1, σf2 , σg2 }. Choose pw = 16L̄κ̄y and pλ = 18 min µg , 213 (1+ϵL̄)Gκ̄4 . y

For every k ≥ 0, use the constant stepsizes γx,k = γy,k =

1 28 L̄κ̄y

,

γλ,k =

κ̄y . 28 L̄

Choose the averaging parameter, finite-difference radius, and batch size as 1 β = 30 2 , 2 κ̄y

&

'

2102 σ̄ 2 (1 + L̄)4 G 4 12 −4 B := κ̄y ϵ . L̄2

ϵ τ = 26 , 2 (1 + L̄)Gκ̄4y

Let ∆V := E[V0 ] − f and run Algorithm 2 for (

K := max 1,

&

5 · 255 (1 + L̄)2 G 2 ∆V 5 −2 κ̄y ϵ L̄ 14

')

.

h

i

Then there exists k⋆ ∈ {0, . . . , K − 1} such that E ∥∇F (xk⋆ )∥ ≤ ϵ. Consequently, the stochastic first-order oracle complexity is   −6 O κ̄17 . y ϵ The resulting ϵ-dependence matches the best-known fully first-order stochastic upper bound, e 11 ϵ−6 ), achieved by F3 BSA [Chen et al., 2025b], while removing the logarithmic factor. To the O(κ̄ y

best of our knowledge, this is the first single-loop fully first-order method to attain the same ϵ−6 −4 dependence. However, compared with the stochastic lower bound Ω(κ4.5 y ϵ ) in [Chen et al., 2025a], an additional ϵ−2 gap remains, together with a substantial gap in the condition-number dependence. Closing the gap between the best-known upper and lower bounds for stochastic NC–SC bilevel optimization remains an open problem.

6

Improved Complexities with Lower-Level Stochastic Smoothness

In this section, we show that the stochastic complexity of Stoc-SGHA can be improved under an additional stochastic smoothness condition on the lower-level objective g. This condition is stronger than the standard bounded-variance oracle model by controlling the mean-square variation of stochastic gradients across different points. Assumption 3. There exists ˜lg,1 > 0 such that, for all (x1 , y1 ), (x2 , y2 ), h

i





Eζ ∥∇g(x1 , y1 ; ζ) − ∇g(x2 , y2 ; ζ)∥2 ≤ ˜lg,1 ∥x1 − x2 ∥2 + ∥y1 − y2 ∥2 . Assumption 3 yields sharper variance control for the stochastic finite-difference approximation of the Hessian–vector products of g. The key is that the two gradient evaluations in each central difference use the same sample in the mini-batch Bg . Under the standard bounded-variance oracle in Assumption 2, the finite-difference error contains a variance term of order σg2 /(Bτ 2 ). Under Assumption 3, this improves to ˜lg,1 Cλ2 /B, where Cλ is the radius of the multiplier domain Λ. Thus, the variance is no longer amplified by the small finite-difference radius τ , and it suffices to choose −1 −2 B ≍ ϵ−2 L . Combined with K ≍ κ̄y ϵL iterations from the refined Lyapunov argument, this yields −4 an internal stochastic first-order oracle complexity of order κ̄−1 y ϵL . We first state the corresponding high-probability guarantee. Theorem 10. Suppose that Assumptions 1, 2, and 3 hold. Fix anyotarget accuracy 0 < ϵ ≤ 1 n and failure probability ρ ∈ (0, 1), and define M̄g := max 1, elg,1 , σf2 , σg2 . Let Λ := {λ : ∥λ∥ ≤ Cλ } with Cλ := 2κ̄y .

Choose pw = 16L̄κ̄y and pλ = 18 min



 √ ϵ ρ µg , 212 (1+L̄)κ̄4 . y

For every k ≥ 0, use the

constant stepsizes γx,k = γy,k =

1 , 28 L̄κ̄y

γλ,k =

κ̄y . 28 L̄

Choose the averaging parameter, finite-difference radius and batch size as 1 β = 30 2 , 2 κ̄y

√ ϵ ρ τ = 25 , 2 (1 + L̄)κ̄4y

&

'

250 M̄g (1 + L̄)2 6 −2 −1 B= κ̄y ϵ ρ . L̄2

15

Let ∆V := E[V0 ] − f , and run Algorithm 2 for (

&

K := max 1,

5 · 253 (1 + L̄)2 ∆V 5 −2 −1 κ̄y ϵ ρ L̄ 

')

.



Then there exists k⋆ ∈ {0, . . . , K −1} such that P ∥∇F (xk⋆ )∥ ≤ ϵ ≥ 1−ρ. Therefore, the stochastic first-order oracle complexity is   −4 −2 O κ̄11 ϵ ρ . y Finally, with the additional bounded-iterate condition, we obtain the following stochastic first-order oracle complexity guarantee in expectation for Algorithm 2. Theorem 11. Suppose that Assumptions 1, 2, and 3 hold. Further assume that there exists Dw > 0 such that the iterates generated by Algorithm 2 satisfy ∥wk ∥ n ≤ Dw almosto surely for all k ≥ 0. Let G be a problem-dependent constant, and let M̄g := max 1, elg,1 , σf2 , σg2 . Fix any target accuracy 0 < ϵ ≤ 1. Let Λ := {λ : ∥λ∥ ≤ Cλ } with Cλ := 2κ̄y . Choose pw = 16L̄κ̄y and  pλ = 81 min µg , 213 (1+ϵL̄)Gκ̄4

. For every k ≥ 0, use the constant stepsizes

y

γx,k = γy,k =

1 28 L̄κ̄y

,

γλ,k =

κ̄y . 28 L̄

Choose the averaging parameter, finite-difference radius, and batch size as 1 β = 30 2 , 2 κ̄y

ϵ τ = 26 , 2 (1 + L̄)Gκ̄4y

&

'

252 M̄g (1 + L̄)2 G 2 6 −2 B= κ̄y ϵ . L̄2

Let ∆V := E[V0 ] − f , and run Algorithm 2 for (

K := max 1,

&

5 · 255 (1 + L̄)2 G 2 ∆V 5 −2 κ̄y ϵ L̄ h

')

.

i

Then there exists k⋆ ∈ {0, . . . , K − 1} such that E ∥∇F (xk⋆ )∥ ≤ ϵ. Therefore, the stochastic first-order oracle complexity is   −4 O κ̄11 ϵ . y The theorems show that imposing stochastic smoothness only on the lower-level objective is sufficient to achieve an ϵ−4 oracle complexity. This ϵ-dependence is optimal, matching the rate for smooth nonconvex single-level optimization [Arjevani et al., 2023]. Previously, such a rate was achieved only when the lower-level gradient is noise-free [Chen et al., 2025b], a special case in which Assumption 3 holds trivially. Nevertheless, the κ̄y -dependence of Algorithm 2 remains worse than the lower bound, and closing this condition-number gap for single-loop fully first-order methods remains an open problem.

7

Numerical Experiments

We conduct two sets of experiments: learn-to-regularize logistic regression and data hyper-cleaning. For each experiment, we tune the stepsizes and method-specific parameters of all baselines under a 16

common evaluation protocol and report the best stable performance achieved by each method.

7.1

Learn-to-Regularize Logistic Regression

We consider the learnable regularization problem for multiclass logistic regression, which has been widely used in bilevel hyperparameter optimization. Let Dtr and Dval denote the training and validation sets. For a feature vector ai ∈ Rd and label bi , let ℓ(W ; ai , bi ) be the cross-entropy loss of a linear classifier W ∈ Rd×C . We learn one regularization parameter per feature by solving min

x∈Rd

f (x, W ∗ (x)) :=

X 1 |Dval | (a ,b )∈D i

s.t.

i

ℓ(W ∗ (x); ai , bi ), val

d X 1 X 1 ℓ(W ; ai , bi ) + exp(xj )∥Wj,· ∥22 . W (x) = arg min 2dC W ∈Rd×C |Dtr | j=1 (a ,b )∈D

(5)

∗

i

i

tr

Here Wj,· ∈ RC denotes the j-th row of W , i.e., the vector of classifier weights associated with the j-th TF-IDF feature across all classes. The lower-level objective is strongly convex in W due to the positive feature-wise ridge regularization, while the upper-level objective is nonconvex in x through both the exponential parameterization and the solution map W ∗ (x). We conduct the experiment on the 20 Newsgroups dataset, which has been commonly used in bilevel hyperparameter optimization [Grazzi et al., 2020, Ji et al., 2021]. The dataset contains approximately 18,000 documents from 20 classes. Each document is represented by a TF–IDF vector with d = 101,631 features. We split the original training set into 7,354 training samples and 3,960 validation samples, and use the 7,532 documents in the by-date test set for evaluation. We compare SGHA (Algorithm 1) with penalty-based methods F2 BSA [Chen et al., 2025b] and F2 SA [Kwon et al., 2023b], the HVP-based methods stocBiO [Ji et al., 2021] and MRBO [Yang et al., 2021], the variance-reduced bilevel method VRBO [Yang et al., 2021], and a baseline without hyperparameter optimization. We use 5 or 10 inner loops for the stochastic bilevel baselines with inner updates, and tune the stepsizes of all methods from preliminary logarithmic grids. The hyperparameters of SGHA are selected as β = 0.2, pw = 0.01, pλ = 10−5 , and τ = 10−4 . We run all methods for 1000 outer iterations. Figure 1 summarizes the results, where the dashed line labeled “w/o Reg” denotes performance without hyperparameter tuning. SGHA consistently outperforms all baselines in terms of both test loss and test accuracy. Among the compared methods, F2 BSA is the strongest baseline, improving over F2 SA and the other stochastic bilevel methods, while SGHA still achieves the best overall performance.

7.2

Data Hyper-Cleaning on MNIST

We further evaluate whether SGHA can identify corrupted training examples in a data hypercleaning problem. This experiment follows the “weights on garbage” diagnostic used in data-cleaning bilevel optimization: when a portion of the training labels is corrupted, an effective hyperparameter optimizer should assign small weights to corrupted examples while retaining useful information from the clean validation set. This experiment is inspired by the data hyper-cleaning formulation [Kwon et al., 2023b, Chen et al., 2025b], where data-source weights are learned by minimizing validation loss and the performance is evaluated by the weights assigned to garbage data. We adapt this

17

0.80 Test Accuracy

Test Loss

2.75 2.50 2.25 2.00 1.75 1.50 1.25 1.00 0.75

0.75 0.70 0.65 0.60

0

200

F2SA

400 600 Iterations

F2BSA

800

1000

VRBO

0

stocBiO

200

400 600 Iterations

MRBO

SGHA

800

1000

w/o Reg

Figure 1: Learn-to-regularize logistic regression on the 20 Newsgroups dataset with all 20 classes and 101, 631 TF-IDF features. SGHA obtains the lowest test loss and the highest test accuracy among all compared methods. idea to a stochastic nonconvex–strongly–convex MNIST hyper-cleaning problem with per-example weights and a strongly convex ridge-regularized lower-level logistic regression model. e tr = {(ai , e Let D bi )}ni=1 denote a training set whose labels are independently corrupted with probability p, and let Dval be a clean validation set. We associate each training example with a 1 learnable weight αi (xi ) = 2σ(xi ) with σ(t) = 1+exp(−t) . With a multiclass linear classifier W ∈ Rd×C and cross-entropy loss ℓ, the bilevel problem is min

X 1 f (x, W (x)) := |Dval | (a ,b )∈D

s.t.

1 W ∗ (x) = arg min W ∈Rd×C n

x∈Rn

i

i

n γ X ℓ(W (x); ai , bi ) + (αi (xi ) − 1)2 , 2n i=1 ∗

∗

val

X

αi (xi )ℓ(W ; ai , ebi ) +

etr (ai ,e bi )∈D

µ ∥W ∥2F . 2

(6)

The lower-level problem is strongly convex in W due to the ridge term, while the upper-level problem is nonconvex in x because of the nonlinear sample-weight map and the solution mapping W ∗ (x). We use the full MNIST dataset [LeCun et al., 1998], obtained from OpenML [Vanschoren et al., 2014], consisting of 70, 000 images with 784 features and 10 classes. The data are split into 38, 500 training examples, 15, 750 validation examples, and 15, 750 test examples. The validation and test labels are kept clean, while the training labels are randomly corrupted with p ∈ {0.5, 0.9, 0.99}. We compare SGHA with penalty-based methods F2 BSA [Chen et al., 2025b] and F2 SA [Kwon et al., 2023b], the HVP-based methods stocBiO [Ji et al., 2021] and MRBO [Yang et al., 2021], the variance-reduced bilevel method VRBO [Yang et al., 2021], and a baseline without learned data weights. All methods are run for 20, 000 iterations using stochastic mini-batches. For SGHA, we use different hyperparameter settings for different corruption ratios. Specifically, for p = 0.5, 0.9 and 0.99, we set (β, pw ) = (0.16, 0.02), (0.24, 0.005), (0.32, 0.005), respectively, while fixing pλ = 10−4 and τ = 10−3 .

18

Weights on Garbage

p = 0.5

p = 0.9

p = 0.99

1.0 0.8 0.6 0.4 0.3 0

5000

10000 15000 20000

0

Iterations F2SA

F2BSA

5000

10000 15000 20000

0

Iterations VRBO

stocBiO

5000

10000 15000 20000

Iterations MRBO

SGHA

w/o-Reg

Figure 2: Data hyper-cleaning on the full MNIST dataset under corruption ratios p ∈ {0.5, 0.9, 0.99}. The vertical axis is the average weight assigned to corrupted training examples; lower is better. To quantify whether an algorithm suppresses corrupted examples, we report GarbageWeight(x) :=

1 X 2σ(xi ), |G| i∈G

where G is the set of corrupted training examples. Lower values are better. Figure 2 reports the data hyper-cleaning results, where the dashed line labeled “w/o Reg” denotes performance without learning data weights. Across all corruption ratios, SGHA assigns substantially smaller weights to corrupted examples than the competing methods, with the advantage becoming more pronounced as the corruption level increases. Among the baselines, F2 BSA performs best overall, but still assigns noticeably larger weights to corrupted samples than SGHA.

8

Conclusions and Future Directions

This paper proposes SGHA and Stoc–SGHA, the first single-loop, fully first-order algorithms for NC–SC bilevel optimization that achieve the optimal ϵ-dependence in the deterministic setting and match the best-known ϵ-dependence of existing nested-loop methods in the stochastic setting. Our approach starts from a Lagrangian formulation of the equality-constrained problem induced by the lower-level first-order optimality condition. We then apply Smoothed GDA to a regularized minimax surrogate and replace the resulting Hessian–vector products with finite-difference approximations of first-order gradients. The analysis is tailored to this specific structure, which is key to obtaining the stated complexity guarantees. Several questions remain open. First, although our algorithms match the best-known ϵdependence in the corresponding settings, their dependence on κy and κ̄y remains worse than existing lower bounds and double-loop penalty methods. Improving the condition-number dependence while preserving the single-loop, fully first-order structure is an important direction. Second, the optimal ϵ-dependence for stochastic NC–SC bilevel optimization under the standard bounded−4 variance oracle is still unknown. Existing Ω(κ4.5 y ϵ ) [Chen et al., 2025a] lower bound constructs a hard instance with a deterministic upper–level objective and a quadratic lower-level objective, and therefore does not fully capture the difficulty of upper-level stochasticity and applies to a restricted problem class. We conjecture that, without these special structures, the tight complexity

19

is Ω(poly(κy )ϵ−6 ). Finally, it remains interesting to determine whether the SGHA framework can be extended beyond strongly convex lower-level problems.

References M. Arbel and J. Mairal. Amortized implicit differentiation for stochastic bilevel optimization. arXiv preprint arXiv:2111.14580, 2021. Y. Arjevani, Y. Carmon, J. C. Duchi, D. J. Foster, N. Srebro, and B. Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199(1–2):165–214, 2023. doi: 10.1007/s10107-022-01822-7. F. Bao, G. Wu, C. Li, J. Zhu, and B. Zhang. Stability and generalization of bilevel programming in hyperparameter optimization. Advances in neural information processing systems, 34:4529–4541, 2021. J. Bolte, T. Le, E. Pauwels, and T. Silveti-Falls. Nonsmooth implicit differentiation for machine-learning and optimization. Advances in neural information processing systems, 34: 13537–13549, 2021. R. I. Boţ and A. Böhm. Alternating proximal-gradient steps for (stochastic) nonconvex-concave minimax problems. SIAM Journal on Optimization, 33(3):1884–1913, 2023. doi: 10.1137/21M1465470. L. Chen, K. Ji, and J. Zhang. On the condition number dependency in bilevel optimization. arXiv preprint arXiv:2511.22331, 2025a. L. Chen, Y. Ma, and J. Zhang. Near-optimal nonconvex-strongly-convex bilevel optimization with fully first-order oracles. Journal of Machine Learning Research, 26(109):1–56, 2025b. T. Chen, Y. Sun, Q. Xiao, and W. Yin. A single-timescale method for stochastic bilevel optimization. In International Conference on Artificial Intelligence and Statistics, pages 2466–2488. PMLR, 2022. X. Chen, T. Xiao, and K. Balasubramanian. Optimal algorithms for stochastic bilevel optimization under relaxed smoothness conditions. Journal of Machine Learning Research, 25(151):1–51, 2024. B. Colson, P. Marcotte, and G. Savard. An overview of bilevel optimization. Annals of operations research, 153(1):235–256, 2007. M. Dagréou, P. Ablin, S. Vaiter, and T. Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. Advances in Neural Information Processing Systems, 35:26698–26710, 2022. J. Domke. Generic methods for optimization-based modeling. In Artificial Intelligence and Statistics, pages 318–326. PMLR, 2012. L. Franceschi, M. Donini, P. Frasconi, and M. Pontil. Forward and reverse gradient-based hyperparameter optimization. In International conference on machine learning, pages 1165–1173. PMLR, 2017. 20

L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International conference on machine learning, pages 1568–1577. PMLR, 2018. S. Ghadimi and M. Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02246, 2018. T. Giovannelli, G. Kent, and L. N. Vicente. Bilevel stochastic methods for optimization and machine learning: Bilevel stochastic descent and darts. arXiv preprint arXiv:2110.00604, 2021. I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial networks. Communications of the ACM, 63(11):139–144, 2020. S. Gould, B. Fernando, A. Cherian, P. Anderson, R. S. Cruz, and E. Guo. On differentiating parameterized argmin and argmax problems with application to bi-level optimization. arXiv preprint arXiv:1607.05447, 2016. R. Grazzi, L. Franceschi, M. Pontil, and S. Salzo. On the iteration complexity of hypergradient computation. In International Conference on Machine Learning, pages 3748–3758. PMLR, 2020. M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 33(1):147–180, 2023. K. Ji, J. Yang, and Y. Liang. Bilevel optimization: Convergence analysis and enhanced design. In International conference on machine learning, pages 4882–4892. PMLR, 2021. P. Khanduri, S. Zeng, M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. A near-optimal algorithm for stochastic bilevel optimization via double-momentum. Advances in neural information processing systems, 34:30271–30283, 2021. Y. Kim, S. Leyffer, and T. Munson. Mpec methods for bilevel optimization problems. In Bilevel optimization: advances and next challenges, pages 335–360. Springer, 2020. V. Konda and J. Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999. W. Kong and R. D. C. Monteiro. An accelerated inexact proximal point method for solving nonconvex-concave min-max problems. SIAM Journal on Optimization, 31(4):2558–2585, 2021. doi: 10.1137/20M1313222. S. G. Krantz and H. R. Parks. The implicit function theorem: history, theory, and applications. Springer Science & Business Media, 2002. G. Kunapuli. Bilevel model selection for support vector machines gautam kunapuli, kristin p. bennett, jing hu, and jong-shi pang. Data mining and mathematical programming, 45:129, 2008. J. Kwon, D. Kwon, S. Wright, and R. Nowak. On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. arXiv preprint arXiv:2309.01753, 2023a.

21

J. Kwon, D. Kwon, S. Wright, and R. D. Nowak. A fully first-order method for stochastic bilevel optimization. In International Conference on Machine Learning, pages 18083–18113. PMLR, 2023b. J. Kwon, D. Kwon, and H. Lyu. On the complexity of first-order methods in stochastic bilevel optimization. In International Conference on Machine Learning, pages 25784–25811. PMLR, 2024. Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998. T. Lin, C. Jin, and M. I. Jordan. Near-optimal algorithms for minimax optimization. In J. Abernethy and S. Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 2738–2779. PMLR, 2020. T. Lin, C. Jin, and M. I. Jordan. Two-timescale gradient descent ascent algorithms for nonconvex minimax optimization. Journal of Machine Learning Research, 26:1–45, 2025. B. Liu, M. Ye, S. Wright, P. Stone, and Q. Liu. Bome! bilevel optimization made easy: A simple first-order approach. Advances in neural information processing systems, 35:17248–17262, 2022. R. Liu, Y. Liu, W. Yao, S. Zeng, and J. Zhang. Averaged method of multipliers for bi-level optimization without lower-level strong convexity. In International Conference on Machine Learning, pages 21839–21866. PMLR, 2023. R. Liu, Z. Liu, W. Yao, S. Zeng, and J. Zhang. Moreau envelope for nonconvex bi-level optimization: A single-loop and hessian-free solution strategy. arXiv preprint arXiv:2405.09927, 2024. A. Mehra and J. Hamm. Penalty method for inversion-free deep bilevel optimization. In Asian conference on machine learning, pages 347–362. PMLR, 2021. M. Nouiehed, M. Sanjabi, T. Huang, J. D. Lee, and M. Razaviyayn. Solving a class of non-convex min-max games using iterative first order methods. In Advances in Neural Information Processing Systems, volume 32, 2019. F. Pedregosa. Hyperparameter optimization with approximate gradient. In International conference on machine learning, pages 737–746. PMLR, 2016. H. Rafique, M. Liu, Q. Lin, and T. Yang. Weakly-convex–concave min–max optimization: Provable algorithms and applications in machine learning. Optimization Methods and Software, 37(3): 1087–1121, 2022. doi: 10.1080/10556788.2021.1895152. A. Rajeswaran, C. Finn, S. M. Kakade, and S. Levine. Meta-learning with implicit gradients. Advances in neural information processing systems, 32, 2019. A. Shaban, C.-A. Cheng, N. Hatch, and B. Boots. Truncated back-propagation for bilevel optimization. In The 22nd international conference on artificial intelligence and statistics, pages 1723–1732. PMLR, 2019. H. Shen and T. Chen. On penalty-based bilevel gradient descent method. In International conference on machine learning, pages 30992–31015. PMLR, 2023. 22

J. Vanschoren, J. N. van Rijn, B. Bischl, and L. Torgo. Openml: Networked science in machine learning. ACM SIGKDD Explorations Newsletter, 15(2):49–60, 2014. H. Von Stackelberg. Market structure and equilibrium. Springer Science & Business Media, 2010. Z. Xu, H. Zhang, Y. Xu, and G. Lan. A unified single-loop alternating gradient projection algorithm for nonconvex-concave and convex-nonconcave minimax problems. Mathematical Programming, 201:635–706, 2023. J. Yang, S. Zhang, N. Kiyavash, and N. He. A catalyst framework for minimax optimization. Advances in Neural Information Processing Systems, 33:5667–5678, 2020. J. Yang, K. Ji, and Y. Liang. Provably faster algorithms for bilevel optimization. Advances in Neural Information Processing Systems, 34:13670–13682, 2021. J. Yang, A. Orvieto, A. Lucchi, and N. He. Faster single-loop algorithms for minimax optimization without strong concavity. In G. Camps-Valls, F. J. R. Ruiz, and I. Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 5485–5517. PMLR, 2022. Y. Yang, P. Xiao, and K. Ji. Achieving O(ϵ−1.5 ) complexity in hessian/jacobian-free stochastic bilevel optimization. Advances in Neural Information Processing Systems, 36:39491–39503, 2023. S. Zeng, T. T. Doan, and J. Romberg. A two-time-scale stochastic optimization framework with applications in control and reinforcement learning. SIAM Journal on Optimization, 34(1): 946–976, 2024. J. Zhang, P. Xiao, R. Sun, and Z. Luo. A single-loop smoothed gradient descent-ascent algorithm for nonconvex-concave min-max problems. Advances in neural information processing systems, 33:7377–7389, 2020. X. Zhang, N. S. Aybat, and M. Gürbüzbalaban. SAPD+: An accelerated stochastic method for nonconvex-concave minimax problems. In Advances in Neural Information Processing Systems, volume 35, pages 21668–21681, 2022.

A

Properties of Reformulated NC–SC Bilevel Optimization

A.1

LICQ of NC-SC Bilevel Optimization

Proof of Lemma 1 Since g(x, ·) is µg -strongly convex, the Jacobian of the constraint mapping with respect to y is ∇yy g(x, y), which satisfies ∇2yy g(x, y) ⪰ µg I. Hence, ∇2yy g(x, y) is nonsingular, and the gradients of the equality constraints are linearly independent. Therefore, the full Jacobian of ∇y g has full row rank, which implies LICQ at every feasible point.

23

A.2

Approximation of Hypergradient

Proof of Theorem 2

First, we justify the stated value of LF̄ ,y . We let

¯ (x, y) = ∇x f (x, y) − ∇xy g(x, y)∇2 g(x, y)−1 ∇y f (x, y). ∇F yy For any y1 , y2 , by the lf,1 -smoothness of f , ∥∇x f (x, y1 ) − ∇x f (x, y2 )∥ ≤ lf,1 ∥y1 − y2 ∥. Moreover, ∥∇xy g(x, y)∇2yy g(x, y)−1 ∥ ≤

lg,1 = κy , µg

and hence ∥∇xy g(x, y1 )∇yy g(x, y1 )−1 (∇y f (x, y1 ) − ∇y f (x, y2 ))∥ ≤ κy lf,1 ∥y1 − y2 ∥. Also, by A−1 − B −1 = A−1 (B − A)B −1 , ∥∇xy g(x, y1 )∇yy g(x, y1 )−1 − ∇xy g(x, y2 )∇yy g(x, y2 )−1 ∥ ≤ ∥∇xy g(x, y1 ) − ∇xy g(x, y2 )∥∥∇yy g(x, y1 )−1 ∥ + ∥∇xy g(x, y2 )∥∥∇yy g(x, y1 )−1 − ∇yy g(x, y2 )−1 ∥ lg,2 lg,1 ≤ ∥y1 − y2 ∥ + 2 ∥∇yy g(x, y1 ) − ∇yy g(x, y2 )∥ µg µg ≤ lg,2

1 lg,1 + 2 µg µg

!

∥y1 − y2 ∥.

Using ∥∇y f (x, y)∥ ≤ lf,0 , we get ∥∇xy g(x, y1 )∇yy g(x, y1 )−1 ∇y f (x, y1 ) − ∇xy g(x, y2 )∇yy g(x, y2 )−1 ∇y f (x, y2 )∥ ≤ κy lf,1 ∥y1 − y2 ∥ + lf,0 lg,2

lg,1 1 + 2 µg µg

!

∥y1 − y2 ∥.

Combining the above inequalities yields ¯ (x, y1 ) − ∇F ¯ (x, y2 )∥ ≤ L ∥y1 − y2 ∥, ∥∇F F̄ ,y with 1 lg,1 + 2 µg µg

LF̄ ,y = lf,1 (1 + κy ) + lf,0 lg,2

!

.

Moreover, 



λ + ∇2yy g(x, y)−1 ∇y f (x, y) = ∇2yy g(x, y)−1 ∇y f (x, y) + ∇2yy g(x, y)λ , Since g(x, ·) is µg -strongly convex, we have λ + ∇2yy g(x, y)−1 ∇y f (x, y) ≤

24

1 ∥∇y f (x, y) + ∇2yy g(x, y)λ∥. µg

Then, we obtain ¯ (x, y) = ∇x f (x, y) − ∇xy g(x, y)∇2 g(x, y)−1 ∇y f (x, y) ∇F yy 



= ∇x f (x, y) + ∇xy g(x, y)λ − ∇xy g(x, y) λ + ∇2yy g(x, y)−1 ∇y f (x, y) . Thus, ¯ (x, y)∥ ≤ ∥∇x f (x, y) + ∇xy g(x, y)λ∥ + ∥∇xy g(x, y)∥ λ + ∇2yy g(x, y)−1 ∇y f (x, y) ∥∇F ≤ ∥∇x f (x, y) + ∇xy g(x, y)λ∥ +

lg,1 ∥∇y f (x, y) + ∇2yy g(x, y)λ∥ µg

= ∥∇x f (x, y) + ∇xy g(x, y)λ∥ + κy ∥∇y f (x, y) + ∇2yy g(x, y)λ∥. Next, we transfer the bound from the current y to the lower-level solution y ⋆ (x). Since g(x, ·) is µg -strongly convex, ∇y g(x, y ⋆ (x)) = 0 and ∥y − y ⋆ (x)∥ ≤

1 1 ∥∇y g(x, y) − ∇y g(x, y ⋆ (x))∥ = ∥∇y g(x, y)∥. µg µg

Moreover, ¯ (x, y ⋆ (x)). ∇F (x) = ∇F ¯ (x, ·) with respect to y, Hence, by the Lipschitz continuity of ∇F ¯ (x, y ⋆ (x))∥ ∥∇F (x)∥ = ∥∇F ¯ (x, y)∥ + ∥∇F ¯ (x, y ⋆ (x)) − ∇F ¯ (x, y)∥ ≤ ∥∇F ≤ ∥∇x f (x, y) + ∇xy g(x, y)λ∥ + κy ∥∇y f (x, y) + ∇2yy g(x, y)λ∥ + LF̄ ,y ∥y − y ⋆ (x)∥ LF̄ ,y ≤ ∥∇x f (x, y) + ∇xy g(x, y)λ∥ + κy ∥∇y f (x, y) + ∇2yy g(x, y)λ∥ + ∥∇y g(x, y)∥. µg

A.3

Boundedness of λ∗

Proof of Theorem 3

At a KKT point (x∗ , y ∗ , λ∗ ), we have the stationarity condition:

∇y L(x∗ , y ∗ , λ∗ ) = ∇y f (x∗ , y ∗ ) + (λ∗ )⊤ ∇2yy g(x∗ , y ∗ ) = 0, which implies (λ∗ )⊤ ∇2yy g(x∗ , y ∗ ) = −∇y f (x∗ , y ∗ ). By the strong convexity of g(x, y) with respect to y, ∇2yy g(x∗ , y ∗ ) is positive definite and invertible with ∥[∇2yy g(x∗ , y ∗ )]−1 ∥ ≤ µ1g . Thus, we have ∥λ∗ ∥ = ∥[∇2yy g(x∗ , y ∗ )]−1 ∇y f (x∗ , y ∗ )∥ ≤ ∥[∇2yy g(x∗ , y ∗ )]−1 ∥ · ∥∇y f (x∗ , y ∗ )∥ ≤ Thus, λ∗ is bounded by a constant independent of the specific KKT point.

25

lf,0 . µg

B

Deterministic NC-SC Bilevel Optimization

B.1

Lower Bound of the Lyapunov Function

Proof of Lemma 5. Since K(·, ŵ, λ) is strongly convex and coercive in w for each λ ∈ Λ, while K(w, ŵ, ·) is continuous and strongly concave on the compact convex set Λ, by Sion’s minimax theorem, P (ŵ) = min max K(w, ŵ, λ) = max min K(w, ŵ, λ) = max Ψ(ŵ, λ). w

λ∈Λ

w

λ∈Λ

λ∈Λ

Then, it is easy to obtain V = V (w, ŵ, λ) = K(w, ŵ, λ) − 2Ψ(ŵ, λ) + 2P (ŵ) = P (ŵ) + (K(w, ŵ, λ) − Ψ(ŵ, λ)) + (P (ŵ) − Ψ(ŵ, λ)) ≥ P (ŵ), Next, by the definition of P , we have 

P (ŵ) = min max f (w) + λ⊤ ∇y g(w) + w

λ∈Λ

pλ pw ∥w − ŵ∥2 − ∥λ∥2 . 2 2



Since Λ = {λ : ∥λ∥ ≤ Cλ } with Cλ > 0, we have 0 ∈ Λ. Therefore, for any fixed w, 

max λ⊤ ∇y g(w) − λ∈Λ

pλ ∥λ∥2 2



≥ 0⊤ ∇y g(w) −

pλ ∥0∥2 2

= 0. Consequently, pw P (ŵ) ≥ min f (w) + ∥w − ŵ∥2 . w 2 



Since p2w ∥w − ŵ∥2 ≥ 0, Assumption 1 implies P (ŵ) ≥ f ,

∀ŵ.

Together with V (w, ŵ, λ) ≥ P (ŵ), this gives Vt ≥ f . This completes the proof.

B.2

Properties of Deterministic Finite Difference Approximation

Lemma 12. Define the deterministic finite-difference approximation of ∇2xy g(x, y)λ and ∇2yy g(x, y)λ as ˜ 2 gλ (x, y) := ∇x g(x, y + τ λ) − ∇x g(x, y − τ λ) , ∇ xy 2τ and ˜ 2 gλ (x, y) := ∇y g(x, y + τ λ) − ∇y g(x, y − τ λ) . ∇ yy 2τ

26

Under Assumption 1 and λ ∈ Λ = {λ : ∥λ∥ ≤ Cλ }, we have ˜ 2xy gλ (x, y) ≤ ∇2xy g(x, y)λ − ∇

lg,2 Cλ2 τ, 2

(7)

˜ 2yy gλ (x, y) ≤ ∇2yy g(x, y)λ − ∇

lg,2 Cλ2 τ. 2

(8)

and

Proof. We first prove (7). Define Gx (s) := ∇x g(x, y + sλ). Then G′x (s) = ∇2xy g(x, y + sλ)λ. Hence, ˜ 2xy gλ (x, y) = Gx (τ ) − Gx (−τ ) = 1 ∇ 2τ 2τ

Z τ −τ

G′x (s) ds.

Therefore,  1 τ  ′ Gx (s) − G′x (0) ds 2τ −τ Z  1 τ  2 ∇xy g(x, y + sλ) − ∇2xy g(x, y) λ ds ≤ 2τ −τ Z 1 τ ≤ lg,2 |s|∥λ∥2 ds 2τ −τ lg,2 = τ ∥λ∥2 2 lg,2 Cλ2 ≤ τ. 2 Z

˜ 2 gλ (x, y) − ∇2 g(x, y)λ = ∇ xy xy

This proves (7). The proof of (8) is identical to that of (7).

B.3

Preliminary Lemmas

Lemma 13. Under Assumption 1, and λ ∈ Λ = {λ : ∥λ∥ ≤ Cλ }, let lL,1 be any constant satisfying lL,1 ≥

√

2(lf,1 + Cλ lg,2 ).

Then ∇w L(w, λ) satisfies ∥∇w L(w, λ) − ∇w L(w′ , λ)∥ ≤ lL,1 ∥w − w′ ∥. ∥∇w L(w, λ) − ∇w L(w, λ′ )∥ ≤ lg,1 ∥λ − λ′ ∥.

27

Proof. By the definition of L(x, y, λ), we have !

′

∇w L(w, λ) − ∇w L(w , λ) =

!

∇x f (x, y) − ∇x f (x′ , y ′ ) ∇2xy g(x, y) − ∇2xy g(x′ , y ′ ) + λ ′ ′ ∇y f (x, y) − ∇y f (x , y ) ∇2yy g(x, y) − ∇2yy g(x′ , y ′ )

≤ (lf,1 + Cλ lg,2 ) ∥x − x′ ∥ + ∥y − y ′ ∥ q √ ≤ 2(lf,1 + Cλ lg,2 ) ∥x − x′ ∥2 + ∥y − y ′ ∥2 √ = 2(lf,1 + Cλ lg,2 )∥w − w′ ∥.

Similarly, ∇w L(w, λ) − ∇w L(w, λ′ ) =

∇2xy g(x, y)(λ − λ′ ) ∇2yy g(x, y)(λ − λ′ )

!

≤ lg,1 ∥λ − λ′ ∥.

The first bound remains valid for every larger deterministic upper bound lL,1 , which proves the stated form. Lemma 14. When pw > lL,1 , K(w, ŵ, λ) is (pw − lL,1 )-strongly convex w.r.t. w, and pλ -strongly concave w.r.t. λ. Moreover, we have ∥w′ − w′′ ∥ ≤

1 ∥∇w K(w′ , ŵ, λ) − ∇w K(w′′ , ŵ, λ)∥. pw − lL,1

Proof. Since K(w, ŵ, λ) is (pw − lL,1 )-strongly convex with respect to w, its gradient satisfies the strong monotonicity property ∇w K(w′ , ŵ, λ) − ∇w K(w′′ , ŵ, λ), w′ − w′′ ≥ (pw − lL,1 )∥w′ − w′′ ∥2 .

(9)

On the other hand, by the Cauchy–Schwarz inequality, we have ∇w K(w′ , ŵ, λ) − ∇w K(w′′ , ŵ, λ), w′ − w′′ ≤ ∥∇w K(w′ , ŵ, λ) − ∇w K(w′′ , ŵ, λ)∥ · ∥w′ − w′′ ∥. (10) Combining (9) and (10), we have (pw − lL,1 )∥w′ − w′′ ∥2 ≤ ∥∇w K(w′ , ŵ, λ) − ∇w K(w′′ , ŵ, λ)∥ · ∥w′ − w′′ ∥. Dividing both sides by ∥w′ − w′′ ∥ completes the proof. Lemma 15. When pw > lL,1 , we have ∥w∗ (ŵ, λ) − w∗ (ŵ′ , λ)∥ ≤ γ1 ∥ŵ − ŵ′ ∥, ∥w∗ (ŵ) − w∗ (ŵ′ )∥ ≤ γ1 ∥ŵ − ŵ′ ∥, ∥w∗ (ŵ, λ) − w∗ (ŵ, λ′ )∥ ≤ γ2 ∥λ − λ′ ∥, l

pw g,1 where γ1 = pw −l , γ2 = pw −l . L,1 L,1

Proof. By Lemma 14, we have (pw − lL,1 )∥w∗ (ŵ, λ) − w∗ (ŵ′ , λ)∥ ≤ ∥∇w K(w∗ (ŵ, λ), ŵ, λ) − ∇w K(w∗ (ŵ′ , λ), ŵ, λ)∥. 28

(11)

Using the first-order optimality condition ∇w K(w∗ (ŵ, λ), ŵ, λ) = 0,

∇w K(w∗ (ŵ′ , λ), ŵ′ , λ) = 0,

we have ∇w K(w∗ (ŵ, λ), ŵ, λ) − ∇w K(w∗ (ŵ′ , λ), ŵ, λ) = ∇w K(w∗ (ŵ, λ), ŵ, λ) − ∇w K(w∗ (ŵ′ , λ), ŵ′ , λ) + ∇w K(w∗ (ŵ′ , λ), ŵ′ , λ) − ∇w K(w∗ (ŵ′ , λ), ŵ, λ) = ∇w K(w∗ (ŵ′ , λ), ŵ′ , λ) − ∇w K(w∗ (ŵ′ , λ), ŵ, λ). Then, (11) reduces to (pw − lL,1 )∥w∗ (ŵ, λ) − w∗ (ŵ′ , λ)∥ ≤ ∥∇w K(w∗ (ŵ′ , λ), ŵ′ , λ) − ∇w K(w∗ (ŵ′ , λ), ŵ, λ)∥.

(12)

Using ∇w K(w, ŵ, λ) = ∇w L(w, λ) + pw (w − ŵ), (12) reduces to (pw − lL,1 )∥w∗ (ŵ, λ) − w∗ (ŵ′ , λ)∥ ≤ pw ∥ŵ − ŵ′ ∥, which implies ∥w∗ (ŵ, λ) − w∗ (ŵ′ , λ)∥ ≤

pw ∥ŵ − ŵ′ ∥ = γ1 ∥ŵ − ŵ′ ∥. pw − lL,1

This proves the first claim. Similarly, since Φ(w, ŵ) is still (pw − lL,1 )-strongly convex with respect to w, we have (pw − lL,1 )∥w∗ (ŵ) − w∗ (ŵ′ )∥ ≤ ∥∇w Φ(w∗ (ŵ), ŵ) − ∇w Φ(w∗ (ŵ′ ), ŵ)∥.

(13)

Using the first-order optimality conditions ∇w Φ(w∗ (ŵ), ŵ) = 0,

∇w Φ(w∗ (ŵ′ ), ŵ′ ) = 0,

we have ∇w Φ(w∗ (ŵ), ŵ) − ∇w Φ(w∗ (ŵ′ ), ŵ) = ∇w Φ(w∗ (ŵ), ŵ) − ∇w Φ(w∗ (ŵ′ ), ŵ′ ) + ∇w Φ(w∗ (ŵ′ ), ŵ′ ) − ∇w Φ(w∗ (ŵ′ ), ŵ) = ∇w Φ(w∗ (ŵ′ ), ŵ′ ) − ∇w Φ(w∗ (ŵ′ ), ŵ). Then, (13) reduces to (pw − lL,1 )∥w∗ (ŵ) − w∗ (ŵ′ )∥ ≤ ∥∇w Φ(w∗ (ŵ′ ), ŵ′ ) − ∇w Φ(w∗ (ŵ′ ), ŵ)∥. Using ∇w Φ(w∗ (ŵ′ ), ŵ′ ) − ∇w Φ(w∗ (ŵ′ ), ŵ) = pw (ŵ − ŵ′ ), (14) reduces to (pw − lL,1 )∥w∗ (ŵ) − w∗ (ŵ′ )∥ ≤ pw ∥ŵ − ŵ′ ∥,

29

(14)

which implies ∥w∗ (ŵ) − w∗ (ŵ′ )∥ ≤

pw ∥ŵ − ŵ′ ∥ = γ1 ∥ŵ − ŵ′ ∥. pw − lL,1

This proves the second claim. Similarly, since ∇w K(w∗ (ŵ, λ), ŵ, λ) = 0,

∇w K(w∗ (ŵ, λ′ ), ŵ, λ′ ) = 0.

we have ∇w K(w∗ (ŵ, λ), ŵ, λ)−∇w K(w∗ (ŵ, λ′ ), ŵ, λ) = − ∇w K(w∗ (ŵ, λ′ ), ŵ, λ) − ∇w K(w∗ (ŵ, λ′ ), ŵ, λ′ ) . (15) By taking norms over both sides of (15), we have

∥∇w K(w∗ (ŵ, λ), ŵ, λ)−∇w K(w∗ (ŵ, λ′ ), ŵ, λ)∥ = ∥∇w K(w∗ (ŵ, λ′ ), ŵ, λ)−∇w K(w∗ (ŵ, λ′ ), ŵ, λ′ )∥. (16) By strong convexity of K(w, ŵ, λ) w.r.t. w, we have (pw − lL,1 )∥w∗ (ŵ, λ) − w∗ (ŵ, λ′ )∥ ≤ ∥∇w K(w∗ (ŵ, λ), ŵ, λ) − ∇w K(w∗ (ŵ, λ′ ), ŵ, λ)∥

(17)

Recall Lemma 13, we have ∥∇w K(w∗ (ŵ, λ′ ), ŵ, λ) − ∇w K(w∗ (ŵ, λ′ ), ŵ, λ′ )∥ ≤ lg,1 ∥λ − λ′ ∥.

(18)

Plugging (17) and (18) into (16), we have (pw − lL,1 )∥w∗ (ŵ, λ) − w∗ (ŵ, λ′ )∥ ≤ lg,1 ∥λ − λ′ ∥, which implies ∥w∗ (ŵ, λ) − w∗ (ŵ, λ′ )∥ ≤

lg,1 ∥λ − λ′ ∥ = γ2 ∥λ − λ′ ∥. pw − lL,1

This proves the third claim. Lemma 16. Under Assumption 1 and the update rule of Algorithm 1, we have xk+1 − xk y k+1 − y k λk+1 − λk

2

2 2

2 l2 C 4 τ 2 γx,k g,2 λ , 2 2 l2 C 4 τ 2 γy,k 2 g,2 λ ∇y K(wk , ŵk , λk ) + , 2

2 ≤ 2γx,k ∇x K(wk , ŵk , λk ) 2 ≤ 2γy,k

2

+

2 2 ≤ 2γλ,k ∥∇y g(xk , y k )∥2 + 2γλ,k p2λ Cλ2 .

Proof. According to the update rule of xk in Algorithm 1 and by (7) in Lemma 12, we have ∥xk+1 − xk ∥2 2 ˜ 2 gλk (xk , y k ) + pw (xk − x̂k ) = γx,k ∇x f (xk , y k ) + ∇ xy

2

2 ≤ 2γx,k ∇x f (xk , y k ) + ∇2xy g(xk , y k )λk + pw (xk − x̂k )

30

2

2 ˜ 2xy gλk (xk , y k ) + 2γx,k ∇2xy g(xk , y k )λk − ∇

2

2 ≤ 2γx,k ∇x K(wk , ŵk , λk )

2

+

2 l2 C 4 τ 2 γx,k g,2 λ . 2

Similarly, for y k , 2 ∥y k+1 − y k ∥2 ≤ 2γy,k ∇y K(wk , ŵk , λk )

2

+

2 l2 C 4 τ 2 γy,k g,2 λ . 2

For λk , by nonexpansiveness of projection operator and ∥λk ∥ ≤ Cλ , 2 2 2 ∥λk+1 − λk ∥2 ≤ γλ,k ∥∇y g(xk , y k ) − pλ λk ∥2 ≤ 2γλ,k ∥∇y g(xk , y k )∥2 + 2γλ,k p2λ Cλ2 .

B.4

Intermediate Lemmas for Lyapunov Function

1 . Then, we have Lemma 17. Under Assumption 1, suppose γw,k ≤ 8(pw +l L,1 )

K(wk , ŵk , λk ) − K(wk+1 , ŵk , λk+1 )   2 γw,k γw,k 2 2 ≥ ∇w K(wk , ŵk , λk ) − + (pw + lL,1 )γw,k lg,2 Cλ4 τ 2 4 4 ! 2 lg,1 pλ k k k k k+1 + ⟨∇y g(x , y ) − pλ λ , λ − λ ⟩ − + ∥λk+1 − λk ∥2 . 2 2(pw + lL,1 ) Proof. Since K(w, ŵ, λ) is (pw + lL,1 )-smooth w.r.t. w, and pλ -smooth w.r.t. λ, we have K(wk , ŵk , λk ) − K(wk+1 , ŵk , λk+1 ) ≥ K(wk , ŵk , λk ) − K(wk+1 , ŵk , λk ) + K(wk+1 , ŵk , λk ) − K(wk+1 , ŵk , λk+1 ) ≥ ⟨∇w K(wk , ŵk , λk ), wk − wk+1 ⟩ + ⟨∇y g(xk , y k ) − pλ λk , λk − λk+1 ⟩ pw + lL,1 k+1 pλ + ⟨∇y g(xk+1 , y k+1 ) − ∇y g(xk , y k ), λk − λk+1 ⟩ − ∥w − wk ∥2 − ∥λk+1 − λk ∥2 . 2 2 By Young’s inequality, ⟨∇y g(xk+1 , y k+1 ) − ∇y g(xk , y k ), λk − λk+1 ⟩ 2 lg,1 pw + lL,1 k+1 k 2 ≥− ∥w −w ∥ − ∥λk+1 − λk ∥2 . 2 2(pw + lL,1 )

Then, according to the update rules of xk and y k , we have K(wk , ŵk , λk ) − K(wk+1 , ŵk , λk+1 ) D

˜ 2 gλk (xk , y k ) + pw (xk − x̂k ) ≥ γx,k ∇x K(wk , ŵk , λk ), ∇x f (xk , y k ) + ∇ xy D

E

˜ 2 gλk (xk , y k ) + pw (y k − ŷ k ) + γy,k ∇y K(wk , ŵk , λk ), ∇y f (xk , y k ) + ∇ yy k

k

k

k

+ ⟨∇y g(x , y ) − pλ λ , λ − λ

k+1

E

2 lg,1 pw + lL,1 k+1 k 2 ⟩− ∥w −w ∥ − ∥λk+1 − λk ∥2 2 2(pw + lL,1 )

31

−

pw + lL,1 k+1 pλ ∥w − wk ∥2 − ∥λk+1 − λk ∥2 2 2

= γx,k ∇x K(wk , ŵk , λk )

2

+ γy,k ∇y K(wk , ŵk , λk )

2

D

E

D

E

˜ 2 gλk (xk , y k ) − γx,k ∇x K(wk , ŵk , λk ), ∇2xy g(xk , y k )λk − ∇ xy ˜ 2 gλk (xk , y k ) − γy,k ∇y K(wk , ŵk , λk ), ∇2yy g(xk , y k )λk − ∇ yy

2 lg,1 pλ + ∥λk+1 − λk ∥2 . 2 2(pw + lL,1 )

!

k

k

k

k

+ ⟨∇y g(x , y ) − pλ λ , λ − λ

k+1

⟩ − (pw + lL,1 )∥w

k+1

k 2

−w ∥ −

By using that fact that ⟨x, y⟩ ≤ 21 ∥x∥2 + 12 ∥y∥2 , we have K(wk , ŵk , λk ) − K(wk+1 , ŵk , λk+1 ) 2 2 γy,k γx,k ∇x K(wk , ŵk , λk ) + ∇y K(wk , ŵk , λk ) ≥ 2 2 2 2 γx,k 2 k k k 2 ˜ xy gλk (xk , y k ) − γy,k ∇2yy g(xk , y k )λk − ∇ ˜ 2yy gλk (xk , y k ) − ∇xy g(x , y )λ − ∇ 2 2 ! 2 lg,1 pλ k k k k k+1 k+1 k 2 + ∥λk+1 − λk ∥2 . + ⟨∇y g(x , y ) − pλ λ , λ − λ ⟩ − (pw + lL,1 )∥w −w ∥ − 2 2(pw + lL,1 ) 1 , we have By Lemma 16, and choosing γw,k = γx,k = γy,k ≤ 8(pw +l L,1 )

K(wk , ŵk , λk ) − K(wk+1 , ŵk , λk+1 )     2 2 γx,k γy,k k k k 2 2 ≥ − 2(pw + lL,1 )γx,k ∇x K(w , ŵ , λ ) + − 2(pw + lL,1 )γy,k ∇y K(wk , ŵk , λk ) 2 2   2 2 2 4 γx,k γy,k lg,2 Cλ 2 (pw + lL,1 )(γx,k + γy,k ) 2 4 2 − + τ − lg,2 Cλ τ 2 2 4 2 ! 2 lg,1 pλ k k k k k+1 + + ⟨∇y g(x , y ) − pλ λ , λ − λ ⟩ − ∥λk+1 − λk ∥2 2 2(pw + lL,1 )   2 γw,k γw,k 2 2 ∇w K(wk , ŵk , λk ) − + (pw + lL,1 )γw,k ≥ lg,2 Cλ4 τ 2 4 4 ! 2 lg,1 pλ k k k k k+1 + ⟨∇y g(x , y ) − pλ λ , λ − λ ⟩ − + ∥λk+1 − λk ∥2 . 2 2(pw + lL,1 )

Lemma 18. The update of ŵ in Algorithm 1 yields K(wk+1 , ŵk , λk+1 ) − K(wk+1 , ŵk+1 , λk+1 ) ≥

pw k+1 ∥ŵ − ŵk ∥2 . 2β

Proof. By the definition of K(w, ŵ, λ) and the update of ŵ, as 0 < β < 1, we have i pw h k+1 ∥w − ŵk ∥2 − ∥wk+1 − ŵk+1 ∥2 2 " # pw 1 (1 − β)2 k+1 k+1 k 2 k 2 ∥ŵ − ŵ ∥ − ∥ŵ − ŵ ∥ = 2 β2 β2

K(wk+1 , ŵk , λk+1 ) − K(wk+1 , ŵk+1 , λk+1 ) =

32

≥

pw k+1 ∥ŵ − ŵk ∥2 . 2β

Lemma 19. With lΨ,1 = pλ + lg,1 γ2 , we have E

D

Ψ(ŵk , λk+1 ) − Ψ(ŵk , λk ) ≥ ∇λ Ψ(ŵk , λk ), λk+1 − λk − Ψ(ŵk+1 , λk+1 ) − Ψ(ŵk , λk+1 ) ≥

lΨ,1 k+1 ∥λ − λk ∥2 , 2

i h pw k+1 (ŵ − ŵk )⊤ ŵk+1 + ŵk − 2w∗ (ŵk+1 , λk+1 ) . 2

Proof. By Danskin’s theorem, we have ∇λ Ψ(ŵ, λ) = ∇λ K(w∗ (ŵ, λ), ŵ, λ). Thus, by Lemma 15, we have ∥∇λ Ψ(ŵ, λ′ ) − ∇λ Ψ(ŵ, λ′′ )∥ = ∥∇λ K(w∗ (ŵ, λ′ ), ŵ, λ′ ) − ∇λ K(w∗ (ŵ, λ′′ ), ŵ, λ′′ ∥ ≤ ∥∇λ K(w∗ (ŵ, λ′ ), ŵ, λ′ ) − ∇λ K(w∗ (ŵ, λ′ ), ŵ, λ′′ ∥ + ∥∇λ K(w∗ (ŵ, λ′ ), ŵ, λ′′ ) − ∇λ K(w∗ (ŵ, λ′′ ), ŵ, λ′′ ∥ ≤ pλ ∥λ′ − λ′′ ∥ + ∥∇y g(w∗ (ŵ, λ′ )) − ∇y g(w∗ (ŵ, λ′′ ))∥ ≤ pλ ∥λ′ − λ′′ ∥ + lg,1 ∥w∗ (ŵ, λ′ ) − w∗ (ŵ, λ′′ )∥ ≤ (pλ + lg,1 γ2 )∥λ′ − λ′′ ∥, which implies Ψ(ŵ, λ′ ) is lΨ,1 -smooth w.r.t. λ. On the other hand, by the definition of w∗ (ŵk , λk+1 ), we have Ψ(ŵk+1 , λk+1 ) − Ψ(ŵk , λk+1 ) = K(w∗ (ŵk+1 , λk+1 ), ŵk+1 , λk+1 ) − K(w∗ (ŵk , λk+1 ), ŵk , λk+1 ) ≥ K(w∗ (ŵk+1 , λk+1 ), ŵk+1 , λk+1 ) − K(w∗ (ŵk+1 , λk+1 ), ŵk , λk+1 ) i pw h k+1 = ∥ŵ − w∗ (ŵk+1 , λk+1 )∥2 − ∥ŵk − w∗ (ŵk+1 , λk+1 )∥2 2 pw k+1 = (ŵ − ŵk )⊤ [ŵk+1 + ŵk − 2w∗ (ŵk+1 , λk+1 )]. 2

Lemma 20. The proximal descent satisfies P (ŵk+1 ) − P (ŵk ) ≤

h i pw k+1 (ŵ − ŵk )⊤ ŵk+1 + ŵk − 2w∗ (ŵk , λ̂∗ (ŵk+1 )) . 2

Proof. By the definition of λ̂∗ (ŵk ), we have P (ŵk+1 ) − P (ŵk ) = Ψ(ŵk+1 , λ̂∗ (ŵk+1 )) − Ψ(ŵk , λ̂∗ (ŵk )) ≤ Ψ(ŵk+1 , λ̂∗ (ŵk+1 )) − Ψ(ŵk , λ̂∗ (ŵk+1 )) = K(w∗ (ŵk+1 , λ̂∗ (ŵk+1 )), ŵk+1 , λ̂∗ (ŵk+1 )) − K(w∗ (ŵk , λ̂∗ (ŵk+1 )), ŵk , λ̂∗ (ŵk+1 )) ≤ K(w∗ (ŵk , λ̂∗ (ŵk+1 )), ŵk+1 , λ̂∗ (ŵk+1 )) − K(w∗ (ŵk , λ̂∗ (ŵk+1 )), ŵk , λ̂∗ (ŵk+1 ))

33

2 2 pw w∗ (ŵk , λ̂∗ (ŵk+1 )) − ŵk+1 − w∗ (ŵk , λ̂∗ (ŵk+1 )) − ŵk 2 h i pw k+1 = (ŵ − ŵk )⊤ ŵk+1 + ŵk − 2w∗ (ŵk , λ̂∗ (ŵk+1 )) . 2





=

Lemma 21. The following inequality holds: 2Ψ(ŵk+1 , λk+1 ) − 2Ψ(ŵk , λk+1 ) − 2P (ŵk+1 ) + 2P (ŵk )   pw ≥ − 2pw γ1 + + 48pw βγ12 ∥ŵk+1 − ŵk ∥2 − 24pw β∥w∗ (ŵk ) − w∗ (ŵk , λk )∥2 − 24pw βγ22 ∥λk+1 − λk ∥2 . 6β Proof. Combining Lemma 19 and Lemma 20, and by Lemma 15, we have 2Ψ(ŵk+1 , λk+1 ) − 2Ψ(ŵk , λk+1 ) − 2P (ŵk+1 ) + 2P (ŵk ) h

i

≥ 2pw (ŵk+1 − ŵk )⊤ w∗ (ŵk , λ̂∗ (ŵk+1 )) − w∗ (ŵk+1 , λk+1 ) h

i

= 2pw (ŵk+1 − ŵk )⊤ w∗ (ŵk , λ̂∗ (ŵk+1 )) − w∗ (ŵk+1 , λ̂∗ (ŵk+1 )) h

+ 2pw (ŵk+1 − ŵk )⊤ w∗ (ŵk+1 , λ̂∗ (ŵk+1 )) − w∗ (ŵk+1 , λk+1 )

i

h

i

≥ −2pw γ1 ∥ŵk+1 − ŵk ∥2 + 2pw (ŵk+1 − ŵk )⊤ w∗ (ŵk+1 , λ̂∗ (ŵk+1 )) − w∗ (ŵk+1 , λk+1 )

pw ∥ŵk+1 − ŵk ∥2 − 6pw β∥w∗ (ŵk+1 ) − w∗ (ŵk+1 , λk+1 )∥2 ≥ − 2pw γ1 + 6β   pw ≥ − 2pw γ1 + ∥ŵk+1 − ŵk ∥2 − 24pw β∥w∗ (ŵk ) − w∗ (ŵk , λk )∥2 − 24pw β∥w∗ (ŵk ) − w∗ (ŵk+1 )∥2 6β − 24pw β∥w∗ (ŵk+1 , λk+1 ) − w∗ (ŵk , λk+1 )∥2 − 24pw β∥w∗ (ŵk , λk+1 ) − w∗ (ŵk , λk )∥2   pw ≥ − 2pw γ1 + + 48pw βγ12 ∥ŵk+1 − ŵk ∥2 − 24pw β∥w∗ (ŵk ) − w∗ (ŵk , λk )∥2 − 24pw βγ22 ∥λk+1 − λk ∥2 . 6β 



Lemma 22. Set pw = 2lL,1 . Suppose

γw,k ≤

1 , 8(pw + lL,1 )

γλ,k ≤ min

   

 

1 

2 lg,1    2 2lΨ,1 + pλ + p +l w

L,1

  l2  , L,1 γ w,k . 2  16lg,1  

Then, we have K(wk , ŵk , λk ) − K(wk+1 , ŵk , λk+1 ) + 2Ψ(ŵk , λk+1 ) − 2Ψ(ŵk , λk ) 2 2 γw,k 1 ≥ ∇w K(wk , ŵk , λk ) + λk+1 − λk − CV,k τ 2 , 8 4γλ,k where



CV,k =

γw,k 2 2 + (pw + lL,1 )γw,k lg,2 Cλ4 . 4 

34

Proof. Combining Lemma 17 and Lemma 19 gives K(wk , ŵk , λk ) − K(wk+1 , ŵk , λk+1 ) + 2Ψ(ŵk , λk+1 ) − 2Ψ(ŵk , λk )   2 γw,k γw,k 2 2 ∇w K(wk , ŵk , λk ) − ≥ + (pw + lL,1 )γw,k lg,2 Cλ4 τ 2 4 4 D

+ ∇y g(xk , y k ) − pλ λk , λk+1 − λk D

E 



+ 2 ∇λ Ψ(ŵk , λk ) − ∇y g(xk , y k ) − pλ λk , λk+1 − λk 2 lg,1 pλ + − lΨ,1 + 2 2(pw + lL,1 )

!

λk+1 − λk

2

E

.

Since 



λk+1 = PΛ λk + γλ,k ∇y g(xk , y k ) − pλ λk



,

the first-order optimality condition of the projection gives D

1

E

∇y g(xk , y k ) − pλ λk , λk+1 − λk ≥

γλ,k

λk+1 − λk

2

.

Therefore, D

k

k

k

k+1

∇y g(x , y ) − pλ λ , λ

≥

pλ − lΨ,1 − γλ,k 2 1

−λ

k

E

pλ − lΨ,1 + 2 

!

2

λk+1 − λk



λk+1 − λk

2

.

Next, by Danskin’s theorem, ∇λ Ψ(ŵk , λk ) = ∇y g(w⋆ (ŵk , λk )) − pλ λk . Hence, by the Lipschitz continuity of ∇y g and Lemma 14, 

∇λ Ψ(ŵk , λk ) − ∇y g(xk , y k ) − pλ λk



= ∇y g(w⋆ (ŵk , λk )) − ∇y g(wk ) ≤ lg,1 w⋆ (ŵk , λk ) − wk ≤

lg,1 ∇w K(wk , ŵk , λk ) . pw − lL,1

Using Young’s inequality, we obtain D





2 ∇λ Ψ(ŵk , λk ) − ∇y g(xk , y k ) − pλ λk , λk+1 − λk

E

≥−

  2 2 1 λk+1 − λk − 2γλ,k ∇λ Ψ(ŵk , λk ) − ∇y g(xk , y k ) − pλ λk 2γλ,k

≥−

2 2 2 2γλ,k lg,1 1 k k k λk+1 − λk − ∇ K(w , ŵ , λ ) . w 2γλ,k (pw − lL,1 )2

Since γλ,k ≤

1 

l2

g,1 2 2lΨ,1 + pλ + pw +l L,1

35

,

we have 1 γλ,k

− lΨ,1 −

2 lg,1 pλ 1 1 − − ≥ . 2 2(pw + lL,1 ) 2γλ,k 4γλ,k

Therefore, K(wk , ŵk , λk ) − K(wk+1 , ŵk , λk+1 ) + 2Ψ(ŵk , λk+1 ) − 2Ψ(ŵk , λk ) ≥

2 2 2 2 2γλ,k lg,1 γw,k 1 ∇w K(wk , ŵk , λk ) − ∇w K(wk , ŵk , λk ) + λk+1 − λk 2 4 (pw − lL,1 ) 4γλ,k   γw,k 2 2 + (pw + lL,1 )γw,k lg,2 Cλ4 τ 2 . − 4

Finally, since pw = 2lL,1 and γλ,k ≤ we have

2 lL,1 (pw − lL,1 )2 γ = w,k 2 2 γw,k , 16lg,1 16lg,1

2 2γλ,k lg,1 γw,k ≤ . 2 (pw − lL,1 ) 8

Thus, K(wk , ŵk , λk ) − K(wk+1 , ŵk , λk+1 ) + 2Ψ(ŵk , λk+1 ) − 2Ψ(ŵk , λk )   2 2 γw,k γw,k 1 2 2 ∇w K(wk , ŵk , λk ) + λk+1 − λk − + (pw + lL,1 )γw,k lg,2 Cλ4 τ 2 . ≥ 8 4γλ,k 4 This completes the proof. Proposition 23. Define the Lyapunov function Vk = K(wk , ŵk , λk ) − 2Ψ(ŵk , λk ) + 2P (ŵk ). Set pw = 2lL,1 . Suppose (

γw,k ≤ min

1 1 , 8pw β 8(pw + lL,1 )

)

,

γλ,k ≤ min



  

1

2   2(2lΨ,1 + p + lg,1 λ pw +l

L,1

and

 2  lL,1 1 , γ , w,k 2 2, 16l 1536p βγ w  g,1 2 )

√ β≤

5−1 . 48γ1

Then, we have Vk − Vk+1 ≥

2 2 2 1 pw β 1 wk − w+ (ŵk , λk ) + λ+ (ŵk ) − λk + wk − ŵk 32γw,k 32γλ,k 8

− 48pw β w⋆ (ŵk ) − w⋆ (ŵk , λ+ (ŵk ))

36

2

− Cτ,k τ 2 ,

where 

Cτ,k :=

2 l2 C 4 pw βγw,k γw,k g,2 λ 2 2 + (pw + lL,1 )γw,k lg,2 Cλ4 + . 4 4



Proof. Combining Lemma 18, Lemma 21 and Lemma 22, and using Lemma 16, we have Vk − Vk+1 = K(wk+1 , ŵk , λk+1 ) − K(wk+1 , ŵk+1 , λk+1 ) + 2 Ψ(ŵk+1 , λk+1 ) − Ψ(ŵk , λk+1 ) − 2 P (ŵk+1 ) − P (ŵk )





+ K(wk , ŵk , λk ) − K(wk+1 , ŵk , λk+1 ) + 2 Ψ(ŵk , λk+1 ) − Ψ(ŵk , λk ) 

≥

pw pw − 2pw γ1 − − 48pw βγ12 2β 6β



− 24pw β w⋆ (ŵk ) − w⋆ (ŵk , λk )

2

By

1 − 24pw βγ22 4γλ,k

!

λk+1 − λk

ŵ +

2 γw,k ∇w K(wk , ŵk , λk ) − CV,k τ 2 . 8

− ŵ

k

2

k+1

+

√ β≤

we have

5−1 , 48γ1

pw pw pw − 2pw γ1 − − 48pw βγ12 ≥ . 2β 6β 4β

Moreover, by γλ,k ≤ we have

1 , 192pw βγ22

1 1 − 24pw βγ22 ≥ . 4γλ,k 8γλ,k

Therefore, Vk − Vk+1 ≥

2 2 2 γw,k pw 1 λk+1 − λk ∇w K(wk , ŵk , λk ) + ŵk+1 − ŵk + 8 4β 8γλ,k

− 24pw β w⋆ (ŵk ) − w⋆ (ŵk , λk )

2

− CV,k τ 2 .

By the update rule of ŵk , ŵk+1 − ŵk = β(wk+1 − ŵk ). Using ∥a∥2 ≥ 21 ∥a − b∥2 − ∥b∥2 , we obtain 2 2 pw pw β ŵk+1 − ŵk = wk+1 − ŵk 4β 4 2 2 pw β pw β wk − ŵk − wk+1 − wk . ≥ 8 4

By Lemma 16 and γx,k = γy,k = γw,k , wk+1 − wk

2

2 ≤ 2γw,k ∇w K(wk , ŵk , λk )

37

2

2 2 + γw,k lg,2 Cλ4 τ 2 .

2

Denote Cw,k =

2 l2 C 4 pw βγw,k g,2 λ , and Cτ,k = CV,k + Cw,k . Thus, 4

2 pw βγw,k γw,k − 8 2

Vk − Vk+1 ≥

!

∇w K(wk , ŵk , λk ) 2

− 24pw β w⋆ (ŵk ) − w⋆ (ŵk , λk )

+

2 2 1 pw β wk − ŵk λk+1 − λk + 8γλ,k 8

− Cτ,k τ 2 .

Since γw,k ≤ we have

2

1 , 8pw β

2 pw βγw,k γw,k γw,k − ≥ . 8 2 16

Therefore, Vk − Vk+1 ≥

2 2 2 γw,k 1 pw β ∇w K(wk , ŵk , λk ) + λk+1 − λk + wk − ŵk 16 8γλ,k 8

− 24pw β w⋆ (ŵk ) − w⋆ (ŵk , λk )

2

− Cτ,k τ 2 .

Next, we convert the actual projected dual step (λk+1 − λk ) into the ghost projected dual step (λ+ (ŵk ) − λk ). By non-expansiveness of PΛ , λk+1 − λ+ (ŵk ) 



= PΛ λk + γλ,k ∇y g(wk ) − pλ λk







− PΛ λk + γλ,k ∇y g(w⋆ (ŵk , λk )) − pλ λk



≤ γλ,k ∇y g(wk ) − ∇y g(w⋆ (ŵk , λk )) ≤ γλ,k lg,1 wk − w⋆ (ŵk , λk ) ≤

γλ,k lg,1 ∇w K(wk , ŵk , λk ) . pw − lL,1

Hence, using ∥a − b∥2 ≥ 12 ∥a∥2 − ∥b∥2 , λk+1 − λk

2

2 2 1 + k λ (ŵ ) − λk − λk+1 − λ+ (ŵk ) 2 2 l2 γλ,k 2 2 1 + k g,1 ≥ λ (ŵ ) − λk − ∇w K(wk , ŵk , λk ) . 2 2 (pw − lL,1 )

≥

Therefore, Vk − Vk+1 ≥

2 γλ,k lg,1 γw,k − 16 8(pw − lL,1 )2

!

∇w K(wk , ŵk , λk )

− 24pw β w⋆ (ŵk ) − w⋆ (ŵk , λk ) Since pw = 2lL,1 ,

γλ,k ≤

2

2

+

2 2 1 pw β λ+ (ŵk ) − λk + wk − ŵk 16γλ,k 8

− Cτ,k τ 2 .

2 2 lL,1 lL,1 (pw − lL,1 )2 γ ≤ γw,k = γw,k , w,k 2 2 2 16lg,1 4lg,1 4lg,1

38

we have

2 γλ,k lg,1 γw,k γw,k − ≥ . 2 16 8(pw − lL,1 ) 32

Thus, Vk − Vk+1 ≥

2 2 2 γw,k 1 pw β ∇w K(wk , ŵk , λk ) + wk − ŵk λ+ (ŵk ) − λk + 32 16γλ,k 8

− 24pw β w⋆ (ŵk ) − w⋆ (ŵk , λk )

2

− Cτ,k τ 2 .

Finally, by Lemma 15, w⋆ (ŵk ) − w⋆ (ŵk , λk )

2

≤ 2 w⋆ (ŵk ) − w⋆ (ŵk , λ+ (ŵk )) ≤ 2 w⋆ (ŵk ) − w⋆ (ŵk , λ+ (ŵk ))

2 2

+ 2 w⋆ (ŵk , λ+ (ŵk )) − w⋆ (ŵk , λk ) + 2γ22 λ+ (ŵk ) − λk

2

2

.

Hence, !

2 2 γw,k 1 Vk − Vk+1 ≥ ∇w K(wk , ŵk , λk ) + − 48pw βγ22 λ+ (ŵk ) − λk 32 16γλ,k 2 2 pw β + wk − ŵk − 48pw β w⋆ (ŵk ) − w⋆ (ŵk , λ+ (ŵk )) − Cτ,k τ 2 . 8

By γλ,k ≤ we have

1 , 1536pw βγ22

1 1 − 48pw βγ22 ≥ . 16γλ,k 32γλ,k

Moreover, by the definition w+ (ŵk , λk ) = wk − γw,k ∇w K(wk , ŵk , λk ), we have

2 2 γw,k 1 ∇w K(wk , ŵk , λk ) = wk − w+ (ŵk , λk ) . 32 32γw,k

Therefore, Vk − Vk+1 ≥

2 2 2 1 1 pw β wk − w+ (ŵk , λk ) + λ+ (ŵk ) − λk + wk − ŵk 32γw,k 32γλ,k 8

− 48pw β w⋆ (ŵk ) − w⋆ (ŵk , λ+ (ŵk )) This completes the proof.

39

2

− Cτ,k τ 2 .

B.5

Oracle Complexity under Deterministic Setting

Lemma 24. Under Assumption 1, suppose that Λ = {λ : ∥λ∥ ≤ Cλ }, and let pw > lL,1 and γλ,k > 0. Define 



λ+ (ŵk ) = PΛ λk + γλ,k ∇λ Ψ(ŵk , λk ) . Then w⋆ (ŵk ) − w⋆ (ŵk , λ+ (ŵk )) ≤ γ3 λ+ (ŵk ) − λk , where γ3 := r

−1 lΨ,1 + γλ,k (pw −l )2 µ2g 2(pw − lL,1 )pλ + (pw +lL,1 2 L,1 )

.

Proof. By Danskin’s theorem, ∇λ Ψ(ŵk , λ) = ∇y g(w⋆ (ŵk , λ)) − pλ λ. We first show that −∇λ Ψ(ŵk , λ) is



(pw −l )µ2g pλ + (pw +lL,1 2 L,1 )



-strongly monotone on Λ. Since K(·, ŵk , λ)

is (pw − lL,1 )-strongly convex and (pw + lL,1 )-smooth with respect to w, we have K(w∗ (ŵk , λ2 ), ŵk , λ1 ) − K(w∗ (ŵk , λ1 ), ŵk , λ1 ) ≥

pw − lL,1 ∗ k ∥w (ŵ , λ1 ) − w∗ (ŵk , λ2 )∥2 , 2

K(w∗ (ŵk , λ1 ), ŵk , λ2 ) − K(w∗ (ŵk , λ2 ), ŵk , λ2 ) ≥

pw − lL,1 ∗ k ∥w (ŵ , λ1 ) − w∗ (ŵk , λ2 )∥2 . 2

and

Adding the two inequalities, and for any fixed w, we have K(w, ŵk , λ1 ) − K(w, ŵk , λ2 ) = (λ1 − λ2 )⊤ ∇y g(w) −

 pλ  ∥λ1 ∥2 − ∥λ2 ∥2 . 2

Then, we obtain D

E

− ∇y g(w∗ (ŵk , λ1 )) − ∇y g(w∗ (ŵk , λ2 )), λ1 − λ2 ≥ (pw − lL,1 )∥w∗ (ŵk , λ1 ) − w∗ (ŵk , λ2 )∥2 . Hence, D

−∇λ Ψ(ŵk , λ1 ) − (−∇λ Ψ(ŵk , λ2 )), λ1 − λ2

E

D

= pλ ∥λ1 − λ2 ∥2 − ∇y g(w∗ (ŵk , λ1 )) − ∇y g(w∗ (ŵk , λ2 )), λ1 − λ2 ≥ pλ ∥λ1 − λ2 ∥2 + (pw − lL,1 )∥w∗ (ŵk , λ1 ) − w∗ (ŵk , λ2 )∥2 . By the first-order optimality of w∗ (ŵk , λ1 ) and w∗ (ŵk , λ2 ), ∇w K(w∗ (ŵk , λ1 ), ŵk , λ1 ) = 0,

∇w K(w∗ (ŵk , λ2 ), ŵk , λ2 ) = 0.

40

E

Moreover, ∇w K(w, ŵk , λ1 ) − ∇w K(w, ŵk , λ2 ) = J(w)⊤ (λ1 − λ2 ), where J(w) := ∇w (∇y g(w)). Thus, ∇w K(w∗ (ŵk , λ2 ), ŵk , λ1 ) = J(w∗ (ŵk , λ2 ))⊤ (λ1 − λ2 ). Since K(·, ŵk , λ1 ) is (pw + lL,1 )-smooth and ∇w K(w∗ (ŵk , λ1 ), ŵk , λ1 ) = 0, we have ∥J(w∗ (ŵk , λ2 ))⊤ (λ1 − λ2 )∥ = ∥∇w K(w∗ (ŵk , λ2 ), ŵk , λ1 ) − ∇w K(w∗ (ŵk , λ1 ), ŵk , λ1 )∥ ≤ (pw + lL,1 )∥w∗ (ŵk , λ1 ) − w∗ (ŵk , λ2 )∥. On the other hand, by the strong convexity of g(x, ·), J(w)J(w)⊤ ⪰ µ2g I. Indeed, for any v ∈ Rdy , ∥J(w)⊤ v∥2 = ∥∇2xy g(w)v∥2 + ∥∇2yy g(w)v∥2 ≥ µ2g ∥v∥2 . Therefore, ∥J(w∗ (ŵk , λ2 ))⊤ (λ1 − λ2 )∥ ≥ µg ∥λ1 − λ2 ∥. Combining the last two displays gives ∥w∗ (ŵk , λ1 ) − w∗ (ŵk , λ2 )∥ ≥

µg ∥λ1 − λ2 ∥. pw + lL,1

Consequently, D

E

−∇λ Ψ(ŵk , λ1 ) − (−∇λ Ψ(ŵk , λ2 )), λ1 − λ2 ≥ 

Thus, −∇λ Ψ(ŵ, λ) is

(pw −l )µ2g pλ + (pw +lL,1 2 L,1 )

(pw − lL,1 )µ2g pλ + (pw + lL,1 )2

!

∥λ1 − λ2 ∥2 .



-strongly monotone on Λ.

Next, let λ̂⋆ (ŵk ) = arg max Ψ(ŵk , λ). λ∈Λ

Equivalently, 0 ∈ −∇λ Ψ(ŵk , λ̂⋆ (ŵk )) + NΛ (λ̂⋆ (ŵk )). 

Since −∇λ Ψ(ŵ, λ) is

(pw −l

)µ2



g pλ + (pw +lL,1 -strongly monotone, the error bound for strongly monotone 2 L,1 )

41

variational inequalities of −∇λ Ψ(ŵ, λ) gives, for any λ ∈ Λ, 1

∥λ − λ̂⋆ (ŵk )∥ ≤ pλ +



(pw −lL,1 )µ2g (pw +lL,1 )2



dist 0, −∇λ Ψ(ŵk , λ) + NΛ (λ) .

We apply this variational inequality at λ = λ+ (ŵk ). By the projection optimality condition for 



λ+ (ŵk ) = PΛ λk + γλ,k ∇λ Ψ(ŵk , λk ) , we have

1 (λk − λ+ (ŵk )) + ∇λ Ψ(ŵk , λk ) ∈ NΛ (λ+ (ŵk )). γλ,k

Therefore, −∇λ Ψ(ŵk , λ+ (ŵk )) +

1 γλ,k

(λk − λ+ (ŵk )) + ∇λ Ψ(ŵk , λk ) ∈ −∇λ Ψ(ŵk , λ+ (ŵk )) + NΛ (λ+ (ŵk )).

Hence, 



dist 0, −∇λ Ψ(ŵk , λ+ (ŵk )) + NΛ (λ+ (ŵk ))

≤ −∇λ Ψ(ŵk , λ+ (ŵk )) − (−∇λ Ψ(ŵk , λk )) + 

1 γλ,k

(λk − λ+ (ŵk ))



−1 ≤ lΨ,1 + γλ,k ∥λ+ (ŵk ) − λk ∥.

We now use the joint primal–dual coercivity retained in the preceding calculation. The optimality conditions give λk − λ+ (ŵk ) + ∇λ Ψ(ŵk , λk ) ∈ NΛ (λ+ (ŵk )). γλ,k

∇λ Ψ(ŵk , λ̂⋆ (ŵk )) ∈ NΛ (λ̂⋆ (ŵk )),

By monotonicity of NΛ and the joint monotonicity inequality proved above, pλ λ+ (ŵk ) − λ̂⋆ (ŵk ) *

≤

2

+ (pw − lL,1 ) w⋆ (ŵk , λ+ (ŵk )) − w⋆ (ŵk , λ̂⋆ (ŵk ))

2

λk − λ+ (ŵk ) −∇λ Ψ(ŵ , λ (ŵ )) + + ∇λ Ψ(ŵk , λk ), λ+ (ŵk ) − λ̂⋆ (ŵk ) γλ,k



k

+



λ+ (ŵk ) − λk

−1 ≤ lΨ,1 + γλ,k

+

k

λ+ (ŵk ) − λ̂⋆ (ŵk ) .

Furthermore, the lower response bound proved above implies w⋆ (ŵk , λ+ (ŵk )) − w⋆ (ŵk , λ̂⋆ (ŵk )) ≥

µg λ+ (ŵk ) − λ̂⋆ (ŵk ) . pw + lL,1

Then, we have 

+

k

⋆

k

pλ λ (ŵ ) − λ̂ (ŵ ) ≥

2

⋆

k

+

k

⋆

k

⋆

k

+ (pw − lL,1 ) w (ŵ , λ (ŵ )) − w (ŵ , λ̂ (ŵ ))

(pw − lL,1 )2 µ2g 2(pw − lL,1 )pλ + (pw + lL,1 )2

!

λ+ (ŵk ) − λ̂⋆ (ŵk )

42

2

 2 2

w⋆ (ŵk , λ+ (ŵk )) − w⋆ (ŵk , λ̂⋆ (ŵk ))

2

.

Combining two inequalities and dividing by ∥λ+ (ŵk ) − λ̂⋆ (ŵk )∥ when it is nonzero gives ⋆

k

⋆

k

−1 lΨ,1 + γλ,k

w (ŵ ) − w (ŵ , λ (ŵ )) ≤ r λ+ (ŵk ) − λk . (pw −lL,1 )2 µ2g 2(pw − lL,1 )pλ + (pw +lL,1 )2 +

k

This proves the claim. Proof of Proposition 6.

By Proposition 23, we know that

1 1 pw β k ∥wk − w+ (ŵk , λk )∥2 + ∥λ+ (ŵk ) − λk ∥2 + ∥w − ŵk ∥2 32γw,k 32γλ,k 8

Vk − Vk+1 ≥

− 48pw β∥w∗ (ŵk ) − w∗ (ŵk , λ+ (ŵk ))∥2 − Cτ,k τ 2 . By Lemma 24, and choosing β ≤ 3072p 1γ

2 w λ,k γ3

, we have

48pw β∥w∗ (ŵk ) − w∗ (ŵk , λ+ (ŵk ))∥2 ≤ 48pw βγ32 ∥λ+ (ŵk ) − λk ∥2 ≤

1 ∥λ+ (ŵk ) − λk ∥2 , 64γλ,k

which implies the conclusion. Proof of Lemma 7.

By the definition of w+ (ŵk , λk ), w+ (ŵk , λk ) = wk − γw,k ∇w K(wk , ŵk , λk ).

Hence −1 −1 ∥∇w K(wk , ŵk , λk )∥ ≤ γw,k ∥wk − w+ (ŵk , λk )∥ ≤ γw,k ϵL .

Since ∇w K(wk , ŵk , λk ) = ∇w L(wk , λk ) + pw (wk − ŵk ), we have 



−1 ∥∇w L(wk , λk )∥ ≤ ∥∇w K(wk , ŵk , λk )∥ + pw ∥wk − ŵk ∥ ≤ γw,k + κ̄y pw ϵL .

Next, we prove that the projected dual step is inactive. From the bound on ∇y L(xk , y k , λk ), we have   −1 ∇y f (xk , y k ) + ∇2yy g(xk , y k )λk ≤ γw,k + κ̄y pw ϵL . Using ∇2yy g(xk , y k ) ⪰ µg I and ∥∇y f (xk , y k )∥ ≤ lf,0 , we obtain 



−1 µg ∥λk ∥ ≤ ∥∇2yy g(xk , y k )λk ∥ ≤ lf,0 + γw,k + κ̄y pw ϵL .

By the choice of ϵL , lf,0 lf,0 1 ∥λ ∥ ≤ + Cλ − µg 4 µg

!

k

43

lf,0 3 = Cλ − Cλ − 4 µg

!

.



l

Thus λk lies in the interior of Λ with distance at least 43 Cλ − µf,0 g



from the boundary. Since

lf,0 1 ∥λ (ŵ )∥ − ∥λ ∥ ≤ ∥λ (ŵ ) − λ ∥ ≤ κ̄y ϵL ≤ Cλ − 4 µg k

+

k

k

+

we have lf,0 1 ∥λ (ŵ )∥ ≤ Cλ − Cλ − 2 µg +

!

k

k

,

!

< Cλ ,

which implies the projection in the definition of λ+ (ŵk ) is inactive. Therefore, λ+ (ŵk ) = λk + γλ,k ∇λ Ψ(ŵk , λk ). By Danskin’s theorem, ∇λ Ψ(ŵk , λk ) = ∇y g(w⋆ (ŵk , λk )) − pλ λk . Hence −1 −1 ∇y g(w⋆ (ŵk , λk )) − pλ λk = γλ,k ∥λ+ (ŵk ) − λk ∥ ≤ κ̄y γλ,k ϵL .

It remains to transfer this bound from w⋆ (ŵk , λk ) to wk . By Lemma 14 and the optimality condition ∇w K(w⋆ (ŵk , λk ), ŵk , λk ) = 0, we have

1 ∥∇w K(wk , ŵk , λk )∥ pw − lL,1 1 ≤ ϵL . (pw − lL,1 )γw,k

∥wk − w⋆ (ŵk , λk )∥ ≤

Therefore, ∥∇y g(wk ) − pλ λk ∥ ≤ ∥∇y g(wk ) − ∇y g(w⋆ (ŵk , λk ))∥ + ∥∇y g(w⋆ (ŵk , λk )) − pλ λk ∥ lg,1 −1 ≤ ϵL + κ̄y γλ,k ϵL . (pw − lL,1 )γw,k Since ∥λk ∥ ≤ Cλ , we get ∥∇λ L(xk , y k , λk )∥ = ∥∇y g(xk , y k )∥ ≤ ∥∇y g(wk ) − pλ λk ∥ + pλ ∥λk ∥ !

≤

lg,1 −1 + κ̄y γλ,k ϵL + pλ Cλ . (pw − lL,1 )γw,k

This completes the proof. Proof of Theorem 4. We first verify that the explicit parameters in the theorem satisfy the conditions of Proposition 23 and Lemma 24. Under Cλ = 2κ̄y , the basic smoothness bound is √ √
√ 2 lf,1 + 2κ̄y lg,2 ≤ 2L̄(1 + 2κ̄y ) ≤ 3 2L̄κ̄y < 8L̄κ̄y =: L0 .

44

Thus, in the generic results above we choose the admissible smoothness upper bound lL,1 := L0 . In particular, the theorem’s choice pw = 16L̄κ̄y = 2L0 has the required form. o n ϵL ϵ 1 satisfies . The choice p = min µ , Define ϵL = 211 (1+ g κ̄y λ 8 L̄)κ̄3 y

pλ ≤

µg L̄ , = 8 8κ̄y

pλ Cλ ≤

ϵL . 4

Moreover, the auxiliary constants used in the appendix satisfy γ1 =

pw = 2, pw − L0

γ2 =

lg,1 lg,1 1 = ≤ . pw − L 0 L0 8κ̄y

Also, lΨ,1 = pλ + lg,1 γ2 = pλ +

2 lg,1 L̄ L̄ L̄ ≤ + = . L0 8κ̄y 8κ̄y 4κ̄y

For the constant γ3 in Lemma 24, its denominator satisfies s

2(pw − L0 )pλ +

(pw − L0 )2 µ2g (pw − L0 )µg L̄ µg = . ≥ = (pw + L0 )2 pw + L 0 3 3κ̄y

8

Since γλ−1 = 2κ̄yL̄ , we obtain L̄ 28 L̄ 4κ̄y + κ̄y

lΨ,1 + γλ−1

γ3 = r ≤ = L̄/(3κ̄y ) (pw −L0 )2 µ2g 2(pw − L0 )pλ + (pw +L0 )2

3075 . 4

We next verify the stepsize conditions in Proposition 23. The primal stepsize satisfies γw =

1 28 L̄κ̄y

≤

1 1 = . 8(pw + L0 ) 192L̄κ̄y

Since β ≤ 1, it also satisfies γw ≤ 8p1w β . For the first multiplier-stepsize condition, 2 lg,1 2 2lΨ,1 + pλ + pw + L 0

!

L̄ L̄ L̄ ≤2 + + 2κ̄y 8κ̄y 24κ̄y

!

Hence, γλ ≤

3κ̄y 1 . ≤  2 /(p + L ) 4L̄ 2 2lΨ,1 + pλ + lg,1 w 0

For the second condition, L20 κ̄y κ̄y γw ≥ ≥ 8 = γλ . 2 16lg,1 64L̄ 2 L̄

45

=

4L̄ . 3κ̄y

For the third condition, as β ≤ 2/3, 1 κ̄y κ̄y ≥ ≥ 8 = γλ . 2 1536pw βγ2 384L̄β 2 L̄ The parameter β satisfies 1 β = 30 2 ≤ 2 κ̄y

√

√ 5−1 5−1 . = 96 48γ1

Furthermore, 3072pw γλ γ32 ≤ 3072



16L̄κ̄y

  κ̄   3075 2 y

28 L̄

4

= 12(3075)2 κ̄2y < 230 κ̄2y = β −1 .

Thus, β ≤ 3072p1 γ γ 2 . Therefore, all the conditions of Proposition 23, Lemma 24 and Proposition 6 w λ 3 are satisfied. Because the stepsizes are constant, Cτ,k ≡ Cτ in Proposition 23 is a constant. Proposition 23 and Lemma 24 give Vk − Vk+1 ≥

2 2 2 pw β 1 1 λ+ (ŵk ) − λk + wk − ŵk − Cτ τ 2 . (19) wk − w+ (ŵk , λk ) + 32γw 64γλ 8

Define

(

a := min

κ̄2y κ̄2y pw β 1 , , 32γw 64γλ 8

)

.

Under the explicit parameter choices, 1 = 8L̄κ̄y , 32γw

κ̄2y = 4L̄κ̄y , 64γλ

κ̄2y pw β L̄κ̄y = 29 . 8 2

Since κ̄y ≥ 1, it follows that a=

L̄κ̄y . 229

Then (19) implies n

o

+ k k 2 −2 k k 2 Vk − Vk+1 ≥ a max ∥wk − w+ (ŵk , λk )∥2 , κ̄−2 − Cτ τ 2 . y ∥λ (ŵ ) − λ ∥ , κ̄y ∥w − ŵ ∥

We next bound Cτ . Using lg,2 ≤ L̄, Cλ = 2κ̄y , and β ≤ 1, we obtain Cτ ≤

1 3 1 + 13 + 14 10 2 L̄κ̄y 2 L̄κ̄y 2 L̄κ̄y

!

L̄2 (2κ̄y )4 =

23 L̄κ̄3 . 210 y

Summing the descent inequality from k = 0 to K − 1 and using VK ≥ f gives a

K−1 X

n

o

+ k k 2 −2 k k 2 max ∥wk − w+ (ŵk , λk )∥2 , κ̄−2 ≤ V0 − f + KCτ τ 2 . y ∥λ (ŵ ) − λ ∥ , κ̄y ∥w − ŵ ∥

k=0

46

Consequently, there exists an index k⋆ ∈ {0, . . . , K − 1} such that n

o

+ k⋆ k⋆ 2 −2 k⋆ k⋆ 2 max ∥wk⋆ − w+ (ŵk⋆ , λk⋆ )∥2 , κ̄−2 ≤ y ∥λ (ŵ ) − λ ∥ , κ̄y ∥w − ŵ ∥

V0 − f Cτ 2 + τ . aK a

Denote ∆V := V0 − f . With K≥

230 ∆V , L̄κ̄y ϵ2L

ϵL 1 2 V we have ∆ aK ≤ 2 ϵL . Moreover, because τ = 213 κ̄y , we have

Cτ 2 (23/210 )L̄κ̄3y ϵ2L 23 2 τ ≤ = ϵ . 26 2 29 a 2 κ̄y 128 L L̄κ̄y /2 Therefore, 

k⋆ 2 k⋆ k⋆ 2 −2 + k⋆ max ∥wk⋆ − w+ (ŵk⋆ , λk⋆ )∥2 , κ̄−2 y ∥λ (ŵ ) − λ ∥ , κ̄y ∥w − ŵ ∥



1 23 + ϵ2 2 128 L 87 2 = ϵ 128 L < ϵ2L . 



≤

It follows that ∥wk⋆ − w+ (ŵk⋆ , λk⋆ )∥ ≤ ϵL ,

∥wk⋆ − ŵk⋆ ∥ ≤ κ̄y ϵL .

∥λ+ (ŵk⋆ ) − λk⋆ ∥ ≤ κ̄y ϵL ,

We now verify the interiority conditions in Lemma 7. Since lf,0 ≤ L̄, Cλ −

lf,0 lf,0 = 2κ̄y − ≥ κ̄y . µg µg

Furthermore, −1 γw + κ̄y pw = 28 L̄κ̄y + 16L̄κ̄2y ≤ 272L̄κ̄2y . ϵ Using ϵL = 211 (1+ and 0 < ϵ ≤ 1, we obtain L̄)κ̄3 y



−1 γw + κ̄y pw



lf,0 Cλ − µg

17 L̄ ϵ L̄ µg κ̄y µg < = ≤ ϵL ≤ 128 1 + L̄ κ̄y 4 4 4

Similarly, lf,0 ϵ 1 κ̄y ϵL = 11 < Cλ − 2 4 µg 2 (1 + L̄)κ̄y

!

.

Hence, Lemma 7 applies at k⋆ . For the primal component, it gives 



−1 ∥∇w L(wk⋆ , λk⋆ )∥ ≤ γw + κ̄y pw ϵL ≤ 272L̄κ̄2y ϵL .

47

!

.

For the multiplier component, lg,1 + κ̄y γλ−1 = 32lg,1 + 28 L̄ ≤ 288L̄. (pw − L0 )γw Since pλ Cλ ≤ ϵL /4, Lemma 7 yields 1 ∥∇λ L(w , λ )∥ ≤ 288L̄ + ϵL . 4 k⋆



k⋆



It remains to translate these bounds to stationarity of the bilevel hyper-objective. The constant in Theorem 2 satisfies LF̄ ,y = lf,1 (1 + κy ) + lf,0 lg,2 Consequently,

1 lg,1 + 2 µg µg

!

≤ L̄(1 + κ̄y )2 ≤ 4L̄κ̄2y .

LF̄ ,y 3 µg ≤ 4κ̄y . Using Theorem 2, we obtain

∥∇F (xk⋆ )∥ ≤ ∥∇x L(wk⋆ , λk⋆ )∥ + κy ∥∇y L(wk⋆ , λk⋆ )∥ +

LF̄ ,y ∥∇λ L(wk⋆ , λk⋆ )∥ µg

1 ϵL 288L̄ + 4 ≤ (1696L̄ + 1)κ̄3y ϵL ≤ 211 (1 + L̄)κ̄3y ϵL = ϵ. ≤ (1 + κ̄y )272L̄κ̄2y ϵL + 4κ̄3y





ϵ Thus, xk⋆ is an ϵ-stationary point of F . Finally, substituting ϵL = 211 (1+ into the iteration L̄)κ̄3 y

bound gives K ≤1+

252 (1 + L̄)2 ∆V 5 −2 κ̄y ϵ . L̄

This completes the proof.

C

Stochastic NC-SC Bilevel Optimization

C.1

Filtration

For the stochastic analysis, define the pre-sampling filtration 



Fk− := σ w0 , ŵ0 , λ0 , {Bft , Bgt }k−1 t=0 . Thus, wk , ŵk , λk and the stepsizes are Fk− -measurable. The fresh mini-batches Bfk and Bgk are independent of Fk− . After sampling and performing the k-th update, define Fk+ := σ(Fk− , Bfk , Bgk ),

− Fk+1 = Fk+ .

Then, wk+1 , ŵk+1 , λk+1 are Fk+ -measurable. Moreover, h

i

E ∇f (xk , y k ; Bfk ) | Fk− = ∇f (xk , y k ),

48

h

i

E ∇g(xk , y k ; Bgk ) | Fk− = ∇g(xk , y k ).

C.2

Properties of Stochastic Finite Difference Approximation

Lemma 25. Define the stochastic finite-difference approximation of ∇2xy g(x, y)λ and ∇2yy g(x, y)λ as B X ∇x g(x, y + τ λ; ζi ) − ∇x g(x, y − τ λ; ζi ) ˜ 2xy gλ (x, y; Bg ) := 1 ∇ , B i=1 2τ and

B X

∇y g(x, y + τ λ; ζi ) − ∇y g(x, y − τ λ; ζi ) ˜ 2yy gλ (x, y; Bg ) := 1 ∇ , B i=1 2τ where Bf = {ξ1 , . . . , ξB }, Bg = {ζ1 , . . . , ζB } are mini-batches with the same cardinality B. Under Assumptions 1 and 2, with λ ∈ Λ = {λ : ∥λ∥ ≤ Cλ }, we have 

E

˜ 2 gλ (x, y; Bg ) ∇2xy g(x, y)λ − ∇ xy

2



˜ 2 gλ (x, y; Bg ) ∇2yy g(x, y)λ − ∇ yy

2



≤

2 C4 lg,2 σg2 λ 2 τ + , 4 Bτ 2

(20)

≤

2 C4 lg,2 σg2 λ 2 τ + . 4 Bτ 2

(21)

and 

E

˜ 2 gλ (x, y; Bg ) and the unbiasedness of the stochastic Proof. We first prove (20). By the definition of ∇ xy gradient oracle, 

E

˜ 2xy gλ (x, y; Bg ) ∇2xy g(x, y)λ − ∇

2



i 2

h

˜ 2xy gλ (x, y; Bg ) = ∇2xy g(x, y)λ − E ∇ 

+E

h

˜ 2 gλ (x, y; Bg ) − E ∇ ˜ 2 gλ (x, y; Bg ) ∇ xy xy

i 2

For the bias term, we have ∇x g(x, y + τ λ) − ∇x g(x, y − τ λ) 1 = 2τ 2τ

Z τ −τ

∇2xy g(x, y + sλ)λ ds.

Therefore, h

˜ 2xy gλ (x, y; Bg ) ∇2xy g(x, y)λ − E ∇

 1 τ  2 ∇xy g(x, y) − ∇2xy g(x, y + sλ) λ ds 2τ −τ Z 1 τ lg,2 |s|∥λ∥2 ds ≤ 2τ −τ lg,2 = τ ∥λ∥2 2 lg,2 Cλ2 ≤ τ. 2 Z

i

=

Thus, h

˜ 2 gλ (x, y; Bg ) ∇2xy g(x, y)λ − E ∇ xy

49

i 2

≤

2 C4 lg,2 λ 2 τ . 4

.

For the variance term, by the independence of samples in Bg , 

E

i 2

h

˜ 2 gλ (x, y; Bg ) − E ∇ ˜ 2 gλ (x, y; Bg ) ∇ xy xy

1 (∇x g(x, y + τ λ; ζ) − ∇x g(x, y + τ λ)) − (∇x g(x, y − τ λ; ζ) − ∇x g(x, y − τ λ)) 2 = E B 2τ i i h  h 1 1 ≤ · 2 · 2E ∥∇x g(x, y + τ λ; ζ) − ∇x g(x, y + τ λ)∥2 + 2E ∥∇x g(x, y − τ λ; ζ) − ∇x g(x, y − τ λ)∥2 B 4τ σg2 ≤ . Bτ 2 #

"

Combining the bias and variance bounds gives 

E

˜ 2xy gλ (x, y; Bg ) ∇2xy g(x, y)λ − ∇

2



≤

2 C4 lg,2 σg2 λ 2 τ + . 4 Bτ 2

The proof of (21) is similar. Indeed, by unbiasedness, h

i

˜ 2yy gλ (x, y; Bg ) = E ∇

∇y g(x, y + τ λ) − ∇y g(x, y − τ λ) . 2τ

Using the same integral argument and the Hessian Lipschitz continuity of g, i 2

h

˜ 2yy gλ (x, y; Bg ) ∇2yy g(x, y)λ − E ∇

≤

2 C4 lg,2 λ 2 τ . 4

Moreover, by the independence of samples in Bg and the variance bound in Assumption 2, 

E

h

˜ 2yy gλ (x, y; Bg ) − E ∇ ˜ 2yy gλ (x, y; Bg ) ∇

i 2

σg2 ≤ . Bτ 2

Therefore, 

E

˜ 2yy gλ (x, y; Bg ) ∇2yy g(x, y)λ − ∇

2



≤

2 C4 lg,2 σg2 λ 2 τ + . 4 Bτ 2

This completes the proof. Lemma 26. Under Assumptions 1 and 2, with the update rule of Algorithm 2, we have k+1

E[∥x

k 2

2 − x ∥ ] ≤ 2γx,k E

2 E[∥y k+1 − y k ∥2 ] ≤ 2γy,k E



k

k

k

∇x K(w , ŵ , λ )



∇y K(wk , ŵk , λk )

2 E[∥λk+1 − λk ∥2 ] ≤ γλ,k E



2



2



2 σ2 2γx,k f 2 + + 2γx,k B

2 C4 lg,2 σg2 λ 2 τ + 4 Bτ 2

!

2 σ2 2γy,k f 2 + + 2γy,k B

2 C4 lg,2 σg2 λ 2 τ + 4 Bτ 2

!

∇y g(xk , y k ) − pλ λk

50

2



+

2 σ2 γλ,k g . B

,

,

In particular, since ∥λk ∥ ≤ Cλ , we also have k+1

E[∥λ

k 2

2 − λ ∥ ] ≤ 2γλ,k E



k

k

∇y g(x , y )

2



2 σ2 γλ,k g . B

2 + 2γλ,k p2λ Cλ2 +

Proof. We first prove the bound for xk+1 − xk . By the update rule of Algorithm 2, 



˜ 2xy gλk (xk , y k ; Bgk ) + pw (xk − x̂k ) . xk+1 − xk = −γx,k ∇x f (xk , y k ; Bfk ) + ∇ Hence, h

E ∥x

k+1

k 2

−x ∥

| Fk−

i

2 = γx,k E



2 ≤ 2γx,k E

˜ 2 gλk (xk , y k ; B k ) + pw (xk − x̂k ) ∇x f (x , y ; Bfk ) + ∇ xy g k



2 + 2γx,k E

k

k

∇x f (x , y ; Bfk ) + ∇2xy g(xk , y k )λk + pw (xk − x̂k ) 

k

˜ 2 gλk (xk , y k ; B k ) − ∇2 g(xk , y k )λk ∇ xy g xy

2

2

2

| Fk−

| Fk−





| Fk− .

For the first term, by the variance bound of the stochastic gradient of f , 

E

∇x f (xk , y k ; Bfk ) + ∇2xy g(xk , y k )λk + pw (xk − x̂k )

≤ ∇x f (xk , y k ) + ∇2xy g(xk , y k )λk + pw (xk − x̂k ) = ∇x K(wk , ŵk , λk )

2

+

2

+

2

| Fk−



σf2 B

σf2 . B

For the second term, by Lemma 25, 

E

˜ 2xy gλk (xk , y k ; Bgk ) − ∇2xy g(xk , y k )λk ∇

2



| Fk− ≤

2 C4 lg,2 σg2 λ 2 τ + . 4 Bτ 2

Combining the above inequalities gives h

E

∥xk+1 − xk ∥2 | Fk−

i

2 ≤ 2γx,k ∇x K(wk , ŵk , λk )

2

2 σ2 2γx,k f 2 + + 2γx,k B

2 C4 lg,2 σg2 λ 2 τ + 4 Bτ 2

!

.

Taking total expectation over both sides yields k+1

E[∥x

k 2

2 − x ∥ ] ≤ 2γx,k E



k

k

k

k

k

k

∇x K(w , ŵ , λ )

2



2



2 σ2 2γx,k f 2 + 2γx,k + B

2 C4 lg,2 σg2 λ 2 τ + 4 Bτ 2

!

2 σ2 2γy,k f 2 + 2γy,k + B

2 C4 lg,2 σg2 λ 2 τ + 4 Bτ 2

!

.

Similarly, E[∥y

k+1

k 2

2 − y ∥ ] ≤ 2γy,k E



∇y K(w , ŵ , λ )

Finally, for λk , by the update rule, 



λk+1 = PΛ λk + γλ,k ∇y g(xk , y k ; Bgk ) − pλ λk 51



.

.



Since λk ∈ Λ, we have PΛ (λk ) = λk . By the non-expansiveness of the projection operator, k+1

E[∥λ

k 2

−λ ∥

| Fk− ] = E





k

PΛ λ + γλ,k

2 ≤ γλ,k E





k

k

∇y g(x , y ; Bgk ) − pλ λk

∇y g(xk , y k ; Bgk ) − pλ λk

2



k

− PΛ (λ )

2

| Fk−





| Fk− .

By the unbiasedness and variance bound of the stochastic gradient of g, 

E

k

2

k

∇y g(x , y ; Bgk ) − pλ λk

| Fk−



≤ ∇y g(xk , y k ) − pλ λk

2

+

σg2 . B

Therefore, taking total expectation yields 2 E[∥λk+1 − λk ∥2 ] ≤ γλ,k E



∇y g(xk , y k ) − pλ λk

2



+

2 σ2 γλ,k g . B

Furthermore, since ∥λk ∥ ≤ Cλ , ∇y g(xk , y k ) − pλ λk

2

≤ 2 ∇y g(xk , y k )

2

+ 2p2λ Cλ2 .

Thus, 2 E[∥λk+1 − λk ∥2 ] ≤ 2γλ,k E



∇y g(xk , y k )

2



2 + 2γλ,k p2λ Cλ2 +

2 σ2 γλ,k g . B

This completes the proof.

C.3

Intermediate Lemmas for Lyapunov Function under Stochastic Setting

1 . Then, we have Lemma 27. Under Assumptions 1 and 2, suppose γw,k ≤ 8(pw +l L,1 )

h

i

h

E K(wk , ŵk , λk ) − E K(wk+1 , ŵk , λk+1 ) γw,k ≥ E 4



k

k

k

∇w K(w , ŵ , λ )



2 − γw,k + 4(pw + lL,1 )γw,k

+E

hD

k

k

k

2

i

 2 C4 lg,2 σg2 λ 2 τ + 4 Bτ 2



k

∇y g(x , y ) − pλ λ , λ − λ

k+1

Ei

!

−

2 4(pw + lL,1 )γw,k σf2 B

2 h i lg,1 pλ + E ∥λk+1 − λk ∥2 . 2 2(pw + lL,1 )

!

−

Proof. Since K(w, ŵ, λ) is (pw + lL,1 )-smooth with respect to w and pλ -smooth with respect to λ, using the same descent decomposition as in Lemma 17, we have K(wk , ŵk , λk ) − K(wk+1 , ŵk , λk+1 ) D

E

D

≥ ∇w K(wk , ŵk , λk ), wk − wk+1 + ∇y g(xk , y k ) − pλ λk , λk − λk+1 + ⟨∇y g(xk+1 , y k+1 ) − ∇y g(xk , y k ), λk − λk+1 ⟩ pw + lL,1 k+1 pλ − ∥w − wk ∥2 − ∥λk+1 − λk ∥2 . 2 2

52

E

(22)

Taking conditional expectation with respect to Fk− and using the unbiasedness of ∇f (xk , y k ; Bfk ), we get hD

E

E

∇w K(wk , ŵk , λk ), wk − wk+1 | Fk−

= γx,k ∇x K(wk , ŵk , λk )

2

i

+ γy,k ∇y K(wk , ŵk , λk )

2

D

h

iE

D

h

iE

˜ 2 gλk (xk , y k ; B k ) − ∇2 g(xk , y k )λk | F − + γx,k ∇x K(wk , ŵk , λk ), E ∇ xy g xy k ˜ 2 gλk (xk , y k ; Bgk ) − ∇2yy g(xk , y k )λk | F − + γy,k ∇y K(wk , ŵk , λk ), E ∇ yy k

.

Using Young’s inequality, we have hD

E

E

i

∇w K(wk , ŵk , λk ), wk − wk+1 | Fk− ≥

2 2 γx,k γy,k ∇x K(wk , ŵk , λk ) + ∇y K(wk , ŵk , λk ) 2 2 h i 2 γx,k 2 k k k ˜ E ∇xy gλk (x , y ; Bg ) − ∇2xy g(xk , y k )λk | Fk− − 2 i 2 h γy,k ˜ 2 gλk (xk , y k ; B k ) − ∇2 g(xk , y k )λk | F − − , E ∇ yy g yy k 2

and ⟨∇y g(xk+1 , y k+1 ) − ∇y g(xk , y k ), λk − λk+1 ⟩ ≥−

2 lg,1 pw + lL,1 k+1 ∥w − wk ∥2 − ∥λk+1 − λk ∥2 . 2 2(pw + lL,1 )

(23)

By Jensen’s inequality and Lemma 25, hD

E

E

i

∇w K(wk , ŵk , λk ), wk − wk+1 | Fk− ≥

2 2 γx,k γy,k ∇x K(wk , ŵk , λk ) + ∇y K(wk , ŵk , λk ) 2 2! 2 C4 2 σ γx,k + γy,k lg,2 g λ 2 τ + − . (24) 2 4 Bτ 2

Moreover, by Lemma 26, h

i

2 E ∥wk+1 − wk ∥2 | Fk− ≤ 2γx,k ∇x K(wk , ŵk , λk )

2

2 + 2γy,k ∇y K(wk , ŵk , λk )

2 + γ 2 )σ 2 2 C4 2(γx,k lg,2 σg2 y,k f λ 2 2 2 + + 2(γx,k + γy,k ) τ + B 4 Bτ 2

Substituting (23), (24) and (25) into (22), and then taking total expectation yields h

i

h

E K(wk , ŵk , λk ) − E K(wk+1 , ŵk , λk+1 )

2 γx,k 2 − 2(pw + lL,1 )γx,k E ∇x K(wk , ŵk , λk ) 2     2 γy,k 2 − 2(pw + lL,1 )γy,k E ∇y K(wk , ŵk , λk ) + 2 ! 2 + γ2 )   l2 C 4 2(pw + lL,1 )(γx,k σg2 g,2 λ 2 y,k 2 − γw,k + 4(pw + lL,1 )γw,k τ + − σf2 4 Bτ 2 B



≥

i







53

2

!

.

(25)

+E

hD

k

k

k

k

∇y g(x , y ) − pλ λ , λ − λ

k+1

2 i h lg,1 pλ + E ∥λk+1 − λk ∥2 . 2 2(pw + lL,1 )

!

Ei

−

1 By choosing γw,k = γx,k = γy,k ≤ 8(pw +l , we have we have L,1 )

h

i

h

E K(wk , ŵk , λk ) − E K(wk+1 , ŵk , λk+1 ) ≥

γw,k E 4 −





∇w K(wk , ŵk , λk )

2 γw,k + 4(pw + lL,1 )γw,k

+E

hD

k

k

2

 2 C4 lg,2 σg2 λ 2 τ + 4 Bτ 2



k

i

k

∇y g(x , y ) − pλ λ , λ − λ

k+1

Ei

!

−

2 4(pw + lL,1 )γw,k σf2 B

2 i h lg,1 pλ + E ∥λk+1 − λk ∥2 . 2 2(pw + lL,1 )

!

−

This completes the proof. Lemma 28. Suppose the conditions in Lemma 27 hold. Set pw = 2lL,1 . Suppose further that

γλ,k ≤ min

   

1 

2 lg,1    2 2lΨ,1 + pλ + p +l w L,1

,

   

2 lL,1 2 γw,k  . 16lg,1  

Then, we have h

i

h

i

h

E K(wk , ŵk , λk ) − E K(wk+1 , ŵk , λk+1 ) + 2E Ψ(ŵk , λk+1 ) − Ψ(ŵk , λk ) ≥

γw,k E 8



∇w K(wk , ŵk , λk )

2



+

1 E 4γλ,k



λk+1 − λk

2

i



2   l2 C 4 4(pw + lL,1 )γw,k σg2 g,2 λ 2 2 2 − σf − γw,k + 4(pw + lL,1 )γw,k τ + B 4 Bτ 2

!

γλ,k σg2 − . B

Proof. Combining Lemma 27 and Lemma 19, we have h

i

h

i

h

E K(wk , ŵk , λk ) − E K(wk+1 , ŵk , λk+1 ) + 2E Ψ(ŵk , λk+1 ) − Ψ(ŵk , λk ) γw,k ≥ E 4 +E

hD



k

k

k

∇w K(w , ŵ , λ )

2



2 lg,1 pλ + E − lΨ,1 + 2 2(pw + lL,1 )

!

∇y g(xk , y k ) − pλ λk , λk+1 − λk

Ei

+ 2E

hD



λ

k+1

i

−λ

k

2





∇λ Ψ(ŵk , λk ) − ∇y g(xk , y k ) − pλ λk , λk+1 − λk

2   l2 C 4 4(pw + lL,1 )γw,k σg2 g,2 λ 2 2 σf2 − γw,k + 4(pw + lL,1 )γw,k τ + − B 4 Bτ 2

!

.

By the update rule, 





λk+1 = PΛ λk + γλ,k ∇y g(xk , y k ; Bgk ) − pλ λk



.

The optimality condition of the projection gives D

E

∇y g(xk , y k ; Bgk ) − pλ λk , λk+1 − λk ≥

54

1 γλ,k

λk+1 − λk

2

.

Ei

Therefore, E

D

D

∇y g(xk , y k ) − pλ λk , λk+1 − λk = ∇y g(xk , y k ; Bgk ) − pλ λk , λk+1 − λk

E

D

− ∇y g(xk , y k ; Bgk ) − ∇y g(xk , y k ), λk+1 − λk ≥

1 γλ,k

2

λk+1 − λk

E E

D

− ∇y g(xk , y k ; Bgk ) − ∇y g(xk , y k ), λk+1 − λk .

Define λ̄k+1 = PΛ (λk + γλ,k (∇y g(xk , y k ) − pλ λk )). Taking conditional expectation with respect to Fk− , and using the non-expansiveness of PΛ , we have hD

E

E

∇y g(xk , y k ; Bgk ) − ∇y g(xk , y k ), λk+1 − λk | Fk−

=E

hD

+E

i

E

i

E

i

∇y g(xk , y k ; Bgk ) − ∇y g(xk , y k ), λk+1 − λ̄k+1 | Fk−

hD

∇y g(xk , y k ; Bgk ) − ∇y g(xk , y k ), λ̄k+1 − λk | Fk−



≤ γλ,k E

k

k

∇y g(x , y ; Bgk ) − ∇y g(xk , y k )

2

| Fk−



+0

γλ,k σg2 . ≤ B Thus, hD

E

∇y g(xk , y k ) − pλ λk , λk+1 − λk

Ei

≥

1 γλ,k



E

2

λk+1 − λk



−

γλ,k σg2 . B

Next, by Young’s inequality, 2E

hD





∇λ Ψ(ŵk , λk ) − ∇y g(xk , y k ) − pλ λk , λk+1 − λk

1 ≥− E 2γλ,k



λ

k+1

−λ

k

2





− 2γλ,k E

k

k

Ei 

k

k

∇λ Ψ(ŵ , λ ) − ∇y g(x , y ) − pλ λ

k

 2

By Danskin’s theorem, ∇λ Ψ(ŵk , λk ) = ∇y g(w⋆ (ŵk , λk )) − pλ λk . Hence, 

∇λ Ψ(ŵk , λk ) − ∇y g(xk , y k ) − pλ λk



= ∇y g(w⋆ (ŵk , λk )) − ∇y g(wk ) ≤ lg,1 w⋆ (ŵk , λk ) − wk ≤

Since γλ,k ≤

lg,1 ∇w K(wk , ŵk , λk ) . pw − lL,1

1 

l2

g,1 2 2lΨ,1 + pλ + pw +l L,1

55

,

.

we have 1 γλ,k

− lΨ,1 −

2 lg,1 pλ 1 1 − − ≥ . 2 2(pw + lL,1 ) 2γλ,k 4γλ,k

Therefore, we get h

i

h

i

h

E K(wk , ŵk , λk ) − E K(wk+1 , ŵk , λk+1 ) + 2E Ψ(ŵk , λk+1 ) − Ψ(ŵk , λk ) 2 2γλ,k lg,1 γw,k − 4 (pw − lL,1 )2

≥

!



k

k

k

∇w K(w , ŵ , λ )

E

2



1 + E 4γλ,k



k+1

λ

−λ

2   l2 C 4 4(pw + lL,1 )γw,k σg2 g,2 λ 2 2 − σf2 − γw,k + 4(pw + lL,1 )γw,k τ + B 4 Bτ 2

k

i

2

!

−



γλ,k σg2 . B

Finally, since pw = 2lL,1 , we have 2 (pw − lL,1 )2 = lL,1 .

By 2 lL,1 (pw − lL,1 )2 γ = w,k 2 2 γw,k , 16lg,1 16lg,1

γλ,k ≤ we have

2 2γλ,k lg,1 γw,k ≤ . 2 (pw − lL,1 ) 8

Thus, h

i

h

i

h

E K(wk , ŵk , λk ) − E K(wk+1 , ŵk , λk+1 ) + 2E Ψ(ŵk , λk+1 ) − Ψ(ŵk , λk ) γw,k ≥ E 8



k

k

k

∇w K(w , ŵ , λ )

2



1 + E 4γλ,k



λ

k+1

−λ

k

2

i



2   l2 C 4 4(pw + lL,1 )γw,k σg2 g,2 λ 2 2 − σf2 − γw,k + 4(pw + lL,1 )γw,k τ + B 4 Bτ 2

!

−

γλ,k σg2 . B

This completes the proof. Proposition 29. Define the Lyapunov function Vk = K(wk , ŵk , λk ) − 2Ψ(ŵk , λk ) + 2P (ŵk ). Suppose (

γw,k ≤ min

1 1 , 8pw β 8(pw + lL,1 )

)

,

γλ,k ≤ min

and

   

2 lg,1    2 2lΨ,1 + pλ + p +l w L,1

√ β≤

1 

5−1 . 48γ1

56

,

   

2 lL,1 1 γw,k , , 2 16lg,1 1536pw βγ22   

Then, we have E[Vk ] − E[Vk+1 ]     2 2 1 1 + ≥ E wk − w+ (ŵk , λk ) E λ+ (ŵk ) − λk 32γw,k 32γλ,k     2 2 pw β ⋆ k ⋆ k + k k k + − 48pw βE w (ŵ ) − w (ŵ , λ (ŵ )) E w − ŵ 8 !   l2 C 4 σg2 g,2 λ 2 2 2 − γw,k + 4(pw + lL,1 )γw,k + pw βγw,k τ + 4 Bτ 2 −

2 σ2 2 σ2 4(pw + lL,1 )γw,k pw βγw,k 9γλ,k σg2 f f − − . B B 8B

Proof. Combining the stochastic versions of Lemma 18 and Lemma 21, and Lemma 28, we have E[Vk ] − E[Vk+1 ] = E[K(wk+1 , ŵk , λk+1 )] − E[K(wk+1 , ŵk+1 , λk+1 )] h

i

h

i

+ 2E Ψ(ŵk+1 , λk+1 ) − Ψ(ŵk , λk+1 ) − 2E P (ŵk+1 ) − P (ŵk ) h

i

+ E[K(wk , ŵk , λk )] − E[K(wk+1 , ŵk , λk+1 )] + 2E Ψ(ŵk , λk+1 ) − Ψ(ŵk , λk ) !

h i h i pw 1 pw − 24pw βγ22 E ∥λk+1 − λk ∥2 − 2pw γ1 − − 48pw βγ12 E ∥ŵk+1 − ŵk ∥2 + ≥ 2β 6β 4γλ,k     2 2 γw,k + − 24pw βE w⋆ (ŵk ) − w⋆ (ŵk , λk ) E ∇w K(wk , ŵk , λk ) 8 ! 2 σ2   l2 C 4 4(pw + lL,1 )γw,k σg2 γλ,k σg2 g,2 λ 2 f 2 − γw,k + 4(pw + lL,1 )γw,k τ + − . − 4 Bτ 2 B B 



By

√

5−1 , 48γ1

β≤ we have

pw pw pw − 2pw γ1 − − 48pw βγ12 ≥ . 2β 6β 4β

Moreover, by γλ,k ≤ we have

1 , 192pw βγ22

1 1 − 24pw βγ22 ≥ . 4γλ,k 8γλ,k

Therefore, E[Vk ] − E[Vk+1 ]   i h i 2 γw,k pw h k+1 1 E ∇w K(wk , ŵk , λk ) + E ∥ŵ − ŵk ∥2 + E ∥λk+1 − λk ∥2 ≥ 8 4β 8γλ,k 

− 24pw βE

⋆

k

⋆

k

k

w (ŵ ) − w (ŵ , λ )

2



57



−

2 γw,k + 4(pw + lL,1 )γw,k



2 C4 lg,2 σg2 λ 2 τ + 4 Bτ 2

!

−

2 σ2 4(pw + lL,1 )γw,k γλ,k σg2 f − . B B

(26)

By the update rule of ŵk , ŵk+1 − ŵk = β(wk+1 − ŵk ). Using ∥a∥2 ≥ 12 ∥a − b∥2 − ∥b∥2 , we obtain pw β k+1 pw k+1 ∥ŵ − ŵk ∥2 = ∥w − ŵk ∥2 4β 4 pw β k pw β k+1 ≥ ∥w − ŵk ∥2 − ∥w − wk ∥2 . 8 4 By Lemma 26, h

E ∥w

k+1

k 2

−w ∥

i

2 ≤ 2γw,k E

h

k

k

k

2

∥∇w K(w , ŵ , λ )∥

i

2 σ2 4γw,k f 2 + + 4γw,k B

2 C4 lg,2 σg2 λ 2 τ + 4 Bτ 2

!

.

Substituting this estimate into (26), we get E[Vk ] − E[Vk+1 ] 2 h i h i pw βγw,k γw,k 1 − E ∥∇w K(wk , ŵk , λk )∥2 + E ∥λk+1 − λk ∥2 ≥ 8 2 8γλ,k   h i 2 pw β + E ∥wk − ŵk ∥2 − 24pw βE w⋆ (ŵk ) − w⋆ (ŵk , λk ) 8 !   l2 C 4 σg2 g,2 λ 2 2 2 − γw,k + 4(pw + lL,1 )γw,k + pw βγw,k τ + 4 Bτ 2

!

2 σ2 2 σ2 pw βγw,k 4(pw + lL,1 )γw,k γλ,k σg2 f f − − . − B B B

Since γw,k ≤ we have

(27)

1 , 8pw β

2 pw βγw,k γw,k γw,k − ≥ . 8 2 16

Thus, E[Vk ] − E[Vk+1 ] i h i γw,k h 1 ≥ E ∥∇w K(wk , ŵk , λk )∥2 + E ∥λk+1 − λk ∥2 16 8γλ,k   h i 2 pw β + E ∥wk − ŵk ∥2 − 24pw βE w⋆ (ŵk ) − w⋆ (ŵk , λk ) 8 !   l2 C 4 σg2 g,2 λ 2 2 2 − γw,k + 4(pw + lL,1 )γw,k + pw βγw,k τ + 4 Bτ 2 2 σ2 2 σ2 4(pw + lL,1 )γw,k pw βγw,k γλ,k σg2 f f − − − . B B B

58

(28)

Next, we convert the actual projected dual step into the ghost projected dual step. By the non-expansiveness of PΛ , h

i

2 σ2 γλ,k g B 2 l2 i γ 2 σ2 h γλ,k g,1 λ,k g ≤ E ∥∇w K(wk , ŵk , λk )∥2 | Fk− + . (pw − lL,1 )2 B

h

i

2 E ∥λk+1 − λ+ (ŵk )∥2 | Fk− ≤ γλ,k E ∥∇y g(wk ) − ∇y g(w⋆ (ŵk , λk ))∥2 | Fk− +

Taking total expectation yields i

h

E ∥λk+1 − λ+ (ŵk )∥2 ≤

2 l2 i γ 2 σ2 h γλ,k g,1 λ,k g k k k 2 + E ∥∇ K(w , ŵ , λ )∥ . w (pw − lL,1 )2 B

Therefore, i h i h i 1 h E ∥λk+1 − λk ∥2 ≥ E ∥λ+ (ŵk ) − λk ∥2 − E ∥λk+1 − λ+ (ŵk )∥2 2 2 l2 i h i γ 2 σ2 γλ,k 1 h g,1 λ,k g k k k 2 E ∥∇ K(w , ŵ , λ )∥ − . ≥ E ∥λ+ (ŵk ) − λk ∥2 − w 2 (pw − lL,1 )2 B

Substituting the above inequality into (28), we get E[Vk ] − E[Vk+1 ] 2 h i h i γλ,k lg,1 γw,k 1 k k k 2 + k k 2 ≥ − E ∥∇ K(w , ŵ , λ )∥ + E ∥λ ( ŵ ) − λ ∥ w 16 8(pw − lL,1 )2 16γλ,k   h i 2 pw β k k 2 ⋆ k ⋆ k k + E ∥w − ŵ ∥ − 24pw βE w (ŵ ) − w (ŵ , λ ) 8 ! 2   l2 C 4 σ g,2 g λ 2 2 − γw,k + 4(pw + lL,1 )γw,k + pw βγw,k τ2 + 4 Bτ 2

!

−

2 σ2 2 σ2 4(pw + lL,1 )γw,k pw βγw,k 9γλ,k σg2 f f − − . B B 8B

Since γλ,k ≤ we have

(pw − lL,1 )2 (pw − lL,1 )2 γw,k ≤ γw,k , 2 2 16lg,1 4lg,1 2 γλ,k lg,1 γw,k γw,k − ≥ . 2 16 8(pw − lL,1 ) 32

Thus, E[Vk ] − E[Vk+1 ] i h i p β h i γw,k h 1 w ≥ E ∥∇w K(wk , ŵk , λk )∥2 + E ∥λ+ (ŵk ) − λk ∥2 + E ∥wk − ŵk ∥2 32 16γλ,k 8 

− 24pw βE

⋆

k

⋆

k

k

w (ŵ ) − w (ŵ , λ )

2



59

(29)

− −



2 2 γw,k + 4(pw + lL,1 )γw,k + pw βγw,k



2 C4 lg,2 σg2 λ 2 τ + 4 Bτ 2

!

2 σ2 2 σ2 pw βγw,k 4(pw + lL,1 )γw,k 9γλ,k σg2 f f − − . B B 8B

Moreover, 

E

⋆

k

⋆

k

k

w (ŵ ) − w (ŵ , λ )

2





≤ 2E

⋆

k

⋆

k

+

k

w (ŵ ) − w (ŵ , λ (ŵ ))

2



+ 2γ22 E



+

k

λ (ŵ ) − λ

Finally, we obtain E[Vk ] − E[Vk+1 ] !

i i h γw,k h 1 ≥ E ∥∇w K(wk , ŵk , λk )∥2 + − 48pw βγ22 E ∥λ+ (ŵk ) − λk ∥2 32 16γλ,k   h i 2 pw β ⋆ k ⋆ k + k k k 2 + E ∥w − ŵ ∥ − 48pw βE w (ŵ ) − w (ŵ , λ (ŵ )) 8 !   l2 C 4 σg2 g,2 λ 2 2 2 − γw,k + 4(pw + lL,1 )γw,k + pw βγw,k τ + 4 Bτ 2

−

2 σ2 2 σ2 pw βγw,k 4(pw + lL,1 )γw,k 9γλ,k σg2 f f − − . B B 8B

By γλ,k ≤ we have

1 , 1536pw βγ22

1 1 − 48pw βγ22 ≥ . 16γλ,k 32γλ,k

Moreover, by the definition w+ (ŵk , λk ) = wk − γw,k ∇w K(wk , ŵk , λk ), we have

2 2 γw,k 1 ∇w K(wk , ŵk , λk ) = wk − w+ (ŵk , λk ) . 32 32γw,k

Therefore, E[Vk ] − E[Vk+1 ]     2 2 1 1 ≥ E wk − w+ (ŵk , λk ) + E λ+ (ŵk ) − λk 32γw,k 32γλ,k     2 2 pw β k k ⋆ k ⋆ k + k + E w − ŵ − 48pw βE w (ŵ ) − w (ŵ , λ (ŵ )) 8 !   l2 C 4 σg2 g,2 λ 2 2 2 τ + − γw,k + 4(pw + lL,1 )γw,k + pw βγw,k 4 Bτ 2 −

2 σ2 2 σ2 4(pw + lL,1 )γw,k pw βγw,k 9γλ,k σg2 f f − − . B B 8B

60

k

2



.

This completes the proof.

C.4

Oracle Complexity under Stochastic Setting

Proposition 30. Suppose the conditions in Proposition 29 hold. Suppose further that β≤

1 , 3072pw γλ,k γ32

where γ3 := r

−1 lΨ,1 + γλ,k (pw −l )2 µ2g 2(pw − lL,1 )pλ + (pw +lL,1 2 L,1 )

.

Then, we have E[Vk ] − E[Vk+1 ]       2 2 2 pw β 1 1 k + k k + k k k k + E w − w (ŵ , λ ) + E λ (ŵ ) − λ E w − ŵ ≥ 32γw,k 64γλ,k 8 − −



2 2 γw,k + 4(pw + lL,1 )γw,k + pw βγw,k

2 C4 lg,2 σg2 λ 2 τ + 4 Bτ 2



!

2 σ2 2 σ2 4(pw + lL,1 )γw,k pw βγw,k 9γλ,k σg2 f f − − . B B 8B

Proof. By Proposition 29, we have E[Vk ] − E[Vk+1 ]     2 2 1 1 + E wk − w+ (ŵk , λk ) E λ+ (ŵk ) − λk ≥ 32γw,k 32γλ,k     2 2 pw β ⋆ k ⋆ k + k k k − 48pw βE w (ŵ ) − w (ŵ , λ (ŵ )) + E w − ŵ 8 !   l2 C 4 σg2 g,2 λ 2 2 2 − γw,k + 4(pw + lL,1 )γw,k + pw βγw,k τ + 4 Bτ 2 −

2 σ2 2 σ2 4(pw + lL,1 )γw,k pw βγw,k 9γλ,k σg2 f f − − . B B 8B

Since Lemma 24 is deterministic conditional on (ŵk , λk ), it holds pathwise. Hence, w⋆ (ŵk ) − w⋆ (ŵk , λ+ (ŵk )) ≤ γ3 λ+ (ŵk ) − λk . Squaring both sides and taking expectation gives 

E

⋆

k

⋆

k

+

k

w (ŵ ) − w (ŵ , λ (ŵ ))

2



≤ γ32 E

Therefore, by the choice β≤

1 , 3072pw γλ,k γ32

61



+

k

λ (ŵ ) − λ

k

2



.

we have 

⋆

k

⋆

k

k

+

w (ŵ ) − w (ŵ , λ (ŵ ))

48pw βE

2



≤ 48pw βγ32 E



+

k

λ (ŵ ) − λ

k

2



1 ≤ E 64γλ,k



+

k

λ (ŵ ) − λ

k

2



.

Substituting this estimate into the previous descent inequality gives E[Vk ] − E[Vk+1 ]       2 2 2 1 1 pw β k + k k + k k k k ≥ + + E w − w (ŵ , λ ) E λ (ŵ ) − λ E w − ŵ 32γw,k 64γλ,k 8 −



2 2 γw,k + 4(pw + lL,1 )γw,k + pw βγw,k



2 C4 lg,2 σg2 λ 2 τ + 4 Bτ 2

!

2 σ2 2 σ2 4(pw + lL,1 )γw,k pw βγw,k 9γλ,k σg2 f f − − − . B B 8B

l

Lemma 31. Under Assumptions 1 and 2, suppose that Λ = {λ : ∥λ∥ ≤ Cλ } with Cλ > µf,0 . Set g pw = 2lL,1 . Further choose constant stepsizes (

γw,k ≤ min

1 1 , 8pw β 8(pw + lL,1 )

)

,

γλ,k ≤ min

   

 

1

 2 lg,1    2 2lΨ,1 + pλ + p +l w

L,1

  l2 1  , L,1 . γ , w,k 2 16lg,1 1536pw βγ22   

Moreover, choose the averaging parameter (√

5−1 1 , 48γ1 3072pw γλ,k γ32

)

κ̄2y κ̄2y pw β 1 , , 32γw,k 64γλ,k 8

)

β ≤ min

.

Define (

a := min

.

Also define 2 2 Cg := γw,k + 4(pw + lL,1 )γw,k + pw βγw,k ,

and 2 2 Cf := 4(pw + lL,1 )γw,k + pw βγw,k .

Without loss of generality, take the declared Hessian–Lipschitz upper bound lg,2 > 0 (it may always be enlarged). Choose 4a 2 τ2 = 2 C 4 ϵL 5Cg lg,2 λ and the positive integer batch size (

&

B = max 1, max

(

5Cg σg2 5Cf σf2 45γλ,k σg2 , , aτ 2 ϵ2L aϵ2L 8aϵ2L

62

)')

,

and run Algorithm 2 for  

 





K = max 1,  

5 E[V0 ] − f aϵ2L

     

iterations. More generally, the same conclusion holds if τ 2 is chosen no larger than its displayed value and B and K are chosen as positive integers no smaller than their displayed values, with the right-hand side for B evaluated at the selected τ . Then there exists an index k ∈ {0, . . . , K − 1} such that n h

i

h

i

h

+ k k 2 −2 k k 2 max E ∥wk − w+ (ŵk , λk )∥2 , κ̄−2 y E ∥λ (ŵ ) − λ ∥ , κ̄y E ∥w − ŵ ∥

io

≤ ϵ2L .

Proof. By Proposition 30, we have E[Vk ] − E[Vk+1 ] ≥

i i p β h i h h 1 1 w E ∥wk − w+ (ŵk , λk )∥2 + E ∥λ+ (ŵk ) − λk ∥2 + E ∥wk − ŵk ∥2 32γw,k 64γλ,k 8

− Cg

2 C4 lg,2 σg2 λ 2 τ + 4 Bτ 2

!

Cf σf2 9γλ,k σg2 − − . B 8B

By the definition of a, (

a = min

κ̄2y κ̄2y pw β 1 , , 32γw,k 64γλ,k 8

)

,

we obtain n h

i

h

i

h

io

i

h

io

+ k k 2 −2 k k 2 E[Vk ] − E[Vk+1 ] ≥ a max E ∥wk − w+ (ŵk , λk )∥2 , κ̄−2 y E ∥λ (ŵ ) − λ ∥ , κ̄y E ∥w − ŵ ∥

− Cg

2 C4 lg,2 σg2 λ 2 τ + 4 Bτ 2

!

−

Cf σf2 9γλ,k σg2 − . B 8B

Summing from k = 0 to K − 1 gives E[V0 ] − f ≥ a

K−1 X

n h

i

h

+ k k 2 −2 k k 2 max E ∥wk − w+ (ŵk , λk )∥2 , κ̄−2 y E ∥λ (ŵ ) − λ ∥ , κ̄y E ∥w − ŵ ∥

k=0

− KCg

2 C4 lg,2 σg2 λ 2 τ + 4 Bτ 2

!

−K

Cf σf2 9γλ,k σg2 −K . B 8B

Therefore, there exists k ∈ {0, . . . , K − 1} such that n h

i

h

2 C4 lg,2 σg2 λ 2 τ + 4 Bτ 2

!

i

h

+ k k 2 −2 k k 2 max E ∥wk − w+ (ŵk , λk )∥2 , κ̄−2 y E ∥λ (ŵ ) − λ ∥ , κ̄y E ∥w − ŵ ∥

E[V0 ] − f Cg ≤ + aK a

+

Cf σf2 9γλ,k σg2 + . aB 8aB

By choosing  

K≥  

5 E[V0 ] − f aϵ2L

63

 ,  

io

we have

E[V0 ] − f 1 ≤ ϵ2L . aK 5

By the choice of τ , 4a 2 2 C 4 ϵL , 5Cg lg,2 λ

τ2 ≤ we have

2 C4 Cg lg,2 1 λ 2 τ ≤ ϵ2L . a 4 5

By the choice of B, (

B ≥ max we have

Cg σg2 1 ≤ ϵ2L , 2 aBτ 5 Combining these estimates yields n h

5Cg σg2 5Cf σf2 45γλ,k σg2 , , aτ 2 ϵ2L aϵ2L 8aϵ2L Cf σf2 1 ≤ ϵ2L , aB 5

i

)

,

9γλ,k σg2 1 ≤ ϵ2L . 8aB 5

h

i

h

+ k k 2 −2 k k 2 max E ∥wk − w+ (ŵk , λk )∥2 , κ̄−2 y E ∥λ (ŵ ) − λ ∥ , κ̄y E ∥w − ŵ ∥

io

≤ ϵ2L .

This completes the proof.

C.5

Oracle Complexity of Stoc-SGHA in High Probability

Proof of Theorem 8.

√ ϵ ρ

Define ϵL := 212 (1+L̄)κ̄3 and L0 := 8L̄κ̄y . Then y

(

pλ =

ϵL 1 min µg , 8 κ̄y

)

,

1 pλ Cλ ≤ ϵL , 4

τ=

ϵL . 213 κ̄y

The verification of the common stepsize and averaging conditions is identical to that in the proof of Theorem 4. In particular, with L0 in place of lL,1 , pw = 2L0 ,

γ1 = 2,

γ2 ≤

1 , 8κ̄y

lΨ,1 ≤

L̄ , 4κ̄y

γ3 ≤

3075 . 4

Hence, the parameters satisfy all the deterministic conditions required in Lemma 31. Define ( ) κ̄2y κ̄2y pw β L̄κ̄y 1 a := min , , = 29 , 32γw 64γλ 8 2 and 2 2 Cg := γw + 4(pw + L0 )γw + pw βγw ,

2 2 Cf := 4(pw + L0 )γw + pw βγw .

Direct calculation gives Cg =

22 + β 23 ≤ 12 , 212 L̄κ̄y 2 L̄κ̄y

Cf =

64

6+β 7 ≤ 12 . 212 L̄κ̄y 2 L̄κ̄y

Using lg,2 ≤ L̄ and Cλ = 2κ̄y , our choice of τ satisfies the condition in Lemma 31: 2 C4 Cg lg,2 23 2 1 λ 2 τ ≤ ϵ < ϵ2 . 4a 128 L 5 L 50 2

Moreover, the batch size in the theorem satisfies B ≥ 2L̄2 ϵσ̄4 . Using the bounds on a, Cg , and Cf , L we obtain 115 · 243 σg2 5Cg σg2 ≤ ≤ B, aτ 2 ϵ2L L̄2 ϵ4L as well as

5Cf σf2 aϵ2L

≤

35 · 217 σf2 L̄2 κ̄2y ϵ2L

45 · 218 σg2 45γλ σg2 ≤ ≤ B, 8aϵ2L L̄2 ϵ2L

≤ B,

where we used κ̄y ≥ 1, ϵL ≤ 1, and σ̄ 2 ≥ σf2 , σg2 . By Lemma 31, the integer K specified in the theorem satisfies &

5∆V K≥ aϵ2L

'

'

&

5 · 253 (1 + L̄)2 ∆V 5 −2 −1 κ̄y ϵ ρ . = L̄

Consequently, there exists k⋆ ∈ {0, . . . , K − 1} such that  h

i

i

h

h

k⋆ 2 −2 k⋆ k⋆ 2 + k⋆ max E ∥wk⋆ − w+ (ŵk⋆ , λk⋆ )∥2 , κ̄−2 y E ∥λ (ŵ ) − λ ∥ , κ̄y E ∥w − ŵ ∥

i

≤ ϵ2L .

√

Set δ := √3ϵρL . By Markov’s inequality and a union bound, with probability at least 1 − ρ, we have ∥wk⋆ − w+ (ŵk⋆ , λk⋆ )∥ ≤ δ, ∥λ+ (ŵk⋆ ) − λk⋆ ∥ ≤ κ̄y δ, ∥wk⋆ − ŵk⋆ ∥ ≤ κ̄y δ. Since

√ δ=

3ϵ

212 (1 + L̄)κ̄3y

≤

ϵ 211 (1 + L̄)κ̄3y

,

the conditions of Lemma 7 that are verified in the proof of Theorem 4 hold with δ in place of ϵL . Also, 1 1 pλ Cλ ≤ ϵL ≤ δ. 4 4 Thus, Lemma 7 applies pathwise and gives ∥∇w L(wk⋆ , λk⋆ )∥ ≤ 272L̄κ̄2y δ. Furthermore, lg,1 + κ̄y γλ−1 = 32lg,1 + 28 L̄ ≤ 288L̄, (pw − L0 )γw and hence



∥∇λ L(wk⋆ , λk⋆ )∥ ≤ 288L̄ + As shown in the proof of Theorem 4, we have

1 δ. 4 

LF̄ ,y 3 µg ≤ 4κ̄y . Therefore, Theorem 2 implies, on the

65

same event, k⋆

∥∇F (x

)∥ ≤ (1 + κ̄y )272L̄κ̄2y δ + 4κ̄3y



√ 11

≤2

(1 + L̄)κ̄3y δ =





1 δ 288L̄ + 4 

3 ϵ < ϵ. 2

Thus, P ∥∇F (xk⋆ )∥ ≤ ϵ ≥ 1 − ρ. Finally, the total oracle complexity is KB = O

(1 + ∆V )σ̄ 2 (1 + L̄)6 17 −6 −3 κ̄y ϵ ρ L̄3

!





−6 −3 = O κ̄17 . y ϵ ρ

This completes the proof.

C.6

Oracle Complexity of Stoc-SGHA in Expectation

Lemma 32 (Bounded Lagrangian and Bilevel Gradients on Bounded Iterates). Under Assumption l 1, suppose that Λ = {λ : ∥λ∥ ≤ Cλ } with Cλ > µf,0 . Suppose further that there exists a constant g Dw > 0 such that ∥wk ∥ ≤ Dw , almost surely. Define Gf (Dw ) :=

sup ∥∇f (w)∥,

Gg (Dw ) :=

∥w∥≤Dw

sup ∥∇y g(w)∥, ∥w∥≤Dw

and define GJ (Dw ) :=

sup ∥∇w (∇y g(w))∥. ∥w∥≤Dw

Then these constants are finite. Moreover, with Gw := Gf (Dw ) + GJ (Dw )Cλ ,

Gλ := Gg (Dw ),

we have ∥∇w L(wk , λk )∥ ≤ Gw ,

∥∇λ L(wk , λk )∥ ≤ Gλ ,

∀k ≥ 0

almost surely. In addition, the true bilevel hypergradient satisfies ∥∇F (xk )∥ ≤ GF := Gf (Dw ) +

lf,1 lg,1 Gg (Dw ) + lf,0 µg µg

almost surely. Proof. Recall that L(w, λ) = f (w) + λ⊤ ∇y g(w). Thus, ∇w L(w, λ) = ∇f (w) + J(w)⊤ λ,

J(w) := ∇w (∇y g(w)),

66

∇λ L(w, λ) = ∇y g(w).

Recall the definitions of Gf (Dw ), Gg (Dw ), and GJ (Dw ) from the statement. Since f and g are smooth, the mappings w 7→ ∇f (w), w 7→ ∇y g(w), w 7→ J(w) are continuous. Since the set {w : ∥w∥ ≤ Dw } is compact, the constants Gf (Dw ), Gg (Dw ), and GJ (Dw ) are finite. Therefore, for every k ≥ 0, ∥∇w L(wk , λk )∥ ≤ Gf (Dw ) + GJ (Dw )Cλ ,

∥∇λ L(wk , λk )∥ ≤ Gg (Dw ).

Taking Gw := Gf (Dw ) + GJ (Dw )Cλ ,

Gλ := Gg (Dw ),

we obtain ∥∇w L(wk , λk )∥ ≤ Gw ,

∥∇λ L(wk , λk )∥ ≤ Gλ .

Let yk⋆ := y ⋆ (xk ). By lower-level strong convexity, ∥y k − yk⋆ ∥ ≤

1 Gg (Dw ) ∥∇y g(xk , y k )∥ ≤ . µg µg

Using the implicit hypergradient formula, the smoothness of f and g, and ∥∇y f (x, y)∥ ≤ lf,0 , we obtain ∥∇F (xk )∥ ≤ ∥∇x f (xk , yk⋆ )∥ +

lg,1 lf,0 µg

≤ ∥∇x f (xk , y k )∥ + lf,1 ∥y k − yk⋆ ∥ + ≤ Gf (Dw ) +

lg,1 lf,0 µg

lf,1 lg,1 Gg (Dw ) + lf,0 = GF . µg µg

This completes the proof. Lemma 33 (Expected stationary point bridge). Under Assumptions 1 and 2, suppose that Λ = {λ : ∥λ∥ ≤ Cλ } with Cλ > lf,0 /µg . Set pw = 2lL,1 . Assume further that there exists a constant Dw > 0 such that ∥wk ∥ ≤ Dw almost surely. Let Gw , Gλ , and GF be the constants in Lemma 32. Define −1 Aw := γw,k + κ̄y pw ,

Aλ :=

lg,1 −1 + κ̄y γλ,k . (pw − lL,1 )γw,k

Also define (

r0 := min

lf,0 Cλ − µg

µg 4Aw

!

1 , 4κ̄y

lf,0 Cλ − µg

!)

.

If h

i

E ∥wk − w+ (ŵk , λk )∥2 ≤ ϵ2L ,

h

i

E ∥λ+ (ŵk ) − λk ∥2 ≤ κ̄2y ϵ2L , 67

h

i

E ∥wk − ŵk ∥2 ≤ κ̄2y ϵ2L ,

then, we have h

i

E ∥∇w L(wk , λk )∥ ≤ Aw ϵL +

3Gw 2 ϵ , r02 L

h

i

E ∥∇λ L(wk , λk )∥ ≤ Aλ ϵL + pλ Cλ +

3Gλ 2 ϵ . r02 L

Furthermore, h

i

E ∥∇F (xk )∥ ≤ (1 + κy )Aw ϵL +

LF̄ ,y 3GF (Aλ ϵL + pλ Cλ ) + 2 ϵ2L . µg r0

Proof. Define the good event

Gk :=

 k  ∥w − w+ (ŵk , λk )∥ ≤ r0 ,     

∥λ+ (ŵk ) − λk ∥ ≤ κ̄y r0 ,

  

k

k

∥w − ŵ ∥ ≤ κ̄y r0

.

  

By the definition of r0 , the interiority conditions in Lemma 7 hold on Gk . Therefore, the proof of Lemma 7 gives −1 ∥∇w L(wk , λk )∥ ≤ γw,k ∥wk − w+ (ŵk , λk )∥ + pw ∥wk − ŵk ∥, and ∥∇λ L(wk , λk )∥ ≤

lg,1 −1 ∥wk − w+ (ŵk , λk )∥ + γλ,k ∥λ+ (ŵk ) − λk ∥ + pλ Cλ . (pw − lL,1 )γw,k

It follows that h

i

h

E ∥∇w L(wk , λk )∥1Gk ≤ Aw ϵL ,

i

E ∥∇λ L(wk , λk )∥1Gk ≤ Aλ ϵL + pλ Cλ .

On the complement Gkc , Lemma 32 bounds the primal and multiplier gradients by Gw and Gλ , respectively. Moreover, Markov’s inequality gives P(Gkc ) ≤ ≤

i h i h i 1 h k 1 1 + k k 2 + k k 2 k k 2 E ∥w − w ( ŵ , λ )∥ + E ∥λ ( ŵ ) − λ ∥ + E ∥w − ŵ ∥ r02 κ̄2y r02 κ̄2y r02

3ϵ2L . r02

Consequently, the primal and multiplier components contribute at most 3Gw ϵ2L /r02 and 3Gλ ϵ2L /r02 , respectively, on Gkc . Combining the estimates on Gk and Gkc separately for the primal and multiplier components gives h i 3Gw E ∥∇w L(wk , λk )∥ ≤ Aw ϵL + 2 ϵ2L . r0 Likewise, h

i

E ∥∇λ L(wk , λk )∥ ≤ Aλ ϵL + pλ Cλ +

68

3Gλ 2 ϵ . r02 L

On the good event Gk , Theorem 2 and the two pathwise bounds above imply i

h

E ∥∇F (xk )∥1Gk ≤ (1 + κy )Aw ϵL +

LF̄ ,y (Aλ ϵL + pλ Cλ ) . µg

On Gkc , Lemma 32 gives ∥∇F (xk )∥ ≤ GF . Combining this with P(Gkc ) ≤ 3ϵ2L /r02 proves the stated hypergradient bound. This completes the proof. Proof of Theorem 9. By Lemma 32 and Cλ = 2κ̄y , choose the problem-dependent constant G in the theorem large enough that G ≥ max{1, Gw /κ̄y , Gλ }. Define ϵL := 213 (1+ϵL̄)Gκ̄3 and L0 := 8L̄κ̄y . y

Then the parameters in the theorem satisfy (

1 ϵL pλ = min µg , 8 κ̄y Define

(

a := min

)

1 pλ Cλ ≤ ϵL , 4

,

κ̄2y κ̄2y pw β 1 , , 32γw 64γλ 8

τ=

)

=

ϵL . 13 2 κ̄y

L̄κ̄y . 229

The verification of the required conditions of Lemma 31 is identical to that in the proof of Theorem 8. In particular, with L0 in place of lL,1 , pw = 2L0 ,

γ2 ≤

γ1 = 2,

1 , 8κ̄y

lΨ,1 ≤

L̄ , 4κ̄y

γ3 ≤

3075 . 4

k⋆

k⋆ 2

By Lemma 31, the integer K specified in the theorem satisfies &

5∆V K≥ aϵ2L

'

&

'

5 · 255 (1 + L̄)2 G 2 ∆V 5 −2 κ̄y ϵ = . L̄

Consequently, there exists an index k⋆ ∈ {0, . . . , K − 1} such that  h

max E ∥w

k⋆

+

k⋆

k⋆

2

− w (ŵ , λ )∥

i

, κ̄−2 y E

h

+

k⋆

k⋆ 2

∥λ (ŵ ) − λ ∥

i

, κ̄−2 y E

h

∥w

− ŵ ∥

i

≤ ϵ2L .

We now apply Lemma 33. Its constants satisfy −1 Aw = γw + κ̄y pw ≤ 272L̄κ̄2y ,

Aλ =

lg,1 + κ̄y γλ−1 ≤ 288L̄. (pw − L0 )γw

l

Furthermore, since Cλ − µf,0 ≥ κ̄y and µg = κ̄L̄y , the radius in Lemma 33 satisfies g (

r0 = min

µg 4Aw

lf,0 Cλ − µg

!

1 , 4κ̄y

lf,0 Cλ − µg

!)

(

≥ min

Consequently, 3 ≤ 3(1088)2 κ̄4y < 222 κ̄4y . r02

69

1 1 , 1088κ̄2y 4

)

=

1 . 1088κ̄2y

(30)

The bounded-hypergradient constant in Lemma 32 satisfies GF = Gf (Dw ) +

lf,1 lg,1 Gg (Dw ) + lf,0 µg µg

≤ 2(1 + L̄)Gκ̄y . Indeed, the preceding choice of G gives Gf (Dw ) ≤ Gκ̄y and Gg (Dw ) ≤ G, while lf,1 /µg ≤ κ̄y , lg,1 /µg ≤ κ̄y , and lf,0 ≤ L̄. As shown in the proof of Theorem 4, LF̄ ,y /µg ≤ 4κ̄3y . Using pλ Cλ ≤ ϵL /4 and applying the hypergradient conclusion of Lemma 33, we obtain h

i

E ∥∇F (xk⋆ )∥ ≤ 211 (1 + L̄)κ̄3y ϵL + 223 (1 + L̄)Gκ̄5y ϵ2L ϵ2 ϵ + 4G 8(1 + L̄)Gκ̄y 3 ≤ ϵ < ϵ, 8 =

where the last inequality uses 0 < ϵ ≤ 1, G ≥ 1, and κ̄y ≥ 1. Finally, the total oracle complexity is KB = O

(1 + ∆V )σ̄ 2 (1 + L̄)6 G 6 17 −6 κ̄y ϵ L̄3

!





−6 = O κ̄17 , y ϵ

where the last expression treats the remaining problem-dependent constants as fixed. This completes the proof.

D

Improved Complexities with Lower-Level Stochastic Smoothness

D.1

Properties of Stochastic Finite Difference Approximation with Stochastic Smoothness of g

Lemma 34. Under Assumptions 1, 2 and 3, suppose that λ ∈ Λ = {λ : ∥λ∥ ≤ Cλ }, we have 

E

˜ 2 gλ (x, y; Bg ) ∇2xy g(x, y)λ − ∇ xy

2



˜ 2 gλ (x, y; Bg ) ∇2yy g(x, y)λ − ∇ yy

2



≤

2 C4 ˜lg,1 C 2 lg,2 λ 2 λ τ + , 4 B

(31)

≤

2 C4 ˜lg,1 C 2 lg,2 λ 2 λ τ + . 4 B

(32)

and 

E

Proof. We prove the first bound; the second is identical. The same sample ζi is used at the two perturbed points. Define Di :=

∇x g(x, y + τ λ; ζi ) − ∇x g(x, y − τ λ; ζi ) . 2τ

70

The samples are independent across i, and E[Di ] is the deterministic central finite difference. Hence, B 1 X E (Di − E[Di ]) B i=1

2

=

1 E ∥D1 − E[D1 ]∥2 B

1 E∥D1 ∥2 B e lg,1 ≤ ∥(x, y + τ λ) − (x, y − τ λ)∥2 4Bτ 2 e e lg,1 ∥λ∥2 lg,1 Cλ2 = ≤ . B B ≤

The deterministic central-difference bias is bounded by lg,2 Cλ2 τ /2 in Lemma 12. Since the sampling error is centered, the squared bias and variance add. This yields (31); applying the same calculation to the y-component yields (32).

D.2

Preliminary Lemmas

Lemma 35. Under Assumptions 1, 2 and 3, and the update rule of Algorithm 2, we have k+1

E[∥x

E[∥y

k+1

k 2

2 − x ∥ ] ≤ 2γx,k E

k 2

2 − y ∥ ] ≤ 2γy,k E



k

k

k

k

k

k

∇x K(w , ŵ , λ )



∇y K(w , ŵ , λ )

2 E[∥λk+1 − λk ∥2 ] ≤ γλ,k E



2



2



2 σ2 2γx,k f 2 + + 2γx,k B

2 C4 ˜lg,1 C 2 lg,2 λ 2 λ τ + 4 B

!

2 σ2 2γy,k f 2 + + 2γy,k B

2 C4 ˜lg,1 C 2 lg,2 λ 2 λ τ + 4 B

!

∇y g(xk , y k ) − pλ λk

2



+

,

2 σ2 γλ,k g . B

In particular, since ∥λk ∥ ≤ Cλ , we also have 2 E[∥λk+1 − λk ∥2 ] ≤ 2γλ,k E



∇y g(xk , y k )

2



2 + 2γλ,k p2λ Cλ2 +

σ2

l̃

2 σ2 γλ,k g . B C2

Proof. The proof is identical to that of Lemma 26, with Bτg2 replaced by g,1B λ throughout.

D.3

Intermediate Lemmas for Lyapunov Function

1 Lemma 36. Under Assumptions 1, 2 and 3, suppose γw,k ≤ 8(pw +l . Then, we have L,1 )

h

i

h

E K(wk , ŵk , λk ) − E K(wk+1 , ŵk , λk+1 ) γw,k ≥ E 4 −





k

k

k

∇w K(w , ŵ , λ )

2 γw,k + 4(pw + lL,1 )γw,k

+E

hD

2



i

 2 C4 ˜lg,1 C 2 lg,2 λ 2 λ τ + 4 B

∇y g(xk , y k ) − pλ λk , λk − λk+1

Ei

!

−

2 4(pw + lL,1 )γw,k σf2 B

2 h i lg,1 pλ + E ∥λk+1 − λk ∥2 . 2 2(pw + lL,1 )

!

−

71

,

σ2

l̃

C2

Proof. The proof is identical to that of Lemma 27, with Bτg2 replaced by g,1B λ throughout. Lemma 37. Suppose the conditions in Lemma 36 hold. Set pw = 2lL,1 . Suppose further that

γλ,k ≤ min

   

 

1 

2 lg,1    2 2lΨ,1 + pλ + p +l w

L,1

  l2  , L,1 γ w,k . 2  16lg,1  

Then, we have h

i

h

i

h

i

E K(wk , ŵk , λk ) − E K(wk+1 , ŵk , λk+1 ) + 2E Ψ(ŵk , λk+1 ) − Ψ(ŵk , λk ) γw,k E ≥ 8



k

k

k

∇w K(w , ŵ , λ )

2



1 + E 4γλ,k



λ

k+1

−λ

2

k



2   l2 C 4 ˜lg,1 C 2 4(pw + lL,1 )γw,k g,2 λ 2 2 λ σf2 − γw,k + 4(pw + lL,1 )γw,k τ + − B 4 B σ2

l̃

!

−

γλ,k σg2 . B

C2

Proof. The proof is identical to that of Lemma 28, with Bτg2 replaced by g,1B λ throughout. Proposition 38. Define the Lyapunov function Vk = K(wk , ŵk , λk ) − 2Ψ(ŵk , λk ) + 2P (ŵk ). Suppose (

γw,k ≤ min

1 1 , 8pw β 8(pw + lL,1 )

)

,

γλ,k ≤ min

   

 

1 

2 lg,1    2 2lΨ,1 + pλ + p +l w

L,1

and

  l2 1  , L,1 , γ , w,k 2 16lg,1 1536pw βγ22   

√ β≤

5−1 . 48γ1

Then, we have E[Vk ] − E[Vk+1 ]     2 2 1 1 k + k k + k k E w − w (ŵ , λ ) E λ (ŵ ) − λ ≥ + 32γw,k 32γλ,k     2 2 pw β + E wk − ŵk − 48pw βE w⋆ (ŵk ) − w⋆ (ŵk , λ+ (ŵk )) 8 !   l2 C 4 ˜lg,1 C 2 g,2 λ 2 2 2 λ τ + − γw,k + 4(pw + lL,1 )γw,k + pw βγw,k 4 B 2 σ2 2 σ2 4(pw + lL,1 )γw,k pw βγw,k 9γλ,k σg2 f f − − − . B B 8B σ2

l̃

C2

Proof. The proof is identical to that of Proposition 29, with Bτg2 replaced by g,1B λ throughout.

72

D.4

Oracle Complexity under Stochastic Setting with Stochastic Smoothness of g

Proposition 39. Suppose the conditions in Proposition 38 hold. Suppose further that β≤ where γ3 := r

1 , 3072pw γλ,k γ32 −1 lΨ,1 + γλ,k

.

(pw −l )2 µ2g 2(pw − lL,1 )pλ + (pw +lL,1 2 L,1 )

Then, we have E[Vk ] − E[Vk+1 ]       2 2 2 1 pw β 1 k + k k + k k k k E w − w (ŵ , λ ) E λ (ŵ ) − λ E w − ŵ + + ≥ 32γw,k 64γλ,k 8 !   l2 C 4 ˜lg,1 C 2 g,2 λ 2 2 2 λ − γw,k + 4(pw + lL,1 )γw,k + pw βγw,k τ + 4 B 2 σ2 2 σ2 pw βγw,k 4(pw + lL,1 )γw,k 9γλ,k σg2 f f − − . − B B 8B σ2

l̃

C2

Proof. The proof is identical to that of Proposition 30, with Bτg2 replaced by g,1B λ throughout. l

Lemma 40. Under Assumptions 1, 2 and 3, suppose that Λ = {λ : ∥λ∥ ≤ Cλ } with Cλ > µf,0 . Set g pw = 2lL,1 . Further choose constant stepsizes (

γw,k ≤ min

1 1 , 8pw β 8(pw + lL,1 )

)

,

γλ,k ≤ min

   

 

1

 2 lg,1    2 2lΨ,1 + pλ + p +l w

L,1

  l2 1  , L,1 . γ , w,k 2 2 16lg,1 1536pw βγ2   

Moreover, choose the averaging parameter (√

β ≤ min

5−1 1 , 48γ1 3072pw γλ,k γ32

)

κ̄2y κ̄2y pw β 1 , , 32γw,k 64γλ,k 8

)

.

Define (

a := min

.

Also define 2 2 Cg := γw,k + 4(pw + lL,1 )γw,k + pw βγw,k ,

and 2 2 Cf := 4(pw + lL,1 )γw,k + pw βγw,k .

Without loss of generality, take the declared Hessian–Lipschitz upper bound lg,2 > 0 (it may always

73

be enlarged). Choose τ2 =

4a 2 2 C 4 ϵL 5Cg lg,2 λ

and the positive integer batch size (

&

(

B = max 1, max

5˜lg,1 Cg Cλ2 5Cf σf2 45γλ,k σg2 , , aϵ2L aϵ2L 8aϵ2L

)')

,

and run Algorithm 2 for  

 

K = max 1,   

5 E[V0 ] − f aϵ2L



     

iterations. More generally, the same conclusion holds if τ 2 is chosen no larger than its displayed value and B and K are chosen as positive integers no smaller than their displayed values. Then there exists an index k ∈ {0, . . . , K − 1} such that n h

i

h

i

h

+ k k 2 −2 k k 2 max E ∥wk − w+ (ŵk , λk )∥2 , κ̄−2 y E ∥λ (ŵ ) − λ ∥ , κ̄y E ∥w − ŵ ∥

io

≤ ϵ2L .

Proof. By Proposition 39, we have E[Vk ] − E[Vk+1 ] ≥

h i h i p β h i 1 1 w E ∥wk − w+ (ŵk , λk )∥2 + E ∥λ+ (ŵk ) − λk ∥2 + E ∥wk − ŵk ∥2 32γw,k 64γλ,k 8 ! 2 2 4 2 2 ˜ Cf σ f lg,2 Cλ 2 lg,1 Cλ 9γλ,k σg − Cg τ + − . − 4 B B 8B

By the definition of a, (

a = min

κ̄2y κ̄2y pw β 1 , , 32γw,k 64γλ,k 8

)

,

we obtain n h

i

h

i

h

io

i

h

io

+ k k 2 −2 k k 2 E[Vk ] − E[Vk+1 ] ≥ a max E ∥wk − w+ (ŵk , λk )∥2 , κ̄−2 y E ∥λ (ŵ ) − λ ∥ , κ̄y E ∥w − ŵ ∥

− Cg

2 C4 ˜lg,1 C 2 lg,2 λ 2 λ τ + 4 B

!

−

Cf σf2 9γλ,k σg2 − . B 8B

Summing from k = 0 to K − 1 gives E[V0 ] − f ≥ a

K−1 X

n h

i

h

+ k k 2 −2 k k 2 max E ∥wk − w+ (ŵk , λk )∥2 , κ̄−2 y E ∥λ (ŵ ) − λ ∥ , κ̄y E ∥w − ŵ ∥

k=0

− KCg

2 C4 ˜lg,1 C 2 lg,2 λ 2 λ τ + 4 B

!

Cf σf2 9γλ,k σg2 −K −K . B 8B

74

Therefore, there exists k ∈ {0, . . . , K − 1} such that i

n h

i

h

h

−2 k k 2 + k k 2 max E ∥wk − w+ (ŵk , λk )∥2 , κ̄−2 y E ∥λ (ŵ ) − λ ∥ , κ̄y E ∥w − ŵ ∥

E[V0 ] − f Cg ≤ + aK a

2 C4 ˜lg,1 C 2 lg,2 λ 2 λ τ + 4 B

!

+

io

Cf σf2 9γλ,k σg2 + . aB 8aB

By choosing  

K≥ 

5 E[V0 ] − f

,  

aϵ2L



we have



E[V0 ] − f 1 ≤ ϵ2L . aK 5

By the choice of τ , τ2 ≤ we have

4a 2 2 C 4 ϵL , 5Cg lg,2 λ

2 C4 1 Cg lg,2 λ 2 τ ≤ ϵ2L . a 4 5

By the choice of B, &

(

B ≥ max

5˜lg,1 Cg Cλ2 5Cf σf2 45γλ,k σg2 , , aϵ2L aϵ2L 8aϵ2L

we have

Cf σf2 1 ≤ ϵ2L , aB 5

˜lg,1 Cg C 2 1 λ ≤ ϵ2L , aB 5 Combining these estimates yields n h

i

)'

,

9γλ,k σg2 1 ≤ ϵ2L . 8aB 5

h

i

h

+ k k 2 −2 k k 2 max E ∥wk − w+ (ŵk , λk )∥2 , κ̄−2 y E ∥λ (ŵ ) − λ ∥ , κ̄y E ∥w − ŵ ∥

io

≤ ϵ2L .

This completes the proof.

D.5

Oracle Complexity of Stoc-SGHA in High Probability with Stochastic Smoothness of g

Proof of Theorem 10.

√ ϵ ρ

Define ϵL := 212 (1+L̄)κ̄3 and L0 := 8L̄κ̄y . Then y

(

1 ϵL pλ = min µg , 8 κ̄y

)

,

1 pλ Cλ ≤ ϵL , 4

τ=

ϵL . 13 2 κ̄y

The verification of the stepsize and averaging conditions is identical to that in the proof of Theorem 8. Indeed, with L0 in place of lL,1 , pw = 2L0 ,

γ1 = 2,

γ2 ≤

1 , 8κ̄y

lΨ,1 ≤

L̄ , 4κ̄y

γ3 ≤

Thus, the parameters satisfy the common conditions required in Lemma 40.

75

3075 . 4

Define

(

a := min

κ̄2y κ̄2y pw β 1 , , 32γw 64γλ 8

)

=

L̄κ̄y , 229

and 2 2 Cg := γw + 4(pw + L0 )γw + pw βγw ,

2 2 Cf := 4(pw + L0 )γw + pw βγw .

The explicit parameter choices give Cg =

23 22 + β ≤ 12 , 12 2 L̄κ̄y 2 L̄κ̄y

Cf =

6+β 7 ≤ 12 . 12 2 L̄κ̄y 2 L̄κ̄y

Using lg,2 ≤ L̄ and Cλ = 2κ̄y , 2 C4 Cg lg,2 23 2 1 λ 2 τ ≤ ϵL < ϵ2L . 4a 128 5 226 M̄

Moreover, the batch size in the theorem satisfies B ≥ L̄2 ϵ2 g . Consequently, L

5elg,1 Cg Cλ2 115 · 219 elg,1 ≤ ≤ B, aϵ2L L̄2 ϵ2L 5Cf σf2 aϵ2L

≤

35 · 217 σf2 L̄2 κ̄2y ϵ2L

≤ B,

45γλ σg2 45 · 218 σg2 = ≤ B, 8aϵ2L L̄2 ϵ2L where we used κ̄y ≥ 1 and the definition of M̄g . By Lemma 40, the integer K specified in the theorem satisfies &

5∆V K≥ aϵ2L

'

&

'

5 · 253 (1 + L̄)2 ∆V 5 −2 −1 = κ̄y ϵ ρ . L̄

Consequently, there exists an index k⋆ ∈ {0, . . . , K − 1} such that  h

i

h

i

h

+ k⋆ k⋆ 2 −2 k⋆ k⋆ 2 max E ∥wk⋆ − w+ (ŵk⋆ , λk⋆ )∥2 , κ̄−2 y E ∥λ (ŵ ) − λ ∥ , κ̄y E ∥w − ŵ ∥

Set δ :=

i

≤ ϵ2L .

√ 3 ϵL √ ρ . By Markov’s inequality and a union bound, with probability at least 1 − ρ,

∥wk⋆ − w+ (ŵk⋆ , λk⋆ )∥ ≤ δ,

∥λ+ (ŵk⋆ ) − λk⋆ ∥ ≤ κ̄y δ,

We next verify the conditions of Lemma 7. Since √ 3ϵ ϵ ≤ 11 , δ = 12 3 2 (1 + L̄)κ̄y 2 (1 + L̄)κ̄3y

76

∥wk⋆ − ŵk⋆ ∥ ≤ κ̄y δ.

(33)

the calculations in the deterministic proof give 



−1 γw + κ̄y pw

!

lf,0 Cλ − µg

µg δ≤ 4

lf,0 1 κ̄y δ ≤ Cλ − 4 µg

,

!

.

Furthermore, 1 1 pλ Cλ ≤ ϵL ≤ δ. 4 4 Thus, Lemma 7 applies pathwise. Using −1 γw + κ̄y pw ≤ 272L̄κ̄2y

and

lg,1 + κ̄y γλ−1 ≤ 288L̄, (pw − L0 )γw

we obtain, on the same event, k⋆

k⋆

∥∇w L(w , λ

)∥ ≤ 272L̄κ̄2y δ,

1 ∥∇λ L(w , λ )∥ ≤ 288L̄ + δ. 4

As shown in the proof of Theorem 4, we have k⋆

∥∇F (x



√ ≤2 



LF̄ ,y 3 µg ≤ 4κ̄y . Therefore, Theorem 2 implies

)∥ ≤ (1 + κ̄y )272L̄κ̄2y δ + 4κ̄3y 11



k⋆

k⋆

(1 + L̄)κ̄3y δ =

1 288L̄ + δ 4 

3 ϵ < ϵ. 2



Hence, P ∥∇F (xk⋆ )∥ ≤ ϵ ≥ 1 − ρ. Finally, the total oracle complexity is KB = O

(1 + ∆V )M̄g (1 + L̄)4 11 −4 −2 κ̄y ϵ ρ L̄3

!





−4 −2 = O κ̄11 . y ϵ ρ

This completes the proof.

D.6

Oracle Complexity of Stoc-SGHA in Expectation with Stochastic Smoothness of g

Proof of Theorem 11. By Lemma 32 and Cλ = 2κ̄y , choose the problem-dependent constant G in the theorem large enough that G ≥ max{1, Gw /κ̄y , Gλ }. Define ϵL := 213 (1+ϵL̄)Gκ̄3 and L0 := 8L̄κ̄y . y

Then

(

pλ =

1 ϵL min µg , 8 κ̄y

Define

(

a := min

)

,

1 pλ Cλ ≤ ϵL , 4

κ̄2y κ̄2y pw β 1 , , 32γw 64γλ 8

τ=

)

=

ϵL . 13 2 κ̄y

L̄κ̄y . 229

The verification of the required conditions of Lemma 40 is identical to that in the proof of

77

Theorem 10. Indeed, with L0 in place of lL,1 , pw = 2L0 ,

γ2 ≤

γ1 = 2,

1 , 8κ̄y

L̄ , 4κ̄y

lΨ,1 ≤

γ3 ≤

3075 . 4

By Lemma 40, the integer K specified in the theorem satisfies &

5∆V K≥ aϵ2L

'

&

'

5 · 255 (1 + L̄)2 G 2 ∆V 5 −2 = κ̄y ϵ . L̄

Consequently, there exists k⋆ ∈ {0, . . . , K − 1} such that  h

i

i

h

h

−2 k⋆ k⋆ 2 + k⋆ k⋆ 2 max E ∥wk⋆ − w+ (ŵk⋆ , λk⋆ )∥2 , κ̄−2 y E ∥λ (ŵ ) − λ ∥ , κ̄y E ∥w − ŵ ∥

i

≤ ϵ2L .

(34)

We next apply Lemma 33. Its constants satisfy −1 Aw = γw + κ̄y pw ≤ 272L̄κ̄2y ,

Aλ =

lg,1 + κ̄y γλ−1 ≤ 288L̄. (pw − L0 )γw

l

Since Cλ − µf,0 ≥ κ̄y and µg = κ̄L̄y , the radius in Lemma 33 satisfies g (

r0 ≥ min

1 1 , 2 1088κ̄y 4

)

=

3 < 222 κ̄4y . r02

1 , 1088κ̄2y

The bounded-hypergradient constant in Lemma 32 satisfies GF ≤ 2(1 + L̄)Gκ̄y . As shown in the deterministic proof, LF̄ ,y /µg ≤ 4κ̄3y . Using pλ Cλ ≤ ϵL /4 and applying the hypergradient conclusion of Lemma 33, we obtain h

i

E ∥∇F (xk⋆ )∥ ≤ 211 (1 + L̄)κ̄3y ϵL + 223 (1 + L̄)Gκ̄5y ϵ2L ϵ ϵ2 + 4G 8(1 + L̄)Gκ̄y 3 ≤ ϵ < ϵ, 8 =

where the last inequality uses 0 < ϵ ≤ 1, G ≥ 1, and κ̄y ≥ 1. Finally, the total stochastic first-order oracle complexity is KB = O

(1 + ∆V )M̄g (1 + L̄)4 G 4 11 −4 κ̄y ϵ L̄3

This completes the proof.

78

!





−4 = O κ̄11 . y ϵ

Related documents

• Federated stochastic bilevel optimization with fully first-order gradients#1110713
• A Hybrid Subgradient Method for Nonsmooth Nonconvex Bilevel Optimization#160891
• Stochastic Bilevel Optimization with Heavy-Tailed Noise#1104884
• Optimal Stochastic Bilevel Optimization with First-Order Oracles#1157114
• S$^3$LDBO: A Snapshot Single-Loop Algorithm for Decentralized Bilevel Optimization#246538