{"id":"1a837db1-ed42-4ee1-9c6d-55ea8f6a9ed0","arxiv_id":"2505.19227","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"For power-law word frequencies, gradient descent needs about d^{1-ε} iterations to reach relative error ε on a linear bigram model, while sign descent needs about √(d/ε), explaining Adam's advantage on heavy-tailed text data.","lead":"This paper derives rigorous scaling laws for how many training steps gradient descent and sign descent need on a simple word-prediction model when word frequencies follow Zipf's law. It explains mathematically why plain gradient descent slows down almost linearly with vocabulary size, while sign-based updates (a proxy for Adam) only slow down with the square root of the vocabulary size.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The sign-descent scaling law is derived from the η/2 oscillation model (Assumption 4.1), not from exact sign descent; for α=1 exact even-time analysis gives O(1/ε) steps, contradicting the claimed √(d/ε) scaling.","rationale":"The reader's weakest-assumption analysis focuses on Assumption 2.3, which is a legitimate concern about matching marginal and conditional power-law exponents. However, an even more load-bearing issue arises under the paper's own idealized data model: the sign-descent theorems are not about the actual sign-descent update. The exact calculation above shows that for α=1, an even-horizon trajectory with the step-size that Proposition 4.3 explicitly allows reaches relative error ε in O(1/ε) iterations, independent of dimension. This falsifies the central quantitative claim that Zipf-distributed data forces SD to scale as √(d/ε). The gradient-descent half of the paper may survive, and the qualitative conclusion that sign-like methods outperform GD may even be strengthened, but the paper's headline scaling law for SD is not established for exact sign descent. The self-admitted curve-fitting in Appendix D.3 reinforces that the SD result is not a fully derived theorem about the algorithm. Because the abstract and Theorem 1.1 present the √d scaling as the main practical contribution, the central claim as written is incorrect or at minimum unsubstantiated for the algorithm named. A revision could reframe the SD results as applying to a phase-averaged or smoothed proxy, but the current claims should not be accepted as statements about sign descent.","tokens_in":29554,"tokens_out":33137,"duration_ms":319111,"concrete_test":"Compute the exact sign-descent loss, using Proposition A.3 rather than Assumption 4.1, on synthetic data satisfying Assumption 2.3 with α=1 for d=10^3,10^4,10^5,10^6. For each d and ε∈{1/4,1/16,1/64}, find the smallest even T such that min_η L_d(T,η)/L_d(0)≤ε, optimizing η over [δ_d(0)/T, δ_1(0)/T]. If the required T stays bounded as d grows, while Proposition E.2 predicts T∝√d, the claimed SD scaling is not valid for exact sign descent. Equivalently, evaluate the exact loss at T even, η=δ_1(0)/T, and verify it is O(a²/T) rather than the O(a²/τ²) predicted by Theorem 4.5.","verdict_should_be":"REJECT","load_bearing_attack":"Theorem 4.5 and Proposition E.2 for sign descent with α>1/2 are proved for the smoothed dynamics of Assumption 4.1, where every oscillating coordinate is assigned magnitude η/2. The theorem is therefore not a statement about the algorithm called sign descent. Under the paper's own data model (Assumption 2.3), take α=1, normalized δ_k(0)=a/k with a=1/H_{d,1}. Choose an even horizon T and step-size η=a/T, the upper endpoint allowed by Proposition 4.3. For k≤T, Tη=a≥δ_k(0), so the exact update δ←δ−η sign(δ) keeps these coordinates inside [−η,η] by time T; their total squared contribution is ≤Tη²=a²/T. For k>T, δ_k(0)<η and an even number of steps returns each such coordinate to its starting value, so these contribute Σ_{k>T} a²/k² ≤ a²/T. The initial loss is a²H_{d,2}∼ζ(2)a², hence the exact relative loss is ≤2/(ζ(2)T), independent of d. Reaching relative error ε therefore requires only T=O(1/ε), not T≈√(d/ε). This contradicts Proposition E.2 for α=1 and indicates the √d dependence is an artifact of the η/2 averaging convention, not a property of sign descent. Appendix D.3 explicitly says the α>1/2 scalings were 'decided arbitrarily to fit empirical data'; the issue here is more severe than a fitted constant, since the functional form of the scaling changes.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies deterministic gradient descent (GD) and sign descent (SD) on a linear bigram model with square loss, assuming that marginal token frequencies and conditionally sorted next-token frequencies both follow π_k ∝ 1/k^α (Assumption 2.3). It derives asymptotic rates r(τ) = lim_d L_d(t_d(τ))/L_d(0) for GD (Theorem 3.1) and for an averaged surrogate of SD (Assumption 4.1, Theorem 4.5), and inverts these rates into iteration counts to reach relative error ε (Propositions E.1 and E.2). For Zipf-distributed data (α = 1), the paper claims GD needs t ≈ d^{1−ε} iterations while SD needs only t ≈ √(d/ε), which it presents as explaining the empirical advantage of Adam-like preconditioning. Experiments on synthetic power-law data and on OpenWebText are used to support the predicted scalings.","tokens_in":29907,"tokens_out":10719,"duration_ms":102715,"significance":"Taken on its own, the GD analysis is a solid and useful contribution: the reduction to the spectral sum Σ k^{-α}(1−k^{-α})^{2t}/H_{d,α} is exact, the sum-integral and Laplace arguments are careful, and the d^{1−ε} scaling at α = 1 is genuinely derived rather than fitted. The synthetic and real-data experiments for GD are convincing. The SD part, however, is not a theorem about sign descent as defined in Section 4.1: it concerns the averaged dynamics of Assumption 4.1, and an exact calculation under the paper's own data model contradicts the claimed √d scaling for α = 1. Because the headline claim about Adam's advantage rests on the SD scaling, the manuscript in its current form does not establish that claim. The paper is transparent about the averaging assumption and about the arbitrary fits in Appendix D.3, which is to its credit, but those are load-bearing issues rather than presentation issues.","major_comments":[{"comment":"The theorems for sign descent are statements about the averaged dynamics of Assumption 4.1, not about the sign descent update δ ← δ − η sign(δ). This distinction is load-bearing. For α = 1 under Assumption 2.3, set a = 1/H_{d,1}, so δ_k(0) = a/k, choose T even and η = a/T, the upper endpoint allowed by Proposition 4.3. In the exact dynamics, every coordinate with k ≤ T is confined to [−η, η] at time T, contributing at most Tη² = a²/T, while coordinates with k > T have δ_k(0) < η and an even number of steps returns them to their starting value, contributing Σ_{k>T} a²/k² ≤ a²/T. Since the initial loss is a²H_{d,2} ∼ ζ(2)a², the exact relative loss is at most 2/(ζ(2)T), so reaching relative error ε requires only T = O(1/ε), independent of d. This directly contradicts Proposition E.2's √(d/ε) scaling for α = 1. The √d dependence in the paper comes from charging d oscillating coordinates with magnitude η/2 each in Assumption 4.1; the exact dynamics confine oscillating coordinates to an interval of length η, removing the factor of d.","section":"§4.1, Assumption 4.1; Theorem 4.5; Proposition E.2"},{"comment":"The paper states explicitly that the extension of the SD scalings to the regime τ² ≤ 1/(2α−1) was \"decided arbitrarily to fit empirical data\" and that the rate 1/(1 + ζ(2α)τ²) is an approximation chosen because it fits the observed data better than the derived 1/(ζ(2α)(1 + τ²)). This is not a fitted constant; it changes the functional form of the rate, and Proposition E.2 inverts this rate to obtain t ≈ √(d/ε). Moreover, for α = 1 and ε = 3/4, the inversion gives τ < 1, which lies outside the derived regime. Consequently, the ε-scaling statement for sign descent at α > 1/2 is not a theorem for the parameter range where it is used, and the plotted ε values in Fig. 2 include points that are not covered by the proven part of the result.","section":"Appendix D.3, final paragraph"},{"comment":"The claimed dimension exponents d^{1−ε} and d^{1/2} depend on the conditional frequencies, after sorting, having exactly the same power-law exponent α as the marginal frequencies. The paper acknowledges in Section 2.1 that this can fail, for example when a token can only be followed by specific tokens, and Fig. 3 shows only medians and quantiles of the raw conditional frequencies rather than a direct validation of the sorted-rank power law with a common α. In the real-data experiments of Fig. 2, the constant c is fitted and the exponent α is not estimated from the conditional frequency table. This does not undermine the mathematical results conditional on Assumption 2.3, but it means the real-data evidence for the specific dimension exponents is weaker than the synthetic validation, and this limitation should be stated more prominently in the main text.","section":"§2.1, Assumption 2.3 and Fig. 2"}],"minor_comments":[{"comment":"The constant is stated as C = Γ(1 − 1/α)/(αζ(2α)), whereas Theorem 3.1 defines C = Γ(1 − 1/α)/(αζ(α)). Since the relative loss for GD has denominator H_{d,α} ∼ ζ(α), the appearance of ζ(2α) here appears to be a typo and should be corrected.","section":"Proposition E.1, α > 1 case"},{"comment":"The notation t ≈ d^{1−ε} is easy to misread because ε denotes both the target relative error and the exponent of d. It would be clearer to write t = d^{1−ε_target} or to state explicitly that the exponent is 1 minus the desired relative error.","section":"Theorem 1.1 and Proposition E.1, α = 1 case"},{"comment":"The caption says the envelope is obtained from the simplified dynamics, but the right panel is used to motivate the dependence of the optimal step-size on the budget T. It would help to state in the caption that the curves are computed using Proposition 4.2 rather than exact sign descent, since the exact dynamics behave differently.","section":"Figure 5, right panel"}],"recommendation":"reject","confidential_remarks":"The GD half of the paper is strong and could stand alone as a publishable contribution. The SD half, however, is built on Assumption 4.1, and a simple exact calculation shows that the claimed √d scaling is false for sign descent on the paper's own α = 1 model. This is not a fitted constant or a presentation issue; the functional form of the central claim is wrong. I would support a resubmission in which the sign-descent analysis is redone with the exact oscillation dynamics, or in which the claims are restricted to the averaged model and the real-data conclusions are adjusted accordingly."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know before you read the rest. The gradient descent half is solid and worth your time: the α≤1 scaling (t ~ d^α log(1/ε), t ~ d^{1−ε}) is a real result, carefully derived, and it formalizes Bulatov's blog conjecture. The sign descent half is not, at least not as a statement about sign descent. The √d scaling for Zipf data is a property of the η/2 averaging model in Assumption 4.1, not of the algorithm, and there's a concrete counterexample showing exact SD behaves differently.\n\nConcretely: with α=1, normalized δ_k(0)=a/k, choose even T and step-size η=a/T—this is the upper endpoint of their own allowed interval from Proposition 4.3. After T even steps, every coordinate k>T returns to its starting value (because δ_k(0)<η), and the first T coordinates have magnitude at most η. The loss is at most Tη² + a²/T = 2a²/T, while the initial loss is a²H_{d,2}~ζ(2)a². So relative error ≤2/(ζ(2)T), independent of d, contradicting Proposition E.2's t≈√(d/ε). This is not a fitted-constant issue; the functional form changes.\n\nThe paper is honest about the approximation: Assumption 4.1 is clearly flagged, and Appendix D.3 admits the α>1/2 scalings were 'decided arbitrarily to fit empirical data.' But the abstract and Theorem 1.1 present the SD scaling as a fact about sign descent. That overclaim is the paper's main problem.\n\nCredit where due: the GD analysis is careful (sum-integral bounds, Laplace asymptotics, correct handling of the α=1 transition), the experiments match the GD predictions, and the relative-error rescaling is a good solution to the degenerate initialization limit. The discussion of source/capacity conditions and why α≤1 is excluded from standard asymptotic analyses is useful. Secondary issues: no code, fitted constant in Fig. 2, and Assumption 2.3 implicitly treats the sorted conditional frequencies as identical to the marginals, which is stronger than the stated 'same exponent' condition.\n\nWho should read this: anyone working on heavy-tailed optimization or vocabulary scaling. The GD half is a genuine contribution. The SD half is a cautionary example of a smoothed model producing a scaling that the exact dynamics contradict. It deserves a serious referee—the GD result alone justifies that—but the revision needs to either analyze exact SD or explicitly downgrade the SD claims to empirical observations about the η/2 model.","headline":"The GD scaling for heavy-tailed spectra is rigorous and new, but the sign-descent result is a theorem about an averaging model, not about sign descent, and exact even-time analysis contradicts the claimed √d scaling.","tokens_in":30487,"tokens_out":12846,"would_cite":true,"duration_ms":79344,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that on a linear bigram model, Zipf-distributed token frequencies force gradient descent to take almost $d^{1-\\varepsilon}$ iterations to reach relative error $\\varepsilon$, while sign descent needs only about…","keywords":["scaling laws","gradient descent","sign descent","Adam optimizer","Zipf's law","heavy-tailed data","linear bigram model","power-law spectrum"],"falsifier":"On synthetic data that exactly satisfies Assumption 2.3 with $\\alpha=1$, run gradient descent with step-size $1/\\pi_1$ for $t=\\tau d/2$ steps across $d=10^3,\\dots,10^6$; the theorem predicts the relative loss tends to $1-\\tau$ for every $\\tau\\in[0,1]$, so a measured limit that differs from $1-\\tau$ would falsify the analysis. Equivalently, on real text one can measure the sorted conditional frequencies $\\pi_{\\rho_j(k)|j}$: if their decay exponent differs from the marginal exponent $\\alpha$, the predicted dimension scalings should not hold.","tokens_in":29289,"feed_emoji":"📉","tokens_out":14859,"duration_ms":113230,"temperature":0.7,"pith_summary":"Gradient descent is known to struggle on the input and output layers of language models, and Adam-style optimizers fix it; this paper offers a first-principles explanation for why. On a linear bigram next-token model whose token frequencies obey a power law $\\pi_k \\propto 1/k^\\alpha$, it derives the number of iterations needed to reach relative error $\\varepsilon$ as the vocabulary size $d$ and $\\varepsilon$ grow. For the Zipf case $\\alpha=1$, the paper finds that gradient descent requires roughly $d^{1-\\varepsilon}$ iterations, while sign descent, a stand-in for Adam, requires only about $\\sqrt{d/\\varepsilon}$, giving a dimension-dependent speedup that matches experiments on real text. These results identify $\\alpha=1$ as the worst case for gradient descent and show that the usual $(1/\\varepsilon)^p$ scaling-law form only holds for lighter-tailed data.","feed_headline":"Zipf data: sign descent needs only sqrt(vocabulary) iterations","feed_subtitle":"A solvable bigram model shows why Adam-like updates beat gradient descent on heavy-tailed language data.","key_machinery":"The load-bearing object is the linear bigram model itself: $d$ tokens, $d^2$ parameters, square loss, and a diagonal Hessian whose eigenvalues are the token frequencies and whose initial residuals are the conditional next-token frequencies. Assumption 2.3 makes both sorted spectra equal power laws with the same exponent $\\alpha$, which is what lets the dynamics collapse to one-dimensional sums. The technical machinery is rescaled-time asymptotics: rather than letting $d\\to\\infty$ with the iteration count fixed, which degenerates to no progress for $\\alpha\\le1$, the paper sets $t=\\tau d^\\alpha$ or $t=\\tau\\sqrt d$ and takes limits of the relative loss. For gradient descent it uses integral approximations via Laplace's method and dominated convergence; for sign descent, since a constant step-size never converges, it introduces an averaged-oscillation model in which components first decrease linearly and then sit at $\\eta/2$, plus a step-size parameterization $\\eta=1/(H_d T\\phi^\\alpha)$ that controls how many components remain in the decreasing phase.","core_discovery":"The paper's central discovery is a set of dimension-scaling laws for deterministic optimization of a linear bigram model with square loss, under Assumption 2.3 that both marginal frequencies and conditionally sorted next-token frequencies decay as $1/k^\\alpha$. Because the Hessian is diagonal with eigenvalues $\\lambda_{ij}=\\pi_i$ and initial residuals $\\delta_{ij}(0)=\\pi_{j|i}$, the gradient-descent dynamics reduce to a single sum $\\sum_k k^{-\\alpha}(1-k^{-\\alpha})^{2t}/H_{d,\\alpha}$, where relative accuracy means $L_d(t)-L_d^*=\\varepsilon(L_d(0)-L_d^*)$. Taking $d\\to\\infty$ with rescaled time gives: for gradient descent, $t\\approx d^\\alpha\\log(1/\\varepsilon)$ when $\\alpha<1$, $t\\approx d^{1-\\varepsilon}$ when $\\alpha=1$, and $t\\approx (1/\\varepsilon)^{\\alpha/(\\alpha-1)}$ when $\\alpha>1$; for sign descent, $t\\approx (1/\\varepsilon)^{1/(2-4\\alpha)}$ when $\\alpha<1/2$, $t\\approx d^{(1-\\varepsilon)/2}$ when $\\alpha=1/2$, and $t\\approx \\sqrt{d/\\varepsilon}$ when $\\alpha>1/2$. For Zipf-distributed data ($\\alpha=1$), sign descent therefore cuts the iteration count by a factor of about $d^{1/2-\\varepsilon}$, which the paper presents as the mechanism behind Adam's advantage on the first and last layers of transformers.","pith_inferences":["A testable extension of the paper's logic is that in stochastic training of real transformers, the time-to-loss at fixed model size should grow roughly with the square root of the tokenizer's vocabulary size for Adam, and roughly linearly for plain SGD.","Because the $\\alpha=1$ scaling is driven by the rare-token tail of the conditional distribution, the analysis suggests that frequency-aware preconditioners could give Adam-like gains with less dependence on the coordinate system.","The averaged-oscillation assumption for sign descent is the least controlled step; replacing it with the exact sawtooth dynamics would show how much of the $\\sqrt d$ law depends on that idealization."],"forward_implications":["At $\\alpha=1$, the cost of training to good relative accuracy with gradient descent grows almost linearly in vocabulary size, so vocabulary growth itself becomes an optimization bottleneck.","With sign descent or Adam-like updates, the same task needs only about $\\sqrt{d/\\varepsilon}$ iterations, a factor-of-$d^{1/2-\\varepsilon}$ saving that grows with vocabulary size.","The standard neural-scaling-law form $(1/\\varepsilon)^p$ is confined to $\\alpha>1$; heavy-tailed data produces explicit dimension-dependent iteration counts instead.","The better algorithm depends on the tail exponent: sign descent wins for $\\alpha>1/2$, while gradient descent's dimension scaling is milder for $\\alpha<1/2$."],"supporting_citations":[{"why":"Supplies the empirical evidence that the heavy-tailed distribution of words causes gradient descent's difficulty on transformer first and last layers, motivating the model.","marker":"Kunstner et al. (2024)"},{"why":"Establishes sign descent as the scale-free coordinate-wise update used as a proxy for Adam.","marker":"Bernstein et al. (2018)"},{"why":"Documents Zipf's law for natural-language word frequencies, the data property the paper models.","marker":"Piantadosi (2014)"},{"why":"Provides the source and capacity power-law spectral conditions whose $\\alpha>1$ regime the paper argues misses Zipfian data.","marker":"Caponnetto and Vito (2007)"},{"why":"Gives tight convergence rates under power-law spectral conditions in optimization, the framework the paper adapts to $\\alpha\\le1$.","marker":"Velikanov and Yarotsky (2024)"},{"why":"Contains the log(t/d) loss heuristic on a similar model that the paper formalizes into the $\\alpha=1$ scaling law.","marker":"Bulatov (2023)"},{"why":"Supplies the OpenWebText corpus used for the real-data validation of the predicted scalings.","marker":"Gokaslan et al. (2019)"}],"fun_headline_variants":["Zipf data: sign descent needs sqrt(vocabulary) iterations","Sign descent beats gradient descent by sqrt(d) on Zipf data","For Zipf tokens, sign descent scales as sqrt(d), GD as d","Heavy tails: sign descent outruns gradient descent by sqrt(d)","Zipf law: sign descent cuts iterations to sqrt of vocabulary size"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Assumption 2.3: the conditionally sorted next-token frequencies must decay as the same power law $1/k^\\alpha$ as the marginal token frequencies, and for sign descent the oscillatory regime must be well approximated by freezing components at half the step-size; if those fail, the derived $d^{1-\\varepsilon}$ and $\\sqrt{d/\\varepsilon}$ scalings are not guaranteed.","fun_headline_variants_meta":{"raw":{"variants":["Zipf data: sign descent needs sqrt(vocabulary) iterations","Sign descent beats gradient descent by sqrt(d) on Zipf data","For Zipf tokens, sign descent scales as sqrt(d), GD as d","Heavy tails: sign descent outruns gradient descent by sqrt(d)","Zipf law: sign descent cuts iterations to sqrt of vocabulary size"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000753,"raw_usage":{"total_tokens":3463,"prompt_tokens":1173,"completion_tokens":2290,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":789,"completion_tokens_details":{"reasoning_tokens":2196}},"tokens_in":789,"tokens_out":2290,"duration_ms":13688,"temperature":1.0,"reasoning_tokens":2196,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T14:18:22.537822+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On synthetic data that exactly satisfies Assumption 2.3 with $\\alpha=1$, run gradient descent with step-size $1/\\pi_1$ for $t=\\tau d/2$ steps across $d=10^3,\\dots,10^6$; the theorem predicts the relative loss tends to $1-\\tau$ for every $\\tau\\in[0,1]$, so a measured limit that differs from $1-\\tau$ would falsify the analysis. Equivalently, on real text one can measure the sorted conditional frequencies $\\pi_{\\rho_j(k)|j}$: if their decay exponent differs from the marginal exponent $\\alpha$, the predicted dimension scalings should not hold.","supporting_citations":[],"review_version":1}