Pith. sign in

REVIEW 3 major objections 6 minor 71 references

A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness

T0 review · 3 major / 6 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read SLIP is a single-loop stochastic bilevel optimizer that reaches an $\epsilon$-stationary point in $\widetilde{O}(1/\epsilon^4)$ oracle calls under unbounded upper-level smoothness, matching the double-loop baseline and the…

desk verdict SLIP is a genuine first single-loop algorithm for unbounded-smoothness bilevel optimization, but the proof has a real locality-radius gap when L_y1 is large relative to L_x1, so it needs a fix before the claimed rate is fully supported. read the letter →

arxiv 2412.20017 v1 pith:45VZR3EL submitted 2024-12-28 cs.LG math.OC

Xiaochuan Gong , Jie Hao , Mingrui Liu This is my paper · ORCID
classification cs.LGmath.OC MSC 90C2690C1590C30
keywords bileveloptimizationunboundedsmoothnessrelaxedsingle-loopalgorithmstochasticdistributionaldrifthypergradientmeta-learning
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks whether a single-loop algorithm can match the near-optimal oracle complexity of double-loop methods for stochastic bilevel optimization when the upper-level objective is nonconvex with unbounded smoothness, the regime that arises in meta-learning with recurrent neural networks. It proposes SLIP: a short logarithmic warm-start for the lower-level variable, then simultaneous updates of the lower-level variable by SGD, the linear-system estimator by SGD, and the upper-level variable by normalized stochastic gradient descent with momentum. The central claim is that SLIP finds an $\epsilon$-stationary point in $\widetilde{O}(1/\epsilon^4)$ stochastic gradient or Hessian-vector product oracle calls, both in expectation and, under a stronger oracle assumption, with high probability; this matches the double-loop baseline and is nearly optimal up to logarithms. The insight that makes this possible is that the lower-level variable need not be accurate at every iteration: only a constant per-iteration tracking error plus a small momentum-weighted average is required, and the paper obtains both from a distributional-drift analysis.

What carries the argument

The load-bearing object is the lower-level tracking error $\|y_t - y^*(x_t)\|$, analyzed through a distributional-drift lemma (Lemma 4.4) for SGD with a slowly moving minimizer. The lemma bounds the tracking error by the contraction factor $(1-\mu\alpha/2)^t$ plus a noise and drift term depending on the upper-level step radius $R$; applied to SLIP with $R=\eta$, it yields Lemma 4.6: per-iteration error at most $1/(8L_1)$ and momentum-weighted average error at most $3\epsilon/(32L_0)$. The other carrying mechanism is the moving-average hypergradient estimator $m_{t+1} = \beta m_t + (1-\beta)(\nabla_x F(x_t,y_t;\xi'_t) - \nabla^2_{xy} G(x_t,y_t;\zeta'_t)z_t)$ combined with the normalized update $x_{t+1}=x_t - \eta m_{t+1}/\|m_{t+1}\|$, which fixes the step length $\eta$ in the drift bound and converts the estimator bias into terms dominated by the weighted lower-level error and the gradient norm.

What would settle it

Run SLIP on a problem where $L_{y,1}$ is much larger than $L_{x,1}$ and record, at each iterate, the distance $\|y_t-y^*(x_t)\|$ alongside the radius $1/\sqrt{2(L_{x,1}^2+L_{y,1}^2)}$ within which the relaxed-smoothness bounds of Assumption 3.1 are certified; if the tracking ball radius $1/(8L_1)$ exceeds the certified radius while the algorithm still runs, then the descent inequality used in the proof is not guaranteed to hold at those iterates and the argument would need an additional condition.

Watch

Extended reading notes

Core claim

On its own terms, the paper's discovery is that accurate estimation of the lower-level minimizer at every outer iteration—the property that forced earlier algorithms into a nested double loop—is not necessary for convergence under unbounded smoothness. SLIP instead controls $\|y_t - y^*(x_t)\|$ through a distributional-drift analysis: the lower-level SGD track the moving minimizer $y^*(x_t)$ because the normalized upper-level step keeps $\|x_{t+1}-x_t\| = \eta$ small. Lemma 4.6 shows that with high probability the per-iteration tracking error stays below a constant $1/(8L_1)$, while the momentum-weighted average of the error is at most $O(\epsilon)$. That weighted average is exactly what controls the bias term $L_{x,1}\|y_t-y^*_t\|\|\nabla\Phi(x_t)\|$ in the hypergradient estimator, so the moving-average hypergradient error can be bounded and the descent lemma closes. The resulting complexity is $\widetilde{O}(\epsilon^{-4})$ in expectation (Theorem 4.1) and with high probability (Theorem 4.3), which the paper argues is nearly optimal.

