Pith. sign in

REVIEW 2 major objections 4 minor 48 references

A single-loop stochastic method gives the first joint stationarity guarantees for nonconvex-nonconvex simple bilevel optimization.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.5

2026-07-14 08:03 UTC pith:KTX3EX2O

load-bearing objection First joint (ε_f, ε_g) rates for fully stochastic nonconvex–nonconvex simple bilevel; rare-visit is the price of the best rates, but they already ship an assumption-free alternative. the 2 major comments →

arxiv 2607.10957 v1 pith:KTX3EX2O submitted 2026-07-12 math.OC

Stochastic Dynamic Barrier Perturbed Gradient Methods for Nonconvex Simple Bilevel Optimization

Mohammad Mahdi Ahmadi , Jincheng Cao , Aryan Mokhtari , Erfan Yazdandoost Hamedani This is my paper
classification math.OC MSC 90C1590C2690C30
keywords simple bilevel optimizationstochastic nonconvex optimizationdynamic barrier gradientdual perturbationstationarity guaranteesvariance reductionpenalty regularization
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

Simple bilevel problems ask for a point that optimizes an upper-level objective while staying inside the solution set of a lower-level problem. When both objectives are nonconvex and only noisy gradients are available, the dual multiplier that couples the two levels can blow up near lower-level stationary points and destroy the analysis. This paper introduces a single-loop algorithm that gently perturbs the dual formulation so the multiplier stays controlled, then proves that the resulting method finds a joint stationary point under a mild condition that the iterates only rarely enter the worst regions. Two variants remove that condition by redesigning the subproblem and by adding variance reduction, at the price of higher but still polynomial sample costs. The result is the first explicit guarantee that both levels can be driven to stationarity together in the fully stochastic nonconvex setting.

Core claim

The authors show that a carefully chosen dual perturbation yields controlled bias and variance for the stochastic descent direction even when the lower-level gradient is small. Under a mild rare-visit assumption this produces an (ε_f, ε_g)-stationary point after O(max{ε_f^{-2}, ε_g^{-2}}) iterations with sample complexities O(ε^{-4}) and O(ε^{-6}) for the upper and lower levels; penalty-regularized and variance-reduced variants remove the assumption while remaining polynomial.

What carries the argument

The Stochastic Dynamic Barrier Perturbed Gradient (SDBPG) direction, obtained by replacing the dual denominator ||∇g||^{2} with ||∇g||^{2} + γ_k and analyzing the resulting joint map T_γ(u,v) that multiplies the dual multiplier by the lower-level gradient.

Load-bearing premise

The iterates are assumed to visit the unstable region where the lower-level gradient is tiny and the two gradients point in opposite directions only a vanishing fraction of the time.

What would settle it

Run SDBPG on a simple nonconvex-nonconvex bilevel instance known to spend a positive fraction of iterates in the negatively aligned near-stationary region and check whether the claimed O(ε^{-4})/O(ε^{-6}) sample rates still hold; failure would falsify the rare-visit claim.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Joint (ε_f, ε_g) stationarity is now attainable from stochastic first-order oracles alone for nonconvex simple bilevel problems.
  • LLM unlearning and other large-scale hierarchical tasks can be attacked by a single-loop method whose sample cost is polynomial in the target accuracy.
  • Penalty regularization removes the need to monitor rare visits, trading a higher polynomial degree for a fully assumption-free algorithm.
  • Variance reduction recovers two powers of ε, showing that the extra cost of the penalty approach is largely statistical rather than structural.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same dual-perturbation idea may stabilize other ratio-type estimators that appear in constrained or multi-objective stochastic optimization.
  • If the rare-visit frequency can be bounded a priori from problem geometry rather than assumed, the best rates become fully non-asymptotic and implementable without trajectory-dependent batch sizes.
  • The gap between O(ε^{-6}) and O(ε^{-8}) after variance reduction suggests that further refinements of the Lyapunov weight could close most of the remaining distance to the deterministic rate.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper studies stochastic simple bilevel optimization with smooth, possibly nonconvex upper- and lower-level objectives accessed only via stochastic gradient oracles. The central difficulty is that the dual multiplier of the dynamic-barrier subproblem can become unbounded near lower-level stationary points, which invalidates standard bounded-dual analyses and produces biased, high-variance ratio estimators. The authors introduce SDBPG, a single-loop method that inserts an adaptive perturbation γ_k into the dual denominator, and prove that under a rare-visit assumption on a carefully defined “bad region” the method attains (ε_f,ε_g)-stationarity with sample complexities O(ε^{-4}) and O(ε^{-6}). They then redesign the subproblem as a penalty-regularized unconstrained quadratic (PR-SDBPG) whose multiplier is uniformly bounded, removing the rare-visit assumption at the cost of higher polynomial rates, and further improve those rates by STORM-type variance reduction (VR-PR-SDBPG). Supporting technical ingredients include a joint Lipschitz analysis of the correlated ratio map and a comparison with inexact primal-dual inner solvers. Numerical experiments on LLM unlearning tasks are consistent with the theory.

