{"id":"8d9b522c-b495-433e-952c-81a07140f527","arxiv_id":"2412.12180","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":8,"one_line_summary":"TRishBB embeds stochastic Barzilai-Borwein steplengths into the TRish trust-region rule and adds convergence guarantees for nonconvex finite-sum problems without diminishing step sizes.","lead":"The paper combines an existing stochastic trust-region scheme with automatically chosen Barzilai-Borwein step sizes derived from mini-batch gradients, producing three optimization algorithms. On standard classification datasets the new variants often match or beat the baseline TRish method on test accuracy and remain stable across parameter choices.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorems 3.2–3.4 overclaim exact convergence limits; the proofs establish only limsup upper bounds, and a constant-objective counterexample refutes the stated limits.","rationale":"The reader identified the L-smoothness mismatch with ReLU experiments, but that concern applies to the experimental validation, not to the internal correctness of the convergence theorems. The most load-bearing issue is internal: the theorem statements assert exact convergence to positive constants, while the proofs only derive one-sided upper bounds on limsup. The f≡0 counterexample with unbiased noise shows the stated limits are genuinely false, not merely unproven: the true expected gap and average squared gradient remain 0, while the claimed limits are positive. This directly undermines the central theoretical claim as summarized in the abstract and by the reader. The good news is that the proofs do establish the standard, weaker conclusion (limsup bounded by the stated constant), so the main algorithmic framework and the contraction arguments remain useful after correcting the statements. For this reason, the appropriate verdict is CONDITIONAL rather than REJECT: the theorems must be revised to limsup/upper-bound form (or the lower-bound claim must be proven), and the abstract should be updated accordingly.","tokens_in":33557,"tokens_out":21769,"duration_ms":233716,"concrete_test":"Analytically instantiate the counterexample: set f_1(x)=sin(x), f_2(x)=-sin(x), N=2, batch size 1, γ1=γ2=1, L=c=1, α=0.1, µmin=0.08, and any valid µk (e.g., µk≡0.1). The stochastic gradient is ±cos(x_k), so E||∇f-g||^2=cos^2(x_k)≤1 and ||∇f||^2=0. Compute the LHS of (32) and the corresponding average in Theorem 3.4; both are 0 for all K, contradicting the positive claimed limits. Alternatively, re-read the final steps of the proofs of Theorems 3.3 and 3.4 and verify that only an upper bound on limsup is derived, with no lower bound.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Theorems 3.2–3.4 state exact limits: Theorem 3.4 claims E[(1/K)Σ||∇f(x_k)||^2] → (16γ1^2/γ2^2 - 1)Mg and Theorem 3.3 claims E[f(x_{k+1})]-f* → 8θ3Mg/(γ2c). The proofs, however, establish only one-sided bounds. In Theorem 3.4, summing inequality (37) gives (1/K)Σ E||∇f(x_k)||^2 ≤ C + O(1/K), so limsup ≤ C; no matching lower bound is shown, so convergence to C does not follow. The same defect appears in Theorems 3.1–3.3, where an affine contraction with a positive additive term yields only that the limsup of the gap is bounded by the stated constant. This is not cosmetic. Let f_1(x)=sin(x), f_2(x)=-sin(x), N=2, and use batch size 1. Then f≡0, ∇f≡0, every point is optimal, and the unbiased estimator g_k=±cos(x_k) has variance ≤1, so Assumptions 3.1, 3.2, and 3.5 hold with c=1, L=1, Mg=1. The expected optimality gap and average squared gradient are identically 0 for every K, yet the claimed limits 8θ3/(γ2c)>0 and (16γ1^2/γ2^2-1)>0 are positive. Thus Theorems 3.3 and 3.4 as stated are false; the correct conclusion is a one-sided 'limsup ≤ constant' bound.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes TRishBB, a family of stochastic trust-region-ish methods in which the trust-region subproblem uses H_k = mu_k^{-1} I and the steplength mu_k is updated by three stochastic Barzilai-Borwein rules (Algorithms 2-4). The authors prove convergence under biased and unbiased gradient models: for PL objectives they claim convergence of the expected optimality gap to a positive constant proportional to the noise level, and for nonconvex objectives they claim convergence of the average squared gradient norm to a positive constant. The analysis requires neither diminishing step sizes nor full gradient evaluations. Numerical experiments on logistic regression and on small neural networks compare the variants with TRish, SGD-BB, and AdaQN and report accuracy improvements for TRishBB v2.","tokens_in":33943,"tokens_out":9684,"duration_ms":104324,"significance":"The framework is a reasonable and cheap extension of TRish, and the three variants are well-motivated methodologically; the experiments are extensive, include standard datasets, and show that TRishBB v2 and v3 are less sensitive to (alpha,gamma1,gamma2) than TRish and often more accurate. The convergence analysis is nontrivial in that it covers biased gradients and nonconvex objectives. However, the exact-limit theorems are stronger than the proofs support, and the analysis is not specific to the BB formulas. With the statements corrected to limsup upper bounds and the scope of the experimental claims clarified, the paper would be a useful contribution to the stochastic trust-region and spectral-step literature.","major_comments":[{"comment":"The four theorems state exact limits (Eqs. (20), (24), (32), and (37) respectively), but the proofs establish only one-sided limsup upper bounds. In Theorem 3.3, inequality (34) has the form z_{k+1} ≤ (1 − δ)z_k + C with δ = γ2αc/8 and C = αθ3Mg; iterating gives limsup_{k→∞} z_k ≤ C/δ = 8θ3Mg/(γ2c), with no matching lower bound. Similarly, Theorem 3.4 sums (37) to obtain (1/K)Σ E‖∇f(x_k)‖² ≤ (f(x0)−f*)/(Kγ2α/16) + (16γ1²/γ2² −1)Mg, which is a limsup bound, not a limit. The same structure appears in Theorems 3.1 and 3.2 via (22) and (25). This distinction is not cosmetic. Let N=2, f1(x)=sin x, f2(x)=−sin x, with batch size 1. Then f≡0, ∇f≡0, and g_k=±cos(x_k) is unbiased with variance cos²(x_k) ≤ 1, so Assumptions 3.1, 3.2, and 3.5 hold with L=1, c=1, Mg=1. For parameter choices satisfying (31) or (35) (e.g., γ1=2, γ2=1, α small, μmin≥4γ1α/5), the expected optimality gap and the average squared gradient are exactly 0, while the limits claimed in Theorems 3.3 and 3.4 are strictly positive, namely 8θ3Mg/(γ2c) > 0 and (16γ1²/γ2² −1)Mg > 0. The same construction, viewed under Assumption 3.3 with ω=1, M1=Mg, M2=1, refutes the exact-limit forms of Theorems 3.1 and 3.2. The theorems should be restated as limsup inequalities.","section":"§3, Theorems 3.1–3.4"},{"comment":"The convergence analysis does not use the Barzilai-Borwein updating formulas of Algorithms 2–4. Every displayed argument in Section 3 bounds the step using only μk ≥ μmin (or μmin ≥ 4γ1α/5) and the normalization rule (4); the secant equations defining μ_{k+1} never appear. Consequently Theorems 3.1–3.4 hold for any sequence μk with μk ∈ [μmin, μmax] (and satisfying Assumption 3.4), not specifically for stochastic BB steps. The authors should state this generality explicitly and discuss what theoretical or practical role the BB construction plays; otherwise the claimed connection between the theory and the new BB mechanisms is unsupported.","section":"§3, Lemmas 3.1–3.3"},{"comment":"The numerical experiments on MNIST and CIFAR10 use networks with ReLU activations, max pooling, and average pooling (Table C.8). The resulting empirical loss is not continuously differentiable and does not verify the L-smoothness-type inequality in Assumption 3.1, so the convergence theorems do not cover these experiments. The theoretical support in Section 3 applies directly only to the logistic-regression problems (a1a, w1a, cina). The paper should either restrict the claims made for the deep-learning experiments or provide an argument (e.g., smoothing or an extension of the analysis) that covers them; as written, the experiments are heuristic evidence beyond the proven scope.","section":"§4 and Table C.8"}],"minor_comments":[{"comment":"The input list chooses μmin together with (α,γ1,γ2), but μmax is only introduced in Algorithms 2–4; include μmax in the general algorithm statement or explain why it is not needed there.","section":"Algorithm 1, lines 1–2"},{"comment":"The quotient s_k^T s_k / (s_k^T y_k) can have zero or near-zero denominator when the objective is flat along the step; the text should state how this case is handled in practice, since thresholding with μmax does not remove a division by zero.","section":"Algorithm 2, line 6"},{"comment":"Table 2 labels the a1a panel as 'ala' and Figure 9 spells 'MNSIT' in the caption; these typos should be corrected.","section":"Table 2 and Figure 9"},{"comment":"The spectral interpretation in (6) is invoked for stochastic gradients, but it requires twice continuous differentiability on the segment, whereas Assumption 3.1 only assumes continuous differentiability and inequality (10); this additional requirement should be stated explicitly.","section":"Section 2.1"}],"recommendation":"major_revision","confidential_remarks":"The paper is within the journal's scope and the algorithmic contribution is sound in spirit. The main revision burden is to replace the exact-limit statements with limsup upper bounds and to clarify that the theory covers a generic bounded-step TRish family rather than the BB construction specifically. I would not require new algorithmic ideas, only corrected statements and a corresponding adjustment of the claims in the abstract and introduction."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper combines TRish with stochastic Barzilai-Borwein stepsizes and proves convergence bounds for biased and unbiased gradients without diminishing stepsizes. That combination is new. But Theorems 3.1–3.4 state exact limits that the proofs do not establish, and the stated limits are false. The correct conclusions are one-sided \"limsup ≤ constant\" bounds.\n\nWhat is good: the three variants are non-trivial constructions, the numerical comparison with TRish, SGD-BB, and AdaQN is extensive, and the claim that TRishBB v2 is robust across hyperparameter choices is believable. The practical value of the framework is plausible, especially for logistic regression problems.\n\nSoft spots, in order. First, the overclaimed theorems. Inequality (22), (34), and (37) are one-sided; they give limsup ≤ constant, not convergence to the constant. A simple counterexample with f = 0 (average of sin and -sin, batch size 1) satisfies Assumptions 3.1, 3.2, and 3.5, but the expected optimality gap and average squared gradient are identically zero while the stated limits are positive. This is not cosmetic, but it is fixable: restate the theorems as limsup bounds and the proofs go through. Second, the convergence analysis does not use the BB formulas at all; it applies to any step-size sequence in the TRish family. So the theoretical support for the BB-specific update is weak. Third, Assumption 3.1 requires L-smoothness, which the ReLU networks in the experiments violate; the theory covers only the logistic regression cases. Fourth, the numerical results have no error bars, and the hyperparameter sweep is wide, so the performance comparisons are suggestive rather than conclusive.\n\nVerdict: the paper deserves a serious referee, but it needs major revision. The theorems must be corrected to limsup statements, and the authors should either soften the claim that the theory covers the deep learning experiments or add a nonsmooth extension. I would not cite it in its current form, but after the theorem corrections it would be a useful reference for stochastic trust-region methods.","headline":"A useful new combination of TRish and stochastic BB stepsizes, but the main theorems overclaim: the proofs establish only limsup bounds, and the stated exact limits are false.","tokens_in":34456,"tokens_out":2603,"would_cite":false,"duration_ms":29411,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65K05","90C30"],"pacs":[],"model":"deepseek-v4-flash","headline":"A fully stochastic trust-region method with Barzilai-Borwein steplengths converges without diminishing step sizes or full-gradient passes.","keywords":["finite-sum minimization","stochastic trust-region methods","Barzilai-Borwein method","stochastic gradient methods","nonconvex optimization","Polyak-Lojasiewicz condition","machine learning"],"falsifier":"Run TRishBB v1 on $f(x)=\\tfrac12\\|x\\|^2$ with exact gradient $g_k=x_k$, taking $\\gamma_1=\\gamma_2=1$ and $\\alpha<1/8$ with $\\mu_{\\min}\\ge 4\\alpha/5$. The theorem predicts the expected average squared gradient norm converges to $(16\\gamma_1^2/\\gamma_2^2 - 1)M_g = 0$, since $M_g=0$; observing a nonzero plateau or divergence would falsify the nonconvex bound. Alternatively, add synthetic unbiased noise with known variance $M_g$ to the same quadratic and check whether the long-run average equals $(16\\gamma_1^2/\\gamma_2^2 - 1)M_g$ within Monte Carlo error.","tokens_in":33346,"feed_emoji":"📉","tokens_out":10871,"duration_ms":104725,"temperature":0.7,"pith_summary":"The paper proposes TRishBB, a class of stochastic trust-region methods for finite-sum minimization that uses stochastic Barzilai-Borwein (BB) steplengths to inject cheap second-order information. Its aim is to show that these steps can be selected by the trust-region-ish rule and still have rigorous convergence guarantees: under smoothness and bounded-variance assumptions, the expected optimality gap contracts to an explicit neighborhood of the optimum under the Polyak-Lojasiewicz condition, and the expected average squared gradient norm converges to an explicit constant for nonconvex objectives. The theorems cover both unbiased and biased stochastic gradients, and they require neither shrinking step sizes nor full gradient evaluations. The authors also give three practical variants and experiments on logistic regression and neural-network classification in which the BB-driven methods match or improve on the first-order TRish baseline and compare well with tuned stochastic quasi-Newton methods.","feed_headline":"Barzilai-Borwein steps make stochastic trust-region methods converge","feed_subtitle":"Convergence holds without shrinking step sizes or full gradient passes, with explicit noise-limited accuracy bounds.","key_machinery":"The central object is the TRishBB step: at iterate $x_k$, compute a mini-batch gradient $g_k$, set $H_k = \\mu_k^{-1}I$ with $\\mu_k$ a stochastic BB steplength, and solve the quadratic trust-region subproblem with radius $\\Delta_k$ chosen as $\\alpha\\gamma_1\\|g_k\\|$, $\\alpha$, or $\\alpha\\gamma_2\\|g_k\\|$ according to the size of $\\|g_k\\|$. The solution is either the unconstrained step $-\\mu_k g_k$ inside the radius or the normalized step $-\\Delta_k g_k/\\|g_k\\|$ on the boundary, so the cost per iteration stays first-order. The stochastic BB steplength is obtained from secant pairs $(s_k, y_k)$ built from mini-batch gradient differences, with three variants based on the current batch, on a moving average of gradients over $m$ iterations, and on an accumulated Fisher information matrix; the resulting value is clipped to $[\\mu_{\\min}, \\mu_{\\max}]$. The proof works by bounding the conditional one-step decrease of $f$ with the $L$-smooth descent inequality and the specially chosen radius rule, then summing the inequalities; the radius rule is what controls the bad event where the stochastic gradient has positive correlation with the true gradient.","core_discovery":"The central claim is that the trust-region-ish step-selection rule can carry stochastic BB steplengths and still produce provable convergence in expectation. Concretely, when $f$ is $L$-smooth and bounded below and the stochastic gradient $g_k$ is unbiased with variance bounded by $M_g$, Theorem 3.3 states that under condition (31) and the PL condition, $E[f(x_{k+1})]-f^* \\to 8\\theta_3 M_g/(\\gamma_2 c)$, with $\\theta_3 = \\gamma_1^2/\\gamma_2 - \\gamma_2/16$ and $c$ the PL constant; Theorem 3.4 states that for nonconvex $f$, under condition (35), the expected average squared gradient norm converges to $(16\\gamma_1^2/\\gamma_2^2 - 1)M_g$. The biased-gradient results, Theorems 3.1 and 3.2, give analogous limits $\\theta_2/(2c\\alpha\\theta_1)$ and $\\theta_2/(\\alpha\\theta_1)$ under correlation bounds (12)-(13) and parameter condition (18). The practical message is that the algorithm needs no hand-tuned diminishing schedule and no full gradient, and the asymptotic accuracy is limited only by the gradient noise $M_g$ and by the ratio $\\gamma_1/\\gamma_2$.","pith_inferences":["The saturation constant $(16\\gamma_1^2/\\gamma_2^2 - 1)M_g$ suggests a variance-reduction strategy that the paper does not explore: instead of shrinking the step, one can grow the mini-batch as $\\|\\nabla f\\|$ approaches the noise floor, pushing $M_g$ toward zero and improving the plateau.","If $\\gamma_1/\\gamma_2$ is chosen close to $1/4$, the predicted nonconvex plateau approaches zero even with nonzero gradient noise; testing this ratio regime on a synthetic quadratic would be a direct check of the theory's practical relevance.","The convergence theorems assume an $L$-smooth, continuously differentiable objective, but the MNIST and CIFAR10 experiments use ReLU networks that are not smooth; a natural extension is to ask whether the same limit formulas survive for nonsmooth losses or whether a smoothed surrogate is required.","The theory treats $M_g$ as a fixed bound, but in practice $M_g$ shrinks as the iterate approaches a minimizer; coupling the BB steplength with an online variance estimate could yield tighter, data-dependent convergence statements."],"forward_implications":["For finite-sum training, TRishBB removes the need to tune or shrink step sizes: the BB steplength adapts curvature information, and convergence holds with fixed algorithm parameters.","The nonconvex limit gives an explicit prediction for the stationarity plateau, $(16\\gamma_1^2/\\gamma_2^2 - 1)M_g$, so a user can trade off mini-batch size (which controls $M_g$) and the $\\gamma_1/\\gamma_2$ ratio to target a desired accuracy.","Under the PL condition, the method converges linearly to a neighborhood whose radius is proportional to $M_g/c$, so reducing gradient variance directly translates into a tighter optimality gap.","Because the algorithms never evaluate $f$, they remain applicable when objective values are expensive or unavailable, as long as mini-batch gradients are available.","The variants with accumulated BB parameters show low sensitivity to $(\\gamma_1, \\gamma_2)$ in the reported experiments, suggesting that the additional tuning burden over first-order TRish is mild."],"supporting_citations":[{"why":"Supplies the trust-region-ish radius rule and the conditional-expectation proof technique that the convergence analysis adapts.","marker":"[7]"},{"why":"The fully stochastic second-order TRish method that TRishBB specializes by taking a diagonal Hessian approximation.","marker":"[9]"},{"why":"Source of the Barzilai-Borwein secant-equation steplength that the stochastic steplengths are built from.","marker":"[1]"},{"why":"Provides the SGD-BB moving-average construction that TRishBB v2 borrows for its accumulated BB parameter.","marker":"[11]"},{"why":"Supplies the accumulated Fisher information matrix idea used in TRishBB v3 to form curvature pairs without extra gradient evaluations.","marker":"[34]"},{"why":"Justifies using the same mini-batch indices in the secant pair, preserving the spectral interpretation of the BB ratio.","marker":"[29]"}],"fun_headline_variants":["Stochastic trust-region with BB steps: no shrinking needed","Stochastic BB trust-region: convergence without step-size schedules","No diminishing steps or full gradients: stochastic BB trust-region works","Barzilai-Borwein meets stochastic trust-region: no shrinking required"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the objective is smooth and bounded below and that the stochastic gradient noise is controlled; the PL results need an additional gradient-dominance condition, and the ReLU-network experiments do not satisfy smoothness.","fun_headline_variants_meta":{"raw":{"variants":["Stochastic trust-region with BB steps: no shrinking needed","Stochastic BB trust-region: convergence without step-size schedules","No diminishing steps or full gradients: stochastic BB trust-region works","Barzilai-Borwein meets stochastic trust-region: no shrinking required"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000854,"raw_usage":{"total_tokens":3746,"prompt_tokens":1018,"completion_tokens":2728,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":634,"completion_tokens_details":{"reasoning_tokens":2661}},"tokens_in":634,"tokens_out":2728,"duration_ms":19939,"temperature":1.0,"reasoning_tokens":2661,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T16:32:36.213838+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run TRishBB v1 on $f(x)=\\tfrac12\\|x\\|^2$ with exact gradient $g_k=x_k$, taking $\\gamma_1=\\gamma_2=1$ and $\\alpha<1/8$ with $\\mu_{\\min}\\ge 4\\alpha/5$. The theorem predicts the expected average squared gradient norm converges to $(16\\gamma_1^2/\\gamma_2^2 - 1)M_g = 0$, since $M_g=0$; observing a nonzero plateau or divergence would falsify the nonconvex bound. Alternatively, add synthetic unbiased noise with known variance $M_g$ to the same quadratic and check whether the long-run average equals $(16\\gamma_1^2/\\gamma_2^2 - 1)M_g$ within Monte Carlo error.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the trust-region-ish radius rule and the conditional-expectation proof technique that the convergence analysis adapts."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The fully stochastic second-order TRish method that TRishBB specializes by taking a diagonal Hessian approximation."},{"cited_title":"Barzilai, J","cited_arxiv_id":null,"evidence_quote":"Source of the Barzilai-Borwein secant-equation steplength that the stochastic steplengths are built from."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the SGD-BB moving-average construction that TRishBB v2 borrows for its accumulated BB parameter."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the accumulated Fisher information matrix idea used in TRishBB v3 to form curvature pairs without extra gradient evaluations."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Justifies using the same mini-batch indices in the secant pair, preserving the spectral interpretation of the BB ratio."}],"review_version":1}