{"id":"f81ee514-1843-4d3d-9d3e-faa0ef5958a4","arxiv_id":"2504.13046","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"A new class of accelerated forward-backward and backward-forward splitting methods with variance-reduced estimators achieves O(1/k^2) and o(1/k^2) expected residual convergence for generalized equations under co-coercivity and co-hypomonotonicity.","lead":"This paper develops two new variance-reduced accelerated splitting methods for solving generalized equations, covering minimax problems and variational inequalities, including nonmonotone cases. They achieve O(1/k^2) and o(1/k^2) expected residual rates, almost sure convergence, and oracle complexities matching the best-known bounds for common estimators.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Expectation-setting o(1/k^2)/a.s. rates require B∞<∞; the fixed mega-batch schedules in Corollaries 22–24 make B∞ diverge, so those rates are not established by the stated parameter choices.","rationale":"The reader's weakest-assumption pick, co-coercivity of F, is explicit and honestly discussed in Sections 2.2 and 6.2; it restricts applicability but does not by itself break the stated theorems. The more load-bearing internal issue is the compatibility of the infinite-horizon rates with the expectation-setting parameter schedules. The strongest claims in the abstract and conclusions — o(1/k^2) in expectation and a.s. convergence in both finite-sum and expectation settings — depend on condition (39), which is not verified for the fixed-batch schedules in Corollaries 22–24 and is in fact violated there because p_k stays bounded below and n_k is fixed. Remark 15's growing mega-batch fix, when combined with the constant reset probabilities used in the corollaries, destroys the claimed oracle complexity. This does not invalidate the finite-sum results or the conditional Theorem 13 when B∞ holds, but it means the paper's expectation-setting rate claims need an additional nontrivial parameter analysis to be substantiated. The reader did note that the expectation-setting O(1/k^2) rate requires growing mega-batches, so there is partial agreement, but the reader did not identify the divergence of B∞ under Corollaries 22–24 as the load-bearing issue. A conditional accept remains appropriate, with the condition that the expectation-setting o(1/k^2)/a.s. claims be either restricted to schedules satisfying (39) with their true oracle cost stated, or proved with a schedule that simultaneously achieves the claimed ε-complexity.","tokens_in":67924,"tokens_out":9303,"duration_ms":90873,"concrete_test":"Independently recompute condition (39) for the Corollary 23 L-SARAH expectation schedule: with t_k = μ(k+r), p_k = ε + 2μ/(μ(k+r−1)−1), b_k = ⌊c_b/ε⌋, and n_k = ⌊c_n/ε^3⌋, verify that the summand t_{k-1}(t_{k-1}−1) σ_k^2/Θ_k is ≥ c0 k^2 σ^2 ε^2/n and hence Σ_k = ∞. Then run VFOSA+ with this schedule on a 1-D stochastic linear GE, F(x,ξ) = a(ξ)x with bounded a(ξ) and Var(a)>0, T=0, and measure k^2 E||G_λ x^k||^2 over k up to several ε^{-1}; if the quantity plateaus at a positive level instead of decreasing to 0, the o(1/k^2) claim for this schedule is refuted.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Theorems 13 and 14, which give the o(1/k^2) expected rate, the a.s. o(1/k^2) rate, and the a.s. iterate convergence, are all conditioned on Eq. (39): B∞ := (Λ/β) Σ_{k=0}^∞ t_{k-1}(t_{k-1}−1) σ_k^2/Θ_k < ∞. For the finite-sum variants with full-batch snapshot, σ_k = 0 and B∞ = 0, so Corollary 21 is safe. For the expectation setting, however, the concrete schedules in Corollaries 22–24 use fixed mega-batch sizes n_k = n ≍ ε^{-3} and reset/SARAH probabilities that are bounded below by a positive ε-dependent constant (e.g., Corollary 22 has p_k = 2ε + 4μ/(μ(k+r−1)−1) ≥ 2ε; Corollary 23 has p_k ≥ ε; HSGD in Corollary 24 has τ_k → 1−√(1−ε) ≈ ε/2). With these choices, σ_k^2/Θ_k is bounded below by a positive constant times p_k^2/n or p_k/n, so the summand in (39) is ≥ c k^2 and B∞ = +∞. Hence Theorems 13–14 do not apply to the expectation-setting algorithm as implemented in Section 4.5. Remark 15 acknowledges that SVRG/SARAH need increasing mega-batches n_k = O(k^{3+ω}) for B∞ < ∞, but with the constant p_k used in Corollaries 22–24 the expected mega-batch oracle cost becomes Ω(Σ k^{3+ω}) = Ω(ε^{-(4+ω)}) for target ε = 1/K, far worse than the claimed Õ(ε^{-3}) or O(ε^{-3}) complexity. The finite-horizon O(1/k^2) bound in Theorem 12 with B_K growing is not affected, but the infinite-horizon o(1/k^2)/a.s. claims for the expectation setting are not supported by the stated parameter choices, and no alternative schedule achieving both (39) and the claimed ε-complexity is supplied.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops two variance-reduced accelerated operator-splitting frameworks, VFOSA+ (forward-backward) and VFOSA- (backward-forward), for solving generalized equations 0 in Fx + Tx under average/expectation co-coercivity of F and maximal rho-co-hypomonotonicity of T. It introduces a unified class of variance-reduced estimators (Definition 4) that covers SVRG, SAGA, SARAH, and Hybrid-SGD, and proves O(1/k^2) and o(1/k^2) rates on the expected squared FBS residual, almost sure o(1/k^2) rates, and almost sure convergence of iterates. The paper also derives oracle complexity bounds in the finite-sum and expectation settings and reports numerical experiments on robust logistic regression, a robust minimax problem, and a Policeman-vs-Burglar game.","tokens_in":68457,"tokens_out":7406,"duration_ms":79249,"significance":"If the stated results hold, this is a substantial contribution: it provides a unified single-loop accelerated splitting framework with variance reduction for a class of generalized equations that includes nonmonotone co-hypomonotone operators, and it matches the best-known oracle complexity bounds in several settings. The Lyapunov analysis in the appendix is detailed and internally structured, and the estimator class in Definition 4 is broad enough to be of independent interest. The numerical experiments are extensive and compare favorably with recent methods. The main weakness is that the infinite-horizon o(1/k^2)/almost-sure claims in the expectation setting are conditioned on B_infinity < infinity, while the concrete parameter schedules given for the expectation-setting variants do not satisfy that condition and no alternative schedule achieving both the condition and the claimed O(epsilon^{-3}) complexity is supplied.","major_comments":[{"comment":"The expectation-setting variants as implemented in Corollaries 22-24 do not satisfy the condition (39) required by Theorems 13 and 14. With t_k = mu(k+r), Eq. (39) requires B_infinity = (Lambda/beta) sum_k t_{k-1}(t_{k-1}-1) sigma_k^2/Theta_k < infinity. In Corollary 22 (L-SVRG) one has p_k >= 2epsilon, b_k = b = Theta(epsilon^{-2}), n_k = n = Theta(epsilon^{-3}), and by Lemma 5 sigma_k^2 = p_k sigma^2/n and Theta_k = 4/(b_k p_k). Hence sigma_k^2/Theta_k = b_k p_k^2 sigma^2/(4n), which is bounded below by a positive constant times epsilon^3 for large k, so the summand is at least c k^2 epsilon^3 and B_infinity diverges. Corollary 23 (L-SARAH) gives the same divergence with sigma_k^2/Theta_k of order epsilon^4, and Corollary 24 (HSGD) uses fixed batches with tau_k -> 1 - sqrt(1-epsilon), which again makes B_infinity infinite. Therefore Theorems 13 and 14, both of which are explicitly conditioned on (39), do not apply to the expectation-setting algorithms under the stated parameter choices. The finite-horizon bound in Theorem 12 and the O(epsilon^{-3}) complexity statements derived from it are not affected, but the o(1/k^2) expected rates, the almost sure o(1/k^2) rates, and the almost sure iterate convergence in the expectation setting are not established by the provided schedules.","section":"Section 4.5, Eq. (39), Corollaries 22-24"},{"comment":"The manuscript does not provide any expectation-setting parameter schedule for which both (39) holds and the claimed O(epsilon^{-3}) oracle complexity is achieved. Remark 15 suggests increasing mega-batch sizes n_k = O(k^{3+omega}) for SVRG and SARAH, but under the constant reset probabilities p_k >= c epsilon used in Corollaries 22-23 the expected mega-batch oracle cost becomes Omega(sum_k k^{3+omega}) = Omega(epsilon^{-(4+omega)}), which is far worse than the claimed O(epsilon^{-3}). The HSGD schedule in Corollary 24 similarly keeps fixed batch sizes and a reset weight tau_k of order epsilon, so B_infinity diverges. Since Corollary 21 establishes B_infinity = 0 only for the finite-sum setting, the expectation-setting entries in Table 1 and the corresponding abstract claims overstate what is proven. The authors should either provide a schedule satisfying (39) with the claimed complexity, or explicitly restrict the o(1/k^2) and almost-sure claims in the expectation setting.","section":"Section 4.5, Remark 15, and Table 1"},{"comment":"The backward-forward splitting results inherit the same gap. Theorem 25's bound (47) and Theorems 26-27 all depend on the same B_K / B_infinity quantity from Theorem 12, and the proof of Theorem 25 explicitly reduces to the VFOSA+ analysis. Since no expectation-setting schedule satisfying (39) is supplied for the concrete estimators, the advertised o(1/k^2) and almost-sure convergence properties of VFOSA- in the expectation setting rest on the same unsupported condition. The finite-horizon complexity statements for VFOSA- are not in question, but the infinite-horizon claims should be corrected or supplemented with a valid schedule.","section":"Section 5, Theorems 25-27"}],"minor_comments":[{"comment":"The sentence discussing preservation of the finite-sum/expectation structure appears to refer to G_lambda in Eq. (6) and S_lambda in Eq. (8), but the text says \"G_lambda in (8)\". This should be corrected for consistency.","section":"Section 2.3(c), near Eq. (8)"},{"comment":"The phrase \"setting tau = 0 in (14)\" is formally problematic because Eq. (14) contains the coefficient (1+tau)/tau. The full-batch case should be obtained as the limit tau -> 0 or by a separate argument, not by direct substitution.","section":"Appendix B.1, proof of Lemma 5"},{"comment":"There are several typographical errors, e.g., \"Subections\" in the heading of Section D, \"Appendicies\" in the proof of Corollary 22, and \"these methods were though derived\" in Section 4.1(c). These should be corrected in a revision.","section":"Throughout the appendix and Section 4.5"},{"comment":"The Policeman-vs-Burglar experiment adds a 10^{-8} regularizer to make the skew-symmetric operator average co-coercive. This changes the problem, and the limitation should be acknowledged more explicitly, especially because Section 2.2(a) suggests reformulations as an alternative route.","section":"Section 6.2"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this is a substantial paper and the core of it holds up. The one thing to know before citing the expectation-setting results is that the o(1/k^2) and almost-sure claims require B∞ < ∞ (condition (39)), and the fixed mega-batch schedules in Corollaries 22–24 do not deliver it. The finite-horizon O(1/k^2) rates and the ε-complexity claims are not affected.\n\nWhat is actually new: Definition 4 is a clean general estimator class that covers SVRG, SAGA, SARAH, and Hybrid-SGD under a single variance-reduction property, and VFOSA+/VFOSA− are the first frameworks I know of that combine biased variance-reduced estimators with Nesterov-type acceleration and co-hypomonotone T (which need not be monotone). The Lyapunov analysis in Section 4 is the real contribution; Lemma 3's strong co-coercivity of the FBS residual is the load-bearing piece, and the appendix proofs are internally coherent and self-contained. The finite-sum results are genuinely clean: with full-batch snapshots σ_k = 0, so B∞ = 0 and the o(1/k^2), summability, a.s., and iterate-convergence results all go through via Corollary 21. The numerics are honest—real datasets, several baselines, a SCAD-regularized nonmonotone instance, and the Policeman-Burglar example with the regularizer built into the model.\n\nSoft spots, in proportion. The main one is the expectation setting. The stress-test note is correct: with fixed n_k = Θ(ε−3) and p_k bounded below by a positive ε-dependent constant (p_k ≥ 2ε in Corollary 22), σ_k^2/Θ_k ~ p_k^2/n stays bounded below by a positive constant, so the summand in (39) grows like k^2 and B∞ = +∞. Theorems 13–14 therefore do not apply to the algorithms as instantiated in Section 4.5, and the abstract's blanket o(1/k^2)/a.s. claim overstates what is proven. Remark 15 acknowledges that growing mega-batches n_k = O(k^{3+ω}) are needed for B∞ < ∞, but with constant p_k the expected oracle cost becomes Ω(ε−(4+ω)), well off the claimed Θ(ε−3). This is fixable—restrict the infinite-horizon claims to the finite-sum setting, or accept the larger complexity—but it should be stated precisely. Minor items: the \"best-known\" complexity wording holds only up to the log factors the paper itself discloses in a footnote, and Assumption 1.2 excludes skew-symmetric operators (bilinear games), which Section 6.2 papers over with an ε = 10−8 regularizer. Both are acknowledged to the author's credit.\n\nBottom line: for anyone working on variance-reduced operator splitting or nonmonotone inclusions, this paper deserves a serious referee. I'd send it out; the revision should reconcile (39) with the Section 4.5 parameter choices and align the abstract with what is proven.","headline":"Genuine framework paper with solid finite-sum theory; the expectation-setting o(1/k^2) and a.s. claims overreach because the stated mega-batch schedules make condition (39) fail.","tokens_in":68991,"tokens_out":7823,"would_cite":true,"duration_ms":67207,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","47H05","65K10","90C33"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that variance-reduced Nesterov acceleration, applied through forward-backward and backward-forward splitting, drives the squared FBS residual of a generalized equation to zero at $o(1/k^2)$ in expectation and almost…","keywords":["generalized equations","operator splitting","variance reduction","Nesterov acceleration","co-hypomonotonicity","forward-backward splitting","backward-forward splitting","finite-sum optimization"],"falsifier":"Run VFOSA+ on a monotone but not co-coercive instance, for example $Fx = [L^{\\top}v; -Lu]$ with $T$ the normal cone of simplexes and no regularizer, and monitor $\\mathbb{E}[\\|G_\\lambda x^k\\|^2]$. If the residual still decays like $o(1/k^2)$, then Assumption 1.2 is not necessary; if it stalls at a positive floor, co-coercivity is doing the work. More directly, numerically evaluate inequality (10) for such an $F$ and check whether the claimed constants $\\bar\\beta$ and $\\Lambda$ make the right-hand side meaningful; if the inequality fails, the Lyapunov descent behind Theorems 12–14 collapses.","tokens_in":67721,"feed_emoji":"⚡","tokens_out":8031,"duration_ms":76211,"temperature":0.7,"pith_summary":"The paper develops two single-loop, accelerated operator-splitting algorithms for generalized equations—inclusions of the form $0 \\in F x + T x$ that cover composite minimization, minimax problems, variational inequalities, and fixed-point problems. It claims that, when $F$ is co-coercive and $T$ is maximally $\\rho$-co-hypomonotone with $L\\rho<1$, the expected squared norm of the forward-backward splitting residual $G_\\lambda x^k$ decreases as $O(1/k^2)$ and actually as $o(1/k^2)$, with almost sure convergence of the iterates to a solution. The framework also accommodates both unbiased and biased variance-reduced estimators—SVRG, SAGA, SARAH, and Hybrid-SGD—and derives oracle complexity bounds that match the best known for such estimators. If correct, this gives accelerated, variance-reduced splitting methods for a broader class of problems, including some nonmonotone saddle-point models, in a single-loop algorithm without restarts or catalyst steps.","feed_headline":"Operator splitting hits 1/k^2 residual decay for generalized equations","feed_subtitle":"Variance-reduced acceleration drives residuals to zero at 1/k^2, even for some nonmonotone inclusions.","key_machinery":"The load-bearing object is the forward-backward splitting residual $G_\\lambda x := \\lambda^{-1}(x - J_{\\lambda T}(x-\\lambda F x))$, which turns the inclusion $0\\in F x + T x$ into the equation $G_\\lambda x=0$. Lemma 3 shows that when $F$ is $1/L$-co-coercive and $T$ is maximally $\\rho$-co-hypomonotone with $L\\rho<1$, $G_\\lambda$ is strongly co-coercive in the sense of (10), with explicit constants $\\bar\\beta$ and $\\Lambda$. That inequality feeds a Lyapunov function $P_k$ that combines the residual norm, a cross term between the residual and the anchoring variable, and the variance-reduced estimator error $\\Delta_k$, whose recursion is captured by the estimator class of Definition 4. The same machinery is repeated for the backward-forward residual $S_\\lambda$.","core_discovery":"On its own terms, the central discovery is a rate: under Assumptions 1.1 and 1.2 with $L\\rho<1$, the variance-reduced fast forward-backward splitting method (VFOSA+) produces iterates whose FBS residual satisfies $\\mathbb{E}[\\|G_\\lambda x^k\\|^2] \\le 2(\\Psi_0^2+E_0^2+B_\\infty)/(\\mu^2(k+r-1)^2)$, together with $o(1/k^2)$ rates in expectation and almost surely, and almost sure convergence of $(x^k,z^k)$ to a zero of $\\Phi=F+T$. The paper proves the same statements for a backward-forward variant (VFOSA$^-$) with respect to the BFS residual. It also specifies the algorithm for four concrete estimators and shows the finite-sum oracle complexities $\\tilde O(n+n^{2/3}\\epsilon^{-1})$ for SVRG/SAGA and $\\tilde O(n+n^{1/2}\\epsilon^{-1})$ for SARAH, and $O(\\epsilon^{-3})$ in the expectation setting, matching the best-known bounds without added acceleration tricks.","pith_inferences":["A natural testable extension is to replace co-coercivity by plain Lipschitz monotonicity; the current proof would break at Lemma 3, and the paper's own Policeman-vs-Burglar experiment adds a small regularizer precisely because the skew-symmetric operator is not co-coercive.","The remark that local co-hypomonotonicity may suffice suggests the rates could hold when co-hypomonotonicity holds only near solutions; verifying this would widen the reach to nonconvex minimax models beyond the examples tested.","Because the estimator class of Definition 4 is defined by a two-line variance recursion, other estimators such as SAG, SEGA, or JacSketch could plausibly be plugged in and inherit the same rates, though the paper only proves the bounds for four estimators.","The residual metric $\\mathbb{E}\\|G_\\lambda x^k\\|^2$ doubles as a stopping criterion; if future work extends the methods to extragradient updates, the same Lyapunov template might weaken the co-coercivity assumption."],"forward_implications":["The SVRG and SAGA variants need $\\tilde O(n + n^{2/3}\\epsilon^{-1})$ evaluations of $F_i$ and resolvents to reach $\\mathbb{E}[\\|G_\\lambda x^K\\|^2]\\le \\epsilon^2$, while the SARAH variant needs $\\tilde O(n+n^{1/2}\\epsilon^{-1})$; the expectation-setting variants need $O(\\epsilon^{-3})$.","The same single-loop algorithm converges almost surely, with iterates landing on a solution of the generalized equation rather than only on a stationary point of some merit function.","Because $T$ is only required to be co-hypomonotone, the result covers nonmonotone operators; the experiments include a robust logistic regression model with a nonconvex SCAD regularizer, where $T$ is locally co-hypomonotone.","The backward-forward variant gives the same rates and complexity, which is useful when the solver wants to preserve the finite-sum structure of $F$ after composition with the resolvent.","For convex composite minimization, VFOSA+ reduces to a new accelerated proximal-gradient-type scheme whose residual is evaluated at $x^k$ rather than at the extrapolated point $y^k$."],"supporting_citations":[{"why":"Supplies the monotone-operator toolkit—co-coercivity, resolvents, and convergence lemmas—used throughout the analysis.","marker":"Bauschke and Combettes (2017)"},{"why":"Establishes the $(\\lambda-\\rho)$-co-coercivity of the Moreau–Yosida approximation that is the first step of Lemma 3.","marker":"Attouch et al. (2018)"},{"why":"Provides the SAGA-type variance-reduction template for root-finding and Proposition 4.1, used for almost sure convergence of iterates.","marker":"Davis (2022)"},{"why":"Defines the SVRG estimator, one of the four instantiations of the paper's estimator class.","marker":"Johnson and Zhang (2013)"},{"why":"Defines the SAGA estimator used in the finite-sum variant with the $\\tilde O(n+n^{2/3}\\epsilon^{-1})$ complexity bound.","marker":"Defazio et al. (2014)"},{"why":"Defines the SARAH estimator, whose biased recursion gives the improved $\\tilde O(n+n^{1/2}\\epsilon^{-1})$ bound.","marker":"Nguyen et al. (2017)"},{"why":"Introduces the Hybrid-SGD estimator, whose expectation-setting variant yields the $O(\\epsilon^{-3})$ bound.","marker":"Tran-Dinh et al. (2022)"},{"why":"The variance-reduced Halpern method whose oracle complexity and parameter choices are compared against and matched in the finite-sum setting.","marker":"Cai et al. (2024)"},{"why":"The supermartingale convergence theorem used to convert summability bounds into almost sure convergence.","marker":"Robbins and Siegmund (1971)"}],"fun_headline_variants":["Variance-reduced splitting: 1/k^2 residual decay for nonmonotone inclusions","Fast operator splitting hits 1/k^2 via variance reduction","Accelerated splitting methods reach 1/k^2 rates","1/k^2 residual decay from variance-reduced operator splitting","Splitting with variance reduction: 1/k^2 convergence for generalized equations"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The smooth part $F$ must be co-coercive on average or in expectation (Assumption 1.2), not merely monotone and Lipschitz, so skew-symmetric linear maps such as bilinear games violate the assumption unless one adds a small regularizer.","fun_headline_variants_meta":{"raw":{"variants":["Variance-reduced splitting: 1/k^2 residual decay for nonmonotone inclusions","Fast operator splitting hits 1/k^2 via variance reduction","Accelerated splitting methods reach 1/k^2 rates","1/k^2 residual decay from variance-reduced operator splitting","Splitting with variance reduction: 1/k^2 convergence for generalized equations"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000334,"raw_usage":{"total_tokens":1933,"prompt_tokens":1101,"completion_tokens":832,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":717,"completion_tokens_details":{"reasoning_tokens":735}},"tokens_in":717,"tokens_out":832,"duration_ms":7766,"temperature":1.0,"reasoning_tokens":735,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T12:17:32.343670+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run VFOSA+ on a monotone but not co-coercive instance, for example $Fx = [L^{\\top}v; -Lu]$ with $T$ the normal cone of simplexes and no regularizer, and monitor $\\mathbb{E}[\\|G_\\lambda x^k\\|^2]$. If the residual still decays like $o(1/k^2)$, then Assumption 1.2 is not necessary; if it stalls at a positive floor, co-coercivity is doing the work. More directly, numerically evaluate inequality (10) for such an $F$ and check whether the claimed constants $\\bar\\beta$ and $\\Lambda$ make the right-hand side meaningful; if the inequality fails, the Lyapunov descent behind Theorems 12–14 collapses.","supporting_citations":[],"review_version":1}