betaFeedback

WorksMathematics

Accelerating Finite-Sum Bilevel Optimization with Fully First-Order Oracles

Abstract

We study nonconvex–strongly-convex bilevel optimization with finite-sum objectives and fully first-order oracles. We propose Sampled Implicit Corrections for Bilevel Optimization (SICBO), which combines a penalty approximation with variance-reduced corrections for the lower-level variables. Under componentwise lower strong convexity, SICBO finds a point xx satisfying E∥∇Φ(x)∥2≤ε2\mathbb{E}\|\nablaΦ(x)\|^2\le\varepsilon^2 within O~(N+Nκ7/2ε−2)\tilde{O}(N+\sqrt{N}κ^{7/2}\varepsilon^{-2}) component-gradient calls, where NN is the total number of components and κκ is the normalized lower-level condition number. The bound achieves square-root finite-sum dependence using only gradients and preserves the best known deterministic fully first-order condition-number exponent for smooth problems. Our improvement follows from a curvature-dependent bound for nonlinear correction errors, which permits epochs of length Θ~(N/κ)\tildeΘ(\sqrt{N/κ}) with batches of size Θ~(Nκ)\tildeΘ(\sqrt{Nκ}). A single-level reduction shows that the dependence on NN and ε\varepsilon is optimal up to logarithmic factors for fixed κκ.

Introduction

We study the finite-sum bilevel optimization problem

min⁡x∈RdxΦ(x):=f(x,y∗(x)),y∗(x):=arg⁡min⁡y∈Rdyg(x,y),(1)\min_{x\in\mathbb{R}^{d_x}}\Phi(x) := f(x,y^*(x)), \qquad y^*(x) := \mathop{\arg\min}_{y\in\mathbb{R}^{d_y}} g(x,y), \tag*{(1)}

where f(x,y)=n−1∑i=1nfi(x,y)f(x,y)=n^{-1}\sum_{i=1}^{n}f_i(x,y) and g(x,y)=m−1∑j=1mgj(x,y)g(x,y)=m^{-1}\sum_{j=1}^{m}g_j(x,y). The lower objective is strongly convex in yy, and Φ\Phi may be nonconvex. Such problems arise when an upper variable is selected through the solution of a training problem. We write N=n+mN=n+m and count individual component-gradient evaluations.

The gradient of Φ\Phi, called the hypergradient, involves the inverse of the lower Hessian. Implicit differentiation methods therefore typically require Hessian-vector products. Fully first-order methods approximate the hypergradient through differences of gradients. The penalty approach of Kwon et al. [16] and Chen et al. [3], combined with accelerated inner minimization, gives a deterministic complexity of O~(κ7/2ε−2)\widetilde{O}(\kappa^{7/2}\varepsilon^{-2}) [4].

Implementing these deterministic methods on (1) by full gradients adds a factor NN. Accelerated finite-sum solvers reduce the inner minimization cost, but a full pass at every outer iteration still contributes Nκ3ε−2N\kappa^3\varepsilon^{-2}. This term exceeds the desired finite-sum rate when N>κN>\kappa.

In this paper, we propose Sampled Implicit Corrections for Bilevel Optimization (SICBO), which tracks the two inner solutions with sampled corrections. The key step is to control sampling errors through these nonlinear corrections in curvature-dependent norms. The resulting epoch estimate gives the complexity

O~(N+Nκ7/2ε−2).(2)\widetilde{O}\left(N+\sqrt{N}\kappa^{7/2}\varepsilon^{-2}\right). \tag*{(2)}

The bound combines gradient-only access, square-root finite-sum dependence, and the κ7/2\kappa^{7/2} exponent of the accelerated deterministic penalty method. The analysis uses curvature-weighted concentration at population endpoints and predictable energy peeling to control the error over each epoch. We also prove a lower bound matching the dependence on NN and ε\varepsilon up to logarithms for fixed κ\kappa; a matching bound in κ\kappa remains open. On a synthetic finite-sum family, SICBO uses the fewest component-gradient calls among the methods in Table 1, with an advantage over the full-refresh benchmark that decreases with κ\kappa as predicted by the amortized cost (§ 6).

Table 1: Component-gradient complexity for achieving (3). All expressions display the dependence on NN, κ\kappa, and ε\varepsilon; logarithmic factors are suppressed. The first two rows implement deterministic methods by full passes. The last two rows assume componentwise lower strong convexity. Every row uses component gradients only.

MethodComponent-gradient complexity
Penalty method of Chen et al. [3]O~(Nκ4ε−2)\widetilde{O}(N\kappa^{4}\varepsilon^{-2})
Accelerated penalty method [4]O~(Nκ7/2ε−2)\widetilde{O}(N\kappa^{7/2}\varepsilon^{-2})
Full refresh with accelerated finite-sum solves (Proposition 3.1)O~(N+(Nκ3+Nκ7/2)ε−2)\widetilde{O}\left(N+(N\kappa^{3}+\sqrt{N}\kappa^{7/2})\varepsilon^{-2}\right)
SICBO (Theorem 5.1)O~(N+Nκ7/2ε−2)\widetilde{O}\left(N+\sqrt{N}\kappa^{7/2}\varepsilon^{-2}\right)

Table 1.

Preliminaries

We use ∥⋅∥\|\cdot\| for the Euclidean norm of vectors and the induced operator norm of matrices. For a positive definite matrix HH, let ∥u∥H2=uTHu\|u\|_{H}^{2}=u^{\mathsf{T}}Hu. We write a≲ba\lesssim b to suppress an absolute constant and O~\widetilde{O} to suppress logarithmic factors. All polynomial dependence on NN, κ\kappa, and ε\varepsilon is explicit. We impose the following assumptions on the whole space.

Assumption 1 (Component smoothness). Each fif_i has a 1-Lipschitz continuous gradient. Each gjg_j is twice continuously differentiable, its gradient is 1-Lipschitz continuous, and its Hessian is 1-Lipschitz continuous. These Lipschitz conditions apply jointly to (x,y)(x,y).

Assumption 2 (Lower strong convexity). For every xx and jj, the function gj(x,⋅)g_j(x,\cdot) is μ\mu-strongly convex, where 0<μ≤10<\mu\le1. We define κ=1/μ\kappa=1/\mu.

Assumption 3 (Upper gradient and initial gap). The average objective satisfies ∥∇yf(x,y)∥≤1\|\nabla_y f(x,y)\|\le1 for all (x,y)(x,y). Furthermore, Φ\Phi is bounded below and the initial point satisfies Φ(x0)−inf⁡xΦ(x)≤Δ\Phi(x_0)-\inf_x\Phi(x)\le\Delta, where a known upper bound Δ=O(1)\Delta=O(1) is available.

The unit bounds in Assumptions [1] and [3] define the normalized class for our condition-number dependence; no powers of other smoothness parameters are suppressed. Componentwise strong convexity makes every sampled correction strongly convex and permits accelerated finite-sum solves. Strong convexity of the average gg alone does not ensure this property. We require neither bounded component-gradient variance nor Hessian smoothness of fif_i.

Our goal is to produce a random point xoutx_{\mathrm{out}} such that

E∥∇Φ(xout)∥2≤ε2,0<ε≤1.(3)\mathbb{E}\|\nabla\Phi(x_{\mathrm{out}})\|^{2}\le\varepsilon^{2},\qquad0<\varepsilon\le1. \tag*{(3)}

One oracle call returns ∇fi(x,y)\nabla f_i(x,y) or ∇gj(x,y)\nabla g_j(x,y) at a specified index and point, so a full gradient costs O(N)O(N) calls. The oracles are exact; arithmetic precision is excluded from the complexity.

For λ≥2κ\lambda\ge2\kappa, define the penalty value function

Hλ(x):=min⁡y{f(x,y)+λg(x,y)}−λmin⁡zg(x,z).(4)H_{\lambda}(x):=\min_y\{f(x,y)+\lambda g(x,y)\}-\lambda\min_z g(x,z). \tag*{(4)}

The following lemma gives the approximation error and smoothness of HλH_{\lambda}. Its proof appears in Appendix § 10.

Lemma 2.1 (Penalty approximation). Under Assumptions [1, 2, 3],

∥∇Hλ(x)−∇Φ(x)∥≤Cκ3λ,Lip⁡(∇Hλ)≤CHκ3,\|\nabla H_{\lambda}(x)-\nabla\Phi(x)\|\le\frac{C\kappa^{3}}{\lambda},\qquad\operatorname{Lip}(\nabla H_{\lambda})\le C_H\kappa^{3},
Φ(x)−κ2λ≤Hλ(x)≤Φ(x).(5)\Phi(x)-\frac{\kappa}{2\lambda}\le H_{\lambda}(x)\le\Phi(x). \tag*{(5)}

In particular, the initial gap of HλH_{\lambda} is at most Δ‾H:=Δ+κ/(2λ)=O(1)\overline{\Delta}_{H}:=\Delta+\kappa/(2\lambda)=O(1).

Related Work

Applications. Bilevel problems arise in hyperparameter optimization [9, 21], training-example reweighting [23], and meta-learning [9]. In the validation-based setting of § 6.2, the upper and lower sums are validation and training losses, respectively.

Hypergradient methods. Implicit hypergradient methods use Hessian- or Jacobian-vector products of the lower objective. Stochastic approximation methods were analyzed by Ghadimi and Wang [10], Hong et al. [11] and Ji et al. [12]; momentum and recursive variance reduction improve their sample complexity [15, 27]. These methods track both the lower solution and a linear-system solution.

Fully first-order methods. Fully first-order methods replace second-order products by differences of gradients. Liu et al. [19] proposed a value-function method, and Kwon et al. [16] developed a penalty-based stochastic approximation method. Kwon et al. [17] studied the penalty landscape, and Shen and Chen [24] analyzed penalty gradient descent without lower-level strong convexity. Under normalized smoothness assumptions, Chen et al. [3] obtained a deterministic gradient complexity of O~(κ4ε−2)\widetilde{O}(\kappa^{4}\varepsilon^{-2}). Accelerated inner solves improve this bound to O~(κ7/2ε−2)\widetilde{O}(\kappa^{7/2}\varepsilon^{-2}) [4 Appendix F]. Full-pass implementations give the first two rows of Table 1.

Finite-sum bilevel methods. SVRG [14], SARAH [20], SPIDER [8] and PAGE [18] reduce full-gradient evaluations in finite-sum optimization. SABA [6] and SRBA [7] apply variance reduction to the implicit hypergradient. SPABA [5] achieves O(N+Nε−2)O(N+\sqrt{N}\varepsilon^{-2}) under (3), including initialization and suppressing other problem constants, with gradient and Hessian/Jacobian-vector oracles. Its κ\kappa dependence is not explicit. Our bound uses only component gradients and gives explicit κ7/2\kappa^{7/2} dependence, under the stronger assumptions of componentwise lower strong convexity and globally bounded average ∇yf\nabla_y f.

Accelerated finite-sum minimization. Katyusha [1] solves a smooth, strongly convex finite sum with MM components and condition number O(κ)O(\kappa) in O~(M+Mκ)\widetilde{O}(M+\sqrt{M\kappa}) gradient calls. This result immediately yields the following benchmark.

Proposition 3.1 (Full-refresh benchmark). Solving both inner problems and computing a full penalty-gradient estimate at every outer iteration gives the component-gradient complexity

O~(N+(Nκ3+Nκ7/2)ε−2).(6)\widetilde{O}\left(N+\left(N\kappa^{3}+\sqrt{N}\kappa^{7/2}\right)\varepsilon^{-2}\right). \tag*{(6)}

For N≤κN \le\kappa, this is bounded by (2).

The proof appears in Appendix Appendix § 14. For N>κN > \kappa, SICBO improves the iterative cost O~(Nκ3ε−2)\widetilde{O}(N\kappa^{3}\varepsilon^{-2}) by a factor Θ~(N/κ)\widetilde{\Theta}(\sqrt{N/\kappa}). The total-cost improvement can be smaller when initialization dominates.

Lower bounds. Ji and Liang [13] established lower bounds for bilevel problems with strongly convex or convex upper objectives. For our nonconvex finite-sum class, the following reduction gives the optimal dependence on NN and ε\varepsilon.

