{"id":"84da288b-c8e9-4c65-bda5-c7f42b45c600","arxiv_id":"2411.15877","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A stabilized RMSProp variant is proven to converge R-linearly on consistent linear least squares, and to a batch-size controlled neighborhood in the inconsistent case.","lead":"This paper introduces SGA-RMSProp, a version of RMSProp that adaptively chooses its discounting factor to keep the per-coordinate scaling stable, and proves linear convergence on least squares problems. It is of interest because it gives a convergence guarantee for an adaptive gradient method on a ubiquitous optimization problem, with experiments comparing it against plain SGD and RMSProp.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 4.4's batch-size lower bound for a guaranteed linear rate appears to be orders of magnitude above the B = 50/1000 settings used in the experiments, so the abstract's unqualified R-linear convergence claim is not supported in the tested regime.","rationale":"The reader identified the batch-size/epsilon condition as the weakest assumption. My stress test sharpens that concern: the condition is not merely qualitative, but quantitatively so demanding that it likely excludes the paper's own numerical regime. I checked the relevant formulas in Corollary 4.4 and the experimental parameter statements in Section 5.1. The proof algebra of Theorem 4.3, including the telescoping factorization around D_k D_{k-1}^{-1/2}, appears internally consistent, and the conditional theorem is plausible. However, the abstract and Theorem 4.3 state R-linear convergence unqualified, while the only proven gamma < 1 regime requires batch sizes far beyond what is tested. This is a scope/overclaim concern, not a demonstrated contradiction, so the existing CONDITIONAL verdict should stand. The proposed computation of B_min for the paper's own instances would settle whether the theorem covers the reported experiments or whether the abstract must be qualified.","tokens_in":34728,"tokens_out":51716,"duration_ms":401398,"concrete_test":"For each of the 12 problems in Section 5.1, compute the Corollary 4.4 lower bound on B exactly, using the reported n, d, singular values, p_j = ||a_j||_2^2 / ||A||_F^2, and the numerical (u, u) choices, and tabulate B_min alongside B = 50, B = 1000, and n = 10^6. If B_min is two to six orders of magnitude above the experimental B, the claim needs to be restricted to the theorem's conditions. A secondary check: run SGA-RMSProp with B set to B_min and the theorem's exact step size to confirm the predicted rate (4.21), which would also detect any hidden proof gap.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central result is Theorem 4.3/Corollary 4.4. The theorem's contraction factor (4.4) is only proven to be <1 under the batch-size condition in Corollary 4.4. For the paper's own sampling rule p_j = ||a_j||_2^2 / ||A||_F^2, that condition reads, roughly, B >= 4 log(2d) ||A||_F^2 (2 sqrt(2) ||A||_2 / lambda_d + sqrt(u/(3 u lambda_d)))^2, with u and u the upper and lower bounds of D_k. Plugging the Section 5.1 synthetic parameters (n = 10^6, d = 102, lambda_d = 1, lambda_1 in [20,100]) and the authors' choice u/u = 5, the lower bound is on the order of 10^7 to 10^9, compared with the experimental B = 1000. Thus the numerical linear convergence in Figure 1 and the faster-initial-convergence comparisons occur in a regime where Theorem 4.3 provides no guarantee. The abstract and Theorem 4.3 statement present the result without these B and epsilon qualifications, so the practical reach of the central claim is much narrower than stated. This does not disprove the conditional theorem, but it means the headline claim, as written, overstates what is established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes SGA-RMSProp, a variant of RMSProp for linear least squares problems in which the discounting factor beta_k is selected adaptively at each iteration so that the diagonal scaling matrix D_k satisfies the stability bound ||D_k^{-1}D_{k-1}-I||_2 <= epsilon. The main theoretical results are Theorem 4.3, an R-linear convergence bound in expectation for the consistent case, and Theorem 4.7, an R-linear convergence bound to a neighborhood of the minimizer for the inconsistent case, with the neighborhood radius controlled by the batch size. The paper also reports numerical experiments comparing SGA-RMSProp against SGD and RMSProp, and proposes a heuristic switching strategy (RMSP2SGD) that starts with SGA-RMSProp and switches to SGD after a stability condition is met.","tokens_in":35017,"tokens_out":5566,"duration_ms":48713,"significance":"If the stated results hold as qualified, the paper contributes a rare convergence-rate analysis for an adaptive coordinate-wise preconditioned stochastic method on a concrete problem class, and the stability mechanism based on controlling ||D_k^{-1}D_{k-1}-I||_2 is a clean, potentially reusable idea. The proofs are detailed and largely self-contained, and the numerical study is organized and reproducible in structure. However, the central R-linear convergence claim is only proven under a large-batch condition that the experiments do not satisfy, so the practical reach of the theoretical result is much narrower than the abstract suggests.","major_comments":[{"comment":"The abstract states that 'R-linear convergence of the algorithm is established on the consistent linear least squares problem' without qualification, and Theorem 4.3 states (4.3) with gamma given by (4.4). However, gamma < 1 is only guaranteed under the batch-size condition of Corollary 4.4 together with the stated bound on epsilon. For the paper's own sampling rule p_j = ||a_j||_2^2 / ||A||_F^2 (Remark 4.5), the Corollary 4.4 condition reads B >= 4 u^2 log(2d) ||A||_F^2 / u^2 * (2 sqrt(2) ||A||_2 / lambda_d(A^T A) + sqrt(u/(3 u lambda_d(A^T A))))^2. Plugging in the Section 5.1 parameters (n = 10^6, d = 102, lambda_d = 1, u/u = 5, and lambda_1 between 20 and 100) gives a lower bound on the order of 10^7 to 10^9, while the experiments use B = 50 and B = 1000. Thus the numerically observed linear convergence in Figure 1 occurs in a regime where Theorem 4.3 provides no guarantee, and the headline claim overstates what is proven. The abstract and theorem statements should be qualified with the batch-size condition, and the relation between the experiments and the proven regime should be discussed explicitly.","section":"Abstract and Theorem 4.3 / Corollary 4.4"},{"comment":"Theorem 4.3 states that the leading constant satisfies rho <= 1, but the proof bounds rho by ||D_K^{1/2}||_2 ||D_0^{-1/2}||_2, which by Proposition 3.1 is at most sqrt(u/u). Since u is a lower bound and u is an upper bound on the scaling, typically u < u, so sqrt(u/u) > 1. Therefore the claim rho <= 1 is not established; the correct statement would be rho <= sqrt(u/u) (or an explicit bound in terms of u and u). R-linear convergence remains meaningful with rho > 1, so this is correctable, but the theorem as stated is inaccurate.","section":"Theorem 4.3, proof around (4.6)"},{"comment":"The rate gamma in (4.4) depends on constants gamma_1,...,gamma_K that are never explicitly defined; the proof only says they are 'bounded above by some constants at most 1' after (4.6). Since Corollary 4.4 and the discussion after Theorem 4.3 rely on the product G(gamma_1,...,gamma_K) being at most 1, the argument would be self-contained if gamma_k were defined as explicit bounds, e.g., gamma_k = ||D_k^{1/2}D_{k-1}^{-1/2}||_2, which Proposition 3.1 already shows to be at most 1. As written, the theorem's rate contains unspecified quantities, which weakens its status as a quantitative convergence guarantee.","section":"Theorem 4.3, definition of gamma_k"}],"minor_comments":[{"comment":"The notation u and u (underline and overline) is visually difficult to distinguish in the typeset text; a different notation such as u_min and u_max would improve readability.","section":"Throughout"},{"comment":"The narrative states that for B = 50 the algorithm generally performs best with u = u1, but then selects u2 and u2 for subsequent experiments; the rationale for not using the empirically better u1 in the later comparisons is not explained.","section":"Section 5.1.2"},{"comment":"Figure 3 is described as having an inset plot in each panel, but the captions do not clearly identify which portion is the inset; this makes the claim about early-stage behavior harder to verify.","section":"Section 5.3"},{"comment":"The interval in the selection rule is written as (max{...}, 1), which suggests an open interval; the algorithm presumably allows beta_k = 1 or values approaching 1, so the interval notation should be made precise.","section":"Algorithm 3.2"}],"recommendation":"major_revision","confidential_remarks":"The core proof appears structurally sound, but the abstract and Theorem 4.3 substantially overstate the proven scope by omitting the batch-size and epsilon conditions under which gamma < 1. The authors should either weaken the headline claim or extend the analysis to cover the experimental regime. I would not recommend rejection because the conditional theorem and the stability mechanism are useful; however, the revision needs to be substantive, not merely cosmetic, in the statement and interpretation of the main results."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the theorem is probably right, but the abstract sells more than the proof delivers. The genuinely new piece is the beta-selection rule that forces D_k to move slowly, and the proof that this yields R-linear convergence for consistent least squares when the batch is large. That fills a gap in the adaptive-gradient literature, and the proof technique—telescoping the random product and bounding fluctuations with matrix Bernstein—is credible. The extension to a neighborhood result in the inconsistent case, with radius controlled by batch size, is also a nice touch.\n\nThe stress-test note checks out numerically. For the paper's own sampling distribution, Corollary 4.4's batch-size lower bound is on the order of 10^7–10^9 for their synthetic problems, while the experiments use B = 50 or 1000. So the theorem does not cover the experiments, and the abstract's unqualified \"R-linear convergence\" overstates what is established. The authors do acknowledge after Theorem 4.3 that sigma must be small and B large, but that qualification is missing from the abstract and from the theorem statement itself. That is the load-bearing soft spot.\n\nSecondary issues: the constants rho and gamma_k are implicit, the step size presumes exact knowledge of the extreme eigenvalues of A^T A, and the numerical gains over SGD are modest and sometimes within noise. None of these are fatal—the conditional theorem stands—but they reduce the paper's immediate usefulness. No code is provided, which would help.\n\nI'd send this to review. The core result is worth referee time, and the proof is detailed enough to be checked. I'd ask the referees to insist that the abstract and Theorem 4.3 state the batch-size and epsilon conditions explicitly, and ideally that the authors release code. It is a good candidate for a revised paper.","headline":"A plausible conditional linear-rate proof for a stable coordinate-wise RMSProp variant, but the abstract's claim runs far ahead of the batch-size regime the theorem actually covers.","tokens_in":35531,"tokens_out":3447,"would_cite":false,"duration_ms":33737,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C06","90C30","68T09","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"A stable RMSProp variant is proved to converge R-linearly on linear least squares problems, with batch size controlling the final error floor in the noisy case.","keywords":["RMSProp","linear least squares","R-linear convergence","stochastic gradient","mini-batch","adaptive gradient methods","matrix Bernstein inequality"],"falsifier":"Take a small consistent least squares problem, say $d=2$ with known eigenvalues of $A^{\\top}A$, set $B$ and $\\varepsilon$ to satisfy Corollary 4.4, run SGA-RMSProp many times with the step size of Theorem 4.3, and compare the empirical mean error against $\\rho\\|x_1-x_*\\|_2\\gamma^K$ with $\\gamma$ from (4.4); a single violation at large $K$ would refute the bound. As a control, computing $u\\lambda_d(A^{\\top}A)-u\\sigma$ for $B=1$ shows the theorem is silent in that regime, so any observed linear convergence there would only show the batch-size condition is not necessary.","tokens_in":34526,"feed_emoji":"📉","tokens_out":8414,"duration_ms":67666,"temperature":0.7,"pith_summary":"The paper proposes SGA-RMSProp, a version of RMSProp that adaptively selects its discounting factor at each iteration so the per-coordinate scaling matrix varies only within a preset tolerance. It proves that on a consistent linear least squares problem the method converges R-linearly in expectation, and on an inconsistent problem it converges R-linearly to a neighborhood of the minimizer whose radius is set by the mini-batch size. This matters because RMSProp is widely used but previously had no linear-rate guarantee on least squares, while stochastic gradient descent has such guarantees. The proof gives an explicit contraction factor, an explicit step size depending on the extreme eigenvalues of $A^{\\top}A$, and a batch-size condition that makes the contraction factor smaller than one.","feed_headline":"RMSProp variant converges linearly on least squares","feed_subtitle":"Stable adaptive discounting yields R-linear convergence; batch size controls the noise floor.","key_machinery":"The load-bearing device is the stable gradient-adjusted mechanism: at each iteration $\\beta_k$ is chosen so that the moving average $u_k$ stays in a bounded interval and the scaling matrix changes slowly, $\\|D_k^{-1}D_{k-1}-I\\|_2 \\le \\varepsilon$. This lets the proof factor the product of stochastic transition matrices into controlled diagonal factors times matrices of the form $I - \\eta D_{k-1}^{1/2} M_k D_{k-1}^{1/2}$, bound the conditional expectation of each factor by $1 - 2(u\\lambda_d(A^{\\top}A)-u\\sigma)/(u(\\lambda_1(A^{\\top}A)+\\lambda_d(A^{\\top}A))) + \\varepsilon$ using the matrix Bernstein inequality, and chain the expectations through the filtration.","core_discovery":"The central claim is that with step size $\\eta = 2/(u(\\lambda_1(A^{\\top}A)+\\lambda_d(A^{\\top}A)))$ and the $\\beta$-selection rule of Algorithm 3.2, SGA-RMSProp satisfies $E[\\|x_{K+1}-x_*\\|_2] \\le \\rho \\|x_1-x_*\\|_2 \\gamma^K$ on the consistent least squares problem, where $\\gamma$ is given in (4.4) as the geometric mean of per-iteration factors times $1 - 2(u\\lambda_d(A^{\\top}A)-u\\sigma)/(u(\\lambda_1(A^{\\top}A)+\\lambda_d(A^{\\top}A))) + \\varepsilon$. On the inconsistent problem the same contraction holds up to an additive error term $R$ whose upper bound is proportional to the residual and decreases as the batch size increases (Theorem 4.7).","pith_inferences":["The proof requires exact knowledge of the extreme eigenvalues of $A^{\\top}A$; estimating them online is the natural next step, and the numerical step-size heuristics suggest the method tolerates moderate deviations.","The linear-rate theorem is silent for small batches because $u\\sigma$ can exceed $u\\lambda_d(A^{\\top}A)$, yet the experiments show the strongest early speedup at $B=50$; this gap suggests either the noise bound is loose or the true worst-case contraction is better than stated.","The mechanism of capping $\\|D_k^{-1}D_{k-1}-I\\|_2$ by $\\varepsilon$ is portable: any adaptive-gradient method that controls its preconditioner's variation could plausibly get similar linear-rate arguments on quadratic objectives.","The RMSP2SGD switching rule (five consecutive $\\beta_k = 1$) is heuristic; a criterion based on when the geometric-mean factor stops improving could make the switch principled."],"forward_implications":["On consistent least squares, SGA-RMSProp has an explicit R-linear rate whenever the batch size is large enough that the noise bound $\\sigma$ in (4.5) satisfies $u\\lambda_d(A^{\\top}A) > u\\sigma$.","On inconsistent least squares, the method converges R-linearly to a neighborhood of the minimizer whose radius is bounded by (4.25) and shrinks as the batch size grows.","The admissible range for the adjusted level is $0 < \\varepsilon < 2(u\\lambda_d(A^{\\top}A)-u\\sigma)/(u(\\lambda_1(A^{\\top}A)+\\lambda_d(A^{\\top}A)))$; within this range the linear rate holds.","Numerical experiments show SGA-RMSProp matches or beats SGD on small batches, and the proposed RMSP2SGD switch (SGA-RMSProp first, then SGD) generally reduces wall-clock time on large batches.","The analysis explains the fast initial phase of RMSProp-style methods as coming from per-iteration factors $\\gamma_k < 1$, rather than from the asymptotic constant alone."],"supporting_citations":[{"why":"Introduces the original RMSProp algorithm that SGA-RMSProp modifies with stable discounting.","marker":"[34]"},{"why":"Establishes exponential (Q-linear) convergence for randomized Kaczmarz on consistent systems, the baseline linear-rate result for stochastic linear solvers.","marker":"[33]"},{"why":"Shows SGD on linear least squares can be analyzed as randomized Kaczmarz and improves the convergence constant, the main comparison for linear rates.","marker":"[29]"},{"why":"Proves R-linear convergence of SGD to a neighborhood for strongly convex objectives, the context for the neighborhood result.","marker":"[27]"},{"why":"Supplies the matrix Bernstein inequality used to bound the noise term $E[\\|M_k - A^{\\top}A\\|_2]$.","marker":"[35]"},{"why":"Source of the mini-batch noise bounds (Lemma 4.2 style) and the residual bound in Lemma 4.6.","marker":"[5]"},{"why":"Provides the mini-batch SGD step-size heuristics used in the numerical comparisons.","marker":"[26]"},{"why":"Proves linear convergence for the closely related Adagrad-norm method, the adaptive-gradient rate to which this result is compared.","marker":"[39]"}],"fun_headline_variants":["SGA-RMSProp converges linearly on least squares","Stable RMSProp variant achieves linear convergence","Batch size controls noise floor in SGA-RMSProp","Adaptive discounting yields faster least-squares convergence","Switch to SGD after SGA-RMSProp for optimal start"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The linear-rate guarantee is conditional on the batch being large enough that the noise term $u\\sigma$ stays strictly below $u\\lambda_d(A^{\\top}A)$; for smaller batches the proof yields no rate, and the step size presumes exact knowledge of the extreme eigenvalues of $A^{\\top}A$.","fun_headline_variants_meta":{"raw":{"variants":["SGA-RMSProp converges linearly on least squares","Stable RMSProp variant achieves linear convergence","Batch size controls noise floor in SGA-RMSProp","Adaptive discounting yields faster least-squares convergence","Switch to SGD after SGA-RMSProp for optimal start"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000857,"raw_usage":{"total_tokens":3695,"prompt_tokens":891,"completion_tokens":2804,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":507,"completion_tokens_details":{"reasoning_tokens":2727}},"tokens_in":507,"tokens_out":2804,"duration_ms":18618,"temperature":1.0,"reasoning_tokens":2727,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:47:45.596003+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small consistent least squares problem, say $d=2$ with known eigenvalues of $A^{\\top}A$, set $B$ and $\\varepsilon$ to satisfy Corollary 4.4, run SGA-RMSProp many times with the step size of Theorem 4.3, and compare the empirical mean error against $\\rho\\|x_1-x_*\\|_2\\gamma^K$ with $\\gamma$ from (4.4); a single violation at large $K$ would refute the bound. As a control, computing $u\\lambda_d(A^{\\top}A)-u\\sigma$ for $B=1$ shows the theorem is silent in that regime, so any observed linear convergence there would only show the batch-size condition is not necessary.","supporting_citations":[{"cited_title":"Tieleman and G","cited_arxiv_id":null,"evidence_quote":"Introduces the original RMSProp algorithm that SGA-RMSProp modifies with stable discounting."},{"cited_title":"Needell, N","cited_arxiv_id":null,"evidence_quote":"Shows SGD on linear least squares can be analyzed as randomized Kaczmarz and improves the convergence constant, the main comparison for linear rates."},{"cited_title":"Moulines and F","cited_arxiv_id":null,"evidence_quote":"Proves R-linear convergence of SGD to a neighborhood for strongly convex objectives, the context for the neighborhood result."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the matrix Bernstein inequality used to bound the noise term $E[\\|M_k - A^{\\top}A\\|_2]$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Proves linear convergence for the closely related Adagrad-norm method, the adaptive-gradient rate to which this result is compared."}],"review_version":1}