Load-bearing premise

The proof's descent and bias bounds rely on the relaxed-smoothness inequalities of Assumption 3.1 holding near every iterate, but the paper certifies them only within a local radius that shrinks with $L_{y,1}$, while the tracking lemma guarantees the iterates stay within a different ball of radius $1/(8L_1)$; no stated condition ensures the guaranteed ball lies inside the certified ball.

Editorial extensions

If this is right

  • If SLIP's guarantees hold as stated, it reaches an $\epsilon$-stationary point in $\widetilde{O}(1/\epsilon^4)$ stochastic gradient or Hessian-vector oracle calls in expectation, with no mean-square smoothness assumption on the stochastic gradient oracle.
  • The same iteration complexity holds with probability at least $1-4\delta$ under the stronger Assumption 4.2, giving, per the paper, the first high-probability convergence guarantee for stochastic bilevel optimization under unbounded smoothness.
  • The rate matches the double-loop baseline and is optimal up to logarithmic factors against the known $\Omega(\epsilon^{-4})$ lower bound for smooth nonconvex stochastic optimization, so further improvement would require additional structural assumptions.
  • The single-loop structure eliminates periodic lower-level refinement; the experiments report consistent wall-clock speedups over the double-loop baseline and other bilevel optimizers on hyper-representation learning and data hyper-cleaning.
  • The warm-start stage needs only a logarithmic number of SGD steps, so the algorithm avoids the polynomial-length initialization refinement used by earlier double-loop methods.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The analysis suggests a transferable principle: for single-loop bilevel methods, a constant per-iteration lower-level error plus a small momentum-weighted average may suffice in place of accurate inner solves, which could extend to other hypergradient estimators or to settings where the lower-level problem is not strongly convex.
  • Because the drift lemma only requires $\|x_{t+1}-x_t\|$ to be small, SLIP should tolerate a slowly time-varying lower-level objective; a natural extension would be nonstationary or continual bilevel optimization where $g$ changes between outer steps.
  • The proof's parameter choices are intricate, so a practical extension not tested in the paper is an adaptive or simplified step-size schedule that preserves the $\widetilde{O}(1/\epsilon^4)$ rate while removing the logarithmic tuning factors.
  • A concrete regime worth checking is $L_{y,1} \gg L_{x,1}$: the locality radius in Assumption 3.1 shrinks with $L_{y,1}$, and whether the guaranteed tracking ball remains inside that radius determines whether the theorem covers the motivating recurrent-network examples.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper proposes SLIP, a single-loop stochastic algorithm for bilevel optimization where the upper-level function is nonconvex with possibly unbounded smoothness (relaxed smoothness in the sense of Zhang et al.) and the lower-level function is strongly convex. The algorithm performs a short warm-start on the lower-level variable and then simultaneously updates x by normalized SGD with momentum, y by SGD, and z by a stochastic linear-system step. The main theoretical claims are (i) an Õ(1/ε^4) oracle complexity for finding an ε-stationary point of the bilevel problem, in expectation (Theorem 4.1), and (ii) the same complexity with high probability under an additional stronger noise assumption (Theorem 4.3). The paper also presents experiments on hyper-representation learning and data hyper-cleaning showing that SLIP outperforms several baselines.

Significance. If correct, the result is significant: it is the first single-loop algorithm for stochastic bilevel optimization under unbounded smoothness, and it matches the rate of the double-loop BO-REP algorithm (Hao et al., 2024) while being simpler and more practical. The proof strategy, which connects the lower-level tracking problem to stochastic optimization under distributional drift, is a nice conceptual contribution. The paper ships a full proof skeleton in the appendix, with detailed parameter choices and supporting lemmas, and its experiments include a fair comparison with multiple baseline methods. The high-probability guarantee (Theorem 4.3) is also presented as a first for this setting. However, the validity of the proofs is currently compromised by a locality-radius gap in the use of the relaxed-smoothness assumption, and the interpretation of the 'expectation' theorem is more subtle than the abstract suggests. These issues are technically fixable but require substantial revision.