Proposition 3.2 (Optimal dependence for fixed condition number). For every fixed κ≥1\kappa\ge1, sufficiently large NN, and sufficiently small ε>0\varepsilon> 0, the worst-case component-gradient complexity of (3) under Assumptions [1, 2, 3], with Δ=1\Delta= 1, is at least Ω(N+Nε−2)\Omega(N+\sqrt{N}\varepsilon^{-2}).

Appendix Appendix § 15 proves the proposition by reduction from the individual-smoothness lower bound of Peng et al. [22], which permits unrestricted randomized component queries. Thus (2) is optimal up to logarithms in NN and ε\varepsilon for fixed κ\kappa. Dagréou et al. [7, Theorem 2] previously proved an Ω(nε−2)\Omega(\sqrt{n}\varepsilon^{-2}) bound for a restricted class of linear bilevel algorithms, where nn is our upper-level sum size. Their regime is ε2≲1/n\varepsilon^{2} \lesssim1/n with other constants fixed, and their result does not characterize κ\kappa dependence.

For condition-number dependence, Chen et al. [4, Theorem 4.1] prove an Ω(κ5/2ε−2)\Omega(\kappa^{5/2}\varepsilon^{-2}) bound for deterministic first-order algorithms with quadratic lower objectives. Their class does not impose our global bound on ∇yf\nabla_y f, so the result does not directly apply here. Appendix Appendix § 15 gives further lower bounds under our assumptions. The sharp joint dependence on NN and κ\kappa remains open; separate lower bounds do not establish a product bound.

The SICBO Method

Scaled gradient differences

Let zz approximate y∗(x)y^{*}(x) and introduce v=λ(y−z)v=\lambda(y-z). For w=(x,z,v)w=(x,z,v), define

Aj(x,z)=∇ygj(x,z),Bij(w)=∇yfi(x,z+v/λ)+λ[∇ygj(x,z+v/λ)−∇ygj(x,z)],Cij(w)=∇xfi(x,z+v/λ)+λ[∇xgj(x,z+v/λ)−∇xgj(x,z)].(7)\begin{aligned} A_j(x,z) &= \nabla_y g_j(x,z),\\ B_{ij}(w) &= \nabla_y f_i(x,z+v/\lambda)+\lambda\left[\nabla_y g_j(x,z+v/\lambda)-\nabla_y g_j(x,z)\right],\\ C_{ij}(w) &= \nabla_x f_i(x,z+v/\lambda)+\lambda\left[\nabla_x g_j(x,z+v/\lambda)-\nabla_x g_j(x,z)\right]. \tag*{(7)} \end{aligned}

Write AA, BB, CC for the population means and ASA_S, BSB_S, CSC_S for sample averages, with A(w)=A(x,z)A(w)=A(x,z). Each batch samples independent uniform pairs (i,j)(i,j) with replacement, and ASA_S ignores ii. Each lower-gradient difference uses the same index jj. Computing full means costs O(N)O(N) calls.

Let z∗(x)=y∗(x)z^{*}(x)=y^{*}(x) and let v∗(x,z)v^{*}(x,z) be the unique root of B(x,z,⋅)B(x,z,\cdot). At these roots,

C(x,z∗(x),v∗(x,z∗(x)))=∇Hλ(x).(8)C(x,z^{*}(x),v^{*}(x,z^{*}(x)))=\nabla H_{\lambda}(x). \tag*{(8)}

The scaling makes the inner condition number independent of λ\lambda: each Bij(x,z,⋅)B_{ij}(x,z,\cdot) is the gradient of a strongly convex potential with condition number O(κ)O(\kappa). The following lemma gives the field regularity.

Algorithm 1 SICBO: Sampled Implicit Corrections for Bilevel Optimization

Input: x0x_0, zinitz_{\mathrm{init}}, vinitv_{\mathrm{init}}; TT, qq, bb, λ\lambda, α\alpha, Γ\Gamma, τ\tau.

  1. for t=0,…,T−1t = 0, \ldots, T - 1 do

  2. if t≡0(modq)t \equiv0 \pmod{q} then

  3. Run Katyusha in ztz_t until ∥A(xt,zt)∥≤τ\lVert A(x_t,z_t)\rVert\le\tau.

  4. Run Katyusha in vtv_t until ∥B(xt,zt,vt)∥≤τ\lVert B(x_t,z_t,v_t)\rVert\le\tau.

  5. (A^t,B^t,G^t)←(A(xt,zt),B(wt),C(wt))(\widehat{A}_t,\widehat{B}_t,\widehat{G}_t) \leftarrow(A(x_t,z_t),B(w_t),C(w_t)).

  6. end if

  7. gt←G^t/max⁡{1,∥G^t∥/Γ}g_t \leftarrow\widehat{G}_t/\max\{1,\lVert\widehat{G}_t\rVert/\Gamma\}.

  8. xt+1←xt−αgtx_{t+1} \leftarrow x_t-\alpha g_t.

  9. if t+1<Tt+1<T and t+1≢0(modq)t+1\not\equiv0 \pmod{q} then

  10. Draw StzS_t^z; run Katyusha in zt+1z_{t+1} until ∥rtz(zt+1)∥≤τ\lVert r_t^z(z_{t+1})\rVert\le\tau.

  11. Draw StvS_t^v; run Katyusha in vt+1v_{t+1} until ∥rtv(vt+1)∥≤τ\lVert r_t^v(v_{t+1})\rVert\le\tau.

  12. Draw RtR_t; set (A^,B^,G^)t+1←(A^,B^,G^)t+(A,B,C)Rt(wt+1)−(A,B,C)Rt(wt)(\widehat{A},\widehat{B},\widehat{G})_{t+1}\leftarrow(\widehat{A},\widehat{B},\widehat{G})_t+(A,B,C)_{R_t}(w_{t+1})-(A,B,C)_{R_t}(w_t).

  13. end if

  14. end for

  15. U←{t<T:∥G^t∥≤Γ}\mathcal{U}\leftarrow\{t<T:\lVert\widehat{G}_t\rVert\le\Gamma\}.

  16. return xξx_\xi with ξ∼Unif⁡(U)\xi\sim\operatorname{Unif}(\mathcal{U}), or x0x_0 if U=∅\mathcal{U}=\varnothing.

Lemma 4.1 (Field regularity). For λ≥2κ\lambda\ge2\kappa, Bij(x,z,⋅)B_{ij}(x,z,\cdot) is (μ/2)(\mu/2)-strongly monotone and 22-Lipschitz. Moreover,

∥v∗(x,z)∥≤κ,Lip⁡(z∗)≤κ,Lip⁡z(v∗)≲κ2.(9)\lVert v^*(x,z)\rVert\le\kappa,\qquad\operatorname{Lip}(z^*)\le\kappa,\qquad\operatorname{Lip}_z(v^*)\lesssim\kappa^2. \tag*{(9)}

On ∥v∥≤2κ\lVert v\rVert\le2\kappa, each BijB_{ij} and CijC_{ij} is O(κ)O(\kappa)-Lipschitz in (x,z)(x,z) and O(1)O(1)-Lipschitz in vv. Consequently, z↦C(x,z,v∗(x,z))z\mapsto C(x,z,v^*(x,z)) is O(κ2)O(\kappa^2)-Lipschitz.

The proof appears in Appendix § 10. The fields in (7) require only component gradients.

Sampled implicit corrections

SICBO maintains ztz_t, vtv_t and the field estimates A^t,B^t,G^t\widehat{A}_t,\widehat{B}_t,\widehat{G}_t. Write wt=(xt,zt,vt)w_t=(x_t,z_t,v_t). Each epoch begins with population inner updates and full field evaluations. Between refreshes, SICBO updates xx, then zz, then vv, using the residual maps

rtz(u):=AStz(xt+1,u)−AStz(xt,zt)+A^t,rtv(u):=BStv(xt+1,zt+1,u)−BStv(wt)+B^t.(10)\begin{aligned} r_t^z(u)&:=A_{S_t^z}(x_{t+1},u)-A_{S_t^z}(x_t,z_t)+\widehat{A}_t,\\ r_t^v(u)&:=B_{S_t^v}(x_{t+1},z_{t+1},u)-B_{S_t^v}(w_t)+\widehat{B}_t. \tag*{(10)} \end{aligned}

We use capped Katyusha iterations to obtain ∥rtz(zt+1)∥≤τ\lVert r_t^z(z_{t+1})\rVert\le\tau and then, with zt+1z_{t+1} fixed, ∥rtv(vt+1)∥≤τ\lVert r_t^v(v_{t+1})\rVert\le\tau. Each residual is the gradient of a strongly convex objective. Every batch contains bb fresh, independent uniform index pairs. The evaluation batch RtR_t is drawn after both corrections, making its increments conditionally centered at the updated points.

The first inner solves start at zinit,vinitz_{\mathrm{init}},v_{\mathrm{init}} and later solves at the preceding iterates. We cap every solve and check its residual. Sampled updates must also satisfy ∥zt+1−zt∥≤1/(512κ)\lVert z_{t+1}-z_t\rVert\le1/(512\kappa) and ∥vt+1∥≤2κ\lVert v_{t+1}\rVert\le2\kappa. A failed test returns x0x_0. The output set U\mathcal{U} uses the estimates that generated the outer steps.

Clipping and the inner checks bound all accepted trajectories, allowing the high-probability tracking estimates to imply (3). A failed check terminates the run without an additional full pass. Appendix § 14 gives the solver budgets and their cost. For N≤κN\le\kappa, we set q=1q=1 and recover the full-refresh benchmark.

Complexity Analysis

Parameters and main result

For N>κN > \kappa, choose

q=⌈N/κ⌉,b=⌈CbκqΛ2⌉,T=⌈CTκ3ε−2⌉,λ=Cλκ3/ε,α=cακ−3,τ=cτεκ−4,θ=cθκ−2,Γ=θ/α,ν=cνεκ−3.(11)\begin{aligned} q &= \left\lceil\sqrt{N/\kappa}\right\rceil,\qquad b = \left\lceil C_b\kappa q\Lambda^2\right\rceil,\qquad T = \left\lceil C_T\kappa^3\varepsilon^{-2}\right\rceil,\\ \lambda&= C_\lambda\kappa^3/\varepsilon,\qquad\alpha= c_\alpha\kappa^{-3},\qquad\tau= c_\tau\varepsilon\kappa^{-4},\\ \theta&= c_\theta\kappa^{-2},\qquad\Gamma= \theta/\alpha,\qquad\nu= c_\nu\varepsilon\kappa^{-3}. \tag*{(11)} \end{aligned}

Here ν\nu is used only in the analysis. To specify the confidence level, put LH=CHκ3L_H = C_H\kappa^3, d=dx+dy+2d = d_x + d_y + 2, and

BT2=4LHΔ‾H+2LH2T2θ2,δ=min⁡{110,ε264(1+BT2)},Λ=log⁡edNκ(T+1)εδ.(12)B_T^2 = 4L_H\overline{\Delta}_H + 2L_H^2T^2\theta^2,\qquad \delta= \min\left\{\frac{1}{10},\frac{\varepsilon^2}{64(1+B_T^2)}\right\},\qquad \Lambda= \log\frac{e d N\kappa(T+1)}{\varepsilon\delta}. \tag*{(12)}

All constants are absolute. We choose cθc_\theta small and CλC_\lambda large, then cα≤min⁡{cθ/10,1/(4CH)}c_\alpha\le\min\{c_\theta/10,1/(4C_H)\}, then cτ,cνc_\tau,c_\nu small and CbC_b large, and finally CTC_T large. In particular, Γ≥10κ\Gamma\ge10\kappa and every outer displacement is at most θ\theta. Each inner solve receives failure probability at most δ/(C(T+1))\delta/(C(T+1)) for a sufficiently large absolute CC.

Theorem 5.1 (Component-gradient complexity). Under Assumptions 1–3, SICBO (Algorithm 1), with (11)–(12) for N>κN > \kappa and q=1q = 1 for N≤κN \le\kappa, returns a point satisfying

E∥∇Φ(xout)∥2≤ε2(13)\mathbb{E}\lVert\nabla\Phi(x_{\mathrm{out}})\rVert^2 \le\varepsilon^2 \tag*{(13)}

