{"id":"892f55c6-5c1a-4809-bd42-f48756dd3a5a","arxiv_id":"1908.09345","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"SVRG and SARAH converge with a weighted averaging scheme driven by estimate sequences, and when combined with Barzilai-Borwein step sizes and an adaptive inner-loop rule they become almost tune-free in numerical tests.","lead":"This paper proposes SVRG and SARAH variants that replace hand-tuned step sizes with Barzilai-Borwein estimates and automatically adapt the inner loop length. It adds a weighted averaging scheme derived from estimate sequences, and tests the resulting almost tune-free algorithms on logistic regression benchmarks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 'almost tune-free' claim relies on θκ=κ and c=1, which violate the strict θκ>κ / m=O(κ²) conditions of Propositions 1-2; no evidence beyond three datasets supports this boundary regime.","rationale":"The reader's weakest assumption correctly identifies the gap between theory and implementation. The theorems for BB-SARAH/BB-SVRG (Propositions 1-2) require strict inequalities on θκ and m=O(κ²); the implemented choices sit exactly at the boundary and can produce m_s=O(κ). The paper's own admission in Section 4.3 is the clearest possible evidence that the central 'tune-free' claim is heuristic. This does not invalidate the theoretical contributions (ES-based analysis, new averaging), which are carefully derived under stated assumptions, nor the empirical observations on a9a, rcv1, real-sim. But those observations are limited: no error bars, no code, no stress tests. The load-bearing premise is that the boundary regime is benign across problems; a concrete stress test would settle this. If the test passes, the paper's practical claim should be upgraded; if it fails, the claim should be restricted. Since the reader already assigned CONDITIONAL, the verdict stands.","tokens_in":22253,"tokens_out":5600,"duration_ms":52839,"concrete_test":"Implement BB-SARAH exactly as in Section 5 (θκ=κ, c=1, W-Avg) and run on a synthetic strongly convex quadratic with κ=10^6, n=10^4, and on two ill-conditioned LIBSVM datasets (e.g., covtype and sido0) for 50 random seeds and 200 outer loops. Compute the per-outer-loop contraction ratio r_s = ||∇f(x̃_s)||² / ||∇f(x̃_{s-1})||². If max_s r_s > 1 for any seed, or if the algorithm does not reach ϵ=10^{-6} within the O((n+κ)ln(1/ϵ)) IFO budget, the tune-free claim is falsified. Also run the same with θκ=1.01κ to check whether the boundary choice is the cause; if the boundary case diverges while 1.01κ converges, the theoretical gap is real.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Sections 4.2-4.3 set θκ=4κ for BB-SVRG and θκ=κ for BB-SARAH, with c=1 in (9). Proposition 2 requires θκ>κ (strict) and m=O(κ²) to ensure λ_s<1; Proposition 1 requires θκ>4κ. At the chosen boundary, and with η_s up to its upper bound 1/(θκ μ), (9) gives m_s = θκ = O(κ), not O(κ²). The paper itself states (Sec. 4.3): 'the selection of these parameters violates slightly the theoretical guarantee... no divergence has been observed.' This is an anecdotal empirical premise: three datasets, no error bars, no released code. The central claim -- that no tuning is needed -- depends entirely on this boundary parameter regime being robust across problems, including ill-conditioned or heterogeneous ones where BB step sizes can be large early on. If the empirical contraction λ_s exceeds 1 in that regime, the algorithm may diverge or stall, and the 'tune-free' contribution is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies SVRG and SARAH for strongly convex finite-sum minimization and proposes weighted averaging (W-Avg) derived from an estimate-sequence analysis. Theorem 1 and Corollary 1 give SVRG with W-Avg linear convergence and O((n+κ)ln(1/ε)) IFO complexity under Assumptions 1-3; Theorem 2 and Corollary 2 give an analogous result for SARAH with W-Avg, measured in E[||∇f(x̃_s)||²], under Assumptions 1 and 4. The paper then analyzes Barzilai-Borwein step sizes for SVRG and SARAH with fixed inner-loop length m=O(κ²) (Propositions 1-2), and proposes an adaptive inner-loop rule m_s=c/(μη_s) with c=1 and θ_κ=4κ (SVRG) or θ_κ=κ (SARAH), marketed as 'almost tune-free.' Numerical experiments on three LIBSVM datasets compare the resulting methods with tuned SVRG and SARAH.","tokens_in":22532,"tokens_out":13579,"duration_ms":133658,"significance":"The estimate-sequence machinery is a real methodological contribution: it extends ES analysis to SARAH's biased gradient estimator and yields provably tighter theoretical rates for W-Avg, and the fixed-m BB variants come with complete proofs. The paper also makes a credible empirical case that averaging is more than a proof trick. However, the headline 'almost tune-free' claim is not established by the theorems: the implemented boundary parameters (θ_κ=4κ or κ, c=1) lie outside the regime covered by Propositions 1-2, and the only support for that regime is three datasets and an anecdotal 'no divergence has been observed' statement. The appendix proofs are organized and appear internally consistent; the central gap is between the proved propositions and the implemented algorithm. If the boundary regime can be proven or convincingly validated across a much broader range of conditioning and random seeds, the contribution would be significant.","major_comments":[{"comment":"The implemented 'tune-free' parameters are outside the proven regime. Since η_s ≤ 1/(θ_κ μ) by Eq. (8), the adaptive rule m_s = c/(μη_s) with c=1 gives m_s = θ_κ = O(κ) at the upper end of the step-size range, whereas Propositions 1 and 2 require m=O(κ²) and strict inequalities θ_κ>4κ (SVRG) or θ_κ>κ (SARAH). At the boundary the contraction bounds fail: for BB-SARAH with θ_κ=κ, m_s=κ and η_s=1/(κμ), the U-Avg rate in the proof of Proposition 2 equals 1/(μη_s m_s)+η_s L/(2−η_s L)=1+1=2, so λ_s>1; for BB-SVRG with θ_κ=4κ and m_s=4κ, the W-Avg bound in the proof of Proposition 1 contains the term 2κ/θ_κ/(1−2κ/θ_κ)=1, hence λ_s≥1. The paper's own caveat in Sec. 4.3 ('the selection of these parameters violates slightly the theoretical guarantee... no divergence has been observed') understates this gap: the violation is not a small constant but an order-of-magnitude difference in m. The central practical claim therefore currently rests on an unproven empirical premise. I ask the authors to either extend the analysis to cover θ_κ=κ, 4κ with m_s=θ_κ (e.g., a sharpened W-Avg contraction with m=O(κ)), or restructure the claim and support it with systematic experiments across conditioning regimes.","section":"4.3, Eq. (9), Propositions 1-2"},{"comment":"The empirical validation of the boundary regime is too thin for the generality of the 'almost tune-free' claim. The experiments use three datasets, all with the same regularized logistic loss, no reported values of L or κ, no error bars or repeated-seed statistics, and no released code. Because Sec. 4.3 explicitly replaces a proof with 'no divergence has been observed,' the revision should report κ for each dataset, include a large-κ example (e.g., κ²≫n, a regime where the paper itself predicts BB slowdown in Sec. 4.2), average over multiple random seeds and starting points, and specify the exact BB implementation including any safeguards for the denominator in Eq. (7). Without this, the claim that the parameter choices are robust across problems is not supported.","section":"5, Table 1"}],"minor_comments":[{"comment":"'L-Lipchitz' should be 'L-Lipschitz'; the same typo appears in the Introduction.","section":"Assumption 1 and Introduction"},{"comment":"In the proof of Lemma 2, 'Hession' should be 'Hessian.'","section":"Appendix A.1"},{"comment":"The last sentence of the proof says 'λSVRG≤0.75' but the quantity analyzed is λSARAH.","section":"Corollary 2 proof"},{"comment":"The legend of Figure 5(b) appears to list 'SVRG' twice; it should include 'BB-SVRG.'","section":"Figure 5"},{"comment":"The paper should clarify what 'almost tune-free' means regarding problem constants: Eq. (9) requires μ, and θ_κ=κ requires L/μ, but no procedure for estimating or obtaining these constants is discussed; Table 1 reports only μ.","section":"4.3, Eq. (9)"},{"comment":"The bibliographic entry for Liu et al. lacks a year; please complete the reference.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The core ES-based analysis is sound and publishable in principle, but the present version overclaims by calling the boundary-parameter implementation 'almost tune-free' when the proofs only cover a different regime. I would encourage the editor to allow a major revision focused on closing or honestly re-scoping this gap: either prove contraction at θ_κ=κ/4κ with m_s=θ_κ, or change the presentation so that the theorem-backed results and the heuristic implementation are clearly separated. The companion technical note [Li and Giannakis, 2019] should be made available to reviewers if its results are used to support extensions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The real contribution here is the estimate-sequence analysis and the W-Avg weighting scheme it produces. Extending estimate sequences to SARAH's biased gradient estimate is a genuine step that had been missing, and the paper proves linear convergence for both SVRG and SARAH with W-Avg at the standard O((n+κ) ln 1/ε) complexity. The proofs in the appendix are detailed and internally coherent. I also give the authors credit for explicitly flagging the gap between their proven BB guarantees and the parameter choices they actually implement. That honesty is earned, and it lets the reader see exactly what is and is not covered.\n\nWhere the paper is soft is precisely at that flagged gap. The 'almost tune-free' claim depends on θκ = κ for SARAH, θκ = 4κ for SVRG, and c = 1, which violate the strict conditions θκ > κ (or > 4κ) and m = O(κ²) in Propositions 1 and 2. The paper's own sentence — 'the selection of these parameters violates slightly the theoretical guarantee... no divergence has been observed' — is an admission that the central practical claim is supported by empirical observation, not by the stated theory. That would be fine if the empirical evidence were strong, but there are only three datasets, no error bars, and no released code. On top of that, the SARAH W-Avg rate requires Assumption 4 (each component strongly convex), which is stronger than the usual Assumption 3; the paper says this can be relaxed to Assumption 3 at the price of O((n+κ²)) complexity, but the main corollary is under the stronger assumption.\n\nNone of this is fatal. The theoretical contributions stand on their own: the W-Avg distribution is new, the analysis is sound, and the paper's message that averaging should be adapted to the step size and inner loop length is well supported by the analytical rates and the experiments (modulo the thin empirical evidence). The 'almost tune-free' claim is overstated, but it is an overstatement the authors themselves partly disclose.\n\nThis paper is for researchers working on variance reduction who care about practical deployment as well as theory. It deserves a serious referee: the core ideas are worth engaging with, and the gap between theory and practice is addressable. A referee should ask for either a proof covering the boundary regime (perhaps under slightly weaker conditions) or a much more thorough empirical validation with more datasets, error bars, and released code. I would recommend sending it to peer review with that request rather than desk rejecting it.","headline":"Solid theoretical core with a genuinely new averaging scheme, but the 'almost tune-free' claim rests on boundary parameter choices that violate the paper's own theorems and are supported only by three datasets without error bars or code.","tokens_in":23012,"tokens_out":1354,"would_cite":true,"duration_ms":15082,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C06","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that SVRG and SARAH can be made almost tune-free using Barzilai-Borwein step sizes, weighted averaging, and an inner-loop length $m_s = c/(\\mu\\eta_s)$, with proven linear convergence.","keywords":["variance reduction","SVRG","SARAH","Barzilai-Borwein step size","weighted averaging","estimate sequence","tune-free optimization","strongly convex finite-sum optimization"],"falsifier":"Run BB-SARAH with $\\theta_\\kappa=\\kappa$, $c=1$, and W-Avg on a strongly convex smooth finite-sum problem, tracking $\\mathbb{E}[\\|\\nabla f(\\tilde{x}_s)\\|^2]$ as $\\eta_s$ ranges through its allowed interval $[1/(\\theta_\\kappa L), 1/(\\theta_\\kappa \\mu)]$; any divergence, or measured IFO complexity worse than $O((n+\\kappa^2)\\ln(1/\\epsilon))$, would falsify the almost tune-free claim.","tokens_in":22089,"feed_emoji":"🧮","tokens_out":9560,"duration_ms":84379,"temperature":0.7,"pith_summary":"The paper sets out to eliminate the grid search that normally accompanies the variance-reduction optimizers SVRG and SARAH: users must tune both the step size and the length of the inner loop. It argues that three ingredients together achieve this: Barzilai-Borwein (BB) step sizes, which are computed from the previous two outer iterates; a new weighted averaging rule (W-Avg) for choosing the next outer iterate; and an inner-loop length $m_s = c/(\\mu\\eta_s)$ tied inversely to the current BB step size. The theory proves linear convergence for SVRG with W-Avg at $O((n+\\kappa)\\ln(1/\\epsilon))$ IFO complexity, and for SARAH with W-Avg in squared-gradient norm at the same order when each $f_i$ is strongly convex. If correct, the practical payoff is that a user can set two boundary constants ($\\theta_\\kappa = \\kappa$ or $4\\kappa$, $c = 1$) and match or beat tuned SVRG and SARAH on several datasets.","feed_headline":"Three tweaks make SVRG and SARAH almost tune-free","feed_subtitle":"Barzilai-Borwein step sizes, weighted averaging, and $m=c/(\\mu\\eta)$ keep linear convergence without grid search.","key_machinery":"The load-bearing object is the estimate sequence, a chain of quadratic surrogate functions $\\Phi_k(x)$ built inside each inner loop from the algorithm's gradient estimates. Starting from $\\Phi_0(x)=\\Phi_0^*+(\\mu_0/2)\\|x-x_0\\|^2$, each step defines $\\Phi_k$ recursively from $\\Phi_{k-1}$ and the current estimate $v_{k-1}$, with $\\delta_k=\\mu_k\\eta$; this sequence supplies both the weighted-averaging probabilities and the contraction factors $\\lambda_{\\mathrm{SVRG}}$ and $\\lambda_{\\mathrm{SARAH}}$. Around it, three components work together: the Barzilai-Borwein step size $\\eta_s$ computed from the two previous outer iterates, which removes step-size tuning; the W-Avg rule, which favors early inner-loop iterates whose gradient estimates carry less noise; and the rule $m_s = c/(\\mu\\eta_s)$, which keeps the product of step size and inner-loop length in the theoretically favorable regime.","core_discovery":"On its own terms, the paper's discovery is that averaging choices inside a double-loop variance-reduction method are performance-critical, and that the right averaging can be read off an estimate-sequence construction. For SVRG, weights $p_s^k = (1-\\mu\\eta)^{m-k-1}/q$ for $k=1,\\dots,m-1$ yield a contraction factor $\\lambda_{\\mathrm{SVRG}}$ that improves on uniform averaging, giving linear convergence with $O((n+\\kappa)\\ln(1/\\epsilon))$ IFO complexity. For SARAH, whose gradient estimate is biased, weights $p_s^k$ proportional to $1-(1-\\mu\\eta)^{m-k-1}$ for $k=0,\\dots,m-2$ yield linear convergence in $\\mathbb{E}[\\|\\nabla f(\\tilde{x}_s)\\|^2]$ under Assumptions 1 and 4. The estimate-sequence machinery is then combined with BB step sizes and the adaptive inner-loop length $m_s=c/(\\mu\\eta_s)$ to produce almost tune-free BB-SVRG and BB-SARAH, with the BB variants proven at $O((n+\\kappa^2)\\ln(1/\\epsilon))$ IFO calls.","pith_inferences":["An implicit consequence of $m_s=c/(\\mu\\eta_s)$ is that the product $\\mu\\eta_s m_s$ is constant, so the per-outer-loop contraction factor is kept away from the unstable regime across the whole range of BB step sizes; the paper hints at this but does not state it as a theorem.","The W-Avg weights have a natural early-ending interpretation: they down-weight late inner iterates whose gradient estimates carry the most variance, which suggests the same adjustment might improve other variance-reduction schemes (e.g., SAGA or loopless SVRG) whenever step sizes are large.","A direct test of the almost-tune-free claim would be to run BB-SARAH with $\\theta_\\kappa=\\kappa$ and $c=1$ on a strongly convex smooth finite-sum problem and record whether divergence ever occurs when $\\eta_s$ is near its smallest value $1/(\\theta_\\kappa L)$; the paper's experiments report no divergence but do not cover all worst-case regimes.","The estimate-sequence proof for biased gradient estimators could be reused to produce averaging rules for other recursive estimators, such as SPIDER or SNVRG, whose bias terms have a similar telescoping structure."],"forward_implications":["SVRG with W-Avg converges linearly in objective value at $O((n+\\kappa)\\ln(1/\\epsilon))$ IFO complexity, matching the order of tuned SVRG without requiring a searched step size.","SARAH with W-Avg converges linearly in $\\mathbb{E}[\\|\\nabla f(\\tilde{x}_s)\\|^2]$ at $O((n+\\kappa)\\ln(1/\\epsilon))$ IFO complexity under smooth strongly convex finite-sum assumptions, extending estimate-sequence analysis to biased gradient estimates.","BB-SVRG and BB-SARAH with $m=O(\\kappa^2)$ and $\\theta_\\kappa=4\\kappa$ or $\\kappa$ have $O((n+\\kappa^2)\\ln(1/\\epsilon))$ complexity, so when $\\kappa^2$ is no larger than $n$, the automatic step size costs almost nothing in theory.","Averaging matters empirically: W-Avg beats L-Avg and U-Avg when the step size or inner-loop length is large, while small step sizes favor L-Avg, so parameter choice should be coordinated across step size, inner-loop length, and averaging.","With the fixed boundary constants $\\theta_\\kappa=4\\kappa$ (SVRG), $\\theta_\\kappa=\\kappa$ (SARAH), and $c=1$, the proposed schemes match or outperform tuned SVRG and SARAH on the datasets tested (a9a, rcv1, real-sim)."],"supporting_citations":[{"why":"Introduces SVRG with uniform averaging and the mean-square-error bound used as Lemma 1, which the W-Avg analysis tightens.","marker":"[Johnson and Zhang, 2013]"},{"why":"Introduces SARAH, its biased gradient estimate, and the contraction of $\\mathbb{E}[\\|v_k\\|^2]$ used in the SARAH W-Avg proof.","marker":"[Nguyen et al., 2017]"},{"why":"Supplies the Barzilai-Borwein step-size scheme for SVRG whose pessimistic inner-loop length the paper shortens.","marker":"[Tan et al., 2016]"},{"why":"Provides the two-point step-size formula that defines $\\eta_s$.","marker":"[Barzilai and Borwein, 1988]"},{"why":"Establishes the L-Avg SARAH convergence results under Assumptions 1-3 and 1+4 that W-Avg is compared against.","marker":"[Li et al., 2020]"},{"why":"Provides the estimate-sequence framework for variance-reduced optimization that the paper adapts to per-inner-loop sequences and to biased estimates.","marker":"[Kulunchakov and Mairal, 2019]"},{"why":"Origin of estimate sequences and the strong-convexity and smoothness inequalities used throughout the proof.","marker":"[Nesterov, 2004]"}],"fun_headline_variants":["BB steps plus averaging: SVRG/SARAH almost tune-free","Almost tune-free SVRG/SARAH via BB and adaptive inner loop","Say goodbye to grid search: SVRG/SARAH get BB and averaging","SVRG/SARAH: almost tune-free with Barzilai-Borwein steps"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The practical claim rests on the empirical premise that the boundary constants $\\theta_\\kappa=4\\kappa$ (SVRG), $\\theta_\\kappa=\\kappa$ (SARAH), and $c=1$ with $m_s=c/(\\mu\\eta_s)$ keep the algorithm convergent even though these choices fall outside the strict conditions of the theorems (which require $\\theta_\\kappa>4\\kappa$ or $\\theta_\\kappa>\\kappa$ and $m=O(\\kappa^2)$); the paper's only support for this premise is that no divergence showed up in its experiments. If that empirical premise fails, the almost tune-free claim collapses.","fun_headline_variants_meta":{"raw":{"variants":["BB steps plus averaging: SVRG/SARAH almost tune-free","Almost tune-free SVRG/SARAH via BB and adaptive inner loop","Say goodbye to grid search: SVRG/SARAH get BB and averaging","SVRG/SARAH: almost tune-free with Barzilai-Borwein steps"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000333,"raw_usage":{"total_tokens":1860,"prompt_tokens":966,"completion_tokens":894,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":582,"completion_tokens_details":{"reasoning_tokens":807}},"tokens_in":582,"tokens_out":894,"duration_ms":8404,"temperature":1.0,"reasoning_tokens":807,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:14:44.706973+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run BB-SARAH with $\\theta_\\kappa=\\kappa$, $c=1$, and W-Avg on a strongly convex smooth finite-sum problem, tracking $\\mathbb{E}[\\|\\nabla f(\\tilde{x}_s)\\|^2]$ as $\\eta_s$ ranges through its allowed interval $[1/(\\theta_\\kappa L), 1/(\\theta_\\kappa \\mu)]$; any divergence, or measured IFO complexity worse than $O((n+\\kappa^2)\\ln(1/\\epsilon))$, would falsify the almost tune-free claim.","supporting_citations":[{"cited_title":"Proof of Theorem","cited_arxiv_id":null,"evidence_quote":"Introduces SARAH, its biased gradient estimate, and the contraction of $\\mathbb{E}[\\|v_k\\|^2]$ used in the SARAH W-Avg proof."}],"review_version":1}