Significance. If the claims hold, the paper supplies the first explicit joint (ε_f,ε_g)-stationarity guarantees for stochastic nonconvex-nonconvex simple bilevel optimization, a setting that arises in continual learning, hyperparameter optimization, and machine unlearning. The strongest rates under the rare-visit assumption match the deterministic iteration complexity of Cao et al. (2025) while remaining single-loop; the penalty-regularized and variance-reduced variants give fully assumption-free polynomial alternatives. The joint Lipschitz analysis of the ratio map and the uniform-multiplier construction are reusable technical tools. Full proofs appear in the appendix and the experimental section, while secondary, aligns with the predicted ordering of the three algorithms.

major comments (2)
  1. Assumption 3.1 (rare-visit) is load-bearing for the best rates claimed in Theorem 3.3 and is only heuristically justified in Remark 3.1. The paper already supplies fully assumption-free alternatives (Theorems 4.2–4.3), so the central existence claim does not collapse; nevertheless the manuscript should either (i) give a verifiable sufficient condition under which the expected visit count is O(K^{1-ς}) or (ii) relegate the rare-visit rates to a secondary corollary and lead with the assumption-free complexities. Without such clarification a reader cannot assess how often the O(ε^{-4})/O(ε^{-6}) rates are attainable.
  2. Proposition 3.2 and the subsequent discussion correctly note that the ideal parameter choices γ_k = K^{-1/2}∥∇g(x_k)∥^{2} and N_g = K γ_k^{-1} are non-implementable. The modified Algorithm 3 used for Theorem 3.3 replaces them by fixed constants, but the text never states how a practitioner should choose the detection thresholds τ,θ or the independent mini-batches that define the observable bad region. A short implementability paragraph (or a default practical schedule) is needed before the strongest rates can be claimed as algorithmic rather than purely analytic.
minor comments (4)
  1. Table 1 lists sample complexities without the precise dependence on problem constants (G_f, L_g, u_g, u_f). Adding a footnote or a short remark would make the comparison with BLOOP and the convex-lower-level methods more transparent.
  2. In Algorithm 1 the same mini-batch is used for both numerator and denominator of λ̃_γ,k; the text correctly flags the resulting bias, but a one-sentence pointer to Lemma A.5 at that location would help the reader locate the joint-Lipschitz argument immediately.
  3. Figure 1 normalizes both stationarity metrics by their initial values; the caption should state this explicitly so that absolute scales can be recovered if desired.
  4. A few typographical inconsistencies appear (e.g., “Stochastic Dynamic Barrier Perturbed Gradient” vs. the acronym SDBPG, and occasional missing spaces around ε_f,ε_g). A light copy-edit pass would remove them.

Circularity Check

0 steps flagged

No circularity: complexity bounds are derived from standard smoothness/oracle assumptions via explicit error decompositions and Lyapunov arguments, not by construction from fitted inputs or self-referential definitions.

full rationale

The paper defines (ε_f, ε_g)-stationarity independently (Def. 2.2), proposes three algorithms (SDBPG, PR-SDBPG, VR-PR-SDBPG) with explicit dual-perturbation or penalty-regularized updates, and derives sample complexities from Assumptions 2.1–2.3 (and 3.1/3.2 or H.1) via bias/second-moment bounds on the stochastic direction (Lem. 3.1, G.2–G.3), joint Lipschitz control of the ratio map (Lem. A.5), uniform multiplier bounds (Lem. 4.1), and Lyapunov descent (Props. 3.2, Thms. 3.3/4.2/4.3). Self-citations to the authors’ deterministic DBGD analysis [21] supply the stationarity notion and baseline rates but are not load-bearing for the new stochastic guarantees; the rare-visit assumption is stated explicitly and removed by the penalty variants. No parameter is fitted to data and then re-presented as a prediction, no uniqueness theorem is imported to force the construction, and no known empirical pattern is merely renamed. The derivation chain is therefore self-contained against its stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 2 invented entities