within

O~(N+Nκ7/2ε−2)(14)\widetilde{O}\left(N+\sqrt{N}\kappa^{7/2}\varepsilon^{-2}\right) \tag*{(14)}

component-gradient calls. For N≤κN \le\kappa, the remaining parameters are unchanged and the unused batch size can be omitted. The hidden logarithms include dimension, solver confidence, and the initial inner-distance bound. No Hessian or Hessian-vector oracle is used.

The proof appears in Appendices B–E. The result allows nonlinear lower objectives and noncommuting component Hessians. Componentwise strong convexity is used in both the sampled root analysis and the accelerated finite-sum solves.

The epoch estimate permits b=Θ~(κq)b = \widetilde{\Theta}(\kappa q), giving the amortized cost

O~(N/q+b)=O~(N/q+κq).(15)\widetilde{O}(N/q+b)=\widetilde{O}(N/q+\kappa q). \tag*{(15)}

Balancing the terms gives q≳N/κq \gtrsim\sqrt{N/\kappa} and cost O~(Nκ)\widetilde{O}(\sqrt{N\kappa}) per step. Together with T=O(κ3ε−2)T = O(\kappa^3\varepsilon^{-2}), this proves (14). An additional polynomial factor of κ\kappa in the batch size would increase the final condition-number exponent.

An epoch estimate for the nonlinear corrections

We outline the epoch estimate that determines the condition-number dependence. Index a correction by its endpoint tt and let

HtA=∇yy2g(xt,zt−1),HtB=∇yy2g(xt,zt+vt−1/λ).H_t^A = \nabla^2_{yy}g(x_t,z_{t-1}),\qquad H_t^B = \nabla^2_{yy}g(x_t,z_t+v_{t-1}/\lambda).

These matrices are used only in the analysis. For a tracker FF, let uˉt\bar{u}_t be the population corrected root, utu_t its sampled approximation, and dt=ut−ut−1d_t = u_t - u_{t-1}. Define

Qt=∥uˉt−ut−1∥Ht2,Et=∥ut−uˉt∥Ht2,Jt=∥dt∥Ht2.(16)\begin{aligned} Q_t &= \lVert\bar{u}_t-u_{t-1}\rVert_{H_t}^2, \qquad E_t = \lVert u_t-\bar{u}_t\rVert_{H_t}^2, \qquad J_t = \lVert d_t\rVert_{H_t}^2. \tag*{(16)} \end{aligned}

Let DtD_t bound the component change caused by the new context at the old inner point. Conditional concentration and local curvature comparison give

Et≲κΛb(Qt+Dt2)+κ2τ2.(17)E_t \lesssim\frac{\kappa\Lambda}{b}(Q_t+D_t^2)+\kappa^2\tau^2. \tag*{(17)}

The population endpoint in (17) is fixed before its correction batch is drawn, so the concentration bound is applied at a sample-independent point.

The independent evaluation batch gives a martingale error Mt=F(wt)−F^tM_t=F(w_t)-\widehat{F}_t. Predictable stopping and peeling bound ∥Mt∥2\lVert M_t\rVert^2 by the realized energy ∑s≤t(Js+Ds2)\sum_{s\leq t}(J_s+D_s^2). Combining this bound with (17) gives the following lemma.

Lemma 5.2 (Epoch error). There is an event T\mathcal{T} with probability at least 1−δ1-\delta on which all safeguards pass and, for every epoch E\mathcal{E} of actual length h≤qh\leq q,

∑t∈E∥G^t−∇Hλ(xt)∥2≤Cκ7qΛb∑t∈E∥xt+1−xt∥2+Ch(κ7τ2+κ6ν2).(18)\sum_{t\in\mathcal{E}}\lVert\widehat{G}_t-\nabla H_\lambda(x_t)\rVert^2 \leq C\frac{\kappa^7q\Lambda}{b}\sum_{t\in\mathcal{E}}\lVert x_{t+1}-x_t\rVert^2+Ch(\kappa^7\tau^2+\kappa^6\nu^2). \tag*{(18)}

The inequality holds pathwise on T\mathcal{T}.

The proof appears in Appendices § 11–§ 12. Let XX be the outer squared movement over an epoch and omit tolerance terms. The first tracker gives ∑∥Δzt∥2≲κ2X\sum\lVert\Delta z_t\rVert^2\lesssim\kappa^2X. The second then receives context energy O(κ4X)O(\kappa^4X) and contributes error O(κ7qΛX/b)O(\kappa^7q\Lambda X/b). The recursive error in C is O(κ6qΛX/b)O(\kappa^6q\Lambda X/b).

For the descent argument, smoothness gives

Hλ(xt+1)≤Hλ(xt)−α4∥gt∥2+α2∥G^t−∇Hλ(xt)∥2.(19)H_\lambda(x_{t+1})\leq H_\lambda(x_t)-\frac{\alpha}{4}\lVert g_t\rVert^2+\frac{\alpha}{2}\lVert\widehat{G}_t-\nabla H_\lambda(x_t)\rVert^2. \tag*{(19)}

Substituting (18) gives the movement coefficient Cα2κ7qΛ/b=Ccα2κqΛ/bC\alpha^2\kappa^7q\Lambda/b=Cc_\alpha^2\kappa q\Lambda/b, which is small enough to absorb. The resulting bound ensures at least T/2T/2 unclipped steps on T\mathcal{T}, controlling the denominator in uniform sampling from U\mathcal{U}. Clipping bounds the gradient at any returned point by BTB_T, so Tc\mathcal{T}^c contributes at most δBT2\delta B_T^2. Lemma 2.1 transfers stationarity from HλH_\lambda to Φ\Phi.

Numerical Experiments

We compare practical implementations of the four methods in Table 1. All use HλH_\lambda with λ=κ3/ε\lambda=\kappa^3/\varepsilon and outer updates xt+1=xt−αgtx_{t+1}=x_t-\alpha g_t. The two penalty methods use full-pass gradient descent and accelerated gradient descent, respectively. The full-refresh method uses q=1q=1 in Algorithm 1; SICBO uses q=⌈N/κ⌉q=\lceil\sqrt{N/\kappa}\rceil and b=⌈κq⌉b=\lceil\kappa q\rceil. We set τ=εκ−4\tau=\varepsilon\kappa^{-4} on the synthetic problem and use the tolerance floor below on real data. SICBO monitors the movement and radius checks without terminating at violations. Appendix § 16 details these implementations and their departures from (11).

Synthetic problem

We take n=m=104n=m=10^4, so that N=2⋅104N=2\cdot10^4, dx=dy=8d_x=d_y=8, and κ∈{10,30,100}\kappa\in\{10,30,100\}. The components are

gj(x,y)=12y⊤Hjy−y⊤Kjx+bj⊤y+ψ(w⊤y),ψ′′(u)=μsin⁡uμ,(20)g_j(x,y)=\frac{1}{2}y^\top H_jy-y^\top K_jx+b_j^\top y+\psi(w^\top y),\qquad\psi^{\prime\prime}(u)=\mu\sin\frac{u}{\sqrt{\mu}}, \tag*{(20)}
fi(x,y)=710∑kρ(yk−tik)+150∑kω(xk),ρ(t)=12log⁡(1+t2),ω(t)=t21+t2.f_i(x,y)=\frac{7}{10}\sum_k\rho(y_k-t_{ik})+\frac{1}{50}\sum_k\omega(x_k),\qquad\rho(t)=\frac{1}{2}\log(1+t^2),\qquad\omega(t)=\frac{t^2}{1+t^2}.

where the component Hessians HjH_j do not commute and Kj=HjM+EjK_j = H_jM + E_j for a fixed matrix MM (Appendix § 16.§ 1). All methods use a common step α\alpha, and the target is ε=10−4∥∇Φ(x0)∥\varepsilon= 10^{-4}\lVert\nabla\Phi(x_0)\rVert.

Figure 1 shows that all methods take essentially the same number of outer iterations. SICBO has the lowest cost per iteration and reaches the target with the fewest calls for every κ\kappa. Its advantage over the full-refresh benchmark decreases at the rate κ−1/2\kappa^{-1/2} predicted by (15) (Appendix § 16.§ 1).

Figure 1. Running minimum of ∥∇Φ(xt)∥\lVert\nabla\Phi(x_t)\rVert against component-gradient calls on (20). Markers are outer iterations. For the full-refresh benchmark and SICBO, each curve averages ten seeds; the two penalty methods are deterministic.

Real data

We also consider per-feature ridge-weight selection for logistic regression, a finite-sum benchmark used by Chu et al. [5], Dagréou et al. [6, 7]. Let (aj,bj)(a_j,b_j) and (ai′,bi′)(a'_i,b'_i) be the mm training and nn validation rows, respectively, with ∥aj∥=∥ai′∥=1\lVert a_j\rVert= \lVert a'_i\rVert= 1 and labels in {±1}\{\pm1\}. Define ϕ(u)=log⁡(1+e−u)\phi(u) = \log(1+e^{-u}) and

gj(x,y)=ϕ(bj⟨aj,y⟩)+12∑k=1prk(x)yk2,fi(x,y)=ϕ(bi′⟨ai′,y⟩),rk(x)=μ+9μ1+e−xk,(21)g_j(x,y) = \phi(b_j\langle a_j,y\rangle) + \frac{1}{2}\sum_{k=1}^{p} r_k(x)y_k^2,\qquad f_i(x,y) = \phi(b'_i\langle a'_i,y\rangle),\qquad r_k(x) = \mu+ \frac{9\mu}{1+e^{-x_k}}, \tag*{(21)}

so x∈Rpx\in\mathbb{R}^p sets one ridge weight per feature. We use the LIBSVM data sets a9a, w8a and ijcnn1 [2], with NN from 3.3⋅1043.3\cdot10^4 to 1.4⋅1051.4\cdot10^5, κ∈{100,1000}\kappa\in\{100,1000\} and ε=10−3∥∇Φ(x0)∥\varepsilon=10^{-3}\lVert\nabla\Phi(x_0)\rVert. The inner tolerance is τ=max⁡{εκ−4,10−11}\tau=\max\{\varepsilon\kappa^{-4},10^{-11}\}. Each method uses its own tuned step, and the penalty methods are stopped after three times SICBO’s mean cost at the reference step multiplier c=1c=1 (Appendix § 16.§ 2). These real-data objectives do not satisfy Assumption 1 globally, as detailed in the same appendix.

Figure 2 shows that SICBO reaches the target with the fewest calls in all six settings. The full-refresh benchmark is second, except on a9a and w8a with κ=100\kappa=100, where the accelerated penalty method has similar cost. On each data set, SICBO’s advantage over full refresh decreases from κ=100\kappa=100 to κ=1000\kappa=1000 and remains nearly the same fraction of N/κ\sqrt{N/\kappa}, consistent with (15) (Appendix § 16.§ 2).

Figure 2. Running minimum of ∥∇Φ(xt)∥\lVert\nabla\Phi(x_t)\rVert against component-gradient calls on (21), with the step tuned for each method. Lines join the outer iterations; markers are drawn at a few of them and are offset between methods, so that coinciding curves remain distinguishable. For the full-refresh benchmark and SICBO, each curve averages ten seeds; the penalty methods are deterministic.

Conclusion

We proposed SICBO for finite-sum nonconvex–strongly-convex bilevel optimization. Its component-gradient complexity O~(N+Nκ7/2ε−2)\widetilde{O}(N + \sqrt{N}\kappa^{7/2}\varepsilon^{-2}) is optimal up to logarithms in NN and ε\varepsilon for fixed κ\kappa and preserves the best known deterministic fully first-order condition-number exponent for smooth problems. The analysis combines curvature-dependent correction bounds with pathwise control of evaluation errors. Experiments on synthetic and LIBSVM data show the fewest component-gradient calls among the compared methods, with an advantage over full refresh that decreases as κ−1/2\kappa^{-1/2}. Extending the result to average lower strong convexity, obtaining a single-loop method, and establishing the sharp joint dependence on NN and κ\kappa remain open.

Acknowledgements

The authors thank Lesi Chen of Tsinghua University for helpful discussions of this open problem. Lesi Chen showed the initial upper bound stated in Proposition 3.1 and conjectured the sharper bound established in this manuscript.

