Pith. sign in

REVIEW 3 major objections 5 minor 59 references

SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel Optimization

T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read SPARKLE is a single-loop primal-dual framework for decentralized bilevel optimization, and its ED and EXTRA variants converge faster than its gradient-tracking variant.

desk verdict A genuinely useful unified framework with honest, coherent proofs; the ED/EXTRA-beats-GT headline is formally right but only bites at spectral gaps below n^{-3}, a regime the paper's own experiments never test. read the letter →

arxiv 2411.14166 v3 pith:VPB6DQEK submitted 2024-11-21 math.OC cs.LGstat.ML

Shuchen Zhu , Boao Kong , Songtao Lu , Xinmeng Huang , Kun Yuan This is my paper · ORCID
classification math.OCcs.LGstat.ML MSC 90C2690C3068W15
keywords decentralizedbileveloptimizationsingle-loopprimal-dualframeworkheterogeneitycorrectionEXTRAExactDiffusiongradienttrackinglinearspeeduptransientiterationcomplexity
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

Decentralized bilevel optimization asks a network of agents to solve a nested problem—an outer objective that depends on the solution of an inner one—using only neighbor-to-neighbor communication. The paper proposes SPARKLE, a single-loop primal-dual framework in which each of the three subproblems (upper, lower, and an auxiliary variable that replaces the Hessian inverse) is updated by one step of the same flexible scheme, with hyperparameters selecting EXTRA, Exact Diffusion (ED), or gradient tracking (GT) independently at each level. Its unified convergence theorem covers every variant under milder assumptions than prior work, dropping bounded-gradient and bounded-heterogeneity conditions. The central quantitative claim is that ED and EXTRA variants reach the linear-speedup regime in $O(n^3/(1-\rho)^2)$ transient iterations, strictly better than the GT variant's $O(\max\{n^3/(1-\rho)^2, n/(1-\rho)^{8/3}\})$ on the same network, and that mixed strategies inherit the better rate. If correct, this gives concrete guidance: for decentralized bilevel problems, the lower-level update mechanism matters most, and gradient tracking alone is not the best choice.

What carries the argument

The load-bearing object is the primal-dual recursion $s^{k+1}=C_s s^k - \alpha_s A_s g_s^k - B_s d_s^k,\ d_s^{k+1}=d_s^k+B_s s^{k+1}$, applied once per level $s\in\{x,y,z\}$, with a momentum variable $r^{k+1}=(1-\theta)r^k+\theta u^k$ only in the upper level. Choosing communication matrices $A_s,B_s,C_s$ as polynomials of a doubly stochastic mixing matrix $W_s$ makes the same recursion specialize to ED, EXTRA, or the ATC/semi/non-ATC gradient-tracking variants. The proof transforms the consensus error into iterations of matrices $\Gamma_s$ with spectral norm below one, then ties the hypergradient error, the lower-level error $\|y-y^\star(x)\|$, and the auxiliary error $\|z-z^\star(x)\|$ into one Lyapunov-style inequality; the moving average absorbs the stochastic variance and is what lets the analysis drop boundedness assumptions and reach the linear-speedup term.

What would settle it

Run SPARKLE-ED on a ring network with $n$ agents and a stochastic bilevel problem satisfying the paper's assumptions, and measure the iteration count at which the empirical squared-gradient average first reaches the linear-speedup curve $\sigma/\sqrt{nK}$. If the required transient iterations scale as $n^3/(1-\rho)^4$ rather than $n^3/(1-\rho)^2$ as the ring's spectral gap $1-\rho$ shrinks, Corollary 2's claimed dependence is falsified.

Watch

Extended reading notes

Core claim