major comments (3)
  1. [§4.3, Lemma 4.6 / Lemma D.7, Lemma D.10, Lemma C.4] The proof uses the relaxed-smoothness inequalities of Assumption 3.1 at separations that are not guaranteed to lie inside the radius where the assumption applies. Assumption 3.1 certifies the two gradient inequalities only for pairs w, w′ with ‖w−w′‖ ≤ R := 1/sqrt(2(L_{x,1}^2+L_{y,1}^2)). Lemma 4.6 only guarantees ‖y_t − y*_t‖ ≤ 1/(8L_1), where L_1 = sqrt(1+l_{g,1}^2/μ^2) L_{x,1}. When L_{y,1} is large compared with L_{x,1}, R is smaller than 1/(8L_1); for example, with l_{g,1}/μ = 1 and L_{y,1} = 10 L_{x,1}, R ≈ 0.0704/L_{x,1} while the guaranteed distance is ≈ 0.0884/L_{x,1}. Lemma D.10 (Eq. D.22) invokes Assumption 3.1 at exactly this separation to bound the hypergradient bias, and Lemma C.4's descent inequality is used under the same local-smoothness condition. No condition in the paper relates L_{y,1} to L_{x,1} or to the condition number, so the inequalities are not justified in the claimed parameter regime. The same gap propagates to the z-tracking estimates (Lemma D.8 and Lemma E.1) and hence to Theorem 4.3. The authors should either impose an explicit condition such as L_{y,1} = O(L_{x,1}) (up to constants) or prove that the iterates satisfy ‖y_t − y*_t‖ ≤ R under the stated assumptions.
  2. [§4.2.1, Theorem 4.1] The statement 'converges to an ε-stationary point in expectation' is not a standard expectation guarantee. The theorem asserts that with probability at least 1−2δ over the randomness in σ(F̃^1_{T0} ∪ F^1_T), the conditional expectation satisfies (1/T) Σ E‖∇Φ(x_t)‖ ≤ 14ε, where the expectation is taken over F̃^e_T. This is a high-probability bound on a conditional expectation, not a bound on the unconditional expectation E[(1/T)Σ‖∇Φ(x_t)‖]. The abstract's 'both in expectation and with high probability' overstates the result; Theorem 4.1 is a weaker, conditional statement. The authors should restate the theorem as a conditional guarantee or provide an unconditional expectation bound by controlling the probability-2δ failure event. This distinction matters for the interpretation of the paper's headline rate.
  3. [§4.2.2, Assumption 4.2 and Appendix E.1] The high-probability result relies on Assumption 4.2, which requires the almost-sure bound ‖(∇²_yy G − ∇²_yy g)z‖ ≤ σ_z for every z. This is a nonstandard and very strong oracle property: standard bounds on Hessian noise, such as bounded spectral norm of the Hessian error, would only give ‖(H−ĥ)z‖ ≤ σ‖z‖, which is not uniformly bounded over all z. The justification in Appendix E.1 constructs a noise matrix with entries proportional to τ/‖z‖, which is undefined at z = 0 and is not a plausible model of real stochastic Hessian-vector products. Since Lemma E.6 and Theorem 4.3 depend essentially on this assumption, the paper should either replace it with a more standard condition (e.g., bounded noise on the Hessian-vector product along the actual trajectory, which is plausible given the boundedness of z_t under the proven events) or discuss the realistic settings where the current Assumption 4.2 is satisfied.
minor comments (6)
  1. [§5.1] Typo: 'output dimention' should be 'output dimension'.
  2. [Figure 2 caption] Typo: 'baselinses' should be 'baselines'.
  3. [§1] Grammar: 'a unbounded smooth' should be 'an unbounded smooth'.
  4. [Theorem 4.1 statement] The phrase 'over over' appears in the guarantee; remove the duplicated 'over'.
  5. [Table 1] The row for 'SLIP (This work, Theorem 4.3; high probability guarantee)' lists the stochastic setting as 'General expectation'; it should be labeled 'High probability' to distinguish it from the expectation result.
  6. [§4.1] The phrase 'the work of (Hao et al., 2024) designed' is awkward; use 'Hao et al. (2024) designed'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: SLIP's eO(1/epsilon^4) guarantee is derived from stated assumptions and external drift analysis, not assumed or fitted.

full rationale

The central claim is a convergence theorem for a new single-loop algorithm. The proof imports Assumption 3.1 and several hypergradient lemmas from the authors' prior BO-REP paper (Hao et al., 2024), e.g., Lemma C.3/C.4 and Lemma D.10. These are published supporting results with stated assumptions; they are used as tools and do not themselves assert the single-loop eO(1/epsilon^4) conclusion. The algorithm-dependent part, Lemma 4.4/4.6 tracking the lower-level iterate, is built on Theorem 6 of Cutler et al. (2023), which is independent external work. No parameter is fitted to data and then renamed a prediction; the theoretical rate follows from the chosen step sizes and parameter restrictions. The only self-citations are to the authors' own prior bilevel smoothness framework, but they function as hypotheses/lemmas, not as the target result, so the derivation is not equivalent to its inputs by construction. A possible concern that Lemma D.7's 1/(8L1) error bound may fall outside Assumption 3.1's local radius when Ly,1 is large relative to Lx,1 is a correctness/assumption-coverage gap, not a circularity. Overall score 0; no circular step is exhibited.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on the relaxed-smoothness and oracle assumptions listed above. No free parameters are fitted to data in the theory; the algorithm's step sizes are explicit functions of problem constants, not data-fitted quantities. No new physical or model entities are introduced.