Codex with GPT-6 Astra and Claude Science Opus 5.5 were used to assist with the development of the construction and proofs, numerical checks of algebraic identities, the review of related literature, and the preparation and revision of this manuscript. The authors are responsible for the mathematical claims, references, and final presentation.

References

Properties of the Component Fields and Penalty

Proof of Lemma 4.1

For fixed (x,z)(x,z), the field Bij(x,z,⋅)B_{ij}(x,z,\cdot) is the gradient of

φij(v)=λfi(x,z+v/λ)+λ2[gj(x,z+v/λ)−gj(x,z)]−λ⟨∇ygj(x,z),v⟩.(22)\varphi_{ij}(v)=\lambda f_i(x,z+v/\lambda)+\lambda^2[g_j(x,z+v/\lambda)-g_j(x,z)]-\lambda\langle\nabla_y g_j(x,z),v\rangle. \tag*{(22)}

The first term is 1/λ1/\lambda-smooth and 1/λ1/\lambda-weakly convex; the second is μ\mu-strongly convex and 11-smooth. Thus φij\varphi_{ij} is (μ−1/λ)(\mu-1/\lambda)-strongly convex and (1+1/λ)(1+1/\lambda)-smooth, giving the claimed constants for λ≥2κ\lambda\ge2\kappa.

Let y=z+v∗/λy=z+v^*/\lambda. The population root equation gives

λ[∇yg(x,y)−∇yg(x,z)]=−∇yf(x,y).\lambda[\nabla_y g(x,y)-\nabla_y g(x,z)]=-\nabla_y f(x,y).

Taking the inner product with y−zy-z, strong convexity and Assumption [3] give ∥v∗∥≤1/μ=κ\lVert v^*\rVert\le1/\mu=\kappa. Comparing the optimality equations at x,x′x,x' also gives ∥z∗(x)−z∗(x′)∥≤κ∥x−x′∥\lVert z^*(x)-z^*(x')\rVert\le\kappa\lVert x-x'\rVert.

For a∈{x,y}a\in\{x,y\}, the fundamental theorem of calculus gives

λ[∇agj(x,z+v/λ)−∇agj(x,z)]=∫01∇ay2gj(x,z+sv/λ)v ds.(23)\lambda[\nabla_a g_j(x,z+v/\lambda)-\nabla_a g_j(x,z)]=\int_0^1\nabla^2_{ay}g_j(x,z+sv/\lambda)v\,\mathrm{d}s. \tag*{(23)}

Hessian Lipschitzness bounds the context Lipschitz constant by O(1+∥v∥)=O(κ)O(1+\lVert v\rVert)=O(\kappa) on ∥v∥≤2κ\lVert v\rVert\le2\kappa. Gradient Lipschitzness gives the global O(1)O(1) bound in vv. Strong monotonicity of BB then yields

∥v∗(x,z)−v∗(x′,z′)∥≲κ2(∥x−x′∥+∥z−z′∥).\lVert v^*(x,z)-v^*(x',z')\rVert\lesssim\kappa^2(\lVert x-x'\rVert+\lVert z-z'\rVert).

Combining these bounds proves the composite Lipschitz estimate for CC.

Proof of Lemma 2.1

Let z=z∗(x)z=z^*(x) and y=yλ∗(x)y=y^*_\lambda(x) be the unique minimizers in (4). The envelope formula gives

∇Hλ(x)=∇xf(x,y)+λ[∇xg(x,y)−∇xg(x,z)].\nabla H_\lambda(x)=\nabla_xf(x,y)+\lambda[\nabla_xg(x,y)-\nabla_xg(x,z)].

The optimality equations give v=λ(y−z)=v∗(x,z)v=\lambda(y-z)=v^*(x,z), proving (8). Lemma 4.1 bounds the Lipschitz constants of x↦v∗(x,z∗(x))x\mapsto v^*(x,z^*(x)) and ∇Hλ\nabla H_\lambda by O(κ3)O(\kappa^3).

To bound the bias, set H=∇yy2g(x,z)H=\nabla^2_{yy}g(x,z) and K=∇xy2g(x,z)K=\nabla^2_{xy}g(x,z). Taylor expansion of the lower gradient and Lipschitzness of the upper gradient imply

∥Hv+∇yf(x,z)∥≤∥v∥λ+∥v∥22λ≲κ2λ.\lVert Hv+\nabla_yf(x,z)\rVert\le\frac{\lVert v\rVert}{\lambda}+\frac{\lVert v\rVert^2}{2\lambda}\lesssim\frac{\kappa^2}{\lambda}.

Therefore

∥v+H−1∇yf(x,z)∥≲κ3λ.\lVert v+H^{-1}\nabla_yf(x,z)\rVert\lesssim\frac{\kappa^3}{\lambda}.

The implicit function theorem and the chain rule give

∇Φ(x)=∇xf(x,z)−KH−1∇yf(x,z).\nabla\Phi(x)=\nabla_xf(x,z)-KH^{-1}\nabla_yf(x,z).

Combining this identity with (A.2) for the xx block proves the bias bound in (5).

Evaluating the first minimum in (4) at zz gives Hλ≤ΦH_\lambda\le\Phi. Conversely, for every yy,

f(x,y)+λ[g(x,y)−g(x,z)]≥Φ(x)−∥y−z∥+λμ2∥y−z∥2≥Φ(x)−12λμ.f(x,y)+\lambda[g(x,y)-g(x,z)]\ge\Phi(x)-\lVert y-z\rVert+\frac{\lambda\mu}{2}\lVert y-z\rVert^2\ge\Phi(x)-\frac{1}{2\lambda\mu}.

Minimizing over yy proves the value bounds and Hλ(x0)−inf⁡Hλ≤Δ+κ/(2λ)H_\lambda(x_0)-\inf H_\lambda\le\Delta+\kappa/(2\lambda).

Local Curvature and Evaluation Martingales

Local inverse and correction error

Use the reference matrices of § 5 at the old inner point and new context: s=xs=x for AA, and s=(x,z)s=(x,z) for BB after the independent zz correction. The BB reference is the lower Hessian, with a 1/λ1/\lambda-Lipschitz gradient perturbation from ff.

Lemma B.1 (Local inverse). Let FF be the gradient of a globally μ0\mu_0-strongly convex differentiable potential, and let H⪰μ0IH \succeq\mu_0 I. Suppose throughout the Euclidean ball of radius rr about u0u_0 the map FF obeys

⟨F(u)−F(v),u−v⟩≥12∥u−v∥H2,∥F(u)−F(v)∥H−1≤2∥u−v∥H.\langle F(u)-F(v),u-v\rangle\ge\frac{1}{2}\lVert u-v\rVert_H^2,\qquad\lVert F(u)-F(v)\rVert_{H^{-1}} \le2\lVert u-v\rVert_H.

For twice differentiable potentials, Jacobians between H/2H/2 and 2H2H suffice. If

∥a∥H−1≤rμ0/16,\lVert a\rVert_{H^{-1}} \le r\sqrt{\mu_0}/16,

then the root of F(u)−F(u0)+a=0F(u)-F(u_0)+a=0 lies inside that ball and satisfies

∥u−u0∥H≤2∥a∥H−1.\lVert u-u_0\rVert_H \le2\lVert a\rVert_{H^{-1}}.

The same conclusion holds around another point strictly inside the ball when the indicated HH-ellipsoid remains in the ball.

Proof. Minimize the shifted potential on the HH-ellipsoid of radius rμ0/2r\sqrt{\mu_0}/2 about u0u_0, which lies in the Euclidean ball. On its boundary, with d=u−u0d=u-u_0,

⟨F(u)−F(u0)+a,d⟩≥12∥d∥H2−∥a∥H−1∥d∥H>0.\langle F(u)-F(u_0)+a,d\rangle\ge\frac{1}{2}\lVert d\rVert_H^2-\lVert a\rVert_{H^{-1}}\lVert d\rVert_H>0.

The minimizer is interior and hence is the unique global root by strong convexity. Applying the same inequality at this root gives the norm bound.

For one correction, condition on the contexts s0,s1s_0,s_1, starting point u0u_0, and correction hh before drawing its batch. Put pi=Fi(s1,u0)−Fi(s0,u0)p_i=F_i(s_1,u_0)-F_i(s_0,u_0), with ∥pi∥≤D\lVert p_i\rVert\le D. Let uˉ\bar{u} solve F(s1,uˉ)−F(s0,u0)+h=0F(s_1,\bar{u})-F(s_0,u_0)+h=0, and set dˉ=uˉ−u0\bar{d}=\bar{u}-u_0, Q=∥dˉ∥H2Q=\lVert\bar{d}\rVert_H^2. Each Fi(s1,⋅)F_i(s_1,\cdot) is a μ0\mu_0-strongly monotone gradient with Lipschitz constant at most two, where μ0≥1/(2κ)\mu_0\ge1/(2\kappa). Take symmetric references μ0I⪯Hi⪯2I\mu_0I\preceq H_i\preceq2I, H=EiHiH=\mathbb{E}_iH_i, such that for all u,vu,v in the local ball

∥Fi(s1,u)−Fi(s1,v)−Hi(u−v)∥≤μ032∥u−v∥.(24)\lVert F_i(s_1,u)-F_i(s_1,v)-H_i(u-v)\rVert\le\frac{\mu_0}{32}\lVert u-v\rVert. \tag*{(24)}

For AA and BB, the component lower Hessians satisfy (B.1) by Hessian Lipschitzness of gjg_j and the 1/λ1/\lambda gradient perturbation from fif_i.

Lemma B.2 (Curvature-weighted correction). Suppose the population corrected root lies in the inner quarter of the local ball and Q+D2Q+D^2 is small enough for the ellipsoids below to remain in that ball. Conditional on the fixed inputs, outside an event of probability at most Cdexp⁡(−cΛ)Cd\exp(-c\Lambda), the computed point uSu_S satisfies

E:=∥uS−uˉ∥H2≤CκΛb(Q+D2)+Cκ2τ2.(25)E:=\lVert u_S-\bar{u}\rVert_H^2\le C\frac{\kappa\Lambda}{b}(Q+D^2)+C\kappa^2\tau^2. \tag*{(25)}

Here the residual of the computed sampled solve is at most τ\tau, and b≥CκΛb\ge C\kappa\Lambda.

Proof. The matrices H−1/2HiH−1/2H^{-1/2}\mathcal{H}_iH^{-1/2} are positive semidefinite with mean II and norm at most 2/μ0≤4κ2/\mu_0 \le4\kappa. Matrix Chernoff [26] gives

34H⪯HS⪯54H\frac{3}{4}H \preceq\mathcal{H}_S \preceq\frac{5}{4}H

except with probability 2dexp⁡(−cb/κ)2d\exp(-cb/\kappa). By (B.1), the averaged remainder has dual norm at most ∥u−v∥H/32\lVert u-v\rVert_H/32, proving the empirical local inequalities of Lemma B.1.

At the population endpoint, set χi=Fi(s1,uˉ)−Fi(s1,u0)\chi_i=F_i(s_1,\bar{u})-F_i(s_1,u_0) and ζS=(pS−pˉ)+(χS−χˉ)\zeta_S=(p_S-\bar{p})+(\chi_S-\bar{\chi}). Both endpoints are fixed before SS. Co-coercivity and local comparison give Ei∥χi∥2≤2⟨χˉ,dˉ⟩≤4Q\mathbb{E}_i\lVert\chi_i\rVert^2\le2\langle\bar{\chi},\bar{d}\rangle\le4Q. Thus the centered summands ZiZ_i, whitened by H−1/2H^{-1/2}, satisfy

Ei∥Zi∥2≤Cκ(D2+Q),∥Zi∥≤CκD2+Q.\mathbb{E}_i\lVert Z_i\rVert^2\le C\kappa(D^2+Q),\qquad\lVert Z_i\rVert\le C\kappa\sqrt{D^2+Q}.

Here ∥dˉ∥≤2κQ\lVert\bar{d}\rVert\le\sqrt{2\kappa Q} and ∥H−1/2∥≤2κ\lVert H^{-1/2}\rVert\le\sqrt{2\kappa}. Vector Bernstein from rectangular matrix Freedman [25] gives