The central claims rest on standard smoothness/Lipschitz and unbiased-oracle assumptions plus two paper-specific conditions (rare-visit and uniform gradient bounds). No free parameters are fitted to data; all constants are chosen a priori as functions of the target accuracy ε. The only invented algorithmic objects are the perturbed dual multiplier and the penalty-regularized subproblem, both fully defined by closed-form expressions.

axioms (5)
  • domain assumption f and g are continuously differentiable with Lipschitz gradients L_f, L_g and are bounded below (Assumption 2.1).
    Standard first-order smoothness used for all descent lemmas.
  • domain assumption Stochastic gradients are unbiased with bounded variance ν_f², ν_g² (Assumption 2.2).
    Standard stochastic-oracle model.
  • domain assumption Gradients of f and g are uniformly bounded by G_f and C_g (Assumption 2.3).
    Used to control dual multipliers and bias terms; common but restrictive for unbounded domains.
  • ad hoc to paper Rare-visit: expected number of visits to bad regions is O(K^{1-ς}) (Assumption 3.1).
    Load-bearing for the best rates of SDBPG; removed by PR-SDBPG.
  • domain assumption Mean-square smoothness of stochastic gradients (Assumption H.1) for the variance-reduced variant.
    Standard for STORM-type analyses.
invented entities (2)
  • Perturbed dual multiplier λ_γ,k with adaptive γ_k no independent evidence
    purpose: Regularizes the denominator of the DBGD dual variable so that bias and variance remain controlled near lower-level stationarity.
    Defined by a closed-form max expression; no independent physical existence claimed.
  • Penalty-regularized unconstrained subproblem (11) no independent evidence
    purpose: Produces a uniformly bounded multiplier without rare-visit assumption.
    Algorithmic construction whose denominator is always ≥γ>0.

pith-pipeline@v1.1.0-grok45 · 43491 in / 2645 out tokens · 23112 ms · 2026-07-14T08:03:34.777304+00:00 · methodology

0 comments
read the original abstract

We study stochastic simple bilevel optimization with smooth, possibly nonconvex upper- and lower-level objectives accessed only through stochastic gradient oracles. A key challenge is that the dual multiplier induced by the lower-level constraint may become unbounded near lower-level stationary points, invalidating bounded-dual analyses and destabilizing stochastic gradient estimates. To address this, we propose \emph{Stochastic Dynamic Barrier Perturbed Gradient} (SDBPG), a single-loop method that adaptively perturbs the dual formulation to regularize this degeneracy. The perturbation stabilizes the multiplier and yields controlled bias and variance even near the lower-level stationarity region. Under a mild rare-visit assumption, SDBPG finds an $(\epsilon_f,\epsilon_g)$-stationary point in $\mathcal{O}(\max\{\epsilon_f^{-2},\epsilon_g^{-2}\})$ iterations, with sample gradient complexities $\mathcal{O}(\epsilon^{-4})$ and $\mathcal{O}(\epsilon^{-6})$ for the upper- and lower-level objectives where $\epsilon=\max\{\epsilon_f,\epsilon_g\}$. We further develop PR-SDBPG, a penalty-regularized variant that eliminates the rare-visit assumption, and VR-PR-SDBPG, which improves the resulting sample complexities entirely through variance reduction. To our knowledge, these are the first explicit $(\epsilon_f,\epsilon_g)$-stationarity guarantees for stochastic nonconvex-nonconvex simple bilevel optimization.

Figures

Figures reproduced from arXiv: 2607.10957 by Aryan Mokhtari, Erfan Yazdandoost Hamedani, Jincheng Cao, Mohammad Mahdi Ahmadi.

