REVIEW 3 major objections 4 minor 28 references
MARINA-P: Superior Performance in Non-smooth Federated Optimization with Adaptive Stepsizes
T0 review · 3 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read This paper proves that two server-to-worker compressed federated methods, EF21-P and MARINA-P, achieve the optimal O(1/sqrt(T)) convergence rate on non-smooth convex objectives, the first such distributed guarantees with downlink…
desk verdict EF21-P is solid and actually proves the global O(1/√T) rate; MARINA-P proves only an average-of-local-gaps rate, so the advertised 'optimal for both algorithms' overstates Theorem 2. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is a Lyapunov function that couples the distance to the optimum with the compression error: V_t = ||x_t - x*||^2 + (1/($\lambda$* $\theta$)) ||w_t - x_t||^2 for EF21-P, and the analogous averaged version for MARINA-P. Two per-iteration bounds feed a descent lemma: a subgradient inequality on the update step and a contraction inequality for the biased (EF21-P) or unbiased (MARINA-P) compressor applied to the broadcast difference. The proof selects the free Young-inequality parameter $\lambda$ optimally to minimize the constant multiplying the squared subgradient norm, yielding B* = 1 + 2 $\sqrt$(1-$\alpha$)/(1-$\sqrt$(1-$\alpha$)) for EF21-P. For MARINA-P, the worker-specific compressors allow a variance-decomposition step that keeps only the averaged subgradient norm, and the correlated Perm_K compressor makes (1/n) sum Q_i(x) = x exactly, which is why it performs best in experiments.
What would settle it
Run distributed EF21-P on a two-worker non-smooth convex problem such as f(x) = (||x||_1 + ||x-1||_1)/2, with one worker forced to use a one-round-old w_t while the other is current, and compare the empirical suboptimality against the claimed O(1/sqrt(T)) bound; if the averaged subgradient is no longer a subgradient at a common point and the function gap stops shrinking at that rate, the synchronized evaluation premise is load-bearing.
Extended reading notes
Core claim
The central claim is Theorem 1 and Theorem 2: under convexity and individual Lipschitz continuity of the client losses, distributed EF21-P and MARINA-P satisfy E[f(wbar_T)-f(x*)] <= $\sqrt$(B* $L0^{2}$ V0)/$\sqrt$(T) with optimally tuned constant stepsizes and with Polyak stepsizes, where B* depends only on the compression factor $\alpha$ (for EF21-P) and on the unbiased-compression parameters omega and p (for MARINA-P). Decreasing stepsizes give E[f(w_hat_T)-f(x*)] <= 2 $\sqrt$(2 B* $L0^{2}$ V0) $\sqrt$(log(T+1)/T). These are the first theoretical guarantees for distributed non-smooth optimization with server-to-worker compression, and the proof extends a single-node non-smooth analysis of EF21-P by averaging subgradients at a common broadcast point w_t. A corollary gives T = O($L0^{2}$ $R0^{2}$/($\alpha$ $epsilon^{2}$)) iterations for EF21-P and a similar epsilon-dependent bound for MARINA-P, with expected communication cost O(d + zeta_C T) per worker.
Load-bearing premise
The analysis requires every worker to evaluate its subgradient at exactly the same synchronized point w_t each round, so a single worker that receives the broadcast late, goes offline, or uses a stale model breaks the descent inequality.
Editorial extensions
If this is right
- With Top-K compression, EF21-P's communication complexity matches that of the uncompressed distributed subgradient method, so downlink compression can be added without worsening the worst-case rate.
- Both methods can use the Polyak stepsize with no extra communication, because the subgradient values needed for the stepsize are already sent to the server.
- For non-smooth objectives, the iteration complexity is independent of the number of workers n, in contrast to MARINA-P's smooth non-convex analysis where complexity scales like 1/n.
- Decreasing stepsizes retain convergence without knowing T or f(x*) but pay a log T factor, the known limitation of subgradient methods.
- MARINA-P with independent or correlated compressors outperforms EF21-P with Top-K in the reported non-smooth convex experiments, especially for many clients.
Reading between the lines
- The synchronized-common-point premise suggests a testable robustness question the paper does not address: if a worker's broadcast is delayed or lost, the averaged subgradient is no longer a subgradient at a single point, so the descent lemma may fail; measuring how much staleness the method tolerates in practice would delimit the theorem's reach.
- Since the optimal rate is already attained with compression, one could try to push the theory to stochastic subgradient or mini-batch settings, where random subgradient noise enters the same Lyapunov recursion.
- The theoretical comparison only uses worst-case constants; the experiments hint that correlated compressors improve real constants substantially, so a sharper analysis tracking the variance reduction from Perm_K could close the gap between theory and the measured advantage.
- If the downlink compression is truly free in non-smooth federated settings, system designers could compress server broadcasts aggressively without changing the asymptotic rate, which is a practical prescription worth testing on real non-smooth models.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper considers the non-smooth convex regime of distributed optimization with server-to-worker compression, a setting that is indeed less studied than the smooth case. It extends EF21-P, previously analyzed in a single-node non-smooth setting, to distributed workers, and adapts MARINA-P, originally designed for smooth non-convex problems, to non-smooth convex objectives. For both algorithms, the paper proves O(1/\sqrt{T}) convergence rates under constant and Polyak stepsizes, O(\log T/\sqrt{T}) rates under decreasing stepsizes, and corresponding communication complexity bounds. The experiments compare EF21-P with Top-K compression against MARINA-P with same, independent, and correlated (Perm-K) compressors on a synthetic \|A_i x\|_1 finite-sum problem, reporting that correlated compressors perform best.
Significance. If fully supported, the paper would fill a genuine gap: it would provide the first distributed non-smooth convex guarantees with server-to-worker compression and adaptive stepsizes, at the optimal O(1/\sqrt{T}) rate for constant and Polyak stepsizes. The EF21-P part is a genuine distributed extension and the Lyapunov-style proofs in the appendix are standard and, as far as I verified, algebraically consistent; the constant optimization in Theorem 1 and Corollary 2 checks out. However, the MARINA-P half proves a different, weaker metric than the advertised global suboptimality, and the EF21-P analysis leans on an anonymous, under-review submission. These two issues affect the paper's central claims and require substantial revision before the stated contributions can be accepted.
major comments (3)
- [Section 4, Theorem 2 and Lemma 5 (Eqs. (20)-(28), (113))] The guarantee proved for MARINA-P is E[1/n \sum_i f_i(w_i^T) - f(x^*)], where w_i^T are per-worker ergodic averages, and not the standard global suboptimality E[f(x_T)-f(x^*)] at any common output. The abstract, contributions, and Corollary 2 advertise an optimal rate for distributed non-smooth optimization, which conventionally means global objective suboptimality. The descent lemma (Lemma 5, Eq. (113)) controls only this averaged local-loss gap, and no argument is given that bridges it to f at a common point. Such a bridge cannot hold in general: with f_1(x)=|x| and f_2(x)=|x-10|, taking w_1=0 and w_2=10 gives (1/2)(f_1(w_1)+f_2(w_2))=0 while f((w_1+w_2)/2)=5. The MARINA-P claims and Corollary 2 must either be explicitly reframed as guarantees for the average of local-model losses, or a genuine bound on E[f(\bar w)-f(x^*)] for a common output must be proved.
- [Section 3 and Appendix C] The distributed EF21-P analysis is explicitly built on the anonymous, under-review submission [Anonymous, 2024]. The paper states that the original proof of Anonymous [2024] 'remains applicable' to the distributed algorithm, and the appendix provides proofs only by 'following the approach' of that unpublished work. Because the central EF21-P guarantees rest on this source, the manuscript is not fully self-contained and its correctness cannot be independently verified from the submitted text. The authors should either cite a publicly available version of the single-node EF21-P analysis or present the single-node proof completely, with all steps, independently of the anonymous submission.
- [Algorithm 1 and Theorem 1] The distributed EF21-P analysis requires that every worker evaluates its subgradient at the identical point w_t, which is true only if the server's broadcast of the compressed difference is applied synchronously and losslessly by all workers. The algorithm description merely notes that 'this procedure ensures that the states w_t remain synchronized' (Section 3, Algorithm 1, lines 13-15), but no formal assumption of synchronous, reliable broadcast is stated. If workers go offline, receive updates with different delays, or use stale local models, the averaged subgradient is no longer a subgradient of f at a common point and the first bound of Lemma 2 fails. The distributed claim should state this synchronization requirement explicitly as an assumption.
minor comments (4)
- [Appendix C.1, proof of Theorem 3, after Eq. (87)] In the Polyak-stepsize proof for EF21-P, the displayed denominator of the expectation contains the term 2||\partial f(w_t)||_2 \sqrt{||\partial f(w_t)||_2^2} \sqrt{(1-p)\omega/p}, which belongs to the MARINA-P analysis and is not part of the EF21-P stepsize. The subsequent inequality uses the correct denominator B^*||\partial f(w_t)||_2^2, so this appears to be a copy-paste typo, but it should be corrected for readability.
- [Appendix C.1, Eq. (80) and surrounding text] Equation (80) and the text around it write E[1/n \sum_i f_i(w_T) - f(x^*)] in the EF21-P proof, but for EF21-P the quantity being bounded is E[f(w_T)-f(x^*)]. This notational slip should be fixed.
- [References] The reference [Anonymous, 2024] is cited with an OpenReview URL but is marked 'under review' and is anonymous. Since this work is load-bearing for the EF21-P results, the paper should either replace it with a stable, publicly verifiable reference or clearly indicate its status in the reference entry.
- [Section 5 and Appendix A, Figures 1 and 7] The experiments are limited to a single synthetic benchmark (\|A_i x\|_1 with tridiagonal A_i). This is acceptable for a theory paper, but the title and abstract claim 'superior performance'; that claim would be stronger with at least one non-synthetic or second benchmark. The communication-cost model and the tuning procedure are described in sufficient detail, which is appreciated.
Circularity Check
No significant circularity: both convergence proofs are self-contained in the appendix; the MARINA-P metric issue is a scope or correctness concern, not circularity.
full rationale
The derivation chain is not circular. Theorem 1 (EF21-P) is proven in Appendix C from Assumptions 1-3: Lemma 2 establishes one-iteration bounds (51)-(52) for the common-iterate distributed update, Lemma 3 combines them in a Lyapunov function, and Theorem 3 (Theorem 1) telescopes the descent lemma for each stepsize. Although Section 3 says Anonymous [2024] proved the single-node case and Appendix C says 'the original proof by Anonymous [2024] ... remains applicable,' the appendix then supplies complete proofs of all lemmas and theorems, so the citation is not load-bearing for the theorem's validity. Theorem 2 (MARINA-P) is proven similarly in Appendix D via Lemmas 4-5 and the tower property, Jensen's inequality, and Cauchy-Schwarz, with the target metric exactly the averaged local gap E[1/n sum_i f_i(w_i^T) - f(x*)] stated in (20)-(28); no fitted parameter is introduced and no step defines a quantity in terms of the conclusion. The Polyak stepsizes use f(x*) as in the classical Polyak rule and are not fitted 'predictions.' The experiments tune step-size multipliers on the test problems, but the convergence theorems are not validated by those tuned runs; the tuning is a practical hyperparameter choice. One should note as a separate correctness or scope concern, not circularity, that Theorem 2's bound is for an average of per-worker ergodic losses, not the global suboptimality f(x_T)-f(x*) of a common output, and the abstract's 'optimal O(1/sqrt(T)) convergence rate' wording glosses over this. The EF21-P proof also contains an apparent typographical or copy-paste issue in the displayed Polyak plug-in step (Eq. 88), but this does not constitute circularity because the claimed contraction is derived from the descent lemma rather than assumed. Overall, no circular reduction by construction is present.
Assumptions & free parameters
free parameters (1)
- stepsize multiplier (experiments) =
selected from {2^-9, ..., 2^7} per method
assumptions (6)
- domain assumption Assumption 1: f has at least one minimizer
- domain assumption Assumption 2: each f_i is convex
- domain assumption Assumption 3: each f_i is L0,i-Lipschitz
- domain assumption Compressor definitions (6) and (7): unbiased with variance omega, or contractive with parameter alpha
- ad hoc to paper Synchronized workers receive broadcast updates identically and on time
- domain assumption Uplink costs are negligible
Cite this review
Pith. "Pith review of MARINA-P: Superior Performance in Non-smooth Federated Optimization with Adaptive Stepsizes." pith.science (2026). https://pith.science/paper/WA2D4IKC
@misc{pith2026241217082,
author = {Pith},
title = {Pith review of: MARINA-P: Superior Performance in Non-smooth Federated Optimization with Adaptive Stepsizes},
year = {2026},
howpublished = {\url{https://pith.science/paper/WA2D4IKC}},
note = {Machine review of arXiv:2412.17082}
}
abstract
Non-smooth communication-efficient federated optimization is crucial for many machine learning applications, yet remains largely unexplored theoretically. Recent advancements have primarily focused on smooth convex and non-convex regimes, leaving a significant gap in understanding the non-smooth convex setting. Additionally, existing literature often overlooks efficient server-to-worker communication (downlink), focusing primarily on worker-to-server communication (uplink). We consider a setup where uplink costs are negligible and focus on optimizing downlink communication by improving state-of-the-art schemes like EF21-P (arXiv:2209.15218) and MARINA-P (arXiv:2402.06412) in the non-smooth convex setting. We extend the non-smooth convex theory of EF21-P [Anonymous, 2024], originally developed for single-node scenarios, to the distributed setting, and extend MARINA-P to the non-smooth convex setting. For both algorithms, we prove an optimal $O(1/\sqrt{T})$ convergence rate and establish communication complexity bounds matching classical subgradient methods. We provide theoretical guarantees under constant, decreasing, and adaptive (Polyak-type) stepsizes. Our experiments demonstrate that MARINA-P with correlated compressors outperforms other methods in both smooth non-convex and non-smooth convex settings. This work presents the first theoretical results for distributed non-smooth optimization with server-to-worker compression, along with comprehensive analysis for various stepsize schemes.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[2024]
URL https://openreview.net/forum?id=Qv9TG9yDG0. under review. Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, edi- tors, Advances in Neural Information Processing Systems , volume 28. Curran Associates, Inc.,
-
[1]
AMD EPYC 7702 64-Core
-
[2]
Intel(R) Xeon(R) Gold 6148 CPU @ 2.40GHz
-
[3]
Intel(R) Xeon(R) Gold 6248 CPU @ 2.50GHz. Algorithm 3 Synthetic datasets generation routine 1: Parameters: number nodes 𝑛, dimension 𝑑, parameter 𝜇 = 10−6, and noise scale 𝑠. 2: for 𝑖 = 1, . . . , 𝑛do 3: Generate random noises 𝜈𝑠 𝑖 = 1 + 𝑠𝜉𝑠 𝑖 , i.i.d. 𝜉𝑠 𝑖∼𝒩 (0, 1) 4: Take the initial tridiagonal matrix A𝑖 = 𝜈𝑠 𝑖 4 ⎛ ⎜⎜⎜⎜⎝ 2 −1 0 −1 ... ... ... ... −1 0 ...
work page 2017
-
[4]
where sameRand𝐾, indRand𝐾, and Perm𝐾 are defined as described in subsection 4.1
MARINA-P with Perm𝐾 compressors. where sameRand𝐾, indRand𝐾, and Perm𝐾 are defined as described in subsection 4.1. In all experiments, we set 𝐾 = 𝑑/𝑛 and for MARINA-P we additionally choose 𝑝 = 𝐾/𝑑 to ensure a fair comparison of communication costs. Indeed, whereas for EF21-P with Top𝐾, parameter 𝐾 (and therefore 26 Method Stepsize type Constant Decreasing...
-
[6]
EF21-P with Top𝐾 compressor
-
[7]
MARINA-P with sameRand𝐾 compressor
-
[8]
MARINA-P with indRand𝐾 compressors
Show all 28 references
-
[10]
Function suboptimality 𝑓(𝑥𝑡)− 𝑓(𝑥*)
-
[11]
We employed 64-bit precision in our experiments
Number of bits per worker send from server to clients (titled as “bits/n” on corresponding Figure 7). We employed 64-bit precision in our experiments. Our communication model assumes that the server transfers (65 + log2(𝑑))𝑞 bits to each worker, where 𝑞 represents the number o...
2022
-
[12]
Superiority of correlated compressors in the non-smooth convex setting. For both constant and Polyak stepsizes, MARINA-P with Perm𝐾 compressors slightly outperforms MARINA-P with indRand𝐾 compressors, showing significant improvement over the conventional approach using the sam...
2024
-
[13]
Superior convergence behavior with adaptive stepsizes. Each pair of experiments differing only in stepsize strategy (e.g., EF21-P with Top𝐾, represented in Figure 7 with the same color and 28 0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 ×108 10−1 100 101 102 f (xt) − f (x⋆) n= 10; σA= 0.09...
-
[14]
smooth" update step (48) with a
MARINA-P with correlated compressors and Polyak stepsize outperforms for all datasets.Figure 7 reveals that while all algorithms under constant stepsizes exhibit similar convergence behavior (slightly outperformed by EF21-P with Polyak stepsize), MARINA-P with correlated compr...
2021
-
[15]
(54) Next, we apply (38) with 𝑠 := 𝜆𝛾𝑡: 2𝛾𝑡 ⟨︀ 𝜕𝑓 (︀ 𝑤𝑡)︀ , 𝑤𝑡− 𝑥𝑡⟩︀ ≤ 𝜆𝛾2 𝑡 ⃦⃦𝜕𝑓 (︀ 𝑤𝑡)︀⃦⃦2 2 + 1 𝜆 ⃦⃦𝑤𝑡− 𝑥𝑡⃦⃦2 2
To establish the first bound, we begin by applying the definition of subgradient: 𝑓(𝑥*) ≥ 𝑓(𝑤𝑡) + ⟨︀ 𝜕𝑓 (︀ 𝑤𝑡)︀ , 𝑥*− 𝑤𝑡⟩︀ , (53) which implies: ⟨︀ 𝜕𝑓 (︀ 𝑤𝑡)︀ , 𝑤𝑡− 𝑥*⟩︀ ≥ 𝑓(𝑤𝑡)− 𝑓(𝑥*). (54) Next, we apply (38) with 𝑠 := 𝜆𝛾𝑡: 2𝛾𝑡 ⟨︀ 𝜕𝑓 (︀ 𝑤𝑡)︀ , 𝑤𝑡− 𝑥𝑡⟩︀ ≤ 𝜆𝛾2 𝑡 ⃦⃦𝜕𝑓 (︀ 𝑤𝑡)︀⃦⃦...
-
[16]
For the second bound, we proceed as follows: E [︁⃦⃦𝑤𝑡+1− 𝑥𝑡+1⃦⃦2 2| 𝑥𝑡, 𝑊𝑡 ]︁ = E [︁⃦⃦𝑤𝑡−𝒞 (𝑥𝑡+1− 𝑤𝑡)− 𝑥𝑡+1⃦⃦2 2| 𝑥𝑡, 𝑊𝑡 ]︁ ≤ (1− 𝛼) ⃦⃦𝑤𝑡− 𝑥𝑡+1⃦⃦2 2 = (1 − 𝛼) ⃦⃦𝑤𝑡− 𝑥𝑡 + 𝛾𝑡𝜕𝑓 (︀ 𝑤𝑡)︀⃦⃦2 2 ≤ (1− 𝛼)(1 + 𝑠) ⃦⃦𝑤𝑡− 𝑥𝑡⃦⃦2 2 + 𝛾2 𝑡 (1− 𝛼)(1 + 𝑠−1) ⃦⃦𝜕𝑓 (︀ 𝑤𝑡)︀⃦⃦2 2 ≤ (1− 𝜃(𝑠)) ⃦⃦𝑤𝑡− ...
2021
-
[17]
If 𝛾𝑡 := 𝛾 >0, then E [︀ 𝑓(𝑤𝑇 )− 𝑓(𝑥*) ]︀ ≤ 𝑉 0 2𝛾𝑇 + 𝐵*𝐿2 0𝛾 2
(Constant stepsize). If 𝛾𝑡 := 𝛾 >0, then E [︀ 𝑓(𝑤𝑇 )− 𝑓(𝑥*) ]︀ ≤ 𝑉 0 2𝛾𝑇 + 𝐵*𝐿2 0𝛾 2 . (65) If, moreover, optimal𝛾 is chosen i.e. 𝛾 := 1√ 𝑇 √︃ 𝑉 0 𝐵*𝐿2 0 , (66) then E [︀ 𝑓(𝑤𝑇 )− 𝑓(𝑥*) ]︀ ≤ √︀ 𝐵*𝐿2 0𝑉 0 √ 𝑇 . (67)
-
[18]
If 𝛾𝑡 is chosen as 𝛾𝑡 := 𝑓(𝑤𝑡)− 𝑓(𝑥*) 𝐵*‖𝜕𝑓 (𝑤𝑡)‖2 2 , (68) 34 then E [︀ 𝑓(𝑤𝑇 )− 𝑓(𝑥*) ]︀ ≤ √︀ 𝐵*𝐿2 0𝑉 0 √ 𝑇
(Polyak stepsize). If 𝛾𝑡 is chosen as 𝛾𝑡 := 𝑓(𝑤𝑡)− 𝑓(𝑥*) 𝐵*‖𝜕𝑓 (𝑤𝑡)‖2 2 , (68) 34 then E [︀ 𝑓(𝑤𝑇 )− 𝑓(𝑥*) ]︀ ≤ √︀ 𝐵*𝐿2 0𝑉 0 √ 𝑇 . (69)
-
[19]
If 𝛾𝑡 is chosen as 𝛾𝑡 := 𝛾0√𝑡 + 1, (70) then E [︀ 𝑓( ̂︀𝑤𝑇 )− 𝑓(𝑥*) ]︀ ≤ 𝑉 0 + 2𝛾2 0 𝐵*𝐿2 0 log(𝑇 + 1) 𝛾0 √ 𝑇
(Decreasing stepsize). If 𝛾𝑡 is chosen as 𝛾𝑡 := 𝛾0√𝑡 + 1, (70) then E [︀ 𝑓( ̂︀𝑤𝑇 )− 𝑓(𝑥*) ]︀ ≤ 𝑉 0 + 2𝛾2 0 𝐵*𝐿2 0 log(𝑇 + 1) 𝛾0 √ 𝑇 . (71) If, moreover, optimal𝛾0 is chosen i.e. 𝛾0 := √︃ 𝑉0 2𝐵*𝐿2 0 log(𝑇 + 1), (72) then E [︀ 𝑓( ̂︀𝑤𝑇 )− 𝑓(𝑥*) ]︀ ≤ 2 √︁ 2𝐵*𝐿2 0𝑉0 √︂ log(𝑇 + 1) 𝑇...
-
[20]
(Constant stepsize). Using (74), Lemma 3, the tower property of expectation (42), and choosing constant stepsize 𝛾𝑡 := 𝛾 >0, we obtain E [︀ 𝑉 𝑡+1]︀ ≤ E [︀ 𝑉 𝑡]︀ − 2𝛾E [︀ 𝑓(𝑤𝑡)− 𝑓(𝑥*) ]︀ + (︂ 1 + 𝜆 + 𝛽 𝜆𝜃 )︂ 𝛾2E [︁⃦⃦𝜕𝑓 (︀ 𝑤𝑡)︀⃦⃦2 2 ]︁ , (75) where 𝜆 >0, 𝜃 := 1−√1− 𝛼 and 𝛽 := 1−...
-
[21]
Using Lemma 3, we have E [︀ 𝑉 𝑡+1| 𝑥𝑡, 𝑊𝑡]︀ ≤ 𝑉 𝑡− 2𝛾𝑡𝑓(𝑤𝑡)− 𝑓(𝑥*) + (︂ 1 + 𝜆 + 𝛽 𝜆𝜃 )︂ 𝛾2 𝑡 ⃦⃦𝜕𝑓 (︀ 𝑤𝑡)︀⃦⃦2 2, (83) where 𝜆 >0, 𝜃 := 1−√1− 𝛼 and 𝛽 := 1−𝛼 1−√1−𝛼
(Polyak stepsize). Using Lemma 3, we have E [︀ 𝑉 𝑡+1| 𝑥𝑡, 𝑊𝑡]︀ ≤ 𝑉 𝑡− 2𝛾𝑡𝑓(𝑤𝑡)− 𝑓(𝑥*) + (︂ 1 + 𝜆 + 𝛽 𝜆𝜃 )︂ 𝛾2 𝑡 ⃦⃦𝜕𝑓 (︀ 𝑤𝑡)︀⃦⃦2 2, (83) where 𝜆 >0, 𝜃 := 1−√1− 𝛼 and 𝛽 := 1−𝛼 1−√1−𝛼. We choose the Polyak stepsize 𝛾𝑡 as the one that minimizes the right-hand side of (83): 𝛾𝑡 := a...
-
[22]
(Decreasing stepsize). By the same arguments as in the analysis for the constant stepsize case, we can get a bound E [︀ 𝑉 𝑡+1]︀ ≤ E [︀ 𝑉 𝑡]︀ − 2𝛾𝑡E [︀ 𝑓(𝑤𝑡)− 𝑓(𝑥*) ]︀ + 𝐵*𝐿2 0𝛾2 𝑡 , (90) where 𝐵* (79) = = 1 + 2 √1−𝛼 1−√1−𝛼 . If 𝛾𝑡 := 𝛾0√𝑡+1 with 𝛾0 > 0, then we can get the bou...
-
[23]
If 𝛾𝑡 := 𝛾 >0, then E [︃ 1 𝑛 𝑛∑︁ 𝑖=1 𝑓𝑖(𝑤𝑇 𝑖 )− 𝑓(𝑥*) ]︃ ≤ 𝑉 0 2𝛾𝑇 + ̃︀𝐵*𝛾 2
(Constant stepsize). If 𝛾𝑡 := 𝛾 >0, then E [︃ 1 𝑛 𝑛∑︁ 𝑖=1 𝑓𝑖(𝑤𝑇 𝑖 )− 𝑓(𝑥*) ]︃ ≤ 𝑉 0 2𝛾𝑇 + ̃︀𝐵*𝛾 2 . (118) If, moreover, the optimal𝛾 is chosen, i.e., 𝛾 := 1√ 𝑇 √︃ 𝑉 0 ̃︀𝐵* , (119) then E [︃ 1 𝑛 𝑛∑︁ 𝑖=1 𝑓𝑖(𝑤𝑇 𝑖 )− 𝑓(𝑥*) ]︃ ≤ √︁ ̃︀𝐵*𝑉 0 √ 𝑇 . (120)
-
[24]
(Polyak stepsize). If 𝛾𝑡 is chosen as 𝛾𝑡 := 1 𝑛 ∑︀𝑛 𝑖=1 𝑓𝑖(𝑤𝑡 𝑖)− 𝑓(𝑥*) ⃦⃦ 1 𝑛 ∑︀𝑛 𝑖=1 𝜕𝑓𝑖 (𝑤𝑡 𝑖) ⃦⃦2 2 + 2 ⃦⃦ 1 𝑛 ∑︀𝑛 𝑖=1 𝜕𝑓𝑖 (𝑤𝑡 𝑖) ⃦⃦ 2 √︁ 1 𝑛 ∑︀𝑛 𝑖=1‖𝜕𝑓𝑖 (𝑤𝑡 𝑖)‖2 2 √︁ (1−𝑝)𝜔 𝑝 , (121) 43 then E [︃ 1 𝑛 𝑛∑︁ 𝑖=1 𝑓𝑖(𝑤𝑇 𝑖 )− 𝑓(𝑥*) ]︃ ≤ √︁ ̃︀𝐵*𝑉 0 √ 𝑇 . (122)
-
[25]
If 𝛾𝑡 is chosen as 𝛾𝑡 := 𝛾0√𝑡 + 1, (123) then E [︃ 1 𝑛 𝑛∑︁ 𝑖=1 𝑓𝑖(𝑤𝑇 𝑖 )− 𝑓(𝑥*) ]︃ ≤ 𝑉 0 + 2𝛾2 0 ̃︀𝐵* log(𝑇 + 1) 𝛾0 √ 𝑇
(Decreasing stepsize). If 𝛾𝑡 is chosen as 𝛾𝑡 := 𝛾0√𝑡 + 1, (123) then E [︃ 1 𝑛 𝑛∑︁ 𝑖=1 𝑓𝑖(𝑤𝑇 𝑖 )− 𝑓(𝑥*) ]︃ ≤ 𝑉 0 + 2𝛾2 0 ̃︀𝐵* log(𝑇 + 1) 𝛾0 √ 𝑇 . (124) If, moreover, the optimal𝛾0 is chosen, i.e., 𝛾0 := √︃ 𝑉0 2 ̃︀𝐵* log(𝑇 + 1) , (125) then E [︃ 1 𝑛 𝑛∑︁ 𝑖=1 𝑓𝑖(𝑤𝑇 𝑖 )− 𝑓(𝑥*) ]︃ ≤...
-
[26]
(Constant stepsize). Using (128), (129), Lemma 5, the tower property of expectation (42), and choosing constant stepsize 𝛾𝑡 := 𝛾 >0, we obtain E [︀ 𝑉 𝑡+1]︀ ≤ E [︀ 𝑉 𝑡]︀ − 2𝛾E [︃ 1 𝑛 𝑛∑︁ 𝑖=1 𝑓𝑖(𝑤𝑡 𝑖)− 𝑓(𝑥*) ]︃ + 𝜆𝛾2 1 𝑛 𝑛∑︁ 𝑖=1 E [︁⃦⃦𝜕𝑓𝑖 (︀ 𝑤𝑡 𝑖 )︀⃦⃦2 2 ]︁ + (︂ 1 + (1− 𝑝)𝜔 𝑝𝜆 )...
-
[27]
(Polyak stepsize). By Lemma 5, we have E [︀ 𝑉 𝑡+1| 𝑥𝑡, 𝑊𝑡]︀ ≤ 𝑉 𝑡− 2𝛾𝑡 (︃ 1 𝑛 𝑛∑︁ 𝑖=1 𝑓𝑖(𝑤𝑡 𝑖)− 𝑓(𝑥*) )︃ + 𝜆𝛾2 𝑡 1 𝑛 𝑛∑︁ 𝑖=1 ⃦⃦𝜕𝑓𝑖 (︀ 𝑤𝑡 𝑖 )︀⃦⃦2 2 +𝛾2 𝑡 (︂ 1 + (1− 𝑝)𝜔 𝑝𝜆 )︂ ⃦⃦⃦⃦⃦ 1 𝑛 𝑛∑︁ 𝑖=1 𝜕𝑓𝑖 (︀ 𝑤𝑡 𝑖 )︀ ⃦⃦⃦⃦⃦ 2 2 . (137) 45 We choose the Polyak stepsize 𝛾𝑡 as the one that ...
-
[28]
(Decreasing stepsize). By the same arguments as in the analysis for the constant stepsize case, we can get a bound E [︀ 𝑉 𝑡+1]︀ (133) ≤ E [︀ 𝑉 𝑡]︀ − 2𝛾𝑡E [︃ 1 𝑛 𝑛∑︁ 𝑖=1 𝑓𝑖(𝑤𝑡 𝑖)− 𝑓(𝑥*) ]︃ + ̃︀𝐵*𝛾2 𝑡 , (144) where ̃︀𝐵* (133) = 𝐿 2 0 + 2𝐿0 ̃︀𝐿0 √︁ (1−𝑝)𝜔 𝑝 . If 𝛾𝑡 := 𝛾0√𝑡+1 with...
-
[2015]
Francis Bach
URL https://proceedings.neurips.cc/paper_files/paper/2015/file/ 7fec306d1e665bc9c748b5d2b99a6e97-[]Paper.pdf. Francis Bach. Learning with submodular functions: A convex optimization perspective. Foundations and Trends® in machine learning, 6(2-3):145–373, 2013. Eric Balkanski ...
2015 arXiv
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.