assumptions (4)
  • domain assumption (Lx,0,Lx,1,Ly,0,Ly,1)-relaxed smoothness of the upper-level function f (Assumption 3.1)
    Motivated by RNNs and inherited from Hao et al. 2024; it is the defining assumption of the problem and is not derived.
  • domain assumption Lower-level g is mu-strongly convex in y, jointly lg,1-smooth, twice differentiable with lg,2-Lipschitz Hessians, and ||grad_y f(x,y*(x))|| <= lf,0 (Assumption 3.2)
    Standard in bilevel optimization; needed for unique y* and Lipschitz hypergradient components.
  • domain assumption Unbiased stochastic oracles with bounded variance for upper-level gradients and Hessian-vector products, and light-tailed lower-level gradient noise (Assumption 3.3)
    Standard stochastic oracle model; light-tail enables high-probability tracking of y.
  • ad hoc to paper Almost-sure bounded gradient and Hessian noise for all directions, including ||(grad2_yy G - grad2_yy g)z|| <= sigma_z (Assumption 4.2)
    Introduced only for the high-probability Theorem 4.3; the paper's own justification (Appendix E.1) constructs a noise law that depends on z, which is not the usual fixed-distribution stochastic oracle.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness." pith.science (2026). https://pith.science/paper/45VZR3EL

@misc{pith2026241220017,
  author       = {Pith},
  title        = {Pith review of: A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/45VZR3EL}},
  note         = {Machine review of arXiv:2412.20017}
}
abstract

This paper studies the problem of stochastic bilevel optimization where the upper-level function is nonconvex with potentially unbounded smoothness and the lower-level function is strongly convex. This problem is motivated by meta-learning applied to sequential data, such as text classification using recurrent neural networks, where the smoothness constant of the upper-level loss function scales linearly with the gradient norm and can be potentially unbounded. Existing algorithm crucially relies on the nested loop design, which requires significant tuning efforts and is not practical. In this paper, we address this issue by proposing a Single Loop bIlevel oPtimizer (SLIP). The proposed algorithm first updates the lower-level variable by a few steps of stochastic gradient descent, and then simultaneously updates the upper-level variable by normalized stochastic gradient descent with momentum and the lower-level variable by stochastic gradient descent. Under standard assumptions, we show that our algorithm finds an $\epsilon$-stationary point within $\widetilde{O}(1/\epsilon^4)$\footnote{Here $\widetilde{O}(\cdot)$ compresses logarithmic factors of $1/\epsilon$ and $1/\delta$, where $\delta\in(0,1)$ denotes the failure probability.} oracle calls of stochastic gradient or Hessian-vector product, both in expectation and with high probability. This complexity result is nearly optimal up to logarithmic factors without mean-square smoothness of the stochastic gradient oracle. Our proof relies on (i) a refined characterization and control of the lower-level variable and (ii) establishing a novel connection between bilevel optimization and stochastic optimization under distributional drift. Our experiments on various tasks show that our algorithm significantly outperforms strong baselines in bilevel optimization.

Figures

Figures reproduced from arXiv: 2412.20017 by the authors.