Figure 1
Figure 1. Figure 1: Comparison of SDBPG (blue), PR-SDBPG (green), and VR-PR-SDBPG (orange) with [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Comparison of SDBPG (blue), PR-SDBPG (green), and VR-PR-SDBPG (orange) with the [PITH_FULL_IMAGE:figures/full_fig_p042_2.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

48 extracted references · 10 linked inside Pith

  1. [1]

    Optimality conditions for a simple convex bilevel programming problem.Variational Analysis and Generalized Differentiation in Optimization and Control: In Honor of Boris S

    Stephen Dempe, Nguyen Dinh, and Joydeep Dutta. Optimality conditions for a simple convex bilevel programming problem.Variational Analysis and Generalized Differentiation in Optimization and Control: In Honor of Boris S. Mordukhovich, pages 149–161, 2010

    2010

  2. [2]

    Algorithmsforsimplebilevelprogramming

    JoydeepDuttaandTanushreePandit. Algorithmsforsimplebilevelprogramming. InBilevel Optimization: Advances and Next Challenges, pages 253–291. Springer, 2020

    2020

  3. [3]

    A conditional gradient-based method for simple bilevel optimization with convex lower-level problem

    Ruichen Jiang, Nazanin Abolfazli, Aryan Mokhtari, and Erfan Yazdandoost Hamedani. A conditional gradient-based method for simple bilevel optimization with convex lower-level problem. InInternational Conference on Artificial Intelligence and Statistics, pages 10305–10323. PMLR, 2023. 11

    2023

  4. [4]

    An accelerated gradient method for convex smooth simple bilevel optimization.Advances in Neural Information Processing Systems, 37:45126–45154, 2024

    Jincheng Cao, Ruichen Jiang, Erfan Yazdandoost Hamedani, and Aryan Mokhtari. An accelerated gradient method for convex smooth simple bilevel optimization.Advances in Neural Information Processing Systems, 37:45126–45154, 2024

    2024

  5. [5]

    Coresets via bilevel optimization for continual learning and streaming.Advances in Neural Information Processing Systems, 33:14879–14890, 2020

    Zalán Borsos, Mojmir Mutny, and Andreas Krause. Coresets via bilevel optimization for continual learning and streaming.Advances in Neural Information Processing Systems, 33:14879–14890, 2020

    2020

  6. [6]

    Bilevel coreset selection in continual learning: A new formulation and algorithm.Advances in Neural Information Processing Systems, 36:51026–51049, 2023

    Jie Hao, Kaiyi Ji, and Mingrui Liu. Bilevel coreset selection in continual learning: A new formulation and algorithm.Advances in Neural Information Processing Systems, 36:51026–51049, 2023

    2023

  7. [7]

    Bilevel programming for hyperparameter optimization and meta-learning

    Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. InInternational Conference on Machine Learning, pages 1568–1577. PMLR, 2018

    2018

  8. [8]

    Truncated back-propagation for bilevel optimization

    Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back-propagation for bilevel optimization. InThe 22nd International Conference on Artificial Intelligence and Statistics, pages 1723–1732. PMLR, 2019

    2019

  9. [9]

    Meta-learning with implicit gradients.Advances in neural information processing systems, 32, 2019

    Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with implicit gradients.Advances in neural information processing systems, 32, 2019

    2019

  10. [10]

    Meta-learning with differentiable closed-form solvers.arXiv preprint arXiv:1805.08136, 2018

    Luca Bertinetto, Joao F Henriques, Philip HS Torr, and Andrea Vedaldi. Meta-learning with differentiable closed-form solvers.arXiv preprint arXiv:1805.08136, 2018

    Pith/arXiv arXiv 2018

  11. [11]

    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

    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

    2023

  12. [12]

    Bi-level actor-critic for multi-agent coordination

    Haifeng Zhang, Weizhe Chen, Zeren Huang, Minne Li, Yaodong Yang, Weinan Zhang, and Jun Wang. Bi-level actor-critic for multi-agent coordination. InProceedings of the AAAI conference on artificial intelligence, volume 34, pages 7325–7332, 2020

    2020

  13. [13]

    Remember what you want to forget: Algorithms for machine unlearning.Advances in Neural Information Processing Systems, 34:18075–18086, 2021

    Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want to forget: Algorithms for machine unlearning.Advances in Neural Information Processing Systems, 34:18075–18086, 2021

    2021

  14. [14]

    Towards safer large language models through machine unlearning

    Zheyuan Liu, Guangyao Dou, Zhaoxuan Tan, Yijun Tian, and Meng Jiang. Towards safer large language models through machine unlearning. InFindings of the Association for Computational Linguistics: ACL 2024, pages 1817–1829, 2024

    2024

  15. [15]

    Blur: A bi-level optimization approach for llm unlearning

    Hadi Reisizadeh, Jinghan Jia, Zhiqi Bu, Bhanukiran Vinzamuri, Anil Ramakrishna, Kai-Wei Chang, Volkan Cevher, Sijia Liu, and Mingyi Hong. Blur: A bi-level optimization approach for llm unlearning. InProceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers), pages 7043–7058, 2026

    2026

  16. [16]

    New York: Wiley, 1977

    Andre Nikolaevich Tikhonov and VIAK Arsenin.Solutions of ill-posed problems. New York: Wiley, 1977

    1977

  17. [17]

    An explicit descent method for bilevel convex optimization.Journal of Convex Analysis, 14(2):227, 2007

    Mikhail Solodov. An explicit descent method for bilevel convex optimization.Journal of Convex Analysis, 14(2):227, 2007

    2007

  18. [18]

    On the complexity of finding first-order critical points in constrained nonlinear optimization.Mathematical Programming, 144(1):93–106, 2014

    Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. On the complexity of finding first-order critical points in constrained nonlinear optimization.Mathematical Programming, 144(1):93–106, 2014

    2014

  19. [19]

    Ghost penalties in nonconvex constrained optimization: Diminishing stepsizes and iteration complexity.Mathematics of Operations Research, 46(2):595–627, 2021

    Francisco Facchinei, Vyacheslav Kungurtsev, Lorenzo Lampariello, and Gesualdo Scutari. Ghost penalties in nonconvex constrained optimization: Diminishing stepsizes and iteration complexity.Mathematics of Operations Research, 46(2):595–627, 2021

    2021

  20. [20]

    Bi-objective trade-off with dynamic barrier gradient descent.NeurIPS 2021, 2021

    Chengyue Gong and Xingchao Liu. Bi-objective trade-off with dynamic barrier gradient descent.NeurIPS 2021, 2021. 12

    2021

  21. [21]

    On the complexity of finding stationary points in nonconvex simple bilevel optimization.arXiv preprint arXiv:2507.23155, 2025

    Jincheng Cao, Ruichen Jiang, Erfan Yazdandoost Hamedani, and Aryan Mokhtari. On the complexity of finding stationary points in nonconvex simple bilevel optimization.arXiv preprint arXiv:2507.23155, 2025

    Pith/arXiv arXiv 2025

  22. [22]

    Careful with that scalpel: improving gradient surgery with an ema.arXiv preprint arXiv:2402.02998, 2024

    Yu-Guan Hsieh, James Thornton, Eugene Ndiaye, Michal Klein, Marco Cuturi, and Pierre Ablin. Careful with that scalpel: improving gradient surgery with an ema.arXiv preprint arXiv:2402.02998, 2024

    Pith/arXiv arXiv 2024

  23. [23]

    Projection-free methods for stochastic simple bilevel optimization with convex lower-level problem

    Jincheng Cao, Ruichen Jiang, Nazanin Abolfazli, Erfan Yazdandoost Hamedani, and Aryan Mokhtari. Projection-free methods for stochastic simple bilevel optimization with convex lower-level problem. Advances in Neural Information Processing Systems, 36:6105–6131, 2023

    2023

  24. [24]

    Conditional gradient methods with standard lmo for stochastic simple bilevel optimization.arXiv preprint arXiv:2505.18037, 2025

    Khanh-Hung Giang-Tran, Soroosh Shafiee, and Nam Ho-Nguyen. Conditional gradient methods with standard lmo for stochastic simple bilevel optimization.arXiv preprint arXiv:2505.18037, 2025

    arXiv 2025

  25. [25]

    Stochastic approximation for estimating the price of stability in stochastic nash games.ACM Transactions on Modeling and Computer Simulation, 34(2):1–24, 2024

    Afrooz Jalilzadeh, Farzad Yousefian, and Mohammadjavad Ebrahimi. Stochastic approximation for estimating the price of stability in stochastic nash games.ACM Transactions on Modeling and Computer Simulation, 34(2):1–24, 2024

    2024

  26. [26]

    Corrigendum: On the complexity of finding first-order critical points in constrained nonlinear optimization.Mathematical Programming, 161(1): 611–626, 2017

    Coralia Cartis, Nicholas IM Gould, and Ph L Toint. Corrigendum: On the complexity of finding first-order critical points in constrained nonlinear optimization.Mathematical Programming, 161(1): 611–626, 2017

    2017

  27. [27]

    Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled kkt conditions and high-order models

    Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled kkt conditions and high-order models. InApproximation and Optimization: Algorithms, Complexity and Applications, pages 5–26. Springer, 2019

    2019

  28. [28]

    Evaluation complexity for nonlinear constrained optimization using unscaled kkt conditions and high-order models

    Ernesto G Birgin, JL Gardenghi, José Mario Martínez, Sandra A Santos, and Ph L Toint. Evaluation complexity for nonlinear constrained optimization using unscaled kkt conditions and high-order models. SIAM Journal on Optimization, 26(2):951–967, 2016

    2016

  29. [29]

    Inexact proximal-point penalty methods for constrained non-convex optimization.arXiv preprint arXiv:1908.11518, 2019

    Qihang Lin, Runchao Ma, and Yangyang Xu. Inexact proximal-point penalty methods for constrained non-convex optimization.arXiv preprint arXiv:1908.11518, 2019

    Pith/arXiv arXiv 1908

  30. [30]

    Stochastic first-order methods for convex and nonconvex functional constrained optimization.Mathematical Programming, 197(1):215–279, 2023

    Digvijay Boob, Qi Deng, and Guanghui Lan. Stochastic first-order methods for convex and nonconvex functional constrained optimization.Mathematical Programming, 197(1):215–279, 2023

    2023

  31. [31]

    A momentum-based linearized augmented lagrangian method for nonconvex constrained stochastic optimization.Mathematics of Operations Research, 51(1):92–133, 2026

    Qiankun Shi, Xiao Wang, and Hao Wang. A momentum-based linearized augmented lagrangian method for nonconvex constrained stochastic optimization.Mathematics of Operations Research, 51(1):92–133, 2026

    2026

  32. [32]

    Stochastic compositional optimization with compositional constraints.INFORMS Journal on Optimization, 8(1):1–21, 2026

    Shuoguang Yang, Wei You, Zhe Zhang, and Ethan X Fang. Stochastic compositional optimization with compositional constraints.INFORMS Journal on Optimization, 8(1):1–21, 2026

    2026

  33. [33]

    Sequential quadratic optimization for solving expectation equality constrained stochastic optimization problems.arXiv preprint arXiv:2503.09490, 2025

    Haoming Shen, Yang Zeng, and Baoyu Zhou. Sequential quadratic optimization for solving expectation equality constrained stochastic optimization problems.arXiv preprint arXiv:2503.09490, 2025

    arXiv 2025

  34. [34]

    A two-phase stochastic momentum-based algorithm for nonconvex expectation-constrained optimization.Journal of Scientific Computing, 104(1):16, 2025

    Yawen Cui, Xiao Wang, and Xiantao Xiao. A two-phase stochastic momentum-based algorithm for nonconvex expectation-constrained optimization.Journal of Scientific Computing, 104(1):16, 2025

    2025

  35. [35]

    Bome! bilevel optimization made easy: A simple first-order approach.Advances in neural information processing systems, 35:17248–17262, 2022

    Bo Liu, Mao Ye, Stephen Wright, Peter Stone, and Qiang Liu. Bome! bilevel optimization made easy: A simple first-order approach.Advances in neural information processing systems, 35:17248–17262, 2022

    2022

  36. [36]

    A generalized alternating method for bilevel learning under the polyak-{\L}ojasiewicz condition.arXiv preprint arXiv:2306.02422, 2023

    Quan Xiao, Songtao Lu, and Tianyi Chen. A generalized alternating method for bilevel learning under the polyak-{\L}ojasiewicz condition.arXiv preprint arXiv:2306.02422, 2023

    Pith/arXiv arXiv 2023

  37. [37]

    On finding small hyper-gradients in bilevel optimization: Hardness results and improved analysis

    Lesi Chen, Jing Xu, and Jingzhao Zhang. On finding small hyper-gradients in bilevel optimization: Hardness results and improved analysis. InThe Thirty Seventh Annual Conference on Learning Theory, pages 947–980. PMLR, 2024. 13

    2024

  38. [38]

    Mohammad Mahdi Ahmadi and Erfan Yazdandoost Hamedani. Single-loop projection-free and projected gradient-based algorithms for nonconvex-concave saddle point problems with bilevel structure.Journal of Scientific Computing, 103(2):52, 2025

    2025

  39. [39]

    On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation.arXiv preprint arXiv:2309.01753, 2023

    Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert Nowak. On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation.arXiv preprint arXiv:2309.01753, 2023

    Pith/arXiv arXiv 2023

  40. [40]

    A near-optimal algorithm for stochastic bilevel optimization via double-momentum.Advances in neural information processing systems, 34:30271–30283, 2021

    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.Advances in neural information processing systems, 34:30271–30283, 2021

    2021

  41. [41]

    Tighter analysis of alternating stochastic gradient method for stochastic nested problems.arXiv preprint arXiv:2106.13781, 2021

    Tianyi Chen, Yuejiao Sun, and Wotao Yin. Tighter analysis of alternating stochastic gradient method for stochastic nested problems.arXiv preprint arXiv:2106.13781, 2021

    Pith/arXiv arXiv 2021

  42. [42]

    Perturbed gra- dient descent via convex quadratic approximation for nonconvex bilevel optimization.arXiv preprint arXiv:2504.17215, 2025

    Nazanin Abolfazli, Sina Sharifi, Mahyar Fazlyab, and Erfan Yazdandoost Hamedani. Perturbed gra- dient descent via convex quadratic approximation for nonconvex bilevel optimization.arXiv preprint arXiv:2504.17215, 2025

    Pith/arXiv arXiv 2025

  43. [43]

    Sequential qcqp for bilevel optimization with line search.IEEE Control Systems Letters, 2025

    Sina Sharifi, Erfan Yazdandoost Hamedani, and Mahyar Fazlyab. Sequential qcqp for bilevel optimization with line search.IEEE Control Systems Letters, 2025

    2025

  44. [44]

    Accelerated stochastic algorithms for convex-concave saddle-point problems.Mathematics of Operations Research, 47(2):1443–1473, 2022

    Renbo Zhao. Accelerated stochastic algorithms for convex-concave saddle-point problems.Mathematics of Operations Research, 47(2):1443–1473, 2022

    2022

  45. [45]

    Momentum-based variance reduction in non-convex SGD

    Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction in non-convex SGD. In Advances in Neural Information Processing Systems, volume 32, 2019

    2019

  46. [46]

    Tofu: A task of fictitious unlearning for llms.arXiv preprint arXiv:2401.06121, 2024

    Pratyush Maini, Zhili Feng, Avi Schwarzschild, Zachary C Lipton, and J Zico Kolter. Tofu: A task of fictitious unlearning for llms.arXiv preprint arXiv:2401.06121, 2024

    Pith/arXiv arXiv 2024

  47. [47]

    Muse: Machine unlearning six-way evaluation for language models.arXiv preprint arXiv:2407.06460, 2024

    Weijia Shi, Jaechan Lee, Yangsibo Huang, Sadhika Malladi, Jieyu Zhao, Ari Holtzman, Daogao Liu, Luke Zettlemoyer, Noah A Smith, and Chiyuan Zhang. Muse: Machine unlearning six-way evaluation for language models.arXiv preprint arXiv:2407.06460, 2024

    Pith/arXiv arXiv 2024

  48. [48]

    Openunlearning: Accelerating llm unlearning via unified benchmarking of methods and metrics.arXiv preprint arXiv:2506.12618, 2025

    Vineeth Dorna, Anmol Mekala, Wenlong Zhao, Andrew McCallum, Zachary C Lipton, J Zico Kolter, and Pratyush Maini. Openunlearning: Accelerating llm unlearning via unified benchmarking of methods and metrics.arXiv preprint arXiv:2506.12618, 2025. 14 Technical Appendix and Supplementary Material A Auxiliary Lemmas Lemma A.1.Let λk and λγ,k be defined as in(4)...

    arXiv 2025