On its own terms, the paper establishes that a single algorithmic template can instantiate several known heterogeneity-correction mechanisms and that this unification yields a strictly sharper convergence theory. Theorem 1 states that with constant step sizes and a moving-average coefficient, SPARKLE converges at rate $\frac{1}{K+1}\sum_{k=0}^K E\|\nabla\Phi(\bar x_k)\|^2 \lesssim \kappa^5\sigma/\sqrt{nK}$ plus lower-order network-dependent terms, matching the single-node SOBA asymptotic rate when $n=1$. From this, Corollaries 2–3 give transient iteration complexities $n^3/(1-\rho)^2$ for SPARKLE-ED and SPARKLE-EXTRA versus $\max\{n^3/(1-\rho)^2, n/(1-\rho)^{8/3}\}$ for SPARKLE-GT, and Corollary 4 shows the ED/EXTRA advantage persists when those methods update the lower and auxiliary variables while GT updates the upper variable. The paper further argues that the lower-level update strategy dominates the transient behavior, allowing a sparser communication graph for the upper variable without harming the rate. It also shows that when the lower-level problem is trivial, SPARKLE degenerates to a known single-level decentralized framework, so the bilevel analysis subsumes the single-level convergence results.

Load-bearing premise

The argument presupposes that every agent's lower-level objective $g_i(x,y)$ is strongly convex in $y$, so the best-response map $y^\star(x)$ exists and is unique; without that, the hypergradient formula and the contraction steps for $y$ and $z$ have no foundation.

Editorial extensions

If this is right

  • Every SPARKLE variant achieves the asymptotic rate $\kappa^5\sigma/\sqrt{nK}$, matching the single-node SOBA bound, so decentralization adds only a lower-order $1/K$ term.
  • SPARKLE-ED and SPARKLE-EXTRA reach linear speedup after $O(n^3/(1-\rho)^2)$ iterations, one power of $1/(1-\rho)$ better than the GT variant's extra transient term $n/(1-\rho)^{8/3}$.
  • Putting ED or EXTRA on the lower and auxiliary levels and GT on the upper level gives the same $n^3/(1-\rho)^2$ transient complexity, so practitioners can keep GT-style upper updates without losing the better rate.
  • The upper variable's communication graph may be sparser than the lower one's as long as $(1-\rho(W_x))^{-1}\lesssim \sqrt{n}(1-\rho(W_y))^{-1}$, cutting per-round communication cost.
  • Setting the lower-level loss trivial ($g_i(x,y)\equiv \|y\|^2/2$) makes SPARKLE reduce to single-level decentralized ED/EXTRA/GT, recovering their known rates from the bilevel theorem.

Reading between the lines

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

  • I read the result as saying the bottleneck in decentralized bilevel optimization is estimating the lower-level solution and the Hessian inverse, not the outer consensus; the same hierarchy of error terms likely appears in other bilevel algorithms even when they do not use this framework.
  • The momentum variable is only needed for the upper level; the analysis suggests one could run lower and auxiliary levels without it and still keep the rate, which would reduce tuning if implemented.
  • Because the framework is orthogonal to variance reduction, a natural testable extension is to feed variance-reduced gradient estimators into each level and ask whether the transient complexity improves further; the paper notes the framework can incorporate them but does not analyze that combination.
  • For merely convex lower-level problems, the paper leaves convergence open; one possible workaround suggested by the structure is to add a small strongly convex regularizer to the lower level and study the bias it introduces.
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 / 5 minor

Summary. The paper proposes SPARKLE, a single-loop primal-dual framework for decentralized stochastic bilevel optimization that unifies gradient tracking, EXTRA, and Exact Diffusion by choosing communication matrices A_s, B_s, C_s for the upper, lower, and auxiliary variables. The central theoretical result (Theorem 1, Lemma 17) gives a non-asymptotic convergence bound under Lipschitz smoothness and strong convexity of the lower level, without bounded-gradient or bounded-heterogeneity assumptions, and yields asymptotic linear speedup with explicit transient iteration complexity. Corollaries 2–4 and Table 2 state that SPARKLE-EXTRA and SPARKLE-ED have transient complexity n^3/(1-ρ)^2, while SPARKLE-GT has max{n^3/(1-ρ)^2, n/(1-ρ)^{8/3}}, leading the authors to conclude that EXTRA and ED are more suitable than GT for decentralized bilevel optimization and that mixed lower/upper strategies can outperform GT alone. The paper also includes experiments on hyper-cleaning, policy evaluation, and meta-learning.