Figure 1
Figure 1. Comparison with bilevel optimization baselines on Hyper-representation. Figure (a) and (b) are the results in the SNLI dataset. Figures (c) and (d) are the results of the Amazon Review Dataset (ARD). be denoted as L(x, yi ; ξi). From the perspective of bilevel optimization, the lower level function aims to find an optimal task-specific parameter y ∗ i on the training set Dtr i , given the meta parameter x. The upper… view at source ↗
Figure 2
Figure 2. Comparison with bilevel optimization baselinses on data hyper-cleaning. Figure (a), (b) are the results with the corruption rate p = 0.2. Figure (c), (d) are the results with the corruption rate p = 0.4. noise. The data hyper-cleaning task (Shaban et al., 2019) aims to train a model on a corrupted set. An important approach to solving this problem is to learn a weight for each individual sample so that the weights a… view at source ↗
Figure 3
Figure 3. Comparison on running time. (a) Results of Hyper-representation on SNLI dataset. (b) Results of Hyper-representation on Amazon Review Dataset (ARD). (c), (d) Results of data Hyper-cleaning on Sentiment140 with corruption rate p = 0.2 and p = 0.4. BO-REP needs multiple separate calculations of gradient w.r.t. y during its periodic updates for y. 6. Conclusion In this paper, we studied the problem of stochastic bileve… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Comparison with bilevel optimization baselines on Hyper-representation. Figure (a) and (b) are the results in the SNLI dataset. Figures (c) and (d) are the results of the Amazon Review Dataset (ARD). G.2. Data Hyper-cleaning 0 5 10 15 20 25 Epoch (for updating y) 0.56 …
Figure 5
Figure 5. Figure 5: Comparison with bilevel optimization baselinses on data hyper-cleaning. Figure (a), (b) are the results with the corruption rate p = 0.2. Figure (c), (d) are the results with the corruption rate p = 0.4. 39 [PITH_FULL_IMAGE:figures/full_fig_p039_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

71 extracted references · 48 canonical work pages

  1. [1]

    and White, D

    Anandalingam, G. and White, D. A solution method for the linear static stackelberg problem using penalty functions. IEEE Transactions on automatic control, 35 0 (10): 0 1170--1173, 1990

    work page 1990

  2. [2]

    and Mairal, J

    Arbel, M. and Mairal, J. Amortized implicit differentiation for stochastic bilevel optimization. arXiv preprint arXiv:2111.14580, 2021

    arXiv 2021

  3. [3]

    C., Foster, D

    Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Srebro, N., and Woodworth, B. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199 0 (1-2): 0 165--214, 2023

    work page 2023

  4. [4]

    F., Torr, P

    Bertinetto, L., Henriques, J. F., Torr, P. H., and Vedaldi, A. Meta-learning with differentiable closed-form solvers. arXiv preprint arXiv:1805.08136, 2018

    arXiv 2018

  5. [5]

    Non-stationary stochastic optimization

    Besbes, O., Gur, Y., and Zeevi, A. Non-stationary stochastic optimization. Operations research, 63 0 (5): 0 1227--1244, 2015

    work page 2015

  6. [6]

    Domain adaptation with structural correspondence learning

    Blitzer, J., McDonald, R., and Pereira, F. Domain adaptation with structural correspondence learning. In Proceedings of the 2006 conference on empirical methods in natural language processing, pp.\ 120--128, 2006

    work page 2006

  7. [7]

    Coresets via bilevel optimization for continual learning and streaming

    Borsos, Z., Mutny, M., and Krause, A. Coresets via bilevel optimization for continual learning and streaming. Advances in neural information processing systems, 33: 0 14879--14890, 2020

    work page 2020

  8. [8]

    R., Angeli, G., Potts, C., and Manning, C

    Bowman, S. R., Angeli, G., Potts, C., and Manning, C. D. A large annotated corpus for learning natural language inference. arXiv preprint arXiv:1508.05326, 2015

    arXiv 2015

Show all 71 references
  1. [9]

    and McGill, J

    Bracken, J. and McGill, J. T. Mathematical programs with optimization problems in the constraints. Operations research, 21 0 (1): 0 37--44, 1973

    1973

  2. [10]

    On bilevel optimization without lower-level strong convexity

    Chen, L., Xu, J., and Zhang, J. On bilevel optimization without lower-level strong convexity. arXiv preprint arXiv:2301.00712, 2023 a

    2023 arXiv

  3. [11]

    Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems

    Chen, T., Sun, Y., and Yin, W. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. Advances in Neural Information Processing Systems, 34: 0 25294--25307, 2021

    2021

  4. [12]

    A single-timescale method for stochastic bilevel optimization

    Chen, T., Sun, Y., Xiao, Q., and Yin, W. A single-timescale method for stochastic bilevel optimization. In International Conference on Artificial Intelligence and Statistics, pp.\ 2466--2488. PMLR, 2022

    2022

  5. [13]

    Optimal algorithms for stochastic bilevel optimization under relaxed smoothness conditions

    Chen, X., Xiao, T., and Balasubramanian, K. Optimal algorithms for stochastic bilevel optimization under relaxed smoothness conditions. arXiv preprint arXiv:2306.12067, 2023 b

    2023 arXiv

  6. [14]

    Generalized-smooth nonconvex optimization is as efficient as smooth nonconvex optimization

    Chen, Z., Zhou, Y., Liang, Y., and Lu, Z. Generalized-smooth nonconvex optimization is as efficient as smooth nonconvex optimization. arXiv preprint arXiv:2303.02854, 2023 c

    2023 arXiv

  7. [15]

    Robustness to unbounded smoothness of generalized signsgd

    Crawshaw, M., Liu, M., Orabona, F., Zhang, W., and Zhuang, Z. Robustness to unbounded smoothness of generalized signsgd. Advances in neural information processing systems, 2022

    2022

  8. [16]

    Episode: Episodic gradient clipping with periodic resampled corrections for federated learning with heterogeneous data

    Crawshaw, M., Bao, Y., and Liu, M. Episode: Episodic gradient clipping with periodic resampled corrections for federated learning with heterogeneous data. In The Eleventh International Conference on Learning Representations, 2023 a

    2023

  9. [17]

    Federated learning with client subsampling, data heterogeneity, and unbounded smoothness: A new algorithm and lower bounds

    Crawshaw, M., Bao, Y., and Liu, M. Federated learning with client subsampling, data heterogeneity, and unbounded smoothness: A new algorithm and lower bounds. In Thirty-seventh Conference on Neural Information Processing Systems, 2023 b

    2023

  10. [18]

    Stochastic optimization under distributional drift

    Cutler, J., Drusvyatskiy, D., and Harchaoui, Z. Stochastic optimization under distributional drift. Journal of Machine Learning Research, 24 0 (147): 0 1--56, 2023

    2023

  11. [19]

    A framework for bilevel optimization that enables stochastic and global variance reduction algorithms

    Dagr \'e ou, M., Ablin, P., Vaiter, S., and Moreau, T. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. Advances in Neural Information Processing Systems, 35: 0 26698--26710, 2022

    2022

  12. [20]

    A lower bound and a near-optimal algorithm for bilevel empirical risk minimization

    Dagr \'e ou, M., Moreau, T., Vaiter, S., and Ablin, P. A lower bound and a near-optimal algorithm for bilevel empirical risk minimization. arXiv preprint arXiv:2302.08766, 2023

    2023 arXiv

  13. [21]

    Saga: A fast incremental gradient method with support for non-strongly convex composite objectives

    Defazio, A., Bach, F., and Lacoste-Julien, S. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural Information Processing Systems, pp.\ 1646--1654, 2014

    2014

  14. [22]

    A dynamic stochastic approximation method

    Dupa c , V. A dynamic stochastic approximation method. The Annals of Mathematical Statistics, pp.\ 1695--1702, 1965

    1965

  15. [23]

    Elman, J. L. Finding structure in time. Cognitive science, 14 0 (2): 0 179--211, 1990

    1990

  16. [24]

    Beyond uniform smoothness: A stopped analysis of adaptive sgd

    Faw, M., Rout, L., Caramanis, C., and Shakkottai, S. Beyond uniform smoothness: A stopped analysis of adaptive sgd. arXiv preprint arXiv:2302.06570, 2023

    2023 arXiv

  17. [25]

    and Hutter, F

    Feurer, M. and Hutter, F. Hyperparameter optimization. In Automated Machine Learning, pp.\ 3--33. Springer, Cham, 2019

    2019

  18. [26]

    Model-agnostic meta-learning for fast adaptation of deep networks

    Finn, C., Abbeel, P., and Levine, S. Model-agnostic meta-learning for fast adaptation of deep networks. In International conference on machine learning, pp.\ 1126--1135. PMLR, 2017

    2017

  19. [27]

    Bilevel programming for hyperparameter optimization and meta-learning

    Franceschi, L., Frasconi, P., Salzo, S., Grazzi, R., and Pontil, M. Bilevel programming for hyperparameter optimization and meta-learning. In International conference on machine learning, pp.\ 1568--1577. PMLR, 2018

    2018

  20. [28]

    and Lan, G

    Ghadimi, S. and Lan, G. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, ii: shrinking procedures and optimal algorithms. SIAM Journal on Optimization, 23 0 (4): 0 2061--2089, 2013 a

    2013

  21. [29]

    and Lan, G

    Ghadimi, S. and Lan, G. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23 0 (4): 0 2341--2368, 2013 b

    2013

  22. [30]

    and Wang, M

    Ghadimi, S. and Wang, M. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02246, 2018

    2018 arXiv

  23. [31]

    Twitter sentiment classification using distant supervision

    Go, A., Bhayani, R., and Huang, L. Twitter sentiment classification using distant supervision. CS224N project report, Stanford, 1 0 (12): 0 2009, 2009

    2009

  24. [32]

    Bilevel optimization with a lower-level contraction: Optimal sample complexity without warm-start

    Grazzi, R., Pontil, M., and Salzo, S. Bilevel optimization with a lower-level contraction: Optimal sample complexity without warm-start. arXiv preprint arXiv:2202.03397, 2022

    2022 arXiv

  25. [33]

    and Ljung, L

    Guo, L. and Ljung, L. Exponential stability of general tracking algorithms. IEEE Transactions on Automatic Control, 40 0 (8): 0 1376--1387, 1995

    1995

  26. [34]

    Randomized stochastic variance-reduced methods for multi-task stochastic bilevel optimization

    Guo, Z., Hu, Q., Zhang, L., and Yang, T. Randomized stochastic variance-reduced methods for multi-task stochastic bilevel optimization. arXiv preprint arXiv:2105.02266, 2021

    2021 arXiv

  27. [35]

    Bilevel coreset selection in continual learning: A new formulation and algorithm

    Hao, J., Ji, K., and Liu, M. Bilevel coreset selection in continual learning: A new formulation and algorithm. In Thirty-seventh Conference on Neural Information Processing Systems, 2023

    2023

  28. [36]

    Bilevel optimization under unbounded smoothness: A new algorithm and convergence analysis

    Hao, J., Gong, X., and Liu, M. Bilevel optimization under unbounded smoothness: A new algorithm and convergence analysis. In The Twelfth International Conference on Learning Representations, 2024

    2024

  29. [37]

    and Kale, S

    Hazan, E. and Kale, S. Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization. Journal of Machine Learning Research, 15 0 (1): 0 2489--2512, 2014

    2014

  30. [38]

    Y., and Shalev-Shwartz, S

    Hazan, E., Levy, K. Y., and Shalev-Shwartz, S. Beyond convexity: Stochastic quasi-convex optimization. arXiv preprint arXiv:1507.02030, 2015

    2015 arXiv

  31. [39]

    and Schmidhuber, J

    Hochreiter, S. and Schmidhuber, J. Long short-term memory. Neural computation, 9 0 (8): 0 1735--1780, 1997

    1997

  32. [40]

    A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic

    Hong, M., Wai, H.-T., Wang, Z., and Yang, Z. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 33 0 (1): 0 147--180, 2023

    2023

  33. [41]

    Bilevel optimization: Convergence analysis and enhanced design

    Ji, K., Yang, J., and Liang, Y. Bilevel optimization: Convergence analysis and enhanced design. In International conference on machine learning, pp.\ 4882--4892. PMLR, 2021

    2021

  34. [42]

    Non-convex distributionally robust optimization: Non-asymptotic analysis

    Jin, J., Zhang, B., Wang, H., and Wang, L. Non-convex distributionally robust optimization: Non-asymptotic analysis. Advances in Neural Information Processing Systems, 34: 0 2771--2782, 2021

    2021

  35. [43]

    A near-optimal algorithm for stochastic bilevel optimization via double-momentum

    Khanduri, P., Zeng, S., Hong, M., Wai, H.-T., Wang, Z., and Yang, Z. A near-optimal algorithm for stochastic bilevel optimization via double-momentum. Advances in Neural Information Processing Systems (NeurIPS), 34: 0 30271--30283, 2021

    2021

  36. [44]

    and Tsitsiklis, J

    Konda, V. and Tsitsiklis, J. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999

    1999

  37. [45]

    On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation

    Kwon, J., Kwon, D., Wright, S., and Nowak, R. On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. arXiv preprint arXiv:2309.01753, 2023 a

    2023 arXiv

  38. [46]

    Kwon, J., Kwon, D., Wright, S., and Nowak, R. D. A fully first-order method for stochastic bilevel optimization. In International Conference on Machine Learning, pp.\ 18083--18113. PMLR, 2023 b

    2023

  39. [47]

    An optimal method for stochastic composite optimization

    Lan, G. An optimal method for stochastic composite optimization. Mathematical Programming, 133 0 (1-2): 0 365--397, 2012

    2012

  40. [48]

    Convergence of adam under relaxed assumptions

    Li, H., Jadbabaie, A., and Rakhlin, A. Convergence of adam under relaxed assumptions. arXiv preprint arXiv:2304.13972, 2023

    2023 arXiv

  41. [49]

    Bome! bilevel optimization made easy: A simple first-order approach

    Liu, B., Ye, M., Wright, S., Stone, P., and Liu, Q. Bome! bilevel optimization made easy: A simple first-order approach. Advances in Neural Information Processing Systems, 35: 0 17248--17262, 2022 a

    2022

  42. [50]

    A communication-efficient distributed gradient clipping algorithm for training deep neural networks

    Liu, M., Zhuang, Z., Lei, Y., and Liao, C. A communication-efficient distributed gradient clipping algorithm for training deep neural networks. Advances in Neural Information Processing Systems, 35: 0 26204--26217, 2022 b

    2022

  43. [51]

    A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton

    Liu, R., Mu, P., Yuan, X., Zeng, S., and Zhang, J. A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton. In International Conference on Machine Learning, pp.\ 6305--6315. PMLR, 2020

    2020

  44. [52]

    Near-optimal non-convex stochastic optimization under generalized smoothness

    Liu, Z., Jagabathula, S., and Zhou, Z. Near-optimal non-convex stochastic optimization under generalized smoothness. arXiv preprint arXiv:2302.0603, 2023

    2023

  45. [53]

    Bounds for the tracking error of first-order online optimization methods

    Madden, L., Becker, S., and Dall’Anese, E. Bounds for the tracking error of first-order online optimization methods. Journal of Optimization Theory and Applications, 189: 0 437--457, 2021

    2021

  46. [54]

    Rapid learning or feature reuse? towards understanding the effectiveness of maml

    Raghu, A., Raghu, M., Bengio, S., and Vinyals, O. Rapid learning or feature reuse? towards understanding the effectiveness of maml. arXiv preprint arXiv:1909.09157, 2019

    1909 arXiv

  47. [55]

    M., and Levine, S

    Rajeswaran, A., Finn, C., Kakade, S. M., and Levine, S. Meta-learning with implicit gradients. In Advances in Neural Information Processing Systems (NeurIPS), pp.\ 113--124, 2019

    2019

  48. [56]

    Variance-reduced clipping for non-convex optimization

    Reisizadeh, A., Li, H., Das, S., and Jadbabaie, A. Variance-reduced clipping for non-convex optimization. arXiv preprint arXiv:2303.00883, 2023

    2023 arXiv

  49. [57]

    E., and Suh, C

    Roh, Y., Lee, K., Whang, S. E., and Suh, C. Fairbatch: Batch selection for model fairness. arXiv preprint arXiv:2012.01696, 2020

    2012 arXiv

  50. [58]

    and Shtern, S

    Sabach, S. and Shtern, S. A first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27 0 (2): 0 640--660, 2017

    2017

  51. [59]

    Truncated back-propagation for bilevel optimization

    Shaban, A., Cheng, C.-A., Hatch, N., and Boots, B. Truncated back-propagation for bilevel optimization. In The 22nd International Conference on Artificial Intelligence and Statistics, pp.\ 1723--1732. PMLR, 2019

    2019

  52. [60]

    and Chen, T

    Shen, H. and Chen, T. On penalty-based bilevel gradient descent method. arXiv preprint arXiv:2302.05185, 2023

    2023 arXiv

  53. [61]

    A constrained optimization approach to bilevel optimization with multiple inner minima

    Sow, D., Ji, K., Guan, Z., and Liang, Y. A constrained optimization approach to bilevel optimization with multiple inner minima. arXiv preprint arXiv:2203.01123, 2022

    2022 arXiv

  54. [62]

    N., Kaiser, ., and Polosukhin, I

    Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, ., and Polosukhin, I. Attention is all you need. Advances in neural information processing systems, 30, 2017

    2017

  55. [63]

    Descent approaches for quadratic bilevel programming

    Vicente, L., Savard, G., and J \'u dice, J. Descent approaches for quadratic bilevel programming. Journal of optimization theory and applications, 81 0 (2): 0 379--399, 1994

    1994

  56. [64]

    Convergence of adagrad for non-convex objectives: Simple proofs and relaxed assumptions

    Wang, B., Zhang, H., Ma, Z., and Chen, W. Convergence of adagrad for non-convex objectives: Simple proofs and relaxed assumptions. In The Thirty Sixth Annual Conference on Learning Theory, pp.\ 161--190. PMLR, 2023

    2023

  57. [65]

    White, D. J. and Anandalingam, G. A penalty function approach for solving bi-level linear programs. Journal of Global Optimization, 3: 0 397--419, 1993

    1993

  58. [66]

    V., and Nedi \'c , A

    Wilson, C., Veeravalli, V. V., and Nedi \'c , A. Adaptive sequential stochastic optimization. IEEE Transactions on Automatic Control, 64 0 (2): 0 496--509, 2018

    2018

  59. [67]

    Provably faster algorithms for bilevel optimization

    Yang, J., Ji, K., and Liang, Y. Provably faster algorithms for bilevel optimization. Advances in Neural Information Processing Systems, 34: 0 13670--13682, 2021

    2021

  60. [68]

    Improved analysis of clipping algorithms for non-convex optimization

    Zhang, B., Jin, J., Fang, C., and Wang, L. Improved analysis of clipping algorithms for non-convex optimization. Advances in Neural Information Processing Systems, 33: 0 15511--15521, 2020 a

    2020

  61. [69]

    Why gradient clipping accelerates training: A theoretical justification for adaptivity

    Zhang, J., He, T., Sra, S., and Jadbabaie, A. Why gradient clipping accelerates training: A theoretical justification for adaptivity. International Conference on Learning Representations, 2020 b

    2020

  62. [70]

    Why gradient clipping accelerates training: A theoretical justification for adaptivity

    Zhang, J., He, T., Sra, S., and Jadbabaie, A. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations, 2020 c

    2020

  63. [71]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.