{"id":"212f8f36-dc52-4f1e-8098-16f16481ebd0","arxiv_id":"2502.07923","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"First high-probability bounds for SignSGD with batching or majority voting under (L0, L1)-smoothness and heavy-tailed noise, with near-optimal epsilon-dependencies.","lead":"This paper proves the first high-probability convergence bounds for sign-based stochastic optimization methods when the objective is (L0, L1)-smooth and gradient estimates have heavy-tailed noise. The authors also train LLaMA-style models up to 1.3B parameters and report that a momentum version of SignSGD matches or slightly beats AdamW in validation perplexity.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 1's high-probability proof chooses the concentration parameter λ as a function of the random sum it is meant to bound, although Lemma 3 is stated only for fixed λ; the claimed 1−δ guarantee is therefore not justified as written.","rationale":"The paper's central contribution is the high-probability sample-complexity bound for minibatch-SignSGD under (L0,L1)-smoothness and heavy-tailed noise. For that claim to hold, Lemma 1 must be a valid high-probability convergence lemma. The proof as written selects the concentration parameter λ from the random path, which is not justified by the stated Lemma 3 and appears to be load-bearing: the subsequent absorption of the S/(48d log) portion of 1/λ is precisely what produces the final bound. If this step fails, the theorem's log(1/δ) guarantee is not established. This is a correctness risk rather than a mere stylistic issue, and it is distinct from the reader's flagged concerns about the majority-voting symmetry assumption and the restrictive stepsize, although those are also legitimate. I therefore partially agree with the reader's conditional verdict: the paper is promising and contains much useful material, but the central HP proof needs a fix before acceptance. The proposed concrete test — redoing the proof with a fixed λ or proving a uniform-in-λ concentration bound — would settle whether the concern lands. If the random-λ step can be made rigorous with only logarithmic losses in T, the verdict should remain CONDITIONAL but with that fix required; if it cannot, the central bound as stated would be unsupported.","tokens_in":40487,"tokens_out":32277,"duration_ms":289688,"concrete_test":"Re-derive Lemma 1 with a deterministic λ of the form λ = 1/[6d(γmax∥∇f(x1)∥1 + M + 2CT L0)], where M is a fixed upper bound on Σγk∥∇f(xk)∥1/(48d log(1/δ)) obtained from the gradient-norm recursion before applying Lemma 3, and check whether the terms 3λΣγk²∥∇f(xk)∥² can still be absorbed. If the absorption requires the realized sum, then replace Lemma 3 by a uniform-in-λ version proved via a union bound over a geometric grid of λ, and verify whether the failure probability remains O(δ) or acquires extra log T/δ factors. As an additional numerical sanity check, instantiate the random-λ argument on a Rademacher martingale with λ = 1/(A S + B) and measure the empirical failure probability against the claimed 1−δ.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In the proof of Lemma 1 (Appendix A.3), the martingale concentration lemma (Lemma 3) is applied with a parameter λ that is then chosen as λ := 1/[6d(γmax∥∇f(x1)∥1 + Σ_{k=1}^T γk∥∇f(xk)∥1/(48d log(1/δ)) + 2CT L0)]. This λ depends on the realized path through the random sum Σ γk∥∇f(xk)∥1 — exactly the quantity the lemma is being used to control. Lemma 3 asserts only that for each fixed λ>0, the inequality ΣDk ≤ (3/4)λΣσk² + (1/λ)log(1/δ) holds with probability at least 1−δ; it does not give a uniform bound over data-dependent λ. The later absorption of the term (6/48)Σγk∥∇f(xk)∥1 into the left-hand side relies on substituting this random λ into the concentration bound, so the step is circular unless a uniform-in-λ inequality or a careful union bound over a λ-grid is supplied. This gap affects Lemma 1 directly, and hence Theorems 1, 2, and all sample-complexity claims built on those lemmas. A related, smaller gap appears in the finite-horizon proof (Theorem 4): the positive term 24d∥∇f(x1)∥1 log(1/δ)/T is dropped as 'lower order' but is never shown to be bounded by ε for the chosen T, so the stated complexity with no dependence on ∥∇f(x1)∥ is not established as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript studies sign-based stochastic first-order methods for non-convex optimization under (L0,L1)-smoothness and heavy-tailed gradient noise. It claims high-probability sample complexity bounds for minibatch-SignSGD, a majority-vote variant under symmetric unimodal noise, momentum-based M-SignSGD (in expectation), and restarted variants for Polyak-Lojasiewicz functions, together with parameter-agnostic tuning schedules and large-scale LLM experiments. The central advertised result is the high-probability bound N = O(((ΔL0d/ε^2) + (ΔL1d^{3/2}/ε))[1 + (‖σ‖1/ε)^{κ/(κ-1)}] log(1/δ)) for κ ∈ (1,2], and an analogous bound for majority voting with milder noise dependence for κ ∈ (0,2].","tokens_in":40803,"tokens_out":8848,"duration_ms":79047,"significance":"If the proofs are repaired, the contribution is significant: it extends the high-probability analysis of sign-based methods to the combined setting of (L0,L1)-smoothness and heavy-tailed noise, with logarithmic dependence on 1/δ and mild parameter dependencies. The two-stage convergence discussion and the large-scale experiments on LLaMA and MoE models give the paper practical relevance. However, the central high-probability lemma contains a serious probabilistic gap, and at least one stepsize feasibility check is algebraically incorrect; as written, the main theorems are not established.","major_comments":[{"comment":"Lemma 3 is stated and used as a fixed-λ concentration bound for martingale difference sequences, but the proof of Lemma 1 chooses λ as a function of the realized path, namely λ := 1/[6d(γmax‖∇f(x1)‖1 + Σ_{k=1}^T γk‖∇f(xk)‖1/(48d log(1/δ)) + 2CT L0)], and then substitutes this random λ into the bound. Lemma 3 does not provide a uniform bound over data-dependent λ, and no union bound over a λ-grid or self-normalized martingale inequality is supplied. This gap affects Lemma 1 directly and hence all downstream results that rely on it (Theorems 1, 2, 4–7, and 9–11). A uniform-in-λ concentration inequality or an appropriate peeling argument is needed.","section":"Appendix A.3, proof of Lemma 1"},{"comment":"After deriving the bound with the term 24d‖∇f(x1)‖1 log(1/δ)/T, the proof discards it with the sentence 'We can omit the last term since its dependency on T has the largest power.' This term is O(1/T), the same order as the main term Δ/(Tγ). For the chosen optimal T in the fast phase it is O(ε‖∇f(x1)‖1/(ΔL1√d)), and in the slow phase O(ε^2‖∇f(x1)‖1/(ΔL0)); neither is bounded by ε under the stated assumptions. Therefore the claimed sample complexity, which is independent of ‖∇f(x1)‖1, is not established as written.","section":"Appendix A.4, proof of Theorem 4"},{"comment":"The verification that γ = sqrt(4Δ/(80T L0 log(1/δ)d)) satisfies γ ≤ 1/(48L1 d^{3/2} log(1/δ)) is algebraically incorrect. With the stated choice of T, the displayed chain yields γ ≤ 1/(40 L1√d log(1/δ)), and the final claimed inequality 1/(40 L1√d log(1/δ)) ≤ 1/(48 L1 d^{3/2} log(1/δ)) is false for d ≥ 1. The argument can likely be repaired by increasing the universal constant in T, but as written the slow-phase stepsize violates the condition of Lemma 1.","section":"Appendix A.4, proof of Theorem 4, slow-phase feasibility check"}],"minor_comments":[{"comment":"There is an inconsistency in the displayed constants: an intermediate line uses 6√d(γmax‖∇f(x1)‖1 + 2CT L0) log(1/δ), while the final bound in Eq. (19) uses 6d(γmax‖∇f(x1)‖1 + 2CT L0) log(1/δ). The constants should be reconciled.","section":"Appendix A.3, Eq. (19) vicinity"},{"comment":"In the two arbitrary-tuning cases, the statement begins with 'T, γk ≡ ...' without specifying the value or range of T. The intended finite-horizon schedule should be stated explicitly.","section":"Theorem 4 statement"},{"comment":"The experiments use α-stable noise with κ ∈ {2, 1.5, 1}, but Assumption 3 requires κ ∈ (1,2] and a finite κ-th moment. For κ = 1 the condition is outside the stated assumption; the text should explain how the experimental noise model is related to the theory, or restrict the reported κ values.","section":"Appendix C, noise model"},{"comment":"The main text compares M-SignSGD with M-ClippedSGD, while Appendix D introduces 'M-ClippedSignSGD'. The relationship between these baselines should be clarified.","section":"Section 3 and Appendix D"}],"recommendation":"major_revision","confidential_remarks":"The paper is likely salvageable: the main ideas and the high-level proof strategy follow established techniques, and the gaps identified appear repairable with standard tools (a uniform/self-normalized martingale concentration bound and a more careful choice of constants). However, the current proof of Lemma 1 is a true circularity in the application of Lemma 3, and the stepsize feasibility error in Theorem 4 is concrete; these are load-bearing issues that should be fixed before the main high-probability claims are accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper has the right idea and probably the right rates, but Lemma 1 has a genuine circularity in the high-probability argument, and until that is fixed the headline complexity bounds are not proven as written.\n\nWhat is new: the first high-probability analysis of sign-based methods under (L0,L1)-smoothness with heavy-tailed noise. The two-phase convergence analysis with threshold 8L0/(L1√d) is sensible, and the majority-vote variant for symmetric unimodal noise is a nice extension. The bounds have clean parameter dependencies and, after accounting for the ℓ1 vs ℓ2 norm, match known lower bounds in the standard-smoothness case. The batching lemma usage is standard, and the LLM experiments are a useful sanity check even if the margin over AdamW at 1.3B is tiny.\n\nThe stress-test note is correct. In Lemma 1 (Appendix A.3), the concentration parameter λ is chosen after seeing the data, and it includes the random sum Σ γk∥∇f(xk)∥1 — the very quantity being bounded. Lemma 3 is stated for a fixed λ; there is no uniform-in-λ bound or union bound over a λ-grid. So the claimed 1−δ guarantee does not follow. This is load-bearing: Theorem 1 and Theorem 2 both rest on Lemma 1. The fix might be straightforward (e.g., a self-bounding argument or a union bound), but it has to be written. A second, smaller gap appears in Theorem 4's finite-horizon proof: the term 24d∥∇f(x1)∥1 log(1/δ)/T is dropped as \"lower order\" without showing it is bounded by ε. As written, the complexity misses dependence on ∥∇f(x1)∥.\n\nAlso, the novelty claim for standard smoothness is a bit generous relative to prior nonlinear-SGD works [3,4,32] that already cover sign maps under heavy tails. The symmetric/unimodal assumption for majority voting is strong, but the authors acknowledge it. The self-citation to [39] for the batching lemma is fine.\n\nThis is a serious theoretical paper with a fixable but real proof gap. It deserves a major revision and then a careful re-review. For a reading group, it is worth dissecting the circularity; I would not cite it in my own work until the proof is repaired.\n\nRecommendation: send to peer review, but with an explicit request to fix Lemma 1 before acceptance.","headline":"The paper has the right idea and probably the right rates, but Lemma 1 has a genuine circularity in the high-probability argument, and until that is fixed the headline complexity bounds are not proven as written.","tokens_in":41353,"tokens_out":4817,"would_cite":false,"duration_ms":42633,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C15","62L20"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves the first high-probability convergence bounds for sign-based SGD under generalized $(L_0,L_1)$-smoothness and heavy-tailed noise, with sample complexity matching clipping and normalization without clipping-level tuning.","keywords":["sign-based optimization","heavy-tailed noise","(L0,L1)-smoothness","high-probability bounds","non-convex optimization","SignSGD","majority voting","stochastic approximation"],"falsifier":"Run minibatch-SignSGD on a synthetic $(L_0,L_1)$-smooth objective with known constants (for instance $f(x)=\\exp(a^\\top x)$ with a small $L_0$ regularizer) and independent Student-$t$ noise of tail index $\\kappa\\in(1,2]$, measuring the sample count to hit average $\\ell_1$ gradient norm $\\varepsilon$ with probability $1-\\delta$. The theorem predicts $N = O((\\Delta L_0 d/\\varepsilon^2 + \\Delta L_1 d^{3/2}/\\varepsilon)(1+(\\sigma/\\varepsilon)^{\\kappa/(\\kappa-1)})\\log(1/\\delta))$; if the empirical exponent of $\\sigma/\\varepsilon$ departs from $\\kappa/(\\kappa-1)$ as $\\kappa$ varies, the central bound is wrong. For majority voting, repeat with skewed heavy-tailed noise: if any coordinate's sign is wrong more than half the time, the $\\sigma^2/\\varepsilon^2$ rate should break, showing the symmetry assumption is indispensable.","tokens_in":40298,"feed_emoji":"","tokens_out":16718,"duration_ms":130243,"temperature":0.7,"pith_summary":"The paper asks whether the sign operator—discarding each gradient coordinate's magnitude and keeping only its sign—can replace clipping or normalization as a defense against heavy-tailed gradient noise in non-convex optimization. It answers yes: under $(L_0,L_1)$-smoothness, a generalized smoothness model in which the Hessian norm may grow linearly with the gradient norm, and under noise with a bounded $\\kappa$-th moment, minibatch-SignSGD reaches average $\\ell_1$ gradient accuracy $\\varepsilon$ with probability at least $1-\\delta$ using $N = O((\\Delta L_0 d/\\varepsilon^2 + \\Delta L_1 d^{3/2}/\\varepsilon)(1+(\\|\\sigma\\|_1/\\varepsilon)^{\\kappa/(\\kappa-1)})\\log(1/\\delta))$ samples, with $\\kappa\\in(1,2]$. The paper claims these are the first high-probability bounds in this combined setting, matching the optimal order for standard smoothness. A second variant, MajorityVote-SignSGD, replaces batching with majority voting over sign observations and, under unimodal symmetric noise, works for every $\\kappa\\in(0,2]$ with a $1/\\kappa^2 + (\\|\\sigma\\|_1/\\varepsilon)^2$ dependence. Experiments on LLaMA-style language models up to 1.3B parameters and on a Switch-Transformer mixture-of-experts model show sign-based momentum methods beating clipped and normalized momentum baselines and matching or slightly beating AdamW.","feed_headline":"First high-probability bounds for SignSGD under heavy-tailed noise","feed_subtitle":"Under generalized smoothness, sign methods match clipping and normalization with no clipping level to tune.","key_machinery":"The load-bearing object is the coordinate-wise sign operator applied to gradient estimates. The proof's engine is a per-coordinate disagreement bound: with noise of $\\kappa$-th moment $\\sigma_i^\\kappa$, the probability that $\\mathrm{sign}(g_i)$ disagrees with $\\mathrm{sign}(\\nabla f_i)$ is at most $\\sigma_i/|\\nabla f_i|$, so the expected aligned length $\\langle\\nabla f, \\mathrm{sign}(g)\\rangle$ is at least $\\|\\nabla f\\|_1 - 2\\|\\sigma\\|_1$. A martingale measure-concentration lemma promotes this to a high-probability bound with only $\\log(1/\\delta)$. The $(L_0,L_1)$-smoothness descent lemma bounds the one-step function decrease by $L_0 d \\gamma^2$ plus an $L_1$-dependent term, forcing the stepsize cap $\\gamma \\leq 1/(48 L_1 d^{3/2} \\log(1/\\delta))$. Batching reduces the effective noise by the factor $B^{-(\\kappa-1)/\\kappa}$, while majority voting uses Gauss's inequality for unimodal symmetric noise to make each coordinate's sign error probability less than $1/2$, so the majority of $M$ independent signs fails with probability $O(1/\\sqrt{M})$ and the $\\kappa$ exponent drops out.","core_discovery":"On its own terms, the paper's central claim is that the sign operator is a complete substitute for clipping and normalization when the objective is $(L_0,L_1)$-smooth and the noise is heavy-tailed. Theorem 1 states that minibatch-SignSGD reaches average $\\ell_1$ gradient accuracy $\\varepsilon$ with probability $1-\\delta$ using $N = O((\\Delta L_0 d/\\varepsilon^2 + \\Delta L_1 d^{3/2}/\\varepsilon)(1+(\\|\\sigma\\|_1/\\varepsilon)^{\\kappa/(\\kappa-1)})\\log(1/\\delta))$ samples for $\\kappa\\in(1,2]$. Theorem 2 states that under unimodal symmetric noise, MajorityVote-SignSGD achieves $N = O((\\Delta L_0 d/\\varepsilon^2 + \\Delta L_1 d^{3/2}/\\varepsilon)(1/\\kappa^2 + (\\|\\sigma\\|_1/\\varepsilon)^2)\\log(1/\\delta))$ for all $\\kappa\\in(0,2]$. The paper claims these are the first high-probability bounds for sign-based methods under $(L_0,L_1)$-smoothness with heavy-tailed noise, and that they reduce to the optimal known rates when $L_1=0$.","pith_inferences":["Because the fast-phase stepsize cap scales as $1/(L_1 d^{3/2}\\log(1/\\delta))$, the practical advantage over normalized SGD may shrink in very high dimension; a clean ablation fixing $L_1$ and varying $d$ would show whether the fast phase survives.","The majority-voting guarantee rests on unimodal symmetric coordinate noise; a quick empirical check on real language-model gradients would show whether this holds, and skewed or multimodal coordinates would make minibatch-SignSGD the safer theoretical contract.","The momentum result is proved in expectation, so a high-probability version of M-SignSGD under $(L_0,L_1)$-smoothness remains open; the experiments suggest it is the practically relevant gap.","The perplexity win over AdamW is not derived from the theorems, which analyze sign updates on raw gradients; testing sign updates on Adam-style preconditioned directions would separate the sign effect from adaptive scaling."],"forward_implications":["SignSGD with batching is a parameter-free alternative to clipping: it attains the same sample-complexity order as ClipSGD and NSGD under heavy-tailed noise without selecting a clipping level.","Convergence is two-stage: for $\\varepsilon \\geq 8L_0/(L_1\\sqrt{d})$ the bound is dominated by $(\\Delta L_1 d^{3/2}/\\varepsilon)(\\|\\sigma\\|_1/\\varepsilon)^{\\kappa/(\\kappa-1)}$, and below that threshold the $L_0$-term $(\\Delta L_0 d/\\varepsilon^2)(\\|\\sigma\\|_1/\\varepsilon)^{\\kappa/(\\kappa-1)}$ takes over.","Under unimodal symmetric noise, majority voting changes the noise dependence from $(\\|\\sigma\\|_1/\\varepsilon)^{\\kappa/(\\kappa-1)}$ to $(\\|\\sigma\\|_1/\\varepsilon)^2$, so the tail index $\\kappa$ enters only through a $1/\\kappa^2$ factor and the method works for every $\\kappa>0$.","Momentum SignSGD keeps the same order of total sample complexity while using small constant batch sizes, the regime used in practical language-model pretraining.","For Polyak-Łojasiewicz objectives, restarted minibatch-SignSGD turns the average-gradient guarantee into high-probability function suboptimality with sample complexity $O((L_0 d/\\mu + L_1 d^{3/2}\\sqrt{\\Delta}/\\sqrt{\\mu})(1+(\\|\\sigma\\|_1^2/(\\mu\\varepsilon))^{\\kappa/(2(\\kappa-1))}))$ up to log factors."],"supporting_citations":[{"why":"Introduces the $(L_0,L_1)$-smoothness model that the paper adopts as its problem class.","marker":"[74]"},{"why":"Original SignSGD method and its $\\ell_1$-norm convergence analysis; the paper extends this to heavy-tailed noise and high probability.","marker":"[5]"},{"why":"High-probability bounds for normalized SGD under heavy-tailed noise; supplies the martingale concentration technique and the comparison baseline.","marker":"[30]"},{"why":"High-probability bound for ClipSGD under heavy-tailed noise; the baseline whose rate SignSGD matches.","marker":"[52]"},{"why":"Provides the $(L_0,L_1)$-smoothness descent inequalities used in every proof step.","marker":"[26]"},{"why":"Gauss's inequality for unimodal symmetric random variables underpins the majority-voting failure-probability estimate.","marker":"[20]"},{"why":"The batching lemma for heavy-tailed martingale differences controls how minibatching reduces the effective noise.","marker":"[12]"},{"why":"Establishes lower bounds for heavy-tailed stochastic optimization in expectation; used as the optimality benchmark for the new rates.","marker":"[75]"},{"why":"Momentum SignSGD convergence result whose proof structure is generalized to heavy-tailed noise in Theorem 3.","marker":"[66]"}],"fun_headline_variants":["SignSGD tames heavy-tailed noise without clipping thresholds","First high-probability bounds for SignSGD with heavy-tailed noise","Sign operator matches clipping under (L0,L1)-smoothness, no tuning","Heavy-tailed corruption? SignSGD works without a clipping level","Sign-based methods: first robust guarantees for non-convex smoothness"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"All high-probability results assume the gradient noise has a finite $\\kappa$-th moment in every coordinate, and the majority-voting results further assume each coordinate's noise is symmetric and unimodal about the true gradient, so skewed or multimodal noise would void that second guarantee.","fun_headline_variants_meta":{"raw":{"variants":["SignSGD tames heavy-tailed noise without clipping thresholds","First high-probability bounds for SignSGD with heavy-tailed noise","Sign operator matches clipping under (L0,L1)-smoothness, no tuning","Heavy-tailed corruption? SignSGD works without a clipping level","Sign-based methods: first robust guarantees for non-convex smoothness"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000419,"raw_usage":{"total_tokens":2285,"prompt_tokens":1201,"completion_tokens":1084,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":817,"completion_tokens_details":{"reasoning_tokens":990}},"tokens_in":817,"tokens_out":1084,"duration_ms":9220,"temperature":1.0,"reasoning_tokens":990,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T11:25:28.992308+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run minibatch-SignSGD on a synthetic $(L_0,L_1)$-smooth objective with known constants (for instance $f(x)=\\exp(a^\\top x)$ with a small $L_0$ regularizer) and independent Student-$t$ noise of tail index $\\kappa\\in(1,2]$, measuring the sample count to hit average $\\ell_1$ gradient norm $\\varepsilon$ with probability $1-\\delta$. The theorem predicts $N = O((\\Delta L_0 d/\\varepsilon^2 + \\Delta L_1 d^{3/2}/\\varepsilon)(1+(\\sigma/\\varepsilon)^{\\kappa/(\\kappa-1)})\\log(1/\\delta))$; if the empirical exponent of $\\sigma/\\varepsilon$ departs from $\\kappa/(\\kappa-1)$ as $\\kappa$ varies, the central bound is wrong. For majority voting, repeat with skewed heavy-tailed noise: if any coordinate's sign is wrong more than half the time, the $\\sigma^2/\\varepsilon^2$ rate should break, showing the symmetry assumption is indispensable.","supporting_citations":[{"cited_title":"Why gradient clipping accelerates training: A theoretical justification for adaptivity","cited_arxiv_id":null,"evidence_quote":"Introduces the $(L_0,L_1)$-smoothness model that the paper adopts as its problem class."},{"cited_title":"The gauss–tchebyshev inequality for uni- modal distributions","cited_arxiv_id":null,"evidence_quote":"Gauss's inequality for unimodal symmetric random variables underpins the majority-voting failure-probability estimate."},{"cited_title":"Optimal mean estimation without a variance","cited_arxiv_id":null,"evidence_quote":"The batching lemma for heavy-tailed martingale differences controls how minibatching reduces the effective noise."},{"cited_title":"Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33:15383–15393, 2020","cited_arxiv_id":null,"evidence_quote":"Establishes lower bounds for heavy-tailed stochastic optimization in expectation; used as the optimality benchmark for the new rates."},{"cited_title":"Momentum ensures convergence of signsgd under weaker assumptions","cited_arxiv_id":null,"evidence_quote":"Momentum SignSGD convergence result whose proof structure is generalized to heavy-tailed noise in Theorem 3."}],"review_version":1}