Significance. If the results hold, the framework is a useful unifying contribution: it extends the known single-level unification of GT/EXTRA/ED to bilevel optimization, removes bounded-gradient and bounded-heterogeneity assumptions that appear in several prior works, allows different mechanisms at different levels, and matches single-level frontier rates in the degenerate case. The proof apparatus is extensive and structurally coherent: the descent lemmas for the upper, lower, and auxiliary levels, the consensus error bounds, and the coupled-inequality argument culminating in Lemma 17 are a substantial technical effort. Section 3.6's reduction to single-level optimization is a noteworthy consistency check that gives the claimed subsumption some content. However, the advertised superiority of EXTRA/ED over GT is more delicate than the abstract and Remark 3 suggest, because the strictness of the inequality between the two transient complexities only occurs in a narrow spectral-gap regime, and the explicit constants supporting the comparison are imported from prior work rather than derived in this manuscript.

major comments (3)
  1. [§3.3, Corollaries 2–3, Remark 3; §4, Figure 3] The claim that SPARKLE-EXTRA and SPARKLE-ED provably outperform SPARKLE-GT in transient iteration complexity is only strict in a narrow regime. Comparing n^3/(1-ρ)^2 with max{n^3/(1-ρ)^2, n/(1-ρ)^{8/3}}, the first term dominates exactly when 1-ρ ≥ n^{-3}, in which case the two upper bounds coincide up to constants. For the experiments in Section 4 with n=10 and ρ ∈ {0.647, 0.828, 0.924, 0.990}, we have 1-ρ ≥ 0.010 ≫ 10^{-3}, so the advertised theoretical ranking is not realized in any tested topology. The observed gains of ED/EXTRA over GT in Figures 2–3 must therefore come from unquantified constant factors, not from the transient-complexity comparison stated in Corollaries 2–3. I recommend that the authors state the regime 1-ρ < n^{-3} explicitly, soften the abstract and Remark 3, and add an experiment (e.g., a ring with n large or a lazily updated mixing matrix) where the comparison actually bites.
  2. [Appendix C.2.2, Table 4] The explicit values of δ_x, δ_y, δ_z and hat-δ_x, hat-δ_y, hat-δ_z used in Corollaries 2–3 are not derived in this paper. Lemma 3 only establishes the existence of matrices O and Γ with ∥Γ∥ < 1; the quantitative bounds such as ∥O∥, ∥O^{-1}∥, ∥Λ_b^{-1}∥, and ∥Γ∥ in Table 4 are taken from [2, Appendix B.2]. Because these constants are load-bearing for the central comparison between SPARKLE variants, the manuscript should either provide a self-contained construction of O and Γ for ED, EXTRA, and GT, or state precisely which results from [2] are being invoked and reproduce the needed arguments in the appendix.
  3. [§4, Figures 2–3 and Remark 3] The experiments in Section 4 measure test accuracy or upper-level loss, not the stationarity measure ∥∇Φ(·)∥^2 used in Theorem 1. Consequently, the empirical ordering of SPARKLE-ED/EXTRA versus SPARKLE-GT does not by itself confirm the transient-complexity ranking in Corollaries 2–3; it is consistent with a constant-factor difference. Since the paper makes a strong theoretical claim about transient complexity, I suggest reporting, at least for a simple synthetic problem as in Appendix D.1, the empirical stationarity gap versus iterations together with the spectral gaps of the mixing matrices, so the regime in which the theoretical ranking is strict is actually tested.
minor comments (5)
  1. [§3.3, after Theorem 1] The sentence 'This recovers the rate in [15]' cites [15] (Eflops: Algorithm and system co-design for a high performance distributed training platform), which appears unrelated to deterministic decentralized bilevel optimization; please verify and replace the citation.
  2. [Figures 2–3, 5–9] The legend labels contain visible 'uni00AD' artifacts (e.g., 'SPARKLE/uni00ADGT'); these should be cleaned in the figure files.
  3. [Footnote on page 1] There is a typo in the affiliation footnote: 'National Engineering Labratory' should be 'Laboratory'.
  4. [Table 1] The table header uses several unexplained symbols (▷, ♢, †, ‡, ◁) and the entry 'ap+qnε2♯' is hard to parse; please define all symbols in the caption or in a separate legend.
  5. [Assumption 2 and Appendix C.2.2] For ED and EXTRA the analysis additionally requires the mixing matrix W to be positive definite, with a lazy-replacement W ← tI + (1-t)W suggested in Appendix C.2.2; this restriction should be stated explicitly in Assumption 2 or in a remark in the main text, since Assumption 2 as written only requires the second eigenvalue to be strictly less than one in magnitude.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central convergence theorem and transient-complexity corollaries are derived from explicit assumptions, and self-citations serve only as technical building blocks or comparison baselines.