∥ζS∥H−1≤C(κΛb+κΛb)D2+Q.\lVert\zeta_S\rVert_{H^{-1}}\le C\left(\sqrt{\frac{\kappa\Lambda}{b}}+\frac{\kappa\Lambda}{b}\right)\sqrt{D^2+Q}.

The input bounds verified below place this residual below the local inverse threshold at uˉ\bar{u}. Lemma B.1 localizes the empirical root and bounds its HH-error by twice the displayed quantity. The solve error is at most 2κτ2\kappa\tau in Euclidean norm, proving (B.2). □

After the correction, write dt=ut−ut−1d_t=u_t-u_{t-1}, Jt=∥dt∥Ht2J_t=\lVert d_t\rVert_{H_t}^2, and ηt=Mt−Mt−1\eta_t=M_t-M_{t-1} for the independent evaluation error. The same conditional vector Bernstein calculation gives

Vt:=∥ηt∥Ht−12≤CκΛb(Jt+Dt2)(26)V_t:=\lVert\eta_t\rVert_{H_t^{-1}}^2\le\frac{C\kappa\Lambda}{b}(J_t+D_t^2) \tag*{(26)}

with the same failure bound, conditional on the completed correction before RtR_t. The unwhitened component increments have second moment at most C(Jt+Dt2)C(J_t+D_t^2) and norm at most Cκ(Jt+Dt2)C\sqrt{\kappa(J_t+D_t^2)}.

Evaluation martingales with a random energy budget

Lemma B.3 (Predictable energy peeling). Suppose an evaluation martingale is sampled in batches of size bb. Before batch tt, a nonnegative quantity WtW_t is known. Each of its bb centered, scaled summands has norm at most CκWt/bC\sqrt{\kappa W_t}/b, and the batch conditional second-moment sum is at most CWt/bCW_t/b. Suppose also ∑tWt≤Wmax⁡\sum_t W_t\le W_{\max} for a deterministically bounded stopped process. If b≥CκΛb\ge C\kappa\Lambda, then, simultaneously over epoch prefixes, except with a probability bounded by the union of O(log⁡(e+Wmax⁡/w0))O(\log(e+W_{\max}/w_0)) matrix-Freedman tails,

