{"id":"ca808ed7-4190-4196-91c3-4c2a66bcf1db","arxiv_id":"1909.00843","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"The non-uniform average of SGD iterates achieves the optimal O(log(1/delta)/T) high-probability error bound on non-smooth strongly convex functions, with a matching lower bound.","lead":"This paper proves that a simple weighted average of SGD iterates reaches the optimal error rate with high probability, not just on average. It also gives a matching lower bound for that rate and compares averaging schemes on SVM problems.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed matching lower bound does not apply to Algorithm 1 as analyzed: Claim 3.3 changes the step size from 2/(μ(t+1)) to 1/(t+1) and uses oracle noise larger than the ||z_t||≤1 assumption of Theorem 3.1, so the 'optimal' claim lacks a valid matching lower bound.","rationale":"The proof of the upper bound (Theorem 3.1, Lemmas 4.1–4.5) is largely coherent: the telescoping identity, the bound on V_T via Rakhlin-style lemmas, and the use of Generalized Freedman's inequality are all plausible, and the subgaussian extension in Appendix C follows the same pattern. I found no internal inconsistency in the upper-bound argument. The main weakness is the lower bound. The reader's rationale flagged the step-size mismatch; I agree and add that the oracle's noise bound also exceeds the one in Theorem 3.1. These two mismatches mean the 'matching lower bound' does not match the analyzed algorithm. A conditional acceptance requiring either a corrected lower bound for the exact schedule or a softened optimality claim would be appropriate, which is exactly the reader's verdict. Hence I do not change the reader's conditional disposition. Minor issue: the displayed statement of Theorem 3.1 appears to omit a factor of 1/T on the first term, but the proof's final bound is clear.","tokens_in":14125,"tokens_out":29711,"duration_ms":250633,"concrete_test":"Re-derive the lower-bound calculation with Algorithm 1's schedule η_t=2/(μ(t+1)) and a noise oracle with |z_t|≤1 (e.g., z_t = c X_t for active t). Using the closed form x_t = 2/(t(t-1)) Σ_{i<t} i z_i, compute the distribution of f(Σγ_t x_t)-f(x*) and check whether it is Ω(log(1/δ)/T) with probability at least δ. If the check fails to produce the claimed rate, Claim 3.3 provides no matching lower bound for Algorithm 1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central 'optimal' claim depends on the lower bound, but Claim 3.3 does not analyze Algorithm 1 under the hypotheses of Theorem 3.1. It explicitly uses step size η_t=1/(t+1) (Remark 5.1) instead of Algorithm 1's η_t=2/(μ(t+1)), so it lower-bounds a different algorithm. In addition, the constructed oracle has |ẑ_t|=(T+1)/(T−t) for T/2<t≤3T/4, reaching about 4, which violates the bounded-noise assumption ‖ẑ_t‖≤1 used in Theorem 3.1 and Lemma 4.1; Claim 5.2 only assumes |ẑ_t|≤6. Because the lower bound is outside the theorem's assumptions, it neither contradicts the upper bound nor demonstrates that the specific algorithm analyzed is optimal. Remark 5.1 asserts the step-size change is nonessential, but that assertion is not proved. The high-probability upper bound appears sound, so the paper's contribution is preserved, but the advertised optimality is not established by the current text.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper analyzes stochastic gradient descent with the non-uniform averaging scheme of Lacoste-Julien et al. for nonsmooth strongly convex functions. The main theoretical result is a high-probability upper bound of O((L log(1/δ) + L^2/μ)/T) on the function error, under the assumption that the oracle noise is almost surely bounded by 1. The proof uses a generalized Freedman inequality to bound the martingale formed by the noise terms, together with deterministic bounds adapted from Rakhlin et al. The paper also claims a matching lower bound of Ω(log(1/δ)/T), extends the upper bound to subgaussian noise, and reports experiments comparing averaging schemes.","tokens_in":14377,"tokens_out":12846,"duration_ms":106536,"significance":"If the upper bound is correct, the paper provides a simple algorithm with a high-probability O(log(1/δ)/T) guarantee, which is optimal in T for fixed δ. The proof is clear and the use of the generalized Freedman inequality is appropriate. However, the advertised matching lower bound is not proved for the algorithm and noise model analyzed in the upper bound, so the optimality claim is not currently established. The upper bound and its proof are nevertheless a useful contribution, and the subgaussian extension is a reasonable addition.","major_comments":[{"comment":"The lower bound is proved for step size η_t = 1/(t+1), whereas Algorithm 1 and Theorem 3.1 use η_t = 2/(μ(t+1)) (with μ = 1 for f(x) = x^2/2). Claim 3.3 states it runs Algorithm 1 with these step sizes, which is inconsistent. Remark 5.1 acknowledges the modification and asserts without proof that it is nonessential. As a result, the lower bound does not apply to the algorithm whose upper bound is proved, and the paper's claim of a matching lower bound in the abstract and introduction is unsupported.","section":"5, Claim 3.3 and Remark 5.1"},{"comment":"The oracle used in the lower bound produces noise ẑ_t = ((T+1)/(T-t)) X_t for T/2 < t ≤ 3T/4, which can have magnitude about 4, violating the bounded-noise assumption ‖ẑ_t‖ ≤ 1 used in Theorem 3.1 and in the proof of Lemma 4.1. Claim 5.2 only assumes |ẑ_t| ≤ 6. Thus the lower bound is proved outside the hypotheses of the upper bound, so it does not demonstrate optimality of Algorithm 1 in the setting where the upper bound holds.","section":"5, lower-bound oracle and Claim 5.2 vs. Theorem 3.1"}],"minor_comments":[{"comment":"In Eq. (4), the second summand is written with ‖ĝ_t‖² but the index of summation is i; this appears to be a typo for ‖ĝ_i‖².","section":"A, proof of Lemma 4.5"},{"comment":"The statement of Lemma C.10 appears to have a typo: the condition should likely be E[exp(X²/κ²)] ≤ 2 (matching the paper's definition of subgaussian) rather than E[exp(X/κ²)] ≤ 2. As written, the lemma does not follow from the cited proposition.","section":"C.2, Lemma C.10"},{"comment":"The telescoping step states 'the right-hand side telescopes' after omitting the non-positive term involving ‖x_{T+1}-x*‖²; this is correct but could be stated explicitly to help the reader.","section":"4, proof of Theorem 3.1"},{"comment":"The abstract claims the non-uniform averaging strategy has 'smaller variance'; the experimental plots in Figure 1 only show trial clouds, so this claim is not quantified. A quantitative variance comparison would strengthen the presentation.","section":"6, experiments"}],"recommendation":"major_revision","confidential_remarks":"The main issue is the mismatch between the lower bound and the upper bound's algorithm and assumptions. The upper-bound proof itself appears sound. The paper's central advertised claim (optimality) depends on the lower bound, so major revision is appropriate. The authors should either prove the lower bound under the exact assumptions of Theorem 3.1, or reframe the paper as a high-probability upper-bound analysis without the optimality claim."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the upper-bound result is real and mostly clean; the 'matching lower bound' is not actually matching the algorithm analyzed, so the optimality claim is overstated as written. If you treat this as a paper about high-probability guarantees for non-uniform averaging, the contribution stands. If you treat it as an optimality proof, it doesn't yet.\n\nThe new piece is the high-probability O(log(1/delta)/T) bound for Lacoste-Julien et al.'s non-uniform averaging, using the Generalized Freedman inequality from Harvey et al. 2018. The proof structure follows that paper and Rakhlin et al., but the adaptation to the t-weighted average is nontrivial enough, and the appendix covers the technical lemmas. The subgaussian extension in Appendix C is a genuine strengthening, not a throwaway. The experiments are fine; they show the non-uniform and suffix averages beat final iterate and uniform average, which matches the theory. Not the main event, but honestly reported.\n\nThe soft spot is the lower bound. Claim 3.3 states a lower bound for 'Algorithm 1', but the proof uses step size 1/(t+1), not 2/(mu(t+1)), and the oracle noise is only assumed bounded by 6, with the actual construction reaching |z_t| about 4. Theorem 3.1 requires ||z_t|| <= 1. So the lower bound applies to a different, noisier algorithm with a different step size. The remark saying the step-size change is nonessential is not backed by a proof. The 'optimal' word in the abstract and intro therefore overreaches. This is a real gap, but it's fixable—adapt the construction to the 2/(mu(t+1)) schedule and bounded noise, or reframe the claim as a lower bound for a closely related variant. The upper bound's internal logic is unaffected.\n\nWho is this for? People working on high-probability bounds for stochastic optimization, and practitioners choosing an averaging scheme. The paper deserves serious peer review; the upper bound alone is a solid incremental contribution. I would send it to a good theory venue with the explicit request that the lower bound be made to match the theorem's assumptions. I'd cite the upper bound now, and the whole paper once the optimality claim is cleaned up.","headline":"Solid upper bound for non-uniform averaging SGD; the lower bound misses the theorem's assumptions, so the optimality claim is not yet established.","tokens_in":14940,"tokens_out":2943,"would_cite":true,"duration_ms":38728,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A non-uniform average of SGD iterates reaches the optimal 1/T convergence rate with probability 1-δ, not just in expectation.","keywords":["stochastic gradient descent","strongly convex","non-smooth optimization","high-probability bounds","Freedman's inequality","non-uniform averaging","martingale concentration","optimal convergence rate"],"falsifier":"Run Algorithm 1 on $f(x)=\\|x\\|^2/2$ with noise drawn uniformly from the unit sphere (so $\\|\\hat z_t\\|\\le1$ and the theorem's assumptions hold), record the empirical $\\delta$-quantile of $f(\\sum_t\\gamma_tx_t)-f(x^*)$ over many trials; if for any fixed constant $C$ the quantile exceeds $C\\log(1/\\delta)/T$ as $T$ grows, the upper bound is false. For the lower bound, compute the exact distribution of the weighted average under the paper's Bernoulli oracle on $x^2/2$ and check whether its tail dominates $\\log(1/\\delta)/(9T)$ with probability $\\delta$.","tokens_in":13898,"feed_emoji":"📉","tokens_out":13450,"duration_ms":106805,"temperature":0.7,"pith_summary":"This paper establishes that a very simple variant of stochastic gradient descent—run ordinary projected SGD, then return the iterates averaged with weights proportional to the iteration number—has error $O(\\log(1/\\delta)/T)$ with probability at least $1-\\delta$ on nonsmooth, strongly convex, Lipschitz problems. That rate matches the optimal $O(1/T)$ convergence already known to hold in expectation, and a matching lower bound shows the $\\log(1/\\delta)$ factor cannot be removed. The practical upshot is that a single run of SGD can carry a rigorous high-probability guarantee, without running many trials or knowing the stopping time in advance. The proof rests on a martingale whose total conditional variance is bounded by a linear function of the martingale itself, making the tail bound sharp. Experiments on regularized SVM problems indicate the weighted average performs as well as suffix averaging and better than the final iterate or uniform average.","feed_headline":"Weighted-average SGD hits the optimal 1/T rate with high probability","feed_subtitle":"A weighted average of iterates gives a per-trial guarantee that matches the best possible rate.","key_machinery":"The proof is carried by a specialized martingale concentration bound: the generalized Freedman inequality, which controls a martingale by its total conditional variance. The relevant martingale has increments $d_t=t\\langle \\hat z_t, x_t-x^*\\rangle$, where $\\hat z_t$ is the oracle noise, and its total conditional variance is $V_T=\\sum_{t=1}^T t^2\\|x_t-x^*\\|^2$. The crucial step (Lemma 4.3) shows that, with the step sizes $\\eta_t=2/(\\mu(t+1))$, this variance can itself be bounded by a linear combination $\\sum_i \\alpha_i d_i+\\beta$ of the martingale increments, with $\\alpha_i=O(T/\\mu)$ and $\\beta=O(L^2T^2/\\mu^2)$. This self-bounding, 'chicken-and-egg' structure lets the inequality produce a tail estimate with only a $\\log(1/\\delta)$ factor instead of the weaker $\\sqrt{T}$ factor that generic martingale arguments would give. The weights $t/(T(T+1)/2)$ and step sizes are chosen so that summing the strong-convexity inequalities telescopes, leaving only the noise term to be controlled.","core_discovery":"The paper's central claim is Theorem 3.1: for a $\\mu$-strongly convex, $L$-Lipschitz function and a stochastic gradient oracle whose noise satisfies $\\|\\hat z_t\\|\\le 1$ almost surely, projected SGD with step size $\\eta_t=2/(\\mu(t+1))$ and averaging weights $\\gamma_t=t/(T(T+1)/2)$ satisfies $f(\\sum_{t=1}^T \\gamma_t x_t)-f(x^*) = O((L\\log(1/\\delta)+L^2/\\mu)/T)$ with probability at least $1-\\delta$. A companion lower bound, Claim 3.3, constructs a zero-mean Bernoulli oracle on $f(x)=x^2/2$ for which the same averaged output has error at least $\\log(1/\\delta)/(9T)$ with probability at least $\\delta$, so the $\\log(1/\\delta)$ factor is necessary. Together these show that the simple, online-computable non-uniform average has the optimal high-probability convergence rate, not merely the optimal expected rate.","pith_inferences":["The paper does not prove it, but the same variance self-binding argument likely extends to any output weights within a constant factor of $t$, such as a sliding-window suffix average, which would give practitioners a larger family of simple high-probability averaging schemes.","A natural testable extension is the heavy-tailed noise regime: if the oracle noise has only finite variance or power-law tails, one would expect the $\\log(1/\\delta)/T$ guarantee to degrade, and truncating the stochastic gradient before averaging might restore it.","The lower bound's Bernoulli oracle suggests that the $\\log(1/\\delta)$ factor is intrinsic to subgaussian noise itself; proving a similar lower bound for any first-order randomized method, rather than for this specific averaging scheme, would make that intuition a theorem.","The high-probability bound is stated for a fixed horizon $T$; combining it with a union bound over horizons could yield a stopping rule with a guaranteed $\\log(1/\\delta)\\log(T)/T$ rate when $T$ is chosen adaptively."],"forward_implications":["A single run of SGD with the non-uniform average gives a rigorous $O(\\log(1/\\delta)/T)$ error bound with probability $1-\\delta$, so users can trust one trial instead of averaging many.","The $\\log(1/\\delta)$ factor is unavoidable: no algorithm of this form can beat the $\\log(1/\\delta)/T$ high-probability rate on nonsmooth strongly convex problems under bounded noise.","Non-uniform averaging matches suffix averaging's high-probability guarantee while remaining fully online, with no need to know the time horizon in advance.","The subgaussian extension (Theorem C.3) covers Gaussian noise with the same $O(\\log(1/\\delta)/T)$ rate, replacing $\\|\\hat z_t\\|\\le1$ by a $\\kappa$-subgaussian assumption.","On regularized SVM problems, the experiments show the weighted average and suffix average dominate the final iterate and uniform average in both typical error and spread."],"supporting_citations":[{"why":"Introduces the non-uniform averaging scheme (Algorithm 1) and proves its expected O(1/T) rate, which this paper upgrades to a high-probability bound.","marker":"[Lacoste-Julien et al., 2012]"},{"why":"Provides the generalized Freedman inequality (Theorem 2.2) and the recursive variance self-bounding observation used throughout the proof.","marker":"[Harvey et al., 2018]"},{"why":"Supplies Lemmas 4.4 and 4.5, the distance bounds with coefficients a_i(t) and b_i(t) used to control the total conditional variance.","marker":"[Rakhlin et al., 2012]"},{"why":"Supplies the reverse Chernoff bound (Lemma B.1) used in the lower-bound proof on the Bernoulli oracle.","marker":"[Klein and Young, 2015]"},{"why":"Gives Hoeffding's Lemma, used in Claim 4.2 to establish the subgaussian moment condition for each martingale increment.","marker":"[Massart, 2007]"},{"why":"Provides Proposition 2.5.2, used in the subgaussian extension to convert a kappa-subgaussian noise tail into an MGF bound.","marker":"[Vershynin, 2018]"}],"fun_headline_variants":["High-probability optimal 1/T rate for weighted-average SGD","Simple weighted average gives optimal high-prob SGD rate","Optimal high-prob 1/T bound for weighted SGD","A weighted average provably nails the 1/T SGD limit"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire argument assumes the oracle noise has bounded or at least subgaussian tails; if the noise is heavy-tailed, the martingale variance bound collapses and the $O(\\log(1/\\delta)/T)$ guarantee may fail.","fun_headline_variants_meta":{"raw":{"variants":["High-probability optimal 1/T rate for weighted-average SGD","Simple weighted average gives optimal high-prob SGD rate","Optimal high-prob 1/T bound for weighted SGD","A weighted average provably nails the 1/T SGD limit"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000957,"raw_usage":{"total_tokens":4040,"prompt_tokens":871,"completion_tokens":3169,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":487,"completion_tokens_details":{"reasoning_tokens":3099}},"tokens_in":487,"tokens_out":3169,"duration_ms":284010,"temperature":1.0,"reasoning_tokens":3099,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T05:34:52.933585+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 on $f(x)=\\|x\\|^2/2$ with noise drawn uniformly from the unit sphere (so $\\|\\hat z_t\\|\\le1$ and the theorem's assumptions hold), record the empirical $\\delta$-quantile of $f(\\sum_t\\gamma_tx_t)-f(x^*)$ over many trials; if for any fixed constant $C$ the quantile exceeds $C\\log(1/\\delta)/T$ as $T$ grows, the upper bound is false. For the lower bound, compute the exact distribution of the weighted average under the paper's Bernoulli oracle on $x^2/2$ and check whether its tail dominates $\\log(1/\\delta)/(9T)$ with probability $\\delta$.","supporting_citations":[{"cited_title":"Making gradient descent optimal for strongly convex stochastic optimization","cited_arxiv_id":null,"evidence_quote":"Supplies Lemmas 4.4 and 4.5, the distance bounds with coefficients a_i(t) and b_i(t) used to control the total conditional variance."},{"cited_title":"On the number of iterations for D antzig-- W olfe optimization and packing-covering approximation algorithms","cited_arxiv_id":null,"evidence_quote":"Supplies the reverse Chernoff bound (Lemma B.1) used in the lower-bound proof on the Bernoulli oracle."},{"cited_title":"Concentration inequalities and model selection","cited_arxiv_id":null,"evidence_quote":"Gives Hoeffding's Lemma, used in Claim 4.2 to establish the subgaussian moment condition for each martingale increment."}],"review_version":1}