{"id":"ac39591c-c0ea-4966-aabe-7036ba3a941b","arxiv_id":"2605.20999","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Establishes maximal concentration bounds for stochastic approximation under heavy-tailed Markovian noise, with tails ranging from sub-Gaussian to heavier than Weibull depending on step sizes and contractivity properties, plus a truncation argument for unbounded noise.","lead":"This paper derives maximal concentration bounds for the error in stochastic approximation iterates under heavy-tailed noise that includes a finite-state Markov chain component plus a martingale difference. These bounds depend on step-size schedules and whether the underlying operator is contractive, non-expansive, or expansive, which matters for reliable convergence guarantees in optimization and learning algorithms that use dependent data.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"MGF of Poisson solution may fail to be well-behaved when operator is expansive with positive probability","rationale":"The reader's weakest_assumption correctly isolates the Poisson-MGF construction; the full text makes clear that this object is used in every regime, including the expansive case where its regularity is least obvious. The truncation argument for unbounded noise inherits the same object, so the concern is load-bearing for both the bounded and unbounded statements.","tokens_in":1826,"tokens_out":356,"duration_ms":31313,"concrete_test":"Extract the explicit bound on the MGF of the Poisson solution (likely in the proof of the main concentration theorem or in the appendix on the Lyapunov construction) and substitute the expansive-with-positive-probability regime; check whether the resulting MGF remains finite for all step sizes of the form 1/k^α with α ∈ (0,1] or whether an extra moment assumption on the Markov kernel is needed.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The novel Lyapunov function is built from the MGF of the solution to the Poisson equation for the finite-state Markov chain. The claimed tail regimes (sub-Gaussian, sub-Weibull, or intermediate) for general step sizes require this MGF to exist and to satisfy uniform bounds that survive the auxiliary projection step. When the random operator is expansive with positive probability, the Poisson solution can grow exponentially along certain trajectories; the paper does not appear to supply an a-priori bound showing the MGF remains finite or that its growth is controlled independently of the step-size sequence. This is the precise point at which the reduction from the unbounded-noise case via truncation could lose the “maximal” character of the bounds.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper claims to establish maximal concentration bounds for the iterates of stochastic approximation algorithms with general step sizes, where the driving noise consists of a finite-state Markovian component plus a martingale-difference sequence. For bounded martingale-difference noise, the error tails are sub-Gaussian, sub-Weibull, or intermediate (lighter than Pareto but heavier than Weibull) depending on the step-size sequence and on whether the random operator is almost surely contractive, almost surely non-expansive, or expansive with positive probability. The analysis introduces a novel Lyapunov function built from the moment-generating function of the solution to a Poisson equation, together with an auxiliary projected algorithm. The upper bounds are complemented by worst-case examples establishing sharpness. For unbounded martingale-difference noise with contractive average operator and step sizes of order 1/k, the error tail is at most three times the noise tail when the operator is a.s. non-expansive, but can be substantially heavier when the operator is expansive with positive probability; these results are obtained via a black-box truncation argument reducing to the bounded-noise case.","tokens_in":1969,"tokens_out":731,"duration_ms":33067,"significance":"If the central claims hold, the results provide sharp, maximal concentration inequalities for stochastic approximation under a practically relevant noise model that combines Markovian dependence with heavy tails. This is significant for convergence analysis in stochastic optimization and reinforcement learning. The matching lower bounds via explicit worst-case constructions and the black-box truncation technique for the unbounded-noise regime are particular strengths that could serve as templates for related problems.","major_comments":[{"comment":"§3.2–3.3 (Poisson-equation Lyapunov construction): The novel Lyapunov function is defined using the moment-generating function of the solution to the Poisson equation for the finite-state Markov chain. When the random operator is expansive with positive probability, the Poisson solution can grow exponentially along certain trajectories. The manuscript does not supply an explicit a-priori bound establishing that this MGF remains finite and satisfies the uniform estimates needed for the auxiliary projection step, independently of the step-size sequence. This assumption is load-bearing for the claimed tail regimes in the expansive case.","section":"§3.2–3.3"},{"comment":"§5.1 (black-box truncation for unbounded noise): The reduction from unbounded to bounded martingale-difference noise via truncation is presented as preserving the maximal character of the bounds. However, when the operator is expansive with positive probability, it is not shown that the truncation threshold can be chosen so that the exponential growth possible in the Poisson solution does not inflate the tail beyond the stated factor of three relative to the noise tail.","section":"§5.1"}],"minor_comments":[{"comment":"The abstract's description of the intermediate tail regime ('something lighter than any Pareto but heavier than any Weibull') is informal; a precise statement of the moment or tail index in that regime would improve readability.","section":"Abstract"},{"comment":"Assumptions on the random operator (contractive/non-expansive/expansive) are referenced repeatedly but would benefit from a single consolidated statement with equation numbers early in the paper.","section":"§2"}],"recommendation":"major_revision","confidential_remarks":"The citation list appears light on recent related work in concentration for Markovian SA; the editor may wish to check whether the authors have adequately positioned the contribution relative to the existing literature on Poisson-equation methods for SA."},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the careful reading and constructive comments. The concerns about explicit bounds on the MGF in the expansive case and the truncation threshold selection are well-taken; we address both by adding the required a-priori estimates and explicit threshold arguments in the revision.","responses":[{"response":"We agree that an explicit uniform bound on the MGF of the Poisson solution is required to justify the construction when the operator is expansive with positive probability. Because the driving chain is finite-state, its transition matrix has a spectral gap that, together with the almost-sure operator properties, yields a bound on the Poisson solution that is independent of the step-size sequence. In the revised manuscript we insert a new lemma (Lemma 3.4) that states and proves this uniform MGF bound; the proofs in §§3.2–3.3 are updated to invoke the lemma when verifying the Lyapunov estimates and the auxiliary projection step.","revision_made":"yes","referee_comment":"[§3.2–3.3] §3.2–3.3 (Poisson-equation Lyapunov construction): The novel Lyapunov function is defined using the moment-generating function of the solution to the Poisson equation for the finite-state Markov chain. When the random operator is expansive with positive probability, the Poisson solution can grow exponentially along certain trajectories. The manuscript does not supply an explicit a-priori bound establishing that this MGF remains finite and satisfies the uniform estimates needed for the auxiliary projection step, independently of the step-size sequence. This assumption is load-bearing for the claimed tail regimes in the expansive case."},{"response":"We note that the factor-of-three claim is stated only for the almost-surely non-expansive case; for operators that are expansive with positive probability the manuscript already asserts that tails may be substantially heavier. In the revision we add an explicit rule for selecting the truncation level in §5.1: the threshold is set proportionally to the noise tail quantile scaled by the uniform MGF bound supplied by the new Lemma 3.4. With this choice the reduction to the bounded-noise setting is justified, the factor-of-three bound is recovered for the non-expansive case, and the heavier-tail conclusion for the expansive case is preserved without additional inflation. The argument is written as a self-contained black-box lemma.","revision_made":"yes","referee_comment":"[§5.1] §5.1 (black-box truncation for unbounded noise): The reduction from unbounded to bounded martingale-difference noise via truncation is presented as preserving the maximal character of the bounds. However, when the operator is expansive with positive probability, it is not shown that the truncation threshold can be chosen so that the exponential growth possible in the Poisson solution does not inflate the tail beyond the stated factor of three relative to the noise tail."}],"tokens_in":1590,"tokens_out":607,"duration_ms":43453,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main thing to know is that this work establishes maximal concentration bounds for stochastic approximation iterates with general step sizes under noise that has both a finite-state Markov component and a martingale-difference part. The tail behavior shifts with the step-size sequence and with whether the random operator is almost surely contractive, non-expansive, or expansive with positive probability; they also handle the unbounded-martingale case for 1/k steps and show the error tail stays within a constant factor of the noise tail when the operator is non-expansive but can get substantially heavier when expansion occurs with positive probability.","headline":"The paper gives sharp maximal concentration bounds for stochastic approximation under mixed Markovian and martingale noise via a new MGF-based Lyapunov and truncation, but the expansive-operator regime needs checking on moment control.","tokens_in":2465,"tokens_out":202,"would_cite":false,"duration_ms":36440,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[],"headline":"Standard concentration analysis for SA with Markov noise; no RS-shaped cost or forcing structure","alignment":"orthogonal","rationale":"The paper develops maximal tail bounds via MGF Lyapunov functions built from Poisson solutions for finite-state Markov chains, plus auxiliary projection/truncation arguments. This is classical stochastic approximation / concentration theory (see e.g. the use of Poisson eq. in Haque-Maguluri or Liu et al.). RS framework derives J-cost, φ-ladders, 8-tick periodicity and parameter-free constants from a single distinction; none of these appear or are paralleled here. Domain is orthogonal to RS theorems on recognition cost or spacetime emergence.","tokens_in":64562,"confidence":"high","tokens_out":155,"duration_ms":9215,"cache_read_input_tokens":38528,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Stochastic approximation achieves concentration bounds whose tail type depends on step sizes and operator expansiveness under Markovian and martingale noise.","keywords":["stochastic approximation","concentration bounds","Markovian noise","heavy tailed noise","martingale difference noise","Poisson equation","Lyapunov function","tail bounds"],"falsifier":"Simulate the stochastic approximation process with an expansive operator and heavy-tailed martingale noise using 1/k steps, then compare the observed error tail decay to the predicted heavier-than-three-times inflation; a mismatch in the tail heaviness would falsify the distinction between non-expansive and expansive cases.","tokens_in":2720,"feed_emoji":"📉","tokens_out":815,"duration_ms":42911,"temperature":0.7,"pith_summary":"The authors establish maximal concentration bounds for iterates of stochastic approximation algorithms that include both finite-state Markovian noise and an additional martingale-difference component. For bounded martingale noise, the error tails can be sub-Gaussian, sub-Weibull, or intermediate between Pareto and Weibull, according to the choice of step-size sequence and whether the random operator is contractive almost surely, non-expansive almost surely, or expansive with positive probability. The analysis introduces a Lyapunov function built around the moment-generating function of the Poisson equation solution and employs an auxiliary projected algorithm to manage the dependencies. Similar but adjusted bounds hold for unbounded martingale noise when steps are of order 1/k, with non-expansive operators keeping error tails at most three times the noise tails and expansive ones allowing substantially heavier tails. These findings matter for applications like reinforcement learning and optimization where dependent heavy-tailed noise is common and tail behavior governs the probability of large errors.","feed_headline":"SA error tails range from sub-Gaussian to near-Pareto with Markov noise","feed_subtitle":"The tail class depends on the step-size sequence and whether the random operator is contractive or expansive almost surely.","key_machinery":"A Lyapunov function that uses the moment-generating function of the solution to a Poisson equation for the Markov process, together with an auxiliary projected stochastic approximation algorithm.","core_discovery":"The central claim is that maximal concentration bounds exist for stochastic approximation under general step sizes with mixed Markovian and martingale-difference noise, and that the qualitative form of these bounds (sub-Gaussian, sub-Weibull, or Pareto-like) is determined by the step-size schedule and the almost-sure contractiveness properties of the random operator, with matching lower bounds from worst-case examples and a truncation reduction for the unbounded-noise case.","pith_inferences":["The truncation argument provides a general technique that might apply to concentration analysis of other dependent stochastic recursions.","Algorithm designers could prefer contractive or non-expansive operators to secure lighter error tails in noisy environments.","Empirical verification on low-dimensional examples with known Markov chains would test the predicted dependence of tail regimes on expansiveness.","These results imply that heavy-tailed noise in iterative methods does not necessarily produce arbitrarily heavy error tails when the operator satisfies suitable contraction properties."],"forward_implications":["When the martingale-difference noise is bounded and the operator is almost surely contractive, sub-Gaussian tails are achievable for suitable step sizes.","Almost sure non-expansiveness leads to sub-Weibull tails.","Expansiveness with positive probability produces tails lighter than Pareto but heavier than Weibull.","With 1/k step sizes and unbounded noise, non-expansive operators limit tail inflation to a factor of three.","Worst-case constructions demonstrate that qualitatively better bounds cannot hold in general."],"fun_headline_variants":["Markovian noise shapes SA concentration from sub-Gaussian to Pareto","Step size choices control SA error tail classes with Markov noise","Contractive maps yield sub-Weibull SA tails in heavy Markov noise","Expansive operators cause heavier tails in stochastic approximation"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The existence of a Poisson equation solution whose moment-generating function is finite and controllable under the given Markov noise model is required for the Lyapunov construction to yield the stated concentration bounds.","fun_headline_variants_meta":{"raw":{"variants":["Markovian noise shapes SA concentration from sub-Gaussian to Pareto","Step size choices control SA error tail classes with Markov noise","Contractive maps yield sub-Weibull SA tails in heavy Markov noise","Expansive operators cause heavier tails in stochastic approximation"]},"model":"grok-4.3","cost_usd":0.007931,"raw_usage":{"total_tokens":3628,"prompt_tokens":696,"num_sources_used":0,"completion_tokens":69,"cost_in_usd_ticks":79312000,"prompt_tokens_details":{"text_tokens":696,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":2863,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":696,"tokens_out":69,"duration_ms":24799,"temperature":1.0,"reasoning_tokens":2863,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-21T02:23:33.534862+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"Simulate the stochastic approximation process with an expansive operator and heavy-tailed martingale noise using 1/k steps, then compare the observed error tail decay to the predicted heavier-than-three-times inflation; a mismatch in the tail heaviness would falsify the distinction between non-expansive and expansive cases.","supporting_citations":[],"review_version":1}