full rationale

The paper's derivation chain is self-contained at the level that matters for circularity. Theorem 1 is proved from Assumptions 1-4 through a long sequence of explicit lemmas (Lemmas 4-17), with step-size choices given in (88)-(89); no parameter is fitted to data and then renamed as a prediction. The transient-iteration-complexity claims in Corollaries 1-4 are obtained by substituting the matrix-norm bounds of Table 4 into the closed-form expression of Lemma 18, and the ED/EXTRA-versus-GT comparison is arithmetic on the resulting max expressions, not a restatement of an input. Section 3.6's claim that bilevel optimization subsumes single-level optimization is explicitly a special-case construction (Gi(x,y)=|y|^2/2, Fi independent of y) that reduces SPARKLE to the single-level framework (6); this is a consistency check, and it is not used to prove the main rates. The references to the authors' prior work are not load-bearing in a circular way: [2] supplies the unified single-level formulation and matrix-norm estimates, but Lemma 3's key similarity transformation is proved in the paper itself, and the rate comparison with D-SOBA [29] treats that work as an external baseline rather than as the source of the main result. The narrowness of the ED/EXTRA superiority claim (requiring 1-rho < n^{-3}, a regime not realized in the paper's own experiments) is a legitimate scope-of-claim or overgeneralization concern, but it is not a circularity: the comparison follows from the derived bounds rather than being assumed into them. No step reduces, by construction or by self-citation, to its own inputs.

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

The central claim rests on standard smoothness/strong-convexity assumptions (Assumption 1), consensus assumptions (Assumption 2), a technical matrix polynomial assumption tailored to the framework (Assumption 3), and bounded variance (Assumption 4). No free parameters are fitted to data; algorithm step sizes are chosen in the proof to satisfy derived inequalities. No new physical or algorithmic entities are postulated beyond the known auxiliary variable z from SOBA [12].

assumptions (6)
  • standard math The hypergradient formula (Eq. 3) expresses ∇Φ(x) using the lower-level solution y*(x) and inverse Hessian; this is taken from [22] and not derived.
    Invoked in Section 2.1 as the starting point for the three-subproblem decomposition.
  • domain assumption Assumption 1: functions and derivatives are Lipschitz, and gi is μg-strongly convex in y.
    Imposed in Section 3.1; needed for contraction of y and z and boundedness of z*.
  • domain assumption Assumption 2: mixing matrices are symmetric, doubly stochastic, strongly connected.
    Standard consensus condition, used throughout the analysis.
  • ad hoc to paper Assumption 3: As, Bs, Cs are polynomials of Ws and the augmented matrix Ls has spectral radius less than one.
    Introduced specifically to make the unified framework tractable; satisfied by all listed variants.
  • domain assumption Assumption 4: unbiased stochastic gradients, Jacobians, and Hessians with bounded variances.
    Standard in stochastic optimization; used in variance bounds.
  • standard math Lemma 3 (existence of O and Γ with norm less than one) is used to bound consensus errors; the explicit construction is deferred to [2].
    The lemma is proven in Appendix C.1.4, but the concrete norm bounds in Table 4 come from [2, Appendix B.2].

how reviews work

0 comments
Cite this review

Pith. "Pith review of SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel Optimization." pith.science (2026). https://pith.science/paper/VPB6DQEK

@misc{pith2026241114166,
  author       = {Pith},
  title        = {Pith review of: SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VPB6DQEK}},
  note         = {Machine review of arXiv:2411.14166}
}
read the original abstract

This paper studies decentralized bilevel optimization, in which multiple agents collaborate to solve problems involving nested optimization structures with neighborhood communications. Most existing literature primarily utilizes gradient tracking to mitigate the influence of data heterogeneity, without exploring other well-known heterogeneity-correction techniques such as EXTRA or Exact Diffusion. Additionally, these studies often employ identical decentralized strategies for both upper- and lower-level problems, neglecting to leverage distinct mechanisms across different levels. To address these limitations, this paper proposes SPARKLE, a unified Single-loop Primal-dual AlgoRithm frameworK for decentraLized bilEvel optimization. SPARKLE offers the flexibility to incorporate various heterogeneitycorrection strategies into the algorithm. Moreover, SPARKLE allows for different strategies to solve upper- and lower-level problems. We present a unified convergence analysis for SPARKLE, applicable to all its variants, with state-of-the-art convergence rates compared to existing decentralized bilevel algorithms. Our results further reveal that EXTRA and Exact Diffusion are more suitable for decentralized bilevel optimization, and using mixed strategies in bilevel algorithms brings more benefits than relying solely on gradient tracking.

Figures

Figures reproduced from arXiv: 2411.14166 by the authors.

Figure 1
Figure 1. SPARKLE algorithms, represented by ribbons, employ mixed decentralized mechanisms at the [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. The test accuracy on hyper-cleaning with various SPARKLE-based algorithms using different corruption rates p. (Left: p = 0.1, Middle: p = 0.2, Right: p = 0.3.) 0 500 1000 1500 2000 2500 3000 3500 number of gradient evaluations 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 test accuracy (a)SPARKLE-EXTRA; Fixed topo x; Varied topo of y, z 2200 2400 2600 2800 3000 3200 3400 0.65 0.70 0.75 0.80 = 0.647 = 0.828 = 0.924 = 0.990 0 5… view at source ↗
Figure 4
Figure 4. The upper-level loss against samples generated by one agent of different algorithms in the policy evaluation. (Left: n = 10, Right: n = 20.) will deteriorate the algorithmic performance. Conversely, preserving the topology for y and z while decreasing the connectivity for x has little impact on the performance. This suggests that the influence of the network topology for y and z on the algorithm dominates over the t… view at source ↗
Figures from the paper (5 more)
Figure 5
Figure 5. Figure 5: The estimation error of D-SOBA, SPARKLE-GT, SPARKLE-ED, and SPARKLE-EXTRA under different networks and data heterogeneity. where x ∈ R D, y ∈ R K and Cr denotes a fixed regularization parameter. For each agent i, we firstly generate the local solution y ∗ i , x∗ i as y…
Figure 6
Figure 6. Figure 6: Hypergradient evaluation times for required test accuracy in hyper-cleaning problem. (Left: [PITH_FULL_IMAGE:figures/full_fig_p070_6.png]
Figure 7
Figure 7. Figure 7: The average test accuracy of SPARKLE-EXTRA and SPARKLE-EXTRA-GT on hyper-cleaning [PITH_FULL_IMAGE:figures/full_fig_p071_7.png]
Figure 8
Figure 8. Figure 8: The test loss against samples generated by one agent of different algorithms in the policy evaluation. [PITH_FULL_IMAGE:figures/full_fig_p072_8.png]
Figure 9
Figure 9. Figure 9: The accuracy on training and testing set of different algorithms for the meta-learning problem. [PITH_FULL_IMAGE:figures/full_fig_p074_9.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

59 extracted references · 49 canonical work pages

  1. [2]

    S. A. Alghunaim and K. Yuan. A unified and refined convergence analysis for non-convex decentralized learning. IEEE Transactions on Signal Processing, 2022

    work page 2022

  2. [1]

    S. A. Alghunaim, E. K. Ryu, K. Yuan, and A. H. Sayed. Decentralized proximal gradient algorithms with linear convergence rates.IEEE Transactions on Automatic Control, 66(6):2787–2794, 2020

    work page 2020

  3. [3]

    Arora, S

    S. Arora, S. Du, S. Kakade, Y. Luo, and N. Saunshi. Provable representation learning for imitation learning via bi-level optimization. InInternational Conference on Machine Learning, pages 367–376. PMLR, 2020

    work page 2020

  4. [4]

    Bertinetto, J

    L. Bertinetto, J. Henriques, P. Torr, and A. Vedaldi. Meta-learning with differentiable closed-form solvers. In International Conference on Learning Representations (ICLR), 2019. International Conference on Learning Representations, 2019

    work page 2019

  5. [5]

    Chang, M

    T.-H. Chang, M. Hong, and X. Wang. Multi-agent distributed optimization via inexact consensus admm.IEEE Transactions on Signal Processing, 63(2):482–497, 2014

    work page 2014

  6. [6]

    Chen and A

    J. Chen and A. H. Sayed. Diffusion adaptation strategies for distributed optimization and learning over networks. IEEE Transactions on Signal Processing, 60(8):4289–4305, 2012

    work page 2012

  7. [7]

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

    work page 2022

  8. [8]

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

    work page 2021

Show all 59 references
  1. [9]

    X. Chen, M. Huang, and S. Ma. Decentralized bilevel optimization.arXiv preprint arXiv:2206.05670, 2022

    2022 arXiv

  2. [10]

    X. Chen, M. Huang, S. Ma, and K. Balasubramanian. Decentralized stochastic bilevel optimization with improved per-iteration complexity. InInternational Conference on Machine Learning, pages 4641–4671. PMLR, 2023

    2023

  3. [11]

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

    2023 arXiv

  4. [12]

    Dagréou, P

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

    2022

  5. [13]

    Di Lorenzo and G

    P. Di Lorenzo and G. Scutari. Next: In-network nonconvex optimization.IEEE Transactions on Signal and Information Processing over Networks, 2(2):120–136, 2016

    2016

  6. [14]

    J. Domke. Generic methods for optimization-based modeling. InArtificial Intelligence and Statistics, pages 318–326. PMLR, 2012

    2012

  7. [15]

    J. Dong, Z. Cao, T. Zhang, J. Ye, S. Wang, F. Feng, L. Zhao, et al. Eflops: Algorithm and system co-design for a high performance distributed training platform. In2020 IEEE International Symposium on High Performance Computer Architecture (HPCA), pages 610–622, 2020

    2020

  8. [16]

    Y. Dong, S. Ma, J. Yang, and C. Yin. A single-loop algorithm for decentralized bilevel optimization.arXiv preprint arXiv:2311.08945, 2023

    2023 arXiv

  9. [17]

    J. C. Duchi, A. Agarwal, and M. J. Wainwright. Dual averaging for distributed optimization: Convergence analysis and network scaling.IEEE Transactions on Automatic control, 57(3):592–606, 2011

    2011

  10. [18]

    C. Finn, P. Abbeel, and S. Levine. Model-agnostic meta-learning for fast adaptation of deep networks.International Conference on Machine Learning, pages 1126–1135, 2017. 13

    2017

  11. [19]

    Franceschi, P

    L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil. Bilevel programming for hyperparameter optimization and meta-learning. InInternational Conference on Machine Learning, pages 1568–1577. PMLR, 2018

    2018

  12. [20]

    B. Gao, Y. Yang, and Y. xiang Yuan. Lancbio: dynamic lanczos-aided bilevel optimization via krylov subspace. arXiv preprint arXiv:2404.03331, 2024

    2024 arXiv

  13. [21]

    H. Gao, B. Gu, and M. T. Thai. On the convergence of distributed stochastic bilevel optimization algorithms over a network. InInternational Conference on Artificial Intelligence and Statistics, pages 9238–9281. PMLR, 2023

    2023

  14. [22]

    Ghadimi and M

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

    2018 arXiv

  15. [23]

    Grazzi, L

    R. Grazzi, L. Franceschi, M. Pontil, and S. Salzo. On the iteration complexity of hypergradient computation. In International Conference on Machine Learning, pages 3748–3758. PMLR, 2020

    2020

  16. [24]

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

    2021 arXiv

  17. [25]

    Hong, H.-T

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

    2023

  18. [26]

    Jakovetić

    D. Jakovetić. A unification and generalization of exact distributed first-order methods.IEEE Transactions on Signal and Information Processing over Networks, 5(1):31–46, 2018

    2018

  19. [27]

    K. Ji, J. Yang, and Y. Liang. Bilevel optimization: Convergence analysis and enhanced design. InInternational Conference on Machine Learning, pages 4882–4892. PMLR, 2021

    2021

  20. [28]

    Koloskova, T

    A. Koloskova, T. Lin, and S. U. Stich. An improved analysis of gradient tracking for decentralized machine learning. Advances in Neural Information Processing Systems, 34:11422–11435, 2021

    2021

  21. [29]

    B. Kong, S. Zhu, S. Lu, X. Huang, and K. Yuan. Decentralized bilevel optimization over graphs: Loopless algorithmic update and transient iteration complexity.arXiv preprint arXiv:2402.03167, 2024

    2024

  22. [30]

    Z. Li, W. Shi, and M. Yan. A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates.IEEE Transactions on Signal Processing, July 2019. early acces. Also available on arXiv:1704.07807

    2019 arXiv

  23. [31]

    X. Lian, C. Zhang, H. Zhang, C.-J. Hsieh, W. Zhang, and J. Liu. Can decentralized algorithms outperform centralized algorithms? A case study for decentralized parallel stochastic gradient descent. InAdvances in Neural Information Processing Systems, pages 5330–5340, 2017

    2017

  24. [32]

    T. Lin, S. P. Karimireddy, S. U. Stich, and M. Jaggi. Quasi-global momentum: Accelerating decentralized deep learning on heterogeneous data. InInternational Conference on Machine Learning, 2021

    2021

  25. [33]

    S. Lu, S. Zeng, X. Cui, M. Squillante, L. Horesh, B. Kingsbury, J. Liu, and M. Hong. A stochastic linearized augmented lagrangian method for decentralized bilevel optimization.Advances in Neural Information Processing Systems, 35:30638–30650, 2022

    2022

  26. [34]

    Lu and C

    Y. Lu and C. De Sa. Optimal complexity in decentralized training. InInternational Conference on Machine Learning, pages 7111–7123. PMLR, 2021

    2021

  27. [35]

    Maclaurin, D

    D. Maclaurin, D. Duvenaud, and R. Adams. Gradient-based hyperparameter optimization through reversible learning. In International Conference on Machine Learning, pages 2113–2122. PMLR, 2015

    2015

  28. [36]

    Madry, A

    A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. InInternational Conference on Learning Representations, 2018

    2018

  29. [37]

    Nedić, A

    A. Nedić, A. Olshevsky, and M. G. Rabbat. Network topology and communication-computation tradeoffs in decentralized optimization. Proceedings of the IEEE, 106(5):953–976, 2018

    2018

  30. [38]

    Nedic, A

    A. Nedic, A. Olshevsky, and W. Shi. Achieving geometric convergence for distributed optimization over time- varying graphs.SIAM Journal on Optimization, 27(4):2597–2633, 2017. 14

    2017

  31. [39]

    Nedic and A

    A. Nedic and A. Ozdaglar. Distributed subgradient methods for multi-agent optimization.IEEE Transactions on Automatic Control, 54(1):48–61, 2009

    2009

  32. [40]

    Y. Niu, J. Xu, Y. Sun, Y. Huang, and L. Chai. Distributed stochastic bilevel optimization: Improved complexity and heterogeneity analysis.arXiv preprint arXiv:2312.14690, 2023

    2023 arXiv

  33. [41]

    Qu and N

    G. Qu and N. Li. Harnessing smoothness to accelerate distributed optimization.IEEE Transactions on Control of Network Systems, 5(3):1245–1260, 2018

    2018

  34. [42]

    Russakovsky, J

    O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, et al. Imagenet large scale visual recognition challenge.International Journal of Computer Vision, 115:211–252, 2015

    2015

  35. [43]

    A. H. Sayed. Adaptive networks.Proceedings of the IEEE, 102(4):460–497, 2014

    2014

  36. [44]

    Shaban, C.-A

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

    2019

  37. [45]

    W. Shi, Q. Ling, G. Wu, and W. Yin. EXTRA: An exact first-order algorithm for decentralized consensus optimization. SIAM Journal on Optimization, 25(2):944–966, 2015

    2015

  38. [46]

    H. Tang, X. Lian, M. Yan, C. Zhang, and J. Liu. D2: Decentralized training over decentralized data. In International Conference on Machine Learning, pages 4848–4856, 2018

    2018

  39. [47]

    Vinyals, C

    O. Vinyals, C. Blundell, T. Lillicrap, D. Wierstra, et al. Matching networks for one shot learning.Advances in Neural Information Processing Systems, 29, 2016

    2016

  40. [48]

    H. Xiao, K. Rasul, and R. Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07747, 2017

    2017 arXiv

  41. [49]

    J. Xu, Y. Tian, Y. Sun, and G. Scutari. Distributed algorithms for composite optimization: Unified framework and convergence analysis.IEEE Transactions on Signal Processing, 69:3555–3570, 2021

    2021

  42. [50]

    J. Xu, S. Zhu, Y. C. Soh, and L. Xie. Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes. InIEEE Conference on Decision and Control (CDC), pages 2055–2060, Osaka, Japan, 2015

    2015

  43. [51]

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

    2021

  44. [52]

    S. Yang, X. Zhang, and M. Wang. Decentralized gossip-based stochastic bilevel optimization over communication networks. Advances in Neural Information Processing Systems, 35:238–252, 2022

    2022

  45. [53]

    K. Yuan, S. A. Alghunaim, and X. Huang. Removing data heterogeneity influence enhances network topology dependence of decentralized SGD.Journal of Machine Learning Research, 24(280):1–53, 2023

    2023

  46. [54]

    K. Yuan, S. A. Alghunaim, B. Ying, and A. H. Sayed. On the influence of bias-correction on distributed stochastic optimization. IEEE Transactions on Signal Processing, 2020

    2020

  47. [55]

    K. Yuan, Q. Ling, and W. Yin. On the convergence of decentralized gradient descent.SIAM Journal on Optimization, 26(3):1835–1854, 2016

    2016

  48. [56]

    K. Yuan, B. Ying, X. Zhao, and A. H. Sayed. Exact dffusion for distributed optimization and learning – Part I: Algorithm development.IEEE Transactions on Signal Processing, 67(3):708 – 723, 2018

    2018

  49. [57]

    SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel Optimization

    Y. Zhang, M. T. Thai, J. Wu, and H. Gao. On the communication complexity of decentralized bilevel optimization. arXiv preprint arXiv:2311.11342, 2023. 15 Appendix for “SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel Optimization” Contents A More ...

    2023 arXiv

  50. [58]

    Subtracting 2 K−1X k=0 (1 − θ)2 θ L2 ∇Φα2 · 2E∥Ek[¯rk+1] − ∇Φ(¯xk)∥2 31 from both sides of (50), we have: KX k=0 θE∥Ek ¯rk+1 − ∇Φ(¯xk)∥2 ≤4 KX k=0 θE∥Ek ¯uk − ∇Φ(¯xk)∥2 + 8 K−1X k=0 (1 − θ)θ2E∥¯uk − Ek ¯uk∥2 + 4(1 − θ)2∥∇Φ(¯x0)∥2 + θ 4 K−1X k=0 E∥∇Φ(¯xk)∥2. (51) Substituting (...

  51. [59]

    κ2∥Oy∥2∥ˆek+1 y ∥2 n # + 6(K + 1)γ µgn 3σ2 g,2 L2 f,0 µ2g + σ2 f,1 ! + 73κ4

    Taking the summation and expectation on the both sides, we get: KX k=0 βµg 2 E[∥¯yk − y⋆(¯xk−1)∥2] + E[∥¯yk+1 − y⋆(¯xk)∥2] ≤E∥¯y0 − y⋆(¯x0)∥2 + KX k=0 E " 3α2 βµg L2 y⋆ ∥¯rk∥2 + 3β µg L2 g,1 ∥xk − ¯xk∥2 n + ∥yk − ¯yk∥2 n + β2 σ2 g,1 n # . Using (36) and the fact thatx0, y0 is ...

Pith tools

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