{"id":"8c257981-db6a-4f55-9528-8a82160e02cd","arxiv_id":"1908.10525","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"AdaGrad-Norm provably reaches ε error in O(log 1/ε) iterations for strongly convex and PL objectives from any initial step size, under new RUIG and zero-noise-at-optimum assumptions.","lead":"This paper proves that AdaGrad-Norm, an adaptive gradient method, converges exponentially fast for strongly convex and some non-convex objectives without the user knowing the problem's smoothness or curvature constants. The result matters because it gives a theoretical reason why adaptive step-size methods can be robust to step-size tuning in machine learning.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 1's high-probability bound on b_N rests on a false independence claim; the proof as written is unsound, although a martingale concentration argument likely repairs it.","rationale":"The central claim of robust linear convergence for AdaGrad-Norm in the stochastic strongly convex setting depends on the two-stage framework, and Stage I is guaranteed by Lemma 1. The proof of Lemma 1 contains a clear probabilistic error: the indicators Z_j depend on the adaptive state x_j, so they are not independent across iterations. The paper's attempted repair via a sub-Gaussian variance proxy is mathematically incorrect, since worst-case dependence prevents concentration of the sum. This is load-bearing because if b_N does not exceed ηL with high probability, the contraction phase cannot be entered within the stated number of iterations. However, the dependence is through a filtration, and a martingale concentration inequality applies to the bounded increments Z_j - E[Z_j | F_{j-1}], yielding a valid high-probability bound with essentially the same scaling in ε. Thus the theorem's rate is likely recoverable, consistent with the CONDITIONAL verdict. The batch results (Theorems 2 and 3) do not use Lemma 1's stochastic concentration and appear sound. The restrictiveness of Assumption (A4) narrows the theorem's scope but does not invalidate it within its assumptions. I therefore recommend no change to the reader's verdict.","tokens_in":23723,"tokens_out":17315,"duration_ms":171330,"concrete_test":"Re-derive Lemma 1 using Azuma-Hoeffding: define F_j as the σ-algebra generated by ξ_0,...,ξ_{j-1}; on the event min_i ||x_i-x*||^2 > ε, note P(Z_j=1 | F_j) ≥ γ for every j. Set δ = sqrt(2N log(1/δ1)) and verify that N = ⌈(C^2-b0^2)/(αγϵ) + δ/γ⌉ still supports the claimed high-probability bound. Then check whether the iteration counts in Theorem 1 remain O(log 1/ε) for Case 1 and O(1/ε + log 1/ε) for Case 2; if the leading dependence on ε degrades, the central linear-convergence claim must be revisited, otherwise the gap is confirmed fixable.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Lemma 1, the indicators Z_j = 1{||∇f_{ξ_j}(x_j)||^2 ≥ α||x_j - x*||^2} are treated as i.i.d. Bernoulli(γ) because the indices ξ_j are independent. This is not valid: x_j depends on ξ_0,...,ξ_{j-1}, so Z_j is not independent of the past. The subsequent remark claiming that the sum of dependent sub-Gaussians with σ=0.5 has variance at most 0.25N^2 and hence concentrates is incorrect; perfect positive correlation gives a sum that is either 0 or N with probability 1-γ or γ, so the claimed lower tail near γN does not concentrate. Since Lemma 1 is the sole engine for Stage I (ensuring b_N > ηL with high probability), Theorem 1's stochastic high-probability statement is not established as written. A martingale concentration bound on the martingale difference sequence Z_j - E[Z_j | F_{j-1}], which is bounded in [-1,1], would yield a valid high-probability tail, but the manuscript does not supply it. This is a genuine proof gap at a load-bearing step, not a mere expository issue.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper analyzes the norm version of AdaGrad (AdaGrad-Norm) and proves non-asymptotic convergence rates for strongly convex objectives in both stochastic and batch settings, and for non-convex objectives satisfying the Polyak--Lojasiewicz (PL) inequality in the batch setting. It introduces the Restricted Uniform Inequality of Gradients (RUIG) assumption, which lower-bounds the probability that a stochastic gradient at a point away from the optimum has norm at least a constant times the distance to the optimum. The proof uses a two-stage framework: Stage I shows that the adaptive stepsize parameter b_t grows past a critical threshold within a controlled number of iterations unless the algorithm has already reached the desired accuracy, and Stage II shows that after the threshold is crossed the error contracts linearly. The principal advertised result is that for stochastic strongly convex problems, AdaGrad-Norm achieves epsilon accuracy in O(log 1/epsilon) iterations with high probability when b0 > eta L, and in O(1/epsilon + log 1/epsilon) iterations for arbitrary b0, without prior knowledge of smoothness, strong convexity, or a containing convex set. Numerical experiments on least squares and a two-layer network illustrate linear convergence and robustness to b0.","tokens_in":23922,"tokens_out":5963,"duration_ms":53377,"significance":"If the stochastic results were fully established, the paper would provide a genuinely parameter-free linear-convergence guarantee for an adaptive SGD method, complementing the known sublinear guarantees for AdaGrad-Norm under bounded-variance assumptions. The RUIG condition is a new and interesting way to quantify the 'balancedness' of stochastic gradient norms, with explicit worked examples (Gaussian least squares, strongly convex sums) that do not presuppose the desired rate. The two-stage framework is clearly explained and likely transferable to other adaptive algorithms. The batch-setting proofs (Theorems 2 and 3) are coherent and follow from co-coercivity and descent arguments, and the numerical experiments support the main qualitative claims. The main weakness is that the stochastic Theorem 1 rests on a high-probability growth lemma whose proof, as written, relies on an invalid independence assertion; this is a load-bearing gap that needs to be repaired or the stochastic claim must be weakened.","major_comments":[{"comment":"The indicators Z_j defined in Eq. (9) are not independent across iterations, because x_j depends on the past samples xi_0,...,xi_{j-1}; the proof treats them as i.i.d. Bernoulli(gamma) and applies Lemma C3. The subsequent remark asserting that the sum of dependent sub-Gaussians with sigma=0.5 has variance at most 0.25N^2 and hence concentrates is incorrect: a perfectly correlated sum can take value 0 or N with probabilities 1-gamma or gamma, so no concentration around gamma N holds. Since Lemma 1 is the sole mechanism forcing b_N > eta L in Stage I of Theorem 1, the stochastic high-probability convergence statement is not established as written. A valid martingale concentration argument on the bounded martingale difference sequence Z_j - E[Z_j | F_{j-1}] would likely repair the proof, but the manuscript does not supply it.","section":"Appendix C.1, Lemma 1"},{"comment":"The assumption P(grad f_i(x*) = 0) = 1 for each component is used as a substitute for the noiseless-at-the-optimum condition in the co-coercivity steps (Appendix D, Eq. (13)) and in the contraction step of Theorem 1 (Appendix A, Eqs. (1)-(2)). The authors themselves note that this 'may not be appropriate for certain applications.' Because Theorem 1 and the bounds in Stage I both rely on this condition, the headline robustness claim in Section 1 should explicitly state that the stochastic linear-convergence guarantee is restricted to settings with a.s. zero component gradient at x*. This is not a correctness error, but it materially narrows the scope of the stochastic result compared to the abstract's phrasing.","section":"Section 2, Assumption (A4)"},{"comment":"The high-probability term exp(-delta^2/(2(N gamma (1-gamma)+delta))) contains the same delta that appears in the iteration count N = ceil((eta^2 L^2 - b0^2)/(alpha gamma epsilon) + delta/gamma), but the dependence of the failure probability on the problem parameters is not discussed. In particular, for the claimed O(1/epsilon + log 1/epsilon) rate, the authors should state explicitly how delta is chosen (e.g., delta = sqrt(4c gamma (1-gamma) N log N)) and verify that the total failure probability tends to zero as epsilon -> 0 without requiring gamma to grow with N. As written, the probability and the iteration bound are not reconciled.","section":"Theorem 1 and Lemma 1"}],"minor_comments":[{"comment":"The phrase 'independent identical Bernoulli' is inaccurate: even under RUIG, the conditional probabilities P(Z_j = 1 | x_j) are only bounded below by gamma; they are not necessarily equal to gamma. Please use 'stochastically dominated by' or similar.","section":"Appendix C.1, Lemma 1"},{"comment":"The constant delta_h is not defined in the theorem statement; it is introduced later in the proof (Appendix A). Define it where the theorem is stated so that the probability bounds are self-contained.","section":"Theorem 1"},{"comment":"For precision, the informal summary of the stochastic result should mention Assumption (A4) explicitly, since the theorem statement relies on it and the assumption materially restricts the data distribution.","section":"Abstract and Section 1"},{"comment":"The threshold b0 > eta (mu + L)/2 is stated in the theorem, while Lemma 2(a) uses a general C; the relation between C and the threshold should be spelled out for readability.","section":"Theorem 2"},{"comment":"There are several typographical issues: 'Polyak- Lojasiewicz' has an errant space; 'AdaGrad-Norm' is sometimes hyphenated inconsistently; 'P_i' is used before being defined in the Notations paragraph.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper has a clear central contribution that is of interest to the adaptive-optimization community. The batch results are solid, and the stochastic gap is likely fixable with a standard martingale concentration bound. However, the current proof of Lemma 1 is not just missing a detail; the stated argument is incorrect. I recommend requiring a rigorous repair of Stage I in the stochastic setting before acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things before reading this one. First, the batch-setting results are solid and the two-stage framework plus RUIG condition are genuinely new tools for AdaGrad-Norm analysis. Second, the stochastic Theorem 1 has a load-bearing proof gap: Lemma 1 treats the indicators Z_j as independent Bernoulli, but x_j depends on the past, so they are not independent. The subsequent remark about sub-Gaussian sums is also wrong—perfect positive correlation would give a sum with variance N^2/4, not N/4, and no concentration around the mean. The stress-test note is right on both counts.\n\nWhat is actually new: the paper gives the first linear convergence guarantee for AdaGrad-Norm in the stochastic strongly convex setting without prior knowledge of L, mu, or a bounded domain. The two-stage idea—first show b_t grows past a threshold, then show contraction in Stage II—is clean and likely portable to other adaptive methods. The batch theorems (2 and 3, for strongly convex and PL objectives) follow from co-coercivity and the descent lemmas, and I checked enough of the algebra to believe them. The numerical experiments are consistent with the theory and show the robustness story that motivates the paper.\n\nThe soft spots are real but localized. Lemma 1's independence issue sits at the base of Stage I, so as written the high-probability statement in Theorem 1 is not established. The good news is the fix is probably not deep: a martingale concentration argument on Z_j - E[Z_j | F_{j-1}], which is bounded in [-1,1], would give the same kind of tail. But the manuscript does not supply it, and the current Remark that tries to wave away dependence is mathematically false. Also, Assumption A4 (noiseless at the optimum) is restrictive; the authors honestly flag this in Section 3, but it means the stochastic result applies only to noiseless or interpolating settings, which is a smaller class than the abstract suggests.\n\nI am not bothered by the reuse of standard lemmas from Ward et al. The citation pattern looks fine, and the RUIG condition is not circular—the examples in Section 3 work without assuming linear convergence. The central claim appears plausible, but the stochastic proof as written is incomplete.\n\nWho is this for: anyone working on adaptive gradient methods, especially on theory for stepsize robustness. The batch results alone are worth having. I would send it to a serious referee, with the expectation of major revision focused on fixing Lemma 1. If that gets repaired, the paper will be an important one.","headline":"A genuinely new two-stage framework for AdaGrad-Norm linear convergence, with a real but likely fixable gap in the stochastic proof.","tokens_in":24489,"tokens_out":883,"would_cite":false,"duration_ms":11360,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W40","90C25","62L20"],"pacs":[],"model":"deepseek-v4-flash","headline":"AdaGrad-Norm converges linearly on strongly convex losses without parameter tuning.","keywords":["AdaGrad-Norm","adaptive stochastic gradient descent","linear convergence","strong convexity","Polyak-Lojasiewicz inequality","Restricted Uniform Inequality of Gradients","two-stage convergence analysis","step-size robustness"],"falsifier":"Run AdaGrad-Norm with $b_0 > \\eta L$ on a strongly convex smooth quadratic whose labels contain independent noise, so $\\nabla f_i(x^*) \\neq 0$ with positive probability; if the error still decreases at an exponential rate to arbitrarily small values, the noiseless-at-the-optimum assumption is unnecessary, and if it plateaus above the noise floor, the theorem's dependence on (A4) is confirmed.","tokens_in":23465,"feed_emoji":"📉","tokens_out":8629,"duration_ms":79208,"temperature":0.7,"pith_summary":"The paper aims to prove that AdaGrad-Norm, the norm-based adaptive stochastic gradient method, converges linearly on smooth strongly convex objectives and on non-convex objectives satisfying the Polyak-Lojasiewicz inequality. The key gain is that this holds without knowing the smoothness constant, the strong-convexity parameter, or a convex set containing the minimizer, and the initial step-size scale can start anywhere. A new landscape assumption, the Restricted Uniform Inequality of Gradients (RUIG), controls the probability that a sampled gradient norm is at least a fixed fraction of the distance to the minimizer; together with a two-stage analysis of the accumulating step-size reciprocal, it yields $O(\\log 1/\\epsilon)$ high-probability rates. A reader would care because adaptive methods are widely used, and this is a proof that their step-size adaptation can supply, rather than require, information about the objective.","feed_headline":"AdaGrad-Norm converges linearly without knowing curvature","feed_subtitle":"Two-stage step-size growth yields log 1/ε rates for strongly convex and PL objectives.","key_machinery":"The central object is the Restricted Uniform Inequality of Gradients (RUIG): for every $\\epsilon > 0$ and every $x$ with $\\|x - x^*\\|^2 > \\epsilon$, the probability over the sample index that $\\|\\nabla f_i(x)\\|^2 \\ge \\alpha \\|x - x^*\\|^2$ is at least $\\gamma$. RUIG guarantees that in Stage I the accumulated step-size reciprocal $b_t$ grows above thresholds such as $\\eta L$, deterministically in the batch setting and with high probability in the stochastic setting, while a separate lemma bounds $\\|x_t - x^*\\|$ during that growth. Once $b_t$ crosses the threshold, AdaGrad-Norm becomes a contraction in expectation and another lemma bounds $b_t$ from above, producing the linear decay. This two-stage split is what removes the need to know $L$, $\\mu$, or a bounded domain.","core_discovery":"In the strongly convex stochastic setting, under assumptions (A1a), (A2), (A3), and (A4), AdaGrad-Norm reaches $\\min_i \\|x_i - x^*\\|^2 \\le \\epsilon$ with high probability after $T = O(\\log 1/\\epsilon)$ iterations when $b_0 > \\eta L$, and after $T = O(1/\\epsilon + \\log 1/\\epsilon)$ iterations when $b_0 \\le \\eta L$. The batch full-gradient analogue gives deterministic $O(\\log 1/\\epsilon)$ rate bounds for strongly convex functions and, via Theorem 3, for non-convex functions satisfying the PL inequality, with a logarithmic correction when $b_0$ starts small. The rates match classical fixed-step-size SGD and GD up to constants, but the algorithm does not need the smoothness constant, strong-convexity parameter, or a bounding box for the minimizer.","pith_inferences":["RUIG can be read as a testable landscape diagnostic: on a real dataset one can estimate the probability that a sampled gradient norm exceeds $\\alpha \\|x - x^*\\|^2$ and check whether the $\\alpha\\gamma$ product stays bounded away from zero.","The high-probability Stage I growth in Lemma 1 relies on the sampled gradient-indicator events being treated as independent; if samples are correlated, the effective variance grows and the warm-up count would need a larger slack term.","The small-$b_0$ guarantee is stated for the best iterate; extending the same rates to the last iterate would require an additional argument and is a natural open follow-up.","The paper names the weak growth condition $E\\|\\nabla f_\\xi(x)\\|^2 \\le M\\|\\nabla F(x)\\|^2 + \\sigma^2$ as a route to relax Assumption (A4); making that step work would widen the stochastic result to objectives with bounded noise at the optimum."],"forward_implications":["With $b_0 > \\eta L$ (a small initial step), stochastic AdaGrad-Norm is linearly convergent from any starting point and no projection or parameter knowledge is needed.","With $b_0 \\le \\eta L$ (a large initial step), the price is only a sublinear warm-up stage; once $b_t$ exceeds $\\eta L$, the same linear contraction applies.","The batch analysis grants the same linear guarantees to non-convex objectives satisfying the PL inequality, a class that includes over-parameterized neural-network training objectives.","The two-stage framework is presented as transferable to other adaptive step-size methods, with Adam and AMSGrad named as direct candidates."],"supporting_citations":[{"why":"Defines AdaGrad-Norm and proves the sublinear $O(1/\\sqrt{T})$ non-convex rate that the current paper extends to linear in Stage II.","marker":"Ward et al., 2018"},{"why":"Gives an earlier linear-convergence result for an AdaGrad-Norm variant that requires a known convex set containing the minimizer, the gap this paper closes.","marker":"Levy, 2017"},{"why":"Establishes sublinear adaptive-method rates under a bounded-variance model, the comparison baseline for the stochastic theorem.","marker":"Levy et al., 2018"},{"why":"Analyzes stochastic adaptive step sizes under bounded variance while requiring smoothness knowledge, contrasting with the parameter-free claim.","marker":"Li and Orabona, 2018"},{"why":"Provides the fixed-step-size SGD linear rate with zero noise at the optimum and the co-coercivity lemma used in the proof.","marker":"Needell et al., 2016"},{"why":"Source of the almost-stationary assumption (A4) that carries the noiseless-at-the-optimum condition in the stochastic argument.","marker":"Moulines and Bach, 2011"},{"why":"Supplies the over-parameterized and fast-SGD context against which Assumption (A4) is positioned as weaker than growth conditions.","marker":"Vaswani et al., 2018"},{"why":"Supplies the Bernstein inequality used to turn the Bernoulli count in Lemma 1 into a high-probability lower bound on $b_t$.","marker":"Wainwright, 2019"},{"why":"Provides the strong-convexity co-coercivity lemma used in the batch proof and the classical GD rate for comparison.","marker":"Bubeck et al., 2015"},{"why":"Gives a matching linear rate for AdaGrad-type methods on a specific two-layer over-parameterized network, which Theorem 3 generalizes.","marker":"Wu et al., 2019"}],"fun_headline_variants":["AdaGrad-Norm converges linearly without tuning","Linear convergence without curvature bounds","Adaptive SGD matches classic rates without tuning","Adaptive SGD: linear rates with no problem constants"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The stochastic linear-rate proof requires Assumption (A4): every component function's gradient vanishes at the global minimizer almost surely, so all stochastic noise disappears at the optimum.","fun_headline_variants_meta":{"raw":{"variants":["AdaGrad-Norm converges linearly without tuning","Linear convergence without curvature bounds","Adaptive SGD matches classic rates without tuning","Adaptive SGD: linear rates with no problem constants"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001525,"raw_usage":{"total_tokens":6072,"prompt_tokens":874,"completion_tokens":5198,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":490,"completion_tokens_details":{"reasoning_tokens":5143}},"tokens_in":490,"tokens_out":5198,"duration_ms":40846,"temperature":1.0,"reasoning_tokens":5143,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:40:43.341256+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run AdaGrad-Norm with $b_0 > \\eta L$ on a strongly convex smooth quadratic whose labels contain independent noise, so $\\nabla f_i(x^*) \\neq 0$ with positive probability; if the error still decreases at an exponential rate to arbitrarily small values, the noiseless-at-the-optimum assumption is unnecessary, and if it plateaus above the noise floor, the theorem's dependence on (A4) is confirmed.","supporting_citations":[{"cited_title":"(2018): F (xk0−1) ≤ F (x0) + η2L 2 (1 + log( b2 k0−1 b2 0 ))","cited_arxiv_id":null,"evidence_quote":"Defines AdaGrad-Norm and proves the sublinear $O(1/\\sqrt{T})$ non-convex rate that the current paper extends to linear in Stage II."}],"review_version":1}