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 satisfying within component-gradient calls, where 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 with batches of size . A single-level reduction shows that the dependence on and is optimal up to logarithmic factors for fixed .
Introduction
We study the finite-sum bilevel optimization problem
where and . The lower objective is strongly convex in , and may be nonconvex. Such problems arise when an upper variable is selected through the solution of a training problem. We write and count individual component-gradient evaluations.
The gradient of , 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 [4].
Implementing these deterministic methods on (1) by full gradients adds a factor . Accelerated finite-sum solvers reduce the inner minimization cost, but a full pass at every outer iteration still contributes . This term exceeds the desired finite-sum rate when .
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
The bound combines gradient-only access, square-root finite-sum dependence, and the 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 and up to logarithms for fixed ; a matching bound in 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 as predicted by the amortized cost (§ 6).
Table 1: Component-gradient complexity for achieving (3). All expressions display the dependence on , , and ; 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.
| Method | Component-gradient complexity |
| Penalty method of Chen et al. [3] | |
| Accelerated penalty method [4] | |
| Full refresh with accelerated finite-sum solves (Proposition 3.1) | |
| SICBO (Theorem 5.1) |
Table 1.
Preliminaries
We use for the Euclidean norm of vectors and the induced operator norm of matrices. For a positive definite matrix , let . We write to suppress an absolute constant and to suppress logarithmic factors. All polynomial dependence on , , and is explicit. We impose the following assumptions on the whole space.
Assumption 1 (Component smoothness). Each has a 1-Lipschitz continuous gradient. Each is twice continuously differentiable, its gradient is 1-Lipschitz continuous, and its Hessian is 1-Lipschitz continuous. These Lipschitz conditions apply jointly to .
Assumption 2 (Lower strong convexity). For every and , the function is -strongly convex, where . We define .
Assumption 3 (Upper gradient and initial gap). The average objective satisfies for all . Furthermore, is bounded below and the initial point satisfies , where a known upper bound 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 alone does not ensure this property. We require neither bounded component-gradient variance nor Hessian smoothness of .
Our goal is to produce a random point such that
One oracle call returns or at a specified index and point, so a full gradient costs calls. The oracles are exact; arithmetic precision is excluded from the complexity.
For , define the penalty value function
The following lemma gives the approximation error and smoothness of . Its proof appears in Appendix § 10.
Lemma 2.1 (Penalty approximation). Under Assumptions [1, 2, 3],
In particular, the initial gap of is at most .
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 . Accelerated inner solves improve this bound to [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 under (3), including initialization and suppressing other problem constants, with gradient and Hessian/Jacobian-vector oracles. Its dependence is not explicit. Our bound uses only component gradients and gives explicit dependence, under the stronger assumptions of componentwise lower strong convexity and globally bounded average .
Accelerated finite-sum minimization. Katyusha [1] solves a smooth, strongly convex finite sum with components and condition number in 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
For , this is bounded by (2).
The proof appears in Appendix Appendix § 14. For , SICBO improves the iterative cost by a factor . 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 and .
Proposition 3.2 (Optimal dependence for fixed condition number). For every fixed , sufficiently large , and sufficiently small , the worst-case component-gradient complexity of (3) under Assumptions [1, 2, 3], with , is at least .
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 and for fixed . Dagréou et al. [7, Theorem 2] previously proved an bound for a restricted class of linear bilevel algorithms, where is our upper-level sum size. Their regime is with other constants fixed, and their result does not characterize dependence.
For condition-number dependence, Chen et al. [4, Theorem 4.1] prove an bound for deterministic first-order algorithms with quadratic lower objectives. Their class does not impose our global bound on , so the result does not directly apply here. Appendix Appendix § 15 gives further lower bounds under our assumptions. The sharp joint dependence on and remains open; separate lower bounds do not establish a product bound.
The SICBO Method
Scaled gradient differences
Let approximate and introduce . For , define
Write , , for the population means and , , for sample averages, with . Each batch samples independent uniform pairs with replacement, and ignores . Each lower-gradient difference uses the same index . Computing full means costs calls.
Let and let be the unique root of . At these roots,
The scaling makes the inner condition number independent of : each is the gradient of a strongly convex potential with condition number . The following lemma gives the field regularity.
Algorithm 1 SICBO: Sampled Implicit Corrections for Bilevel Optimization
Input: , , ; , , , , , , .
for do
if then
Run Katyusha in until .
Run Katyusha in until .
.
end if
.
.
if and then
Draw ; run Katyusha in until .
Draw ; run Katyusha in until .
Draw ; set .
end if
end for
.
return with , or if .
Lemma 4.1 (Field regularity). For , is -strongly monotone and -Lipschitz. Moreover,
On , each and is -Lipschitz in and -Lipschitz in . Consequently, is -Lipschitz.
The proof appears in Appendix § 10. The fields in (7) require only component gradients.
Sampled implicit corrections
SICBO maintains , and the field estimates . Write . Each epoch begins with population inner updates and full field evaluations. Between refreshes, SICBO updates , then , then , using the residual maps
We use capped Katyusha iterations to obtain and then, with fixed, . Each residual is the gradient of a strongly convex objective. Every batch contains fresh, independent uniform index pairs. The evaluation batch is drawn after both corrections, making its increments conditionally centered at the updated points.
The first inner solves start at and later solves at the preceding iterates. We cap every solve and check its residual. Sampled updates must also satisfy and . A failed test returns . The output set 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 , we set and recover the full-refresh benchmark.
Complexity Analysis
Parameters and main result
For , choose
Here is used only in the analysis. To specify the confidence level, put , , and
All constants are absolute. We choose small and large, then , then small and large, and finally large. In particular, and every outer displacement is at most . Each inner solve receives failure probability at most for a sufficiently large absolute .
Theorem 5.1 (Component-gradient complexity). Under Assumptions 1–3, SICBO (Algorithm 1), with (11)–(12) for and for , returns a point satisfying
within
component-gradient calls. For , 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 , giving the amortized cost
Balancing the terms gives and cost per step. Together with , this proves (14). An additional polynomial factor of 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 and let
These matrices are used only in the analysis. For a tracker , let be the population corrected root, its sampled approximation, and . Define
Let bound the component change caused by the new context at the old inner point. Conditional concentration and local curvature comparison give
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 . Predictable stopping and peeling bound by the realized energy . Combining this bound with (17) gives the following lemma.
Lemma 5.2 (Epoch error). There is an event with probability at least on which all safeguards pass and, for every epoch of actual length ,
The inequality holds pathwise on .
The proof appears in Appendices § 11–§ 12. Let be the outer squared movement over an epoch and omit tolerance terms. The first tracker gives . The second then receives context energy and contributes error . The recursive error in C is .
For the descent argument, smoothness gives
Substituting (18) gives the movement coefficient , which is small enough to absorb. The resulting bound ensures at least unclipped steps on , controlling the denominator in uniform sampling from . Clipping bounds the gradient at any returned point by , so contributes at most . Lemma 2.1 transfers stationarity from to .
Numerical Experiments
We compare practical implementations of the four methods in Table 1. All use with and outer updates . The two penalty methods use full-pass gradient descent and accelerated gradient descent, respectively. The full-refresh method uses in Algorithm 1; SICBO uses and . We set 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 , so that , , and . The components are
where the component Hessians do not commute and for a fixed matrix (Appendix § 16.§ 1). All methods use a common step , and the target is .
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 . Its advantage over the full-refresh benchmark decreases at the rate predicted by (15) (Appendix § 16.§ 1).
Figure 1. Running minimum of 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 and be the training and validation rows, respectively, with and labels in . Define and
so sets one ridge weight per feature. We use the LIBSVM data sets a9a, w8a and ijcnn1 [2], with from to , and . The inner tolerance is . 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 (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 , where the accelerated penalty method has similar cost. On each data set, SICBO’s advantage over full refresh decreases from to and remains nearly the same fraction of , consistent with (15) (Appendix § 16.§ 2).
Figure 2. Running minimum of 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 is optimal up to logarithms in and for fixed 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 . Extending the result to average lower strong convexity, obtaining a single-loop method, and establishing the sharp joint dependence on and 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 , the field is the gradient of
The first term is -smooth and -weakly convex; the second is -strongly convex and -smooth. Thus is -strongly convex and -smooth, giving the claimed constants for .
Let . The population root equation gives
Taking the inner product with , strong convexity and Assumption [3] give . Comparing the optimality equations at also gives .
For , the fundamental theorem of calculus gives
Hessian Lipschitzness bounds the context Lipschitz constant by on . Gradient Lipschitzness gives the global bound in . Strong monotonicity of then yields
Combining these bounds proves the composite Lipschitz estimate for .
Proof of Lemma 2.1
Let and be the unique minimizers in (4). The envelope formula gives
The optimality equations give , proving (8). Lemma 4.1 bounds the Lipschitz constants of and by .
To bound the bias, set and . Taylor expansion of the lower gradient and Lipschitzness of the upper gradient imply
Therefore
The implicit function theorem and the chain rule give
Combining this identity with (A.2) for the block proves the bias bound in (5).
Evaluating the first minimum in (4) at gives . Conversely, for every ,
Minimizing over proves the value bounds and .
Local Curvature and Evaluation Martingales
Local inverse and correction error
Use the reference matrices of § 5 at the old inner point and new context: for , and for after the independent correction. The reference is the lower Hessian, with a -Lipschitz gradient perturbation from .
Lemma B.1 (Local inverse). Let be the gradient of a globally -strongly convex differentiable potential, and let . Suppose throughout the Euclidean ball of radius about the map obeys
For twice differentiable potentials, Jacobians between and suffice. If
then the root of lies inside that ball and satisfies
The same conclusion holds around another point strictly inside the ball when the indicated -ellipsoid remains in the ball.
Proof. Minimize the shifted potential on the -ellipsoid of radius about , which lies in the Euclidean ball. On its boundary, with ,
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 , starting point , and correction before drawing its batch. Put , with . Let solve , and set , . Each is a -strongly monotone gradient with Lipschitz constant at most two, where . Take symmetric references , , such that for all in the local ball
For and , the component lower Hessians satisfy (B.1) by Hessian Lipschitzness of and the gradient perturbation from .
Lemma B.2 (Curvature-weighted correction). Suppose the population corrected root lies in the inner quarter of the local ball and is small enough for the ellipsoids below to remain in that ball. Conditional on the fixed inputs, outside an event of probability at most , the computed point satisfies
Here the residual of the computed sampled solve is at most , and .
Proof. The matrices are positive semidefinite with mean and norm at most . Matrix Chernoff [26] gives
except with probability . By (B.1), the averaged remainder has dual norm at most , proving the empirical local inequalities of Lemma B.1.
At the population endpoint, set and . Both endpoints are fixed before . Co-coercivity and local comparison give . Thus the centered summands , whitened by , satisfy
Here and . Vector Bernstein from rectangular matrix Freedman [25] gives
The input bounds verified below place this residual below the local inverse threshold at . Lemma B.1 localizes the empirical root and bounds its -error by twice the displayed quantity. The solve error is at most in Euclidean norm, proving (B.2). □
After the correction, write , , and for the independent evaluation error. The same conditional vector Bernstein calculation gives
with the same failure bound, conditional on the completed correction before . The unwhitened component increments have second moment at most and norm at most .
Evaluation martingales with a random energy budget
Lemma B.3 (Predictable energy peeling). Suppose an evaluation martingale is sampled in batches of size . Before batch , a nonnegative quantity is known. Each of its centered, scaled summands has norm at most , and the batch conditional second-moment sum is at most . Suppose also for a deterministically bounded stopped process. If , then, simultaneously over epoch prefixes, except with a probability bounded by the union of matrix-Freedman tails,
The constant is sufficiently large; enlarging the constant in the tail threshold if necessary gives each tail probability at most .
Proof. At a deterministic level , stop before any batch that would raise cumulative above . This is predictable before its evaluation draws. The stopped increments are bounded by $C\sqrt{\kappa w}/b, with variance sum at most . Rectangular matrix Freedman, applied to the vector as a -by-1 matrix, gives uniformly over prefixes
Peel over beyond . 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 ; otherwise the bound is for sufficiently large . A union bound proves (B.4).
For the two trackers take . For , take
The unscaled centered increments have norm and variance . The independent draws in , conditional on the correction, permit the individual-index filtration required by the lemma.
Localization and radius control
The two trackers use the following scales:
| tracker | input bound | population energy bound | actual displacement |
| A | |||
| B |
Table B.3.
All constants are absolute.
Lemma B.4 (Localization and radius control). With the parameter choices above, there is an event of probability at least on which all inner residual tests and movement/radius checks pass throughout the 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 , , , , can be chosen independently of , , , .
Proof. Proceed in sampling order. For , use radius about the old , giving component Hessian oscillation at most . For , use radius about the old . The lower and upper contributions to (B.1) have Lipschitz bounds and , whose sum is at most for large .
Assume the preceding bounds hold and . Then
where includes the solve error and satisfies .
Hence the next population forcing is
The preceding displacements bound consecutive reference differences by for . For , the bound is
Small and large make these small multiples of . Metric comparison and the bound on give
At an epoch start, the initial residual replaces the last two terms by . Put . If the preceding population energy is at most , (B.2) and (B.3) give
For , take , choose larger than twice the forcing constant, and take small enough to absorb its coefficient. Since , the dual forcing is , below for small . Lemma B.1 gives and localizes the population root. Lemma B.2 then localizes the empirical root and gives (B.2); small keep its ellipsoid inside the ball. Thus .
Conditional on this correction, draw independently. The context bound gives . The same argument with large bounds the dual forcing by , population energy by , and displacement by . Since and , these lie inside the 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,
Choose the constants to make . Strong monotonicity and the first identity of (B.5) imply
Furthermore, (B.2) and the energy cap give
Together with , this gives , using only the preceding martingale value.
For the stopped process, suppress an evaluation before drawing 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 , , and for , , . Thus Lemma B.3 applies without conditioning on future events.
There are concentration events and epoch martingales. The polynomial energy ceilings and floor give peeling levels under (11)–(12). Conditional union bounds, with a large constant in each tail threshold, give total probability at most . Allocate 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, . The nonnegative final outer movement may be added to the right-hand side. Proof. Use the energies in (16) and in (B.3). For one tracker the preceding lemmas give
with an initial additive and . Summing and substituting the bounds for leaves a coefficient on . Absorbing it gives, for ,
The identity and strong monotonicity give
Insert (B.4) with , sum over times, and use :
For , . Hence
For , . Equations (C.1) and (C.2) imply
The term arising in the substitution is at most by the batch choice. For the evaluation martingale, peeling and the movement estimates give
Finally, Lemma 4.1 gives
Squaring, summing, and applying the tracking bound with multiplier proves (18). The first full estimate has error at most , 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 and let be the output set. Smoothness with , , and Young’s inequality give (19). Accuracy. On , the tolerance term in (18) is at most for arbitrarily small by choosing . The actual epoch lengths sum to , also when . Since ,
is sufficiently small. Summing the epoch estimates and (19), then absorbing the movement term, gives pathwise
Each clipped step contributes to the first sum. Since and , large and small give at most clipped steps. Hence pathwise on . Conditional on the trajectory,
On every outcome, including failure, the returned point is either or an outer iterate within of . Smoothness and lower boundedness imply
Thus contributes at most . Choose so that . The squared triangle inequality proves (13).
Inner Solves and Oracle Complexity
Each sampled problem has strongly convex, smooth components, so a capped accelerated finite-sum solve costs
gradient calls, including residual verification. For failure probability , run to mean objective gap at most . The bound and Markov’s inequality give residual failure probability at most , at logarithmic extra cost.
For full solves, write the potential as the sum of the averages of
For , have strong convexity at least and absolute smoothness constants: the nonquadratic part of is -weakly convex. The quadratics cancel between the averages. Let
Average copies of each and copies of each . The weights lie in , giving components of condition number and gradient cost. A common strongly convex quadratic may be reserved for the solver. For , full epoch solves therefore cost
The caps are uniform over accepted histories. Between refreshes, the checks bound ’s movement by and by . Paired increments cancel component linear offsets. The initial gradient of a shifted sampled problem is ; for it is polynomial in . Strong convexity bounds initial gaps by squared gradient norms divided by . Scheduled warm starts obey analogous bounds since and . 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 ordinary steps and full starts. Failed checks terminate the run, so the capped cost is
This proves Theorem 5.1 for .
The full-refresh regime and Proposition 3.1
Set 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
Lemma 4.1 therefore yields . With , the error is an arbitrarily small multiple of . Appendix D, total solver failure probability , and the same penalty bias give (3) in steps.
Each step costs , including full gradients and residual checks, proving Proposition 3.1. For ,
which proves Theorem 5.1 in the remaining regime.
Lower Bounds
Proof of Proposition 3.2
Let be an individually 1-smooth finite sum with initial gap at most one. Set , , and
All assumptions hold with normalized condition number exactly and . Each upper query requires one component query to ; lower replies are known. Theorem 3.1 of Peng et al. [22] gives calls for unrestricted randomized queries and arbitrary outputs at sufficiently small constant failure probability. Since implies for fixed , take with sufficiently large . The expected-budget extension covers random stopping. Substituting proves the rate over worst-case decompositions of total size , rather than every prescribed .
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 such that, for , , , and , every randomized component-gradient algorithm satisfying (3) on all problems obeying Assumptions 1–3, with , has worst-case complexity at least
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 , take to obtain for .
A bounded-gradient hidden chain. Use the independent encoding tables and gate of Peng et al. [22], Appendices A–C. For , , set
The unit sign vectors satisfy . Choose the least parity-compatible integer and , giving . The nondecreasing gate obeys below , above , , and . Replace the quadratic radial term by
with zero gradient at . For , define
Then
where and . The 1-Lipschitz Huber gradient preserves the bound by the block-row argument of their Lemma C.3. The gap bound follows from , , and .
The first unfinished block has gradient , where . Their Lemma A.6 gives the lower bound inside the radius-five ball; outside, gives . Each block gradient has norm at most , proving the final bound under the Lipschitz upper-gradient assumption in Assumption 1.
For , set
where is an absolute constant. When , (F.3) gives
An unfinished block gives . 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 component calls, a fixed instance satisfying
The imported information argument charges calls per revealed stage over stages, reserving the final stage for an output that need not have been queried. Their logarithmic choice of 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 , , and the construction above with . Set
Each is jointly 1-smooth, , and the lower Hessian is
Its eigenvalues have modulus at most one, and its block is . Lower smoothness, componentwise strong convexity, and Hessian Lipschitzness follow. Also , , and the initial gap is at most .
Simulate each upper query at by one query to at ; the known quadratic answers lower queries without accessing . Preserve private randomness and return . Since , (F.5) gives failure probability at least at threshold for budgets at most . The iterative term follows from . If , scaling gives , covered by the linear bound below.
For the term, draw independent uniform and , and set
All assumptions hold with gap . Until is queried, the sign is unknown and one sign gives at any output. With at most calls, the index is missed with probability at least , giving gradient failure probability at least .
For the term, draw independent uniform and , and set
where is the scalar radius-one Huber function. The joint upper gradient is one-Lipschitz, , , and the gap is . Since , one sign has gradient magnitude at any output. At most calls give failure probability at least . Take 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 , cap the algorithm at calls. Markov’s inequality changes its output with probability at most . Subtracting this from the fixed-budget bounds gives expected squared gradients at least for the amplified family and for the upper needle. The lower needle has the same probability bound at threshold . Each contradicts (3); reducing the absolute constant proves the expected-budget claim. ∎
The square-root term uses the upper sum size ; for the construction gives no term. When , a factor remains relative to SICBO’s upper bound. The conjectured joint lower bound for unrestricted randomized algorithms remains open.
Details of the Numerical Experiments
Synthetic problem
In (20), is a random unit vector. Each has eigenvalue along , with , and independently rotated eigenvalues in on the complement of . Thus the component Hessians do not commute. has random singular vectors and geometrically spaced singular values from to ; ; , are Gaussian. Each is -strongly convex with joint Hessian norm at most and ; each is -smooth with .
Katyusha uses Allen-Zhu [1]’s parameters and snapshots for residual checks; the exact used for plotting is uncounted. Relative to (11), we use with a sampled estimate of , replace by , and monitor safeguards without enforcing them. The displacement bound was exceeded on 55–90% of sampled steps; the 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 approximately in proportion to .
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 , and . Strong convexity and give . The joint Hessian of contains and , which are unbounded over . Hence Assumption 1 fails globally, and the experiments lie outside the normalized theoretical class. The choice in Dagréou et al. [6, 7] does not permit prescribed .
We use and , choosing for each method and setting by the median cost over three seeds (one for deterministic methods). The selected value was in every setting: the bounded regularizers saturate and decays roughly as . The penalty methods stop after three times SICBO’s mean cost at ; 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 and differing by roughly at (Table 1). Movement and radius safeguards were monitored without enforcement. The displacement bound was exceeded on 78–100% of SICBO’s sampled steps; the bound always held and clipping never activated.
For data hyper-cleaning on a9a, we flip 30% of training labels and use with and from (21). SICBO needed the fewest calls at both values of . Each is supported on coordinate ; a sampled correction changes at most of the coordinates of , yielding substantial departures from exact gradient descent. These objectives also fail global joint smoothness in Assumption 1.
References
- [1]Zeyuan Allen-Zhu. Katusha: The first direct acceleration of stochastic gradient methods. Journal of Machine Learning Research, 18(221):1–51, 2018.
- [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]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]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]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]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]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]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]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]Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02246, 2018.arxiv.org/abs/1802.02246
- [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]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]Kaiyi Ji and Yingbin Liang. Lower bounds and accelerated algorithms for bilevel optimization. Journal of Machine Learning Research, 24(22):1–56, 2023.
- [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]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]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]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]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]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]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]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]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]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]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]Joel A. Tropp. Freedman’s inequality for matrix martingales. Electronic Communications in Probability, 16:262–270, 2011.arxiv.org/abs/1101.3039
- [26]Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12:389–434, 2012.DOI
- [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