∥Mt∥2≤CΛb∑s≤tWs+ν2,w0=bν2C′Λ.(27)\lVert M_t\rVert^2\le\frac{C\Lambda}{b}\sum_{s\le t}W_s+\nu^2,\qquad w_0=\frac{b\nu^2}{C'\Lambda}. \tag*{(27)}

The constant C′C' is sufficiently large; enlarging the constant in the tail threshold if necessary gives each tail probability at most dexp⁡(−cΛ)d\exp(-c\Lambda).

Proof. At a deterministic level ww, stop before any batch that would raise cumulative WW above ww. This is predictable before its evaluation draws. The stopped increments are bounded by $C\sqrt{\kappa w}/b, with variance sum at most Cw/bCw/b. Rectangular matrix Freedman, applied to the vector as a dd-by-1 matrix, gives uniformly over prefixes

∥Mt∥≤C(wΛb+κwΛb)≤CwΛb.\lVert M_t\rVert\le C\left(\sqrt{\frac{w\Lambda}{b}}+\frac{\sqrt{\kappa w\Lambda}}{b}\right)\le C\sqrt{\frac{w\Lambda}{b}}.

Peel over w=w0,2w0,4w0,…w=w_0,2w_0,4w_0,\ldots beyond Wmax⁡W_{\max}. For each realized prefix, the first level above its energy gives the same stopped process up to that prefix. This level is at most twice the energy when the energy exceeds w0w_0; otherwise the bound is ν2\nu^2 for sufficiently large C′C'. A union bound proves (B.4).

For the two trackers take Wt=Dt2+JtW_t=D_t^2+J_t. For CC, take

WtC=κ2∥Δ(x,z)t∥2+∥Δvt∥2.W_t^C=\kappa^2\lVert\Delta(x,z)_t\rVert^2+\lVert\Delta v_t\rVert^2.

The unscaled centered increments have norm O(WtC)O(\sqrt{W_t^C}) and variance O(WtC)O(W_t^C). The independent draws in RtR_t, conditional on the correction, permit the individual-index filtration required by the lemma.

Localization and radius control

The two trackers use the following scales:

trackerinput bound Dmax⁡D_{\max}population energy bound Qmax⁡Q_{\max}actual displacement
Aθ\thetaaAκθ2a_A\kappa\theta^2CAκθC_A\kappa\theta
BCDκ2θC_D\kappa^2\thetaaBκ5θ2a_B\kappa^5\theta^2CBκ3θC_B\kappa^3\theta

Table B.3.

All constants are absolute.

Lemma B.4 (Localization and radius control). With the parameter choices above, there is an event TT of probability at least 1−δ1-\delta on which all inner residual tests and movement/radius checks pass throughout the TT steps. On this event, the table holds, consecutive reference metrics are comparable within a factor two, and (B.2), (B.3), and (B.4) hold for all relevant prefixes. The constants cθc_\theta, CλC_\lambda, cτc_\tau, cνc_\nu, CbC_b can be chosen independently of NN, κ\kappa, ε\varepsilon, dd.

Proof. Proceed in sampling order. For AA, use radius rA=1/(128κ)r_A=1/(128\kappa) about the old zz, giving component Hessian oscillation at most 1/(128κ)1/(128\kappa). For BB, use radius rB=8κr_B=8\kappa about the old vv. The lower and upper contributions to (B.1) have Lipschitz bounds 8κ/λ8\kappa/\lambda and 1/λ1/\lambda, whose sum is at most μ/128\mu/128 for large CλC_\lambda.

Assume the preceding bounds hold and ∥vt−1∥≤2κ\lVert v_{t-1}\rVert\le2\kappa. Then

F(st,uˉt)=Mt−1,F(st,ut)=Mt−1+kt,F^t=kt−ηt,(28)F(s_t,\bar{u}_t)=M_{t-1},\qquad F(s_t,u_t)=M_{t-1}+k_t,\qquad\widehat{F}_t=k_t-\eta_t, \tag*{(28)}

where et=ut−uˉte_t=u_t-\bar{u}_t includes the solve error and kt=F(st,ut)−F(st,uˉt)k_t=F(s_t,u_t)-F(s_t,\bar{u}_t) satisfies ∥kt∥Ht−1≤2∥et∥Ht\lVert k_t\rVert_{H_{t}^{-1}}\le2\lVert e_t\rVert_{H_t}.

Hence the next population forcing is

at+1=pˉt+1+kt−ηt.a_{t+1}=\bar{p}_{t+1}+k_t-\eta_t.

The preceding displacements bound consecutive reference differences by θ+CAκθ\theta+C_A\kappa\theta for AA. For BB, the bound is

θ+CAκθ+CBκ3θ/λ.\theta+C_A\kappa\theta+C_B\kappa^3\theta/\lambda.

Small cθc_{\theta} and large CλC_{\lambda} make these small multiples of μ\mu. Metric comparison and the bound on ktk_t give

∥at+1∥Ht+1−12≤C(κDt+12+Et+Vt).(29)\lVert a_{t+1}\rVert_{H_{t+1}^{-1}}^2 \le C(\kappa D_{t+1}^2+E_t+V_t). \tag*{(29)}

At an epoch start, the initial residual replaces the last two terms by O(κτ2)O(\kappa\tau^2). Put β=CκΛ/b\beta=C\kappa\Lambda/b. If the preceding population energy is at most Qmax⁡Q_{\max}, (B.2) and (B.3) give

Et≤β(Qmax⁡+Dmax⁡2)+Cκ2τ2,Jt≤2Qmax⁡+2Et,Vt≤β(Jt+Dmax⁡2).E_t\le\beta(Q_{\max}+D_{\max}^2)+C\kappa^2\tau^2,\qquad J_t\le2Q_{\max}+2E_t,\qquad V_t\le\beta(J_t+D_{\max}^2).

For AA, take Dmax⁡=θD_{\max}=\theta, choose aAa_A larger than twice the forcing constant, and take β\beta small enough to absorb its coefficient. Since κ2τ2≪κθ2\kappa^2\tau^2\ll\kappa\theta^2, the dual forcing is O(κθ)O(\sqrt{\kappa}\theta), below rAμ/2/16r_A\sqrt{\mu/2}/16 for small cθc_\theta. Lemma B.1 gives Qt≤aAκθ2Q_t\le a_A\kappa\theta^2 and localizes the population root. Lemma B.2 then localizes the empirical root and gives (B.2); small β,cτ\beta,c_\tau keep its ellipsoid inside the ball. Thus ∥Δzt∥≤CAκθ<1/(512κ)\lVert\Delta z_t\rVert\le C_A\kappa\theta<1/(512\kappa).

Conditional on this zz correction, draw StvS_t^v independently. The context bound gives DtB≤CDκ2θD_t^B\le C_D\kappa^2\theta. The same argument with large aBa_B bounds the dual forcing by O(κ5/2θ)O(\kappa^{5/2}\theta), population energy by aBκ5θ2a_B\kappa^5\theta^2, and displacement by CBκ3θC_B\kappa^3\theta. Since κ5/2θ=cθκ\kappa^{5/2}\theta=c_\theta\sqrt{\kappa} and rBμ/2≍κr_B\sqrt{\mu/2}\asymp\sqrt{\kappa}, these lie inside the BB ball. The curvature comparisons and concentration ellipsoids hold before the next evaluation batch.

To prove the radius, apply Lemma B.3 to the evaluation process stopped before any correction that has failed the preceding induction. On every active prefix,

∑s≤t(DB,s2+JB,s)≤Cqκ5θ2,∥MtB∥2≤CΛqκ5θ2b+ν2≤Ccθ2CbΛ+ν2.\sum_{s\le t}(D_{B,s}^2+J_{B,s})\le C_q\kappa^5\theta^2,\qquad\lVert M_t^B\rVert^2\le\frac{C\Lambda q\kappa^5\theta^2}{b}+\nu^2\le\frac{Cc_\theta^2}{C_b\Lambda}+\nu^2.

Choose the constants to make ∥MtB∥≤1/32\lVert M_t^B\rVert\le1/32. Strong monotonicity and the first identity of (B.5) imply

∥vˉt−v∗(xt,zt)∥≤2κ∥Mt−1B∥.\lVert\bar v_t-v^*(x_t,z_t)\rVert\le2\kappa\lVert M_{t-1}^B\rVert.

Furthermore, (B.2) and the energy cap give

∥etB∥≤Cβ κ3θ+Cκ3/2τ≤κ/16.\lVert e_t^B\rVert\le C\sqrt{\beta}\,\kappa^3\theta+C\kappa^{3/2}\tau\le\kappa/16.

Together with ∥v∗∥≤κ\lVert v^*\rVert\le\kappa, this gives ∥vt∥≤κ+κ/16+κ/16<2κ\lVert v_t\rVert\le\kappa+\kappa/16+\kappa/16<2\kappa, using only the preceding martingale value.

For the stopped process, suppress an evaluation before drawing RtR_t whenever its correction violates a local bound. If an evaluation inequality fails, include that evaluation and stop before the next correction. The draws remain conditionally centered, and active inputs have deterministic energy ceilings Cqκθ2C_q\kappa\theta^2, Cqκ5θ2C_q\kappa^5\theta^2, and Cqκ6θ2C_q\kappa^6\theta^2 for AA, BB, CC. Thus Lemma B.3 applies without conditioning on future events.

There are O(T)O(T) concentration events and epoch martingales. The polynomial energy ceilings and floor give O(log⁡(e+Wmax⁡/w0))=O(Λ)O(\log(e+W_{\max}/w_0))=O(\Lambda) peeling levels under (11)–(12). Conditional union bounds, with a large constant in each tail threshold, give total probability at most δ/2\delta/2. Allocate δ/2\delta/2 to capped solver failures. On the joint complement the induction continues throughout, agrees with the algorithm, and all safeguards pass.

Proof of the Epoch Estimate

Index within-epoch transitions by their endpoints, Δut=ut−ut−1\Delta u_t=u_t-u_{t-1}. The nonnegative final outer movement may be added to the right-hand side. Proof. Use the energies in (16) and VtV_t in (B.3). For one tracker the preceding lemmas give

Et≤β(Qt+Dt2)+Cκ2τ2,Jt≤2Qt+2Et,Vt≤β(Jt+Dt2),Qt≤CκDt2+CEt−1+CVt−1,\begin{aligned} E_t &\le\beta(Q_t + D_t^2) + C\kappa^2\tau^2, \qquad&J_t &\le2Q_t + 2E_t,\\ V_t &\le\beta(J_t + D_t^2), &Q_t &\le C\kappa D_t^2 + CE_{t-1} + CV_{t-1}, \end{aligned}

with an initial additive Cκτ2C\kappa\tau^2 and β=CκΛ/b\beta= C\kappa\Lambda/b. Summing and substituting the bounds for Et,Vt,JtE_t,V_t,J_t leaves a coefficient Cβ<1/2C\beta< 1/2 on ∑t(Qt+Jt)\sum_t(Q_t + J_t). Absorbing it gives, for U=∑tDt2U = \sum_t D_t^2,

∑t(Qt+Jt)≤CκU+Cκ2hτ2,∑t∥dt∥2≤Cκ2U+Cκ3hτ2.(30)\sum_t(Q_t + J_t) \le C\kappa U + C\kappa^2h\tau^2,\qquad\sum_t\lVert d_t\rVert^2 \le C\kappa^2U + C\kappa^3h\tau^2. \tag*{(30)}

The identity F(st,uˉt)=Mt−1F(s_t,\bar{u}_t) = M_{t-1} and strong monotonicity give

∥ut−u∗(st)∥2≤Cκ2∥Mt−1∥2+CκEt.\lVert u_t - u^*(s_t)\rVert^2 \le C\kappa^2\lVert M_{t-1}\rVert^2 + C\kappa E_t.

Insert (B.4) with Wt=Jt+Dt2W_t = J_t + D_t^2, sum over h≤qh \le q times, and use b≥CκqΛb \ge C\kappa q\Lambda:

∑t∥ut−u∗(st)∥2≤Cκ3qΛbU+Cκ3hτ2+Cκ2hν2.(31)\sum_t\lVert u_t - u^*(s_t)\rVert^2 \le C\frac{\kappa^3q\Lambda}{b}U + C\kappa^3h\tau^2 + C\kappa^2h\nu^2. \tag*{(31)}

For AA, UA≤X:=∑t∥Δxt∥2U_A \le X := \sum_t\lVert\Delta x_t\rVert^2. Hence

∑t∥Δzt∥2≤Cκ2X+Cκ3hτ2.\sum_t\lVert\Delta z_t\rVert^2 \le C\kappa^2X + C\kappa^3h\tau^2.

For BB, UB≤Cκ2∑t∥Δ(x,z)t∥2≤Cκ4X+Cκ5hτ2U_B \le C\kappa^2\sum_t\lVert\Delta(x,z)_t\rVert^2 \le C\kappa^4X + C\kappa^5h\tau^2. Equations (C.1) and (C.2) imply

∑t∥Δvt∥2≤Cκ6X+Cκ7hτ2,\sum_t\lVert\Delta v_t\rVert^2 \le C\kappa^6X + C\kappa^7h\tau^2,
∑t∥vt−v∗(xt,zt)∥2≤Cκ7qΛbX+Cκ7hτ2+Cκ2hν2.\sum_t\lVert v_t - v^*(x_t,z_t)\rVert^2 \le C\frac{\kappa^7q\Lambda}{b}X + C\kappa^7h\tau^2 + C\kappa^2h\nu^2.

The term κ8qhΛτ2/b\kappa^8qh\Lambda\tau^2/b arising in the substitution is at most Cκ7hτ2C\kappa^7h\tau^2 by the batch choice. For the CC evaluation martingale, peeling and the movement estimates give

∑t∥MtC∥2≤Cκ6qΛbX+Cκ6hτ2+Chν2.\sum_t\lVert M_t^C\rVert^2 \le C\frac{\kappa^6q\Lambda}{b}X + C\kappa^6h\tau^2 + Ch\nu^2.

Finally, Lemma 4.1 gives

∥G^t−∇Hλ(xt)∥≲∥MtC∥+∥vt−v∗(xt,zt)∥+κ2∥zt−z∗(xt)∥.\lVert\widehat{G}_t - \nabla H_\lambda(x_t)\rVert\lesssim\lVert M_t^C\rVert+ \lVert v_t - v^*(x_t,z_t)\rVert+ \kappa^2\lVert z_t - z^*(x_t)\rVert.

Squaring, summing, and applying the AA tracking bound with multiplier κ4\kappa^4 proves (18). The first full estimate has error at most Cκ3τC\kappa^3\tau, included in the tolerance term. Passing to the epoch’s input iterates discards only the unused final tracking estimate.

Accuracy of the Returned Point

Let et=G^t−∇Hλ(xt)e_t = \widehat{G}_t - \nabla H_\lambda(x_t) and let UU be the output set. Smoothness with LHα≤1/2L_H\alpha\le1/2, ⟨G^t,gt⟩≥∥gt∥2\langle\widehat{G}_t,g_t\rangle\ge\lVert g_t\rVert^2, and Young’s inequality give (19). Accuracy. On T\mathcal{T}, the tolerance term in (18) is at most c0hε2c_0h\varepsilon^2 for arbitrarily small c0c_0 by choosing cτ,cνc_\tau, c_\nu. The actual epoch lengths sum to TT, also when q>Tq>T. Since Δx=−αg\Delta x=-\alpha g,

Cα2κ7qΛ/b=Ccα2κqΛ/bC\alpha^2\kappa^7q\Lambda/b=Cc_\alpha^2\kappa q\Lambda/b

is sufficiently small. Summing the epoch estimates and (19), then absorbing the movement term, gives pathwise

∑t<T∥gt∥2≤CΔ‾Hα+Cc0Tε2,∑t<T∥et∥2≤CΔ‾Hα+Cc0Tε2.(32)\sum_{t<T}\|g_t\|^2\le C\frac{\overline{\Delta}H}{\alpha}+Cc_0T\varepsilon^2,\qquad\sum_{t<T}\|e_t\|^2\le C\frac{\overline{\Delta}H}{\alpha}+Cc_0T\varepsilon^2. \tag*{(32)}

Each clipped step contributes Γ2\Gamma^2 to the first sum. Since Γ≥10κ\Gamma\ge10\kappa and T≍CTκε−2T\asymp C_T\kappa\varepsilon^{-2}, large CTC_T and small c0c_0 give at most T/2T/2 clipped steps. Hence ∣U∣≥T/2|U|\ge T/2 pathwise on T\mathcal{T}. Conditional on the trajectory,

Eoutput∥∇Hλ(xout)∥2≤4T∑t<T(∥gt∥2+∥et∥2)≤CΔ‾HαT+Cc0ε2≤ε2/8.\mathbb{E}_{\mathrm{output}}\|\nabla H_\lambda(x_{\mathrm{out}})\|^2\le\frac{4}{T}\sum_{t<T}\left(\|g_t\|^2+\|e_t\|^2\right)\le C\frac{\overline{\Delta}H}{\alpha T}+Cc_0\varepsilon^2\le\varepsilon^2/8.

On every outcome, including failure, the returned point is either x0x_0 or an outer iterate within TθT\theta of x0x_0. Smoothness and lower boundedness imply

∥∇Hλ(x0)∥2≤2LHΔ‾H,∥∇Hλ(xout)∥2≤BT2.\|\nabla H_\lambda(x_0)\|^2\le2L_H\overline{\Delta}H,\qquad\|\nabla H_\lambda(x_{\mathrm{out}})\|^2\le B_T^2.

Thus Tc\mathcal{T}^c contributes at most δBT2≤ε2/64\delta B_T^2\le\varepsilon^2/64. Choose CλC_\lambda so that ∥∇Hλ−∇Φ∥≤ε/4\|\nabla H_\lambda-\nabla\Phi\|\le\varepsilon/4. The squared triangle inequality proves (13).

Inner Solves and Oracle Complexity

Each sampled problem has bb strongly convex, smooth components, so a capped accelerated finite-sum solve costs

O~(b+bκ)=O~(b).\widetilde{O}(b+\sqrt{b\kappa})=\widetilde{O}(b).

gradient calls, including residual verification. For failure probability p≤δ/(C(T+1))p\le\delta/(C(T+1)), run to mean objective gap at most pτ2/(2L)p\tau^2/(2L). The bound ∥∇ψ∥2≤2L(ψ−ψ∗)\|\nabla\psi\|^2\le2L(\psi-\psi^*) and Markov’s inequality give residual failure probability at most pp, at logarithmic extra cost.

For full BB solves, write the potential as the sum of the averages of

Pi(v)=λfi(x,z+v/λ)+μ8∥v∥2,P_i(v)=\lambda f_i(x,z+v/\lambda)+\frac{\mu}{8}\|v\|^2,
Qj(v)=λ2[gj(x,z+v/λ)−gj(x,z)]−λ⟨∇ygj(x,z),v⟩−μ8∥v∥2.Q_j(v)=\lambda^2\left[g_j(x,z+v/\lambda)-g_j(x,z)\right]-\lambda\langle\nabla_y g_j(x,z),v\rangle-\frac{\mu}{8}\|v\|^2.

For λ≥8κ\lambda\ge8\kappa, Pi,QjP_i,Q_j have strong convexity at least μ/8,3μ/4\mu/8,3\mu/4 and absolute smoothness constants: the nonquadratic part of PiP_i is 1/λ1/\lambda-weakly convex. The quadratics cancel between the averages. Let

rf=⌈N/n⌉,rg=⌈N/m⌉,M=nrf+mrg∈[2N,3N].r_f=\lceil N/n\rceil,\qquad r_g=\lceil N/m\rceil,\qquad M=nr_f+mr_g\in[2N,3N].

Average rfr_f copies of each (M/(nrf))Pi(M/(nr_f))P_i and rgr_g copies of each (M/(mrg))Qj(M/(mr_g))Q_j. The weights lie in [1,3][1,3], giving O(N)O(N) components of condition number O(κ)O(\kappa) and O(1)O(1) gradient cost. A common strongly convex quadratic may be reserved for the solver. For N>κN>\kappa, full epoch solves therefore cost

O~(N+Nκ)=O~(N).\widetilde{O}(N+\sqrt{N\kappa})=\widetilde{O}(N).

The caps are uniform over accepted histories. Between refreshes, the checks bound zz’s movement by O(q/κ)O(q/\kappa) and ∥v∥\lVert v\rVert by 2κ2\kappa. Paired increments cancel component linear offsets. The initial gradient of a shifted sampled BB problem is O(κq+τ)O(\kappa q+\tau); for AA it is polynomial in q,κq,\kappa. Strong convexity bounds initial gaps by squared gradient norms divided by μ\mu. Scheduled warm starts obey analogous bounds since Lip⁡(z∗)≤κ\operatorname{Lip}(z^*)\le\kappa and ∥v∗∥≤κ\lVert v^*\rVert\le\kappa. At initialization, a full gradient bounds the initial gap by its squared norm divided by twice the strong convexity parameter. Thus observed data fix the caps, with only logarithmic dependence on the initial residual or distance.

There are at most TT ordinary steps and 1+⌊T/q⌋1+\lfloor T/q\rfloor full starts. Failed checks terminate the run, so the capped cost is

O~(N+T(Nq+b))=O~(N+Nκ7/2ε−2).\widetilde{O}\left(N+T\left(\frac{N}{q}+b\right)\right)=\widetilde{O}\left(N+\sqrt{N}\kappa^{7/2}\varepsilon^{-2}\right).

This proves Theorem 5.1 for N>κN>\kappa.

The full-refresh regime and Proposition 3.1

Set q=1q=1 in Algorithm 1; no sampled corrections or recursive evaluations are performed. On the event that all full solves meet their residual tolerance, strong monotonicity gives

∥zt−z∗(xt)∥≤κτ,∥vt−v∗(xt,zt)∥≤2κτ.\lVert z_t-z^*(x_t)\rVert\le\kappa\tau,\qquad\lVert v_t-v^*(x_t,z_t)\rVert\le2\kappa\tau.

Lemma 4.1 therefore yields ∥G^t−∇Hλ(xt)∥≲κ3τ\lVert\widehat{G}_t-\nabla H_\lambda(x_t)\rVert\lesssim\kappa^3\tau. With τ=cτεκ−4\tau=c_\tau\varepsilon\kappa^{-4}, the error is an arbitrarily small multiple of ε\varepsilon. Appendix D, total solver failure probability δ\delta, and the same penalty bias give (3) in T=O(κ3ε−2)T=O(\kappa^3\varepsilon^{-2}) steps.

Each step costs O~(N+Nκ)\widetilde{O}(N+\sqrt{N\kappa}), including full gradients and residual checks, proving Proposition 3.1. For N≤κN\le\kappa,

Nκ3≤Nκ7/2,N\kappa^3\le\sqrt{N}\kappa^{7/2},

which proves Theorem 5.1 in the remaining regime.

Lower Bounds

Proof of Proposition 3.2

Let h=n−1∑ihih=n^{-1}\sum_i h_i be an individually 1-smooth finite sum with initial gap at most one. Set m=1m=1, n=N−1n=N-1, and

fi(x,y)=hi(x),g1(x,y)=12(y12+κ−1y22).f_i(x,y)=h_i(x),\qquad g_1(x,y)=\frac{1}{2}\left(y_1^2+\kappa^{-1}y_2^2\right).

All assumptions hold with normalized condition number exactly κ\kappa and Φ=h\Phi=h. Each upper query requires one component query to hh; lower replies are known. Theorem 3.1 of Peng et al. [22] gives Ω(n+nη−2)\Omega(n+\sqrt{n}\eta^{-2}) calls for unrestricted randomized queries and arbitrary outputs at sufficiently small constant failure probability. Since E∥∇h∥2≤ε2\mathbb{E}\lVert\nabla h\rVert^2\le\varepsilon^2 implies Pr⁡{∥∇h∥>aε}≤a−2\Pr\{\lVert\nabla h\rVert>a\varepsilon\}\le a^{-2} for fixed a>0a>0, take η=aε\eta=a\varepsilon with sufficiently large aa. The expected-budget extension covers random stopping. Substituting n=N−1n=N-1 proves the rate over worst-case decompositions of total size NN, rather than every prescribed (n,m)(n,m).

An unrestricted randomized joint lower bound

We modify the dense weak hiding chain of Peng et al. [22] to bound its average gradient, then amplify stationarity through an affine lower solution.

Proposition F.1 (Joint lower bound). There are absolute constants c,ε0>0c,\varepsilon_0>0 such that, for n≥1024n\ge1024, m≥1m\ge1, κ≥2\kappa\ge2, and 0<ε≤ε00<\varepsilon\le\varepsilon_0, every randomized component-gradient algorithm satisfying (3) on all problems obeying Assumptions 1–3, with Δ=1\Delta=1, has worst-case complexity at least

c(n+m+nκ2ε−2)(33)c\left(n+m+\sqrt{n\kappa^2\varepsilon^{-2}}\right) \tag*{(33)}

This holds for fixed and worst-case expected budgets, arbitrary adaptive component indices and query points, repeated queries, and arbitrary measurable outputs. Dimension may grow with the parameters and budget. For prescribed N=n+mN=n+m, take m=1m=1 to obtain Ω(N+Nκ2ε−2)\Omega\left(N+\sqrt{N\kappa^2\varepsilon^{-2}}\right) for N≥1025N\ge1025.

A bounded-gradient hidden chain. Use the independent encoding tables and gate of Peng et al. [22], Appendices A–C. For z=(z1,…,zK)z=(z_1,\ldots,z_K), zt∈RDz_t\in\mathbb{R}^D, set

Ψ(z)=z1+∥z∥2,qt(z)=⟨ut,Ψ(z)⟩,q~it(z)=ρ−1⟨sit,Ψ(z)⟩.\Psi(z)=\frac{z}{\sqrt{1+\lVert z\rVert^2}},\qquad q_t(z)=\langle u_t,\Psi(z)\rangle,\qquad\widetilde q_{it}(z)=\rho^{-1}\langle s_{it},\Psi(z)\rangle.

The unit sign vectors ut,situ_t,s_{it} satisfy n−1∑isit=ρutn^{-1}\sum_i s_{it}=\rho u_t. Choose the least parity-compatible integer mρ≥nm_\rho\ge\sqrt n and ρ=mρ/n\rho=m_\rho/n, giving n−1/2≤ρ<17/(16n)≤1/8n^{-1/2}\le\rho<17/(16\sqrt n)\le1/8. The nondecreasing gate GG obeys G=G′=0G=G'=0 below 5/325/32, G=1G=1 above 9/329/32, ∥G′∥∞≤17\lVert G'\rVert_\infty\le17, and ∥G′′∥∞≤259\lVert G''\rVert_\infty\le259. Replace the quadratic radial term by

H5(z)={∥z∥2/2,∥z∥≤5,5∥z∥−25/2,∥z∥>5,∇H5(z)=zmin⁡{1,5/∥z∥},H_5(z)= \begin{cases} \lVert z\rVert^2/2, & \lVert z\rVert\le5,\\ 5\lVert z\rVert-25/2, & \lVert z\rVert>5, \end{cases} \qquad\nabla H_5(z)=z\min\{1,5/\lVert z\rVert\},

with zero gradient at z=0z=0. For ℓ=33/16\ell=33/16, define

R~i(z)=−q~i1(z1)−∑t=2KG(qt−1(zt−1))(q~it(zt)+1)+ℓ∑t=1KH5(zt),R~=1n∑iR~i.(34)\widetilde R_i(z)=-\widetilde q_{i1}(z_1)-\sum_{t=2}^{K}G(q_{t-1}(z_{t-1}))(\widetilde q_{it}(z_t)+1)+\ell\sum_{t=1}^{K}H_5(z_t),\qquad\widetilde R=\frac{1}{n}\sum_i\widetilde R_i. \tag*{(34)}

Then

Lip⁡(∇R~i)≤H/ρ,R~(0)−inf⁡R~≤2K,\operatorname{Lip}(\nabla\widetilde R_i)\le H/\rho,\qquad\widetilde R(0)-\inf\widetilde R\le2K,
min⁡tqt(zt)<9/32 ⟹ ∥∇R~(z)∥≥χ,sup⁡z∥∇R~(z)∥≤46K,(35)\min_t q_t(z_t)<9/32\ \Longrightarrow\ \lVert\nabla\widetilde R(z)\rVert\ge\chi,\qquad\sup_z\lVert\nabla\widetilde R(z)\rVert\le46\sqrt K, \tag*{(35)}

where H=341H=341 and χ=((1−(9/32)2)2−ℓ(9/32))/1−(9/32)2>5/18\chi=((1-(9/32)^2)^2-\ell(9/32))/\sqrt{1-(9/32)^2}>5/18. The 1-Lipschitz Huber gradient preserves the H/ρH/\rho bound by the block-row argument of their Lemma C.3. The gap bound follows from −q1−∑t≥2G(qt−1)(qt+1)≥−2K-q_1-\sum_{t\ge2}G(q_{t-1})(q_t+1)\ge-2K, H5≥0H_5\ge0, and R~(0)=0\widetilde R(0)=0.

The first unfinished block has gradient ℓ∇H5(zt)−γt∇qt(zt)\ell\nabla H_5(z_t)-\gamma_t\nabla q_t(z_t), where 1≤γt≤351\le\gamma_t\le35. Their Lemma A.6 gives the lower bound χ\chi inside the radius-five ball; outside, ∥∇qt(zt)∥≤(1+∥zt∥2)−1/2\lVert\nabla q_t(z_t)\rVert\le(1+\lVert z_t\rVert^2)^{-1/2} gives 5ℓ−35/26>35\ell-35/\sqrt{26}>3. Each block gradient has norm at most 5ℓ+35<465\ell+35<46, proving the final bound under the Lipschitz upper-gradient assumption in Assumption 1.

For η>0\eta>0, set

β=ρχ8Hη,α=64Hη2ρχ2,K=⌈ρc∗η2⌉,Fi(y)=αR~i(βy),(36)\beta=\frac{\rho\chi}{8H\eta},\qquad\alpha=\frac{64H\eta^2}{\rho\chi^2},\qquad K=\left\lceil\frac{\rho}{c_*\eta^2}\right\rceil,\qquad F_i(y)=\alpha\widetilde R_i(\beta y), \tag*{(36)}

where 0<c∗≤χ2/(256H)0<c_*\le\chi^2/(256H) is an absolute constant. When K≥2K\ge2, (F.3) gives

Lip⁡(∇Fi)≤1,F(0)−inf⁡F≤12,sup⁡y∥∇F(y)∥≤462Hρ<1,F=1n∑iFi.\operatorname{Lip}(\nabla F_i)\le1,\qquad F(0)-\inf F\le\frac12,\qquad\sup_y\lVert\nabla F(y)\rVert\le\frac{46}{2\sqrt H}\sqrt\rho<1,\qquad F=\frac1n\sum_iF_i.

An unfinished block gives ∥∇F∥≥8η\lVert\nabla F\rVert\ge8\eta. The table-independent replacement preserves exact reply locality and conditions (R1)–(R4) of their Appendix § 11. Their optimized-bias Lemma B.2, Theorem B.5, Corollary B.6, and randomized conversion in Appendix § 15.§ 1 therefore give, for every randomized algorithm with at most c1nη−2c_1\sqrt{n}\eta^{-2} component calls, a fixed instance satisfying

Pr⁡{∥∇F(y^)∥≥4η}≥11/16.(37)\Pr\{\lVert\nabla F(\widehat{y})\rVert\ge4\eta\} \ge11/16. \tag*{(37)}

The imported information argument charges r=⌊n/512⌋r=\lfloor n/512\rfloor calls per revealed stage over K=Θ(1/(nη2))K=\Theta(1/(\sqrt{n}\eta^2)) stages, reserving the final stage for an output that need not have been queried. Their logarithmic choice of DD controls premature alignment at arbitrary query points; the argument thus applies to this modified chain, without asserting a theorem for arbitrary bounded-gradient functions.

Proof of Proposition F.1. Take μ=κ−1\mu=\kappa^{-1}, s=κ−1s=\kappa-1, and the construction above with η=ϵ/s\eta=\epsilon/s. Set

fi(x,y)=Fi(y),gj(x,y)=μ2∥y∥2−(1−μ)⟨x,y⟩(j=1,…,m).(38)f_i(x,y)=F_i(y), \qquad g_j(x,y)=\frac{\mu}{2}\lVert y\rVert^2-(1-\mu)\langle x,y\rangle\qquad(j=1,\ldots,m). \tag*{(38)}

Each fif_i is jointly 1-smooth, ∥∇yf∥≤1\lVert\nabla_y f\rVert\le1, and the lower Hessian is

(0−(1−μ)I−(1−μ)IμI).\begin{pmatrix} 0 & -(1-\mu)I \\ -(1-\mu)I & \mu I \end{pmatrix}.

Its eigenvalues (μ±μ2+4(1−μ)2)/2(\mu\pm\sqrt{\mu^2+4(1-\mu)^2})/2 have modulus at most one, and its yyyy block is μI\mu I. Lower smoothness, componentwise strong convexity, and Hessian Lipschitzness follow. Also y∗(x)=sxy^*(x)=sx, Φ(x)=F(sx)\Phi(x)=F(sx), and the initial gap is at most 1/21/2.

Simulate each upper query at (x,y)(x,y) by one query to FiF_i at yy; the known quadratic answers lower queries without accessing FF. Preserve private randomness and return y^=sxout\widehat{y}=sx_{\mathrm{out}}. Since ∇Φ(x)=s∇F(sx)\nabla\Phi(x)=s\nabla F(sx), (F.5) gives failure probability at least 11/1611/16 at threshold 4ϵ4\epsilon for budgets at most c1ns2ϵ−2c_1\sqrt{n}s^2\epsilon^{-2}. The iterative term follows from s≥κ/2s\ge\kappa/2. If K<2K<2, scaling gives nκ2ϵ−2=O(n)\sqrt{n}\kappa^2\epsilon^{-2}=O(n), covered by the linear bound below.

For the nn term, draw independent uniform i∗∈[n]i^*\in[n] and σ∈{−1,1}\sigma\in\{-1,1\}, and set

fi(x,y)=γ2x2−nτσ1{i=i∗}x,gj(x,y)=μ2y2,τ=2ϵ,γ=2ϵ2.f_i(x,y)=\frac{\gamma}{2}x^2-n\tau\sigma\mathbf{1}_{\{i=i^*\}}x,\qquad g_j(x,y)=\frac{\mu}{2}y^2,\qquad\tau=2\epsilon,\quad\gamma=2\epsilon^2.

All assumptions hold with gap τ2/(2γ)=1\tau^2/(2\gamma)=1. Until i∗i^* is queried, the sign is unknown and one sign gives ∣γx−τσ∣≥2ϵ|\gamma x-\tau\sigma|\ge2\epsilon at any output. With at most n/4n/4 calls, the index is missed with probability at least 3/43/4, giving gradient failure probability at least 3/83/8.

For the mm term, draw independent uniform j∗∈[m]j^*\in[m] and σ\sigma, and set

fi(x,y)=12H1(x−y),gj(x,y)=μ2y2−mμσ1{j=j∗}y,f_i(x,y)=\frac{1}{2}H_1(x-y),\qquad g_j(x,y)=\frac{\mu}{2}y^2-m\mu\sigma\mathbf{1}_{\{j=j^*\}}y,

where H1H_1 is the scalar radius-one Huber function. The joint upper gradient is one-Lipschitz, ∣∇yf∣≤1/2|\nabla_y f|\le1/2, y∗=σy^*=\sigma, and the gap is 1/41/4. Since ∇Φ(x)=12clip⁡(x−σ,[−1,1])\nabla\Phi(x)=\frac{1}{2}\operatorname{clip}(x-\sigma,[-1,1]), one sign has gradient magnitude 1/21/2 at any output. At most m/4m/4 calls give failure probability at least 3/83/8. Take ϵ0≤1/8\epsilon_0\le1/8 so that both needles contradict (3), and use that the maximum of three bounds is at least one third of their sum.

For worst-case expected budget BB, cap the algorithm at 32B32B calls. Markov’s inequality changes its output with probability at most 1/321/32. Subtracting this from the fixed-budget bounds gives expected squared gradients at least 16(11/16−1/32)ϵ216(11/16-1/32)\epsilon^2 for the amplified family and 4(3/8−1/32)ϵ24(3/8-1/32)\epsilon^2 for the upper needle. The lower needle has the same probability bound at threshold 1/21/2. Each contradicts (3); reducing the absolute constant proves the expected-budget claim. ∎

The square-root term uses the upper sum size nn; for m≫nm \gg n the construction gives no m\sqrt{m} term. When n≍Nn \asymp N, a factor κ3/2\kappa^{3/2} remains relative to SICBO’s upper bound. The conjectured joint κ5/2\kappa^{5/2} lower bound for unrestricted randomized algorithms remains open.

Details of the Numerical Experiments

Synthetic problem

In (20), ww is a random unit vector. Each HjH_j has eigenvalue 2μ+Ij/42\mu+I_j/4 along ww, with Pr⁡(Ij=1)=4μ\Pr(I_j=1)=4\mu, and independently rotated eigenvalues in [0.1,0.5][0.1,0.5] on the complement of ww. Thus the component Hessians do not commute. MM has random singular vectors and geometrically spaced singular values from 0.60.6 to 0.060.06; ∥Ej∥=0.08\lVert E_j\rVert=0.08; bjb_j, tit_i are Gaussian. Each gj(x,⋅)g_j(x,\cdot) is μ\mu-strongly convex with joint Hessian norm at most 0.940.94 and ∣ψ′′′∣≤μ\lvert\psi''' \rvert\le\sqrt{\mu}; each fif_i is 0.70.7-smooth with ∥∇yf∥<1\lVert\nabla_y f\rVert<1.

Katyusha uses Allen-Zhu [1]’s parameters and snapshots for residual checks; the exact ∇Φ\nabla\Phi used for plotting is uncounted. Relative to (11), we use α=1/L^\alpha=1/\widehat{L} with a sampled estimate L^\widehat{L} of Lip⁡(∇Φ)\operatorname{Lip}(\nabla\Phi), replace CbΛ2C_b\Lambda^2 by 11, and monitor safeguards without enforcing them. The zz displacement bound was exceeded on 55–90% of sampled steps; the vv bound always held and clipping never activated. Full-refresh and SICBO costs average ten seeds. The ratio of full-refresh to SICBO cost per outer iteration decreases with κ\kappa approximately in proportion to N/κ\sqrt{N}/\kappa.

Real data

For (21), a9a and w8a use 5,000 validation rows and the remainder for training; ijcnn1 uses its training and test files [6, 7]. At the tested κ\kappa, ∇yy2gj⪯(1/4+10μ)I⪯I\nabla^2_{yy}g_j\preceq(1/4+10\mu)I\preceq I and ∥∇yf∥≤1\lVert\nabla_y f\rVert\le1. Strong convexity and ∥∇yg(x,0)∥≤1/2\lVert\nabla_y g(x,0)\rVert\le1/2 give ∥y∗(x)∥≤κ/2\lVert y^*(x)\rVert\le\kappa/2. The joint Hessian of gjg_j contains rk′(x)ykr_k'(x)y_k and 12rk′′(x)yk2\frac{1}{2}r_k''(x)y_k^2, which are unbounded over yy. Hence Assumption 1 fails globally, and the experiments lie outside the normalized theoretical class. The choice rk(x)=exkr_k(x)=e^{x_k} in Dagréou et al. [6, 7] does not permit prescribed κ\kappa.

We use τ=max⁡{ϵκ−4,10−11}\tau=\max\{\epsilon\kappa^{-4},10^{-11}\} and α=c/L^\alpha=c/\widehat{L}, choosing c∈{1/4,1/2,1,2,4}c\in\{1/4,1/2,1,2,4\} for each method and setting by the median cost over three seeds (one for deterministic methods). The selected value was c=4c=4 in every setting: the bounded regularizers saturate and ∥∇Φ(xt)∥\lVert\nabla\Phi(x_t)\rVert decays roughly as 1/(αt)1/(\alpha t). The penalty methods stop after three times SICBO’s mean cost at c=1c=1; the penalty method never reached the target, and its accelerated variant reached it only on a9a and w8a. The accelerated penalty method and full-refresh benchmark approximate the same population outer update, with comparable per-iteration costs at κ=100\kappa=100 and differing by roughly 10\sqrt{10} at κ=1000\kappa=1000 (Table 1). Movement and radius safeguards were monitored without enforcement. The zz displacement bound was exceeded on 78–100% of SICBO’s sampled steps; the vv bound always held and clipping never activated.

For data hyper-cleaning on a9a, we flip 30% of training labels and use gj(x,y)=ϕ(bj⟨aj,y⟩)/(1+e−xj)+μ2∥y∥2g_j(x,y)=\phi(b_j\langle a_j,y\rangle)/(1+e^{-x_j})+\frac{\mu}{2}\lVert y\rVert^2 with x∈Rmx\in\mathbb{R}^m and fif_i from (21). SICBO needed the fewest calls at both values of κ\kappa. Each CijC_{ij} is supported on coordinate jj; a sampled correction changes at most bb of the mm coordinates of G^t\widehat{G}_t, yielding substantial departures from exact gradient descent. These objectives also fail global joint smoothness in Assumption 1.

References

  1. [1]Zeyuan Allen-Zhu. Katusha: The first direct acceleration of stochastic gradient methods. Journal of Machine Learning Research, 18(221):1–51, 2018.
  2. [2]Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2(3):27:1–27:27, 2011.
  3. [3]Lesi Chen, Yaohua Ma, and Jingzhao Zhang. Near-optimal nonconvex-strongly-convex bilevel optimization with fully first-order oracles. Journal of Machine Learning Research, 26(109):1–56, 2025.
  4. [4]Lesi Chen, Kaiyi Ji, and Jingzhao Zhang. On the condition number dependency in bilevel optimization. arXiv preprint arXiv:2511.22331v4, 2026.arxiv.org/abs/2511.22331
  5. [5]Tianshu Chu, Dachuan Xu, Wei Yao, and Jin Zhang. SPABA: A single-loop and probabilistic stochastic bilevel algorithm achieving optimal sample complexity. In Proceedings of the 41st International Conference on Machine Learning, 235, pages 8848–8903, 2024.arxiv.org/abs/2405.18777
  6. [6]Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. In Advances in Neural Information Processing Systems, 35, 2022.
  7. [7]Mathieu Dagréou, Thomas Moreau, Samuel Vaiter, and Pierre Ablin. A lower bound and a near-optimal algorithm for bilevel empirical risk minimization. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics, 238, pages 82–90, 2024.arxiv.org/abs/2302.08766
  8. [8]Cong Fang, Chris Junchi Li, Zhоуchen Lin, and Tong Zhang. SPIDER: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems, 31, 2018.
  9. [9]Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In Proceedings of the 35th International Conference on Machine Learning, 80, pages 1568–1577, 2018.arxiv.org/abs/1806.04910
  10. [10]Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02246, 2018.arxiv.org/abs/1802.02246
  11. [11]Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran 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.DOI
  12. [12]Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In Proceedings of the 38th International Conference on Machine Learning, 139, pages 4882–4892, 2021.
  13. [13]Kaiyi Ji and Yingbin Liang. Lower bounds and accelerated algorithms for bilevel optimization. Journal of Machine Learning Research, 24(22):1–56, 2023.
  14. [14]Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, 26, pages 315–323, 2013.
  15. [15]Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A near-optimal algorithm for stochastic bilevel optimization via double-momentum. In Advances in Neural Information Processing Systems, 34, 2021.arxiv.org/abs/2102.07367
  16. [16]Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert D. Nowak. A fully first-order method for stochastic bilevel optimization. In Proceedings of the 40th International Conference on Machine Learning, 202, pages 18083–18113, 2023.arxiv.org/abs/2301.10945
  17. [17]Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert D. Nowak. On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. In International Conference on Learning Representations, 2024.arxiv.org/abs/2309.01753
  18. [18]Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In Proceedings of the 38th International Conference on Machine Learning, 139, pages 6286–6295, 2021.arxiv.org/abs/2008.10898
  19. [19]Bo Liu, Mao Ye, Stephen Wright, Peter Stone, and Qiang Liu. BOME! Bilevel optimization made easy: A simple first-order approach. In Advances in Neural Information Processing Systems, 35, 2022.arxiv.org/abs/2209.08709
  20. [20]Lam M. Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. SARAH: A novel method for machine learning problems using stochastic recursive gradient. In Proceedings of the 34th International Conference on Machine Learning, 70, pages 2613–2621, 2017.arxiv.org/abs/1703.00102
  21. [21]Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In Proceedings of the 33rd International Conference on Machine Learning, 48, pages 737–746, 2016.arxiv.org/abs/1602.02355
  22. [22]Yuxing Peng, Zhiqing Tang, and Weijia Jia. Dense weak hiding: Closing complexity gaps in nonconvex and PL finite-sum optimization under individual smoothness. arXiv preprint arXiv:2609.00454v2, 2026.
  23. [23]Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun. Learning to reweight examples for robust deep learning. In Proceedings of the 35th International Conference on Machine Learning, 80, pages 4334–4343, 2018.
  24. [24]Han Shen and Tianyi Chen. On penalty-based bilevel gradient descent method. In Proceedings of the 40th International Conference on Machine Learning, 202, pages 30992–31015, 2023.arxiv.org/abs/2302.05185
  25. [25]Joel A. Tropp. Freedman’s inequality for matrix martingales. Electronic Communications in Probability, 16:262–270, 2011.arxiv.org/abs/1101.3039
  26. [26]Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12:389–434, 2012.DOI
  27. [27]Junjie Yang, Kaiyi Ji, and Yingbin Liang. Probably faster algorithms for bilevel optimization. In Advances in Neural Information Processing Systems, 34, 2021.arxiv.org/abs/2106.04692

Paper details

vlnc:W_p8be86zd
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Codex with GPT-6 Astra, Claude Science Opus 5.5

View statement
Looking for related papers…
Contents