{"id":"5de9f16b-5600-4b88-8994-bd5963ffe867","arxiv_id":"2508.20645","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"TV-HSGT couples hybrid variance-reduced stochastic gradients with AB gradient tracking to obtain a dynamic regret bound over time-varying directed networks without assuming bounded gradients.","lead":"This paper proposes TV-HSGT, a distributed online algorithm that combines hybrid stochastic variance reduction with gradient tracking over time-varying directed networks. It reports a dynamic regret bound without a bounded-gradient assumption and shows improved logistic regression performance on A9A and MNIST.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"M(α) uses m11 = µn instead of µnη, so the entrywise inequality M_t(α) ≤ M(α) fails at position (3,3), and the spectral-radius step in Theorem 1 is not established as written.","rationale":"The reader's verdict is CONDITIONAL, and my analysis agrees that the proof has a critical gap. The reader's stated weakest assumption was the existence of uniform bounds in (22), especially η > 0; however, those bounds do follow from Assumptions 4–6 via Lemmas 5 and 6, which give [ϕ_t]_i ≥ a^n/n and [π_t]_i ≥ b^n/n, so η ≥ a^n b^n / n > 0. The more serious and less repairable-as-written issue is the incorrect m11 constant in (38): using m11 = µn instead of µnη reverses the needed inequality at entry (3,3), so M(α) does not dominate M_t(α) entrywise and the spectral radius argument collapses. This is a concrete algebraic error in the central proof, distinct from the uniform-bound concern but also likely fixable. Other issues (the sign error in Corollary 1's geometric-series limit, the discrepancy between b2 and β²σ²b'_2 in the theorem statement, and the unsupported sublinear claim in Remark 1) are secondary and do not change the overall assessment. The paper's algorithmic idea and high-level proof strategy are plausible, so a CONDITIONAL verdict remains appropriate; the authors should correct m11 and rerun the step-size condition before the theorem can be accepted.","tokens_in":26046,"tokens_out":6182,"duration_ms":54187,"concrete_test":"Analytically verify the entrywise bound M_t(α) ≤ M(α) with a concrete instance: let n = 2, µ = 1, α = 0.01, and choose row-stochastic A_t and column-stochastic B_t (e.g., uniform weights with self-loops) such that ϕ_t^T π_t = 0.5. From (36) and (38), M_t(3,3) = 1 − 0.01·2·0.5 = 0.99, whereas M(3,3) = 1 − 0.01·2 = 0.98, so the claimed inequality fails. Then recompute the spectral-radius bounds (39)–(46) with the corrected m11 = µnη, where η is the uniform lower bound from Lemmas 5–6; check whether a positive α still satisfies all bounds for a small example. If yes, the theorem is likely repairable; if no, a different contraction argument is needed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing flaw is the construction of the uniform bound matrix M(α) in Proposition 1. The time-varying matrix M_t(α) has entry (3,3) = 1 − α m11_t with m11_t = µn ϕ_t^T π_t (eq. 36). To apply the spectral-radius argument, the paper replaces m11_t by the constant m11 = µn (eq. 38), without the uniform lower bound η. Since ϕ_t^T π_t ≤ 1 and typically η < 1, m11 > m11_t, which makes 1 − α µn < 1 − α µn ϕ_t^T π_t. Therefore M(α)'s (3,3) entry is strictly smaller than M_t(α)'s entry, so the claimed entrywise inequality M_t(α) ≤ M(α) is false. The subsequent derivation of step-size condition (46) and the conclusion ρ(M(α)) < 1 do not imply contraction of M_t(α). This directly undermines Theorem 1's regret bound. The error is repairable: one should set m11 = µnη, using the positive lower bound η ≤ ϕ_t^T π_t, which does follow from Lemmas 5 and 6 together with Assumptions 5 and 6. Until that correction is made, the central theorem is unproven as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes TV-HSGT, a distributed online stochastic optimization algorithm for time-varying directed networks. The algorithm combines an AB (row-stochastic/column-stochastic) communication scheme, gradient tracking, and a hybrid variance-reduction update for stochastic gradients. The main theoretical claim is a dynamic regret bound, stated in Theorem 1, that does not assume uniformly bounded gradients. The paper also gives a static-optimization corollary and reports numerical experiments on A9A and MNIST logistic regression tasks, comparing against DSGD, DSGT, and DSGT-HB.","tokens_in":26319,"tokens_out":11450,"duration_ms":109867,"significance":"If the main theorem is correct, this would be a useful contribution: it targets a genuinely harder setting than most prior work, combining time-varying directed graphs, stochastic gradients, variance reduction, and no bounded-gradient assumption. The proof framework—constructing a coupled four-component error recursion and then applying a spectral-radius argument—is reasonable and builds on established contraction lemmas. The paper also makes good use of existing AB/Push-Pull tools rather than inventing ad hoc assumptions. However, several concrete proof errors currently block the central claim, so the contribution is not yet established as written.","major_comments":[{"comment":"The entrywise bound M_t(α) ≤ M(α) is false at position (3,3). In M_t(α), the (3,3) entry is 1 − α m11_t with m11_t = µn φ_t^T π_t, while M(α) in Eq. (38) sets m11 = µn. Since φ_t^T π_t ≤ 1 and α > 0, we have 1 − αµn ≤ 1 − αµn φ_t^T π_t, so M(α)'s (3,3) entry is smaller than M_t(α)'s entry, not larger. For an upper-bounding matrix, m11 must be a uniform lower bound on µn φ_t^T π_t, i.e., m11 = µnη. Such an η does follow from Lemmas 5 and 6 together with Assumptions 5 and 6. Until this is corrected, the conclusion ρ(M(α)) < 1 does not imply contraction of the time-varying recursion, and Theorem 1 is unproven as written.","section":"§4.2, Proposition 1 and Eq. (38)"},{"comment":"The step-size condition in (46) does not ensure that Lemma 11 applies at every time. Lemma 11 requires 0 < α < 2/(n(µ + L_g) φ_t^T π_t) for each t. Since η defined in (22) is a lower bound on φ_t^T π_t, the threshold 2/(n(µ + L_g)η) is larger than the individual thresholds, and the smallest threshold over t occurs at the largest value of φ_t^T π_t, not at the lower bound η. Thus α satisfying α < 2/(n(µ + L_g)η) can violate the per-step condition from Lemma 11. A sufficient uniform condition would be α < 2/(n(µ + L_g)), using φ_t^T π_t ≤ 1, or alternatively an upper bound on max_t φ_t^T π_t.","section":"Theorem 1, condition (46)"},{"comment":"The driving-noise term in the final regret bound is inconsistent with the recursion established in Proposition 1. Proposition 1 defines b2 = [0, 6nτ²ψ/(1−τ)β²σ², 0, 2nβ²σ²]^T, while Theorem 1 states the bound in terms of b'_2 = [0, 6nτ²ψ/(1−τ), 0, n]^T and the proof concludes with b2 = β²σ² b'_2. The fourth component of β²σ² b'_2 is nβ²σ², not 2nβ²σ². Either Proposition 1's b2 should be corrected to have nβ²σ² in the fourth component, or b'_2's fourth component should be 2n. Without this, the stated O(β²σ²T‖b'_2‖) term does not follow from (30).","section":"Theorem 1 statement and final lines of proof"},{"comment":"The geometric-series argument in the proof of Corollary 1 has a sign error. The displayed derivation gives lim sup_{t→∞} V_t ≤ −(I−M(α))^{-1} b. Since b ≥ 0 and M(α) has spectral radius less than 1, the matrix (I−M(α))^{-1} = Σ_{k≥0} M(α)^k is nonnegative with nonnegative entries, so (I−M(α))^{-1} b is nonnegative. A negative upper bound on the nonnegative vector V_t is impossible. The correct limiting bound is lim sup_{t→∞} V_t ≤ (I−M(α))^{-1} b. This error directly affects the stated static-case result.","section":"Appendix I, proof of Corollary 1"}],"minor_comments":[{"comment":"TV-HSGT is tested on time-varying directed graphs, while the baselines DSGD, DSGT, and DSGT-HB are run on fixed complete graphs with symmetric doubly stochastic weights. This confounds the algorithmic comparison with the topology difference; the authors should either run the baselines under the same AB time-varying directed scheme or clearly discuss this limitation.","section":"§5, experimental setup"},{"comment":"There are numerous typographical and formatting issues, including missing spaces in equations such as 'minT t=1', the caption 'or different algorithms' in Figs. 7 and 10, and inconsistent notation between z_t and z_{t+1} in the algorithm description. A careful proofread is needed.","section":"Throughout"},{"comment":"The comparison in Table 1 lists only doubly stochastic or row-stochastic predecessors; the text would benefit from explicitly discussing how the claimed 'no Perron vector estimation' property differs from the Push-Sum based methods when the network is time-varying directed.","section":"§1, Table 1"},{"comment":"The uniform bounds c, τ, ψ, κ, φ in Eq. (22) are introduced by assertion. For a fixed finite agent set, Assumptions 4–6 do imply uniform bounds, but the authors should state this explicitly and point to the finiteness of the set of admissible graphs, since the proof depends on these bounds in a load-bearing way.","section":"§4.2, Eq. (22)"}],"recommendation":"major_revision","confidential_remarks":"The paper fits the journal's scope and the algorithmic idea is plausibly valuable. The proof issues listed in the major comments are local and repairable—particularly the m11 = µnη correction and the sign fix in Corollary 1—so I do not recommend rejection. However, Theorem 1 as currently written is not proven, and the experiment section should be strengthened by matching the baselines' network settings before the paper can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The algorithm is a sensible and genuinely new combination: hybrid variance reduction grafted onto the AB/Push-Pull gradient-tracking scheme, applied to online strongly convex optimization over time-varying directed graphs, with no bounded-gradient assumption. If the theory held up, this would be a solid contribution to the decentralized online learning subfield. The paper is also honest about what it borrows, and the comparisons in Table 1 look accurate.\n\nThe problem is the proof as written. The central step is Proposition 1's claim that the time-varying matrix M_t(α) is upper-bounded entrywise by a constant matrix M(α). That fails at position (3,3). The time-varying entry is 1 − α µn φ_tᵀπ_t, while M(α) uses 1 − α µn. Since φ_tᵀπ_t ≤ 1, the actual entry is larger than the proposed bound, so the entrywise inequality goes the wrong way. The spectral-radius argument in Theorem 1 therefore does not go through as written. The fix is straightforward — set m11 = µnη using the positive lower bound η on φ_tᵀπ_t — but until that correction is made, the main regret bound is unproven.\n\nThere are smaller issues too. Corollary 1 concludes lim sup V_t ≤ −(I−M(α))⁻¹b with nonnegative b, which cannot bound a nonnegative error vector; the geometric sum sign is simply wrong. Theorem 1 writes b2 = β²σ²b'_2, but the earlier definition of b2 has a 2n factor while b'_2 has n; that is a minor inconsistency, but needs cleanup. Remark 1's sublinear-regret claim is unsupported: it requires time-varying step size and mixing parameter, while the analysis only covers constant ones. And the experiments compare TV-HSGT on time-varying directed graphs against baselines on a fixed complete graph, which is not an apples-to-apples comparison; it weakens the empirical claims but doesn't affect the theory.\n\nNone of this looks like a fundamentally broken idea. The lemmas build a coherent error decomposition, and every flaw I found appears repairable without changing the algorithm. But the current manuscript's headline theorem is not established.\n\nWho should read this? Researchers working on decentralized online optimization or distributed variance reduction. It deserves a serious referee — send it out — and the right outcome is major revision, not desk reject. I would not cite the current version, but I would keep an eye on a revised one.","headline":"A promising but unproven synthesis: hybrid variance reduction plus AB gradient tracking for time-varying directed networks, with a repairable but load-bearing gap in the main theorem's proof.","tokens_in":26850,"tokens_out":3313,"would_cite":false,"duration_ms":30820,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W15","90C25","90C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that a hybrid variance-reduced gradient-tracking algorithm, TV-HSGT, achieves a dynamic regret bound over time-varying directed networks without assuming uniformly bounded gradients.","keywords":["distributed online optimization","dynamic regret","gradient tracking","variance reduction","time-varying directed networks","row-column stochastic matrices","hybrid stochastic gradients","strong convexity"],"falsifier":"Construct a sequence of strongly connected directed graphs whose smallest positive edge weight decays to zero while preserving the row-stochastic and column-stochastic conditions, and compute the product $\\phi_t^\\top \\pi_t$ from the recursions; if this product tends to zero, the uniform lower bound $\\eta$ in (22) does not exist and the step-size condition (46) forces $\\alpha \\to 0$, so the claimed bound cannot hold with a fixed step size. Separately, one can verify algebraically at the (3,3) entry whether the constant matrix $M(\\alpha)$ actually dominates the time-varying $M_t(\\alpha)$ entrywise; since $m_{11,t}=\\mu n \\phi_t^\\top \\pi_t \\le \\mu n = m_{11}$, the (3,3) entry of $M_t(\\alpha)-M(\\alpha)$ is nonnegative whenever $\\phi_t^\\top \\pi_t<1$, so the dominance claim requires checking the other entries.","tokens_in":25819,"feed_emoji":"🕸️","tokens_out":13398,"duration_ms":103715,"temperature":0.7,"pith_summary":"This paper introduces TV-HSGT, a distributed online optimization algorithm for agents connected by time-varying directed networks, and proves a dynamic regret bound for it in a stochastic strongly convex setting. The central claim is that combining a hybrid stochastic-gradient estimator (a convex mixture of the current stochastic gradient and a stochastic recursive gradient) with a gradient-tracking variable lets each agent track the global descent direction without the usual uniformly-bounded-gradient assumption. The proof bounds four coupled error terms through a single linear inequality, then chooses the step size so that the constant bounding matrix has spectral radius below one. If correct, this gives the first dynamic regret bound for a hybrid variance-reduced gradient-tracking method over time-varying directed topologies, and it indicates that unbounded gradients need not preclude sublinear dynamic regret.","feed_headline":"Regret bound without bounded gradients on changing directed networks","feed_subtitle":"The bound holds even when gradients are unbounded and the network is directed.","key_machinery":"The central object is the coupled error vector $V_t = [\\mathbb{E}\\|x_t-\\hat{x}_t\\|^2_{\\phi_t},\\ \\mathbb{E}S^2(y_t,\\pi_t),\\ \\mathbb{E}\\|\\hat{x}_t-x_t^*\\|^2,\\ \\mathbb{E}\\|z_t-\\nabla F_t(x_t)\\|^2]^\\top$, stacking consensus error, gradient-tracking error, optimality error, and hybrid gradient-estimation error. The argument drives this vector through a time-invariant linear inequality $V_{t+1}\\le M(\\alpha)V_t + b_{1,t}+b_2$, where $M(\\alpha)$ is constructed from uniform bounds on the network-dependent quantities (a positive lower bound $\\eta$ on $\\phi_t^\\top\\pi_t$, contraction constants $c,\\tau$, and bounds $\\psi,\\kappa,\\varphi$). The hybrid estimator $z_{i,t+1}=(1-\\beta)(z_{i,t}-\\nabla\\hat{f}_{i,t+1}(x_{i,t},\\xi_{i,t+1}))+\\nabla\\hat{f}_{i,t+1}(x_{i,t+1},\\xi_{i,t+1})$ damps the stochastic noise term, while the row-stochastic $A_t$ and column-stochastic $B_t$ updates form the AB communication scheme that avoids Perron-vector estimation.","core_discovery":"On the paper's own terms, the discovery is that this setting admits the dynamic regret bound $R_d^T \\le O(\\|V_0\\| + \\sum_{t=0}^{T-1}\\|b_{1,t}\\| + \\beta^2\\sigma^2 T \\|b'_2\\|)$, where $V_0$ collects the initial consensus, tracking, optimality, and gradient-estimation errors, $b_{1,t}$ accumulates the temporal drift of the objective gradients and minimizers (through $q_t$ and $p_t$), and the $\\beta^2\\sigma^2$ term is the residual stochastic noise the hybrid estimator damps. The analysis avoids the pervasive bounded-gradient assumption using only Lipschitz stochastic gradients, bounded variance, and strong convexity. The bound follows by showing the four error components contract jointly: the step-size condition (46) makes the spectral radius of the time-invariant matrix $M(\\alpha)$ smaller than one, and the per-step disturbances are summed as a geometric series.","pith_inferences":["The same four-error coupled contraction could likely be replayed with other variance-reduction estimators (e.g., SVRG-style periodic snapshots), since the proof only needs the estimator drift controlled by $\\|x_{t+1}-x_t\\|^2$ as in Lemma 16; the hybrid mixture is sufficient, not necessary.","The explicit $\\beta^2\\sigma^2$ floor in the bound suggests a concrete tuning rule: decay $\\beta$ in step with the drift measures $q_t$ and $p_t$ (or with $1/\\sqrt{T}$) to convert the variance term into a sublinear contribution; the paper states the general condition but does not give a schedule.","If the uniform $\\eta$-floor fails on sparse or large-scale networks, one could adapt the proof to per-agent or per-step step sizes, treating the time-varying $M_t(\\alpha)$ rather than a single $M(\\alpha)$; the current analysis points to that generalization but does not carry it out."],"forward_implications":["In the static case $f_t = f$, Corollary 1 yields a linearly convergent gradient-tracking algorithm with variance reduction, whose steady-state error can be made arbitrarily small by reducing $\\beta$.","Under sublinear decay of the temporal variations $q_t$ and $p_t$, with a decaying step size and mixing parameter, the dynamic regret becomes sublinear in $T$.","The algorithm requires no Perron-vector estimation or out-degree information; agents use only local rows and columns of the weight matrices, making it implementable under local information.","The step-size range (46) is explicit and computable from the uniform bounds, giving a concrete tuning rule for contraction.","The hybrid estimator reduces the stochastic-gradient variance floor from $\\sigma^2$ to $\\beta^2\\sigma^2$ in the regret bound, directly quantifying the benefit of the variance-reduction mechanism."],"supporting_citations":[{"why":"Supplies the hybrid variance-reduction estimator (9) and its variance-reduction guarantees, the core mechanism that damps stochastic noise.","marker":"[50]"},{"why":"Provides the optimal hybrid variance-reduced method for stochastic composite optimization that motivates the estimator's two-gradient combination.","marker":"[27]"},{"why":"Yields Lemmas 5 and 7: the existence of the stochastic weight sequence $\\phi_t$ and the row-stochastic contraction used for consensus error.","marker":"[36]"},{"why":"Yields Lemmas 6 and 8: the lower bounds on $\\pi_t$ and the column-stochastic contraction used for gradient-tracking error.","marker":"[32]"},{"why":"The gradient-tracking method over time-varying directed networks that Corollary 1 extends with hybrid variance reduction.","marker":"[1]"},{"why":"The GTAdam baseline that already removes the bounded-gradient assumption; the paper contrasts its dynamic-regret analysis with this line.","marker":"[4]"},{"why":"Supplies the spectral-radius criterion ($M(\\alpha)\\delta<\\delta$ implies $\\rho(M(\\alpha))<1$) that turns the linear inequality system into a contraction.","marker":"[13]"}],"fun_headline_variants":["Hybrid tracking tames unbounded gradients","Distributed online optimization without gradient bounds","TV-HSGT cuts variance on shifting digraphs","Unbounded gradients? Hybrid tracking still converges","Dynamic regret bound for time-varying networks"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof rests on assuming the network's time-varying weight structure, through the overlap $\\phi_t^\\top \\pi_t$ and the per-step contraction constants, admits fixed uniform bounds that hold at every time step; if edge weights can decay without a positive floor, the contraction step-size condition (46) has no positive solution and the regret bound collapses.","fun_headline_variants_meta":{"raw":{"variants":["Hybrid tracking tames unbounded gradients","Distributed online optimization without gradient bounds","TV-HSGT cuts variance on shifting digraphs","Unbounded gradients? Hybrid tracking still converges","Dynamic regret bound for time-varying networks"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00025,"raw_usage":{"total_tokens":1530,"prompt_tokens":897,"completion_tokens":633,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":513,"completion_tokens_details":{"reasoning_tokens":565}},"tokens_in":513,"tokens_out":633,"duration_ms":5454,"temperature":1.0,"reasoning_tokens":565,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:43:21.496228+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a sequence of strongly connected directed graphs whose smallest positive edge weight decays to zero while preserving the row-stochastic and column-stochastic conditions, and compute the product $\\phi_t^\\top \\pi_t$ from the recursions; if this product tends to zero, the uniform lower bound $\\eta$ in (22) does not exist and the step-size condition (46) forces $\\alpha \\to 0$, so the claimed bound cannot hold with a fixed step size. Separately, one can verify algebraically at the (3,3) entry whether the constant matrix $M(\\alpha)$ actually dominates the time-varying $M_t(\\alpha)$ entrywise; since $m_{11,t}=\\mu n \\phi_t^\\top \\pi_t \\le \\mu n = m_{11}$, the (3,3) entry of $M_t(\\alpha)-M(\\alpha)$ is nonnegative whenever $\\phi_t^\\top \\pi_t<1$, so the dominance claim requires checking the other entries.","supporting_citations":[{"cited_title":"A hybrid variance- reduced method for decentralized stochastic non-convex opti- mization","cited_arxiv_id":null,"evidence_quote":"Supplies the hybrid variance-reduction estimator (9) and its variance-reduction guarantees, the core mechanism that damps stochastic noise."},{"cited_title":"Distributed Nash equilibrium seeking over time-varying directed communication networks","cited_arxiv_id":null,"evidence_quote":"Yields Lemmas 5 and 7: the existence of the stochastic weight sequence $\\phi_t$ and the row-stochastic contraction used for consensus error."},{"cited_title":"AB/Push-Pull method for distributed optimization in time-varying directed networks","cited_arxiv_id":null,"evidence_quote":"Yields Lemmas 6 and 8: the lower bounds on $\\pi_t$ and the column-stochastic contraction used for gradient-tracking error."},{"cited_title":"Distributed stochastic optimization with gradient track- ing over time- varying directed networks","cited_arxiv_id":null,"evidence_quote":"The gradient-tracking method over time-varying directed networks that Corollary 1 extends with hybrid variance reduction."},{"cited_title":"Gtadam: Gradient tracking with adap- tive momentum for distributed online optimization.IEEE Trans- actions on Control of Network Systems , 10(3):1436–1448, 2022","cited_arxiv_id":null,"evidence_quote":"The GTAdam baseline that already removes the bounded-gradient assumption; the paper contrasts its dynamic-regret analysis with this line."},{"cited_title":"Matrix analysis","cited_arxiv_id":null,"evidence_quote":"Supplies the spectral-radius criterion ($M(\\alpha)\\delta<\\delta$ implies $\\rho(M(\\alpha))<1$) that turns the linear inequality system into a contraction."}],"review_version":2}