{"id":"b8a4ac11-f7f1-4fe7-ab16-697380286388","arxiv_id":"2608.10040","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"An online potential-based algorithm achieves O(sqrt n) terminal discrepancy with exponentially high probability for independent sub-Gaussian inputs, and a sparsity-aware variant achieves O(sqrt k).","lead":"This paper gives a fast online algorithm that assigns plus or minus signs to a stream of random vectors while keeping the largest coordinate of their signed sum small. It proves a near-optimal sqrt(n) guarantee for Gaussian and other sub-Gaussian inputs, settling a conjecture from the symmetric binary perceptron literature.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 16's omitted weighted-rank concentration estimate is the load-bearing gap: without it, Lemma 26 and Theorem 1 are not established.","rationale":"The reader's weakest_assumption identifies precisely the cluster of omitted technical estimates in Lemma 16, Lemma 24, and Lemma 25, and the present stress-test agrees that the most load-bearing of these is the missing weighted-rank concentration estimate behind Lemma 16(iii). The central theorem is coherent and the framework is plausible, but the exponential-moment contraction in Lemma 26 cannot be certified without that estimate. The author's own footnote acknowledges the omission, so the state of the proof is transparent. Since the reader already assigned CONDITIONAL on these grounds, this stress-test does not move the verdict: it reinforces CONDITIONAL rather than upgrading to ACCEPT or downgrading to REJECT. The proposed test would settle whether the omitted estimate is valid or whether the proof needs a substantial new idea.","tokens_in":70652,"tokens_out":2880,"duration_ms":33128,"concrete_test":"Write out a complete proof of Lemma 16(iii) for the simplest nontrivial special case: v_{t+1}(i) Rademacher, s >> R, m = n/2, with a fixed history satisfying Psi_t = s and |I_t| = m. Verify that the adaptively reweighted sum eDelta beta_t - E[eDelta beta_t] satisfies E exp(theta (eDelta beta_t - E)) <= exp(C theta^2 / m) for |theta| <= c sqrt(m) with C,c absolute. If the proof requires additional independence assumptions on the ranks bpi_{t+1} or the exchange set, the current argument is incomplete. As a complementary numerical check, simulate 10^5 one-step updates of this conditional sum for n=2000, m=1000 and compare the empirical psi_2 norm with K/sqrt(m): if the ratio grows with n or the tail is heavier than sub-Gaussian, the claimed bound is false.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The core exponential-moment contraction (Lemma 26) requires the adjusted account-balance proxy eDelta beta_t to be conditionally sub-Gaussian with psi_2-norm O(m^{-1/2}) (Lemma 16(iii)). The proof of Lemma 16 stops precisely at the point where this is needed: after conditioning on (Psi_t, |I_t|), the ordering bpi_{t+1} and the exchange pairs depend on the fresh vector v_{t+1}, so the summands of eDelta beta_t are not independent. The text states that a “joint weighted-rank concentration estimate” is required and then omits it. Since Corollary 8 and Lemma 26 rely directly on this estimate, the horizon-independent high-probability bound in Theorem 1 is currently unsupported at that step. A second connected gap is Lemma 24/25: the exponential bound on the number of exchange pairs is only a chip-game heuristic, and Lemma 25 invokes a weighted interface-count version with the technical details omitted; this controls the residual moving-level error R_t used in the same contraction. If Lemma 16(iii) fails with an n-dependent constant, the negative drift is insufficient for the exponential-moment method and the claimed exp(-Omega(sigma^3 sqrt(n))) failure probability may not follow. The concern is not an identified contradiction; it is a missing proof in the central chain.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims a polynomial-time online algorithm for terminal discrepancy minimization on i.i.d. random vectors whose coordinates are independent, symmetric, centered, unit-variance sub-Gaussian with sub-Gaussian norm at most sigma. Theorem 1 asserts terminal discrepancy O(sigma^8 sqrt(n)) with failure probability exp(-Omega(sigma^3 sqrt(n))) for every prescribed finite horizon T. Theorem 2 extends the bound to O(sigma^8 sqrt(k)) for Bernoulli-masked inputs with expected support size k >= (log n)^2. The algorithm is a potential-based method combining an ell_{1/2}-regularized ell_infty potential restricted to an adaptively chosen active coordinate set, with an amortized account that pays for switching costs. The proof proceeds through one-step drift estimates, sub-Gaussian/sub-exponential concentration of proxy increments, and an exponential-moment contraction that is uniform in t.","tokens_in":70941,"tokens_out":4915,"duration_ms":49152,"significance":"If the theorems are correct, this is a substantial generalization of the Bansal-Spencer Rademacher result, gives an efficient O(sqrt(n)) Gaussian guarantee as conjectured by Gamarnik et al., and determines the Gaussian online threshold for the symmetric binary perceptron up to constant factors. The regularized-and-restricted potential framework and the account-based amortization are interesting technical contributions, and many supporting lemmas are proved in detail. However, the central exponential-moment contraction is not currently complete: several key estimates are explicitly asserted with only heuristic or omitted proofs. The result is therefore conditional on the completion of those estimates.","major_comments":[{"comment":"The proof of Lemma 16 stops at the exact point where the sub-Gaussian concentration of the adjusted account-balance proxy is needed. After conditioning on (Psi_t, |I_t|), the ordering hat(pi)_{t+1} and the exchange pairs depend on the fresh vector v_{t+1}, so the summands of eDelta beta_t are not independent. The text states that a joint weighted-rank concentration estimate is required and then says \"We omit this technical argument.\" This estimate is directly used in Corollary 8 and in the Holder-step of Lemma 26; without it, the negative drift in the exponential-moment recursion is not established.","section":"§5.2, Lemma 16(iii) and the footnote following it"},{"comment":"The exponential bound on the number of exchange pairs r is justified only by a chip-game heuristic. The lemma itself says that a complete proof requires a technical coupling argument and that these details are omitted. Lemma 24 is used in the proof of Lemma 25, and Lemma 25 controls the residual moving-level error R_t that appears in the main contraction Lemma 26. Thus this is a load-bearing gap in the central proof chain.","section":"§5.3, Lemma 24"},{"comment":"The weighted interface-count estimate used to bound E_t^ex is stated without proof: the text says it \"does not follow immediately from Lemma 24\" because the layer counts are dependent and then says \"we omit the resulting technical details.\" This estimate is not a formal consequence of the preceding lemmas, and it is necessary for the exponential moment bound on R_t. Since Lemma 26 relies on this bound, the high-probability statement in Theorem 1 is currently unsupported at this step.","section":"§5.3, Lemma 25"},{"comment":"The proof of Lemma 23 uses the assertion that the auxiliary random walk (X_t) has stronger concentration around R/4 than the actual relative-position process (Y_t). This stochastic domination is asserted rather than proved; Appendix B analyzes the stationary measure of (X_t) but does not establish the needed comparison with (Y_t). Lemma 23 supplies the expectation bound on eDelta rho_t(j) that feeds into Lemma 16(ii), so this is another load-bearing point in the dense-regime proof.","section":"§5.2, comparison-walk argument before Lemma 23"}],"minor_comments":[{"comment":"The theorem states n ≳ sigma^24, but the proof repeatedly uses n ≫ sigma^24 to absorb prefactors such as log(sigma^8 sqrt(n)) into the exponential tail. The intended asymptotic regime (n -> infinity with sigma fixed or growing slowly) should be stated explicitly.","section":"Theorem 1 and §5, proof of Lemma 17"},{"comment":"The constants c and C are used both as absolute constants and as the large constant appearing in the definition of R and eta. The presentation would be clearer if all dependencies on the large absolute constant C were tracked explicitly, or if the proof stated that C is chosen sufficiently large after all other absolute constants.","section":"§5.3, Lemma 26 and proof of Lemma 17"},{"comment":"The footnote containing the omitted weighted-rank estimate is a central technical step, not a side remark. It would be better placed as a separate lemma with a full proof in an appendix.","section":"§5.2, proof of Lemma 16"},{"comment":"The proof of Lemma 37 uses the condition R ≳ sigma^2 in the displayed inequality after (47). This condition follows from the standing assumption n ≳ sigma^24 and R = C sigma^7 sqrt(n), but the implication is not stated; adding one sentence would avoid confusion.","section":"Appendix B, Lemma 37"}],"recommendation":"major_revision","confidential_remarks":"The paper makes a strong claim and contains many detailed supporting lemmas, but the exponential-moment contraction in Section 5.3 depends on three omitted technical arguments: the weighted-rank concentration in Lemma 16(iii), the exchange-pair coupling in Lemma 24, and the weighted interface-count estimate in Lemma 25. A fourth gap is the unproved comparison-walk domination in Section 5.2. These are local but load-bearing, and they should be repairable within the manuscript's framework. I therefore recommend major revision rather than rejection. If the author can supply complete proofs of these four items, the paper is likely to be a significant contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper you asked about is worth a serious look. The main result, if the proof were complete, is the first polynomial-time online algorithm achieving O(σ^8 sqrt n) terminal discrepancy with exponentially high probability for i.i.d. sub-Gaussian inputs with independent symmetric centered unit-variance coordinates. That generalizes Bansal–Spencer beyond Rademacher entries, gives the Gaussian online SBP threshold up to constants (combining with GKPX23 lower bound), and the Bernoulli-masked sparse extension to O(σ^8 sqrt k) is also new. The regularization-and-restriction potential framework is a genuine technical invention, and the paper is honest about the dependence on T being removed.\n\nWhat the paper does well: the high-level amortization story is clear, many of the supporting lemmas (the restricted potential calculus, the fixed/variable-cost accounting, the capping refresh) are proved in detail, and the author flags exactly where the proof stops. The comparison with prior work, including the concurrent Fiedler–Jackson–Lacker–Niles-Weed result, is accurate and fairly drawn. The citation pattern looks fine.\n\nWhere the soft spots are: they are in the load-bearing concentration estimates. Lemma 16(iii) asserts the adjusted account-balance proxy is sub-Gaussian with psi_2-norm O(m^{-1/2}), but the proof stops precisely at the point where the ordering and exchange pairs depend on the fresh vector, so the summands are no longer independent. The text says a 'joint weighted-rank concentration estimate' is required and then omits it. Corollary 8 and Lemma 26 depend directly on this. Separately, Lemma 24 is justified only by a chip-game heuristic, and Lemma 25 invokes a weighted interface-count version of it with details omitted; these control the residual moving-level error in the same contraction. So the exponential-moment recursion—the heart of the horizon-independent high-probability bound—is currently unsupported at three connected points.\n\nI don't see an identified contradiction or a fitted-parameter circularity. The parameter choices are not data-dependent, and the target bound is not assumed. The gaps are missing proofs, not false statements, and the author is upfront about them. That makes the paper conditionally acceptable rather than rejectable.\n\nFor whom: anyone working on online discrepancy, the SBP statistical-computational gap, or potential-based algorithms. A reader who needs the theorem as a black box should wait until the gaps are closed. A serious referee could productively push on the three omitted estimates.\n\nMy recommendation: send it to peer review. It deserves referee time, and the author has done the community a service by making the state of the proof transparent.","headline":"A plausible and genuinely new potential-based online discrepancy algorithm for sub-Gaussian inputs, but the central proof currently rests on three explicitly omitted technical estimates.","tokens_in":71442,"tokens_out":2184,"would_cite":false,"duration_ms":22584,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves a polynomial-time online algorithm that keeps terminal discrepancy at $O(\\sigma^8\\sqrt{n})$ for i.i.d. sub-Gaussian inputs, with failure probability $\\exp(-\\Omega(\\sigma^3\\sqrt{n}))$, for every finite horizon $T$.","keywords":["online discrepancy minimization","sub-Gaussian random vectors","regularized infinity norm","potential function","Bernoulli masking","symmetric binary perceptron","exponential moment method","horizon-independent bounds"],"falsifier":"Simulate the restriction procedure on Rademacher or Gaussian inputs at dimension $n=10^4$ and record the exchange count $r$ and active-set size $m$ at each step; if $\\log \\mathbb{E}\\exp(\\theta r/m)$ grows faster than the claimed $\\theta/(C\\sigma^7\\sqrt{n})$ scale for admissible $\\theta$, Lemma 24 is false and with it the contraction argument. Separately, a direct disproof of the main theorem would exhibit unit-variance sub-Gaussian inputs for which the algorithm's terminal discrepancy exceeds $C\\sigma^8\\sqrt{n}$ with probability larger than $\\exp(-\\Omega(\\sigma^3\\sqrt{n}))$.","tokens_in":70404,"feed_emoji":"📐","tokens_out":11381,"duration_ms":101769,"temperature":0.7,"pith_summary":"The paper establishes a polynomial-time online algorithm for discrepancy minimization: when the arriving vectors have independent, symmetric, centered, unit-variance sub-Gaussian coordinates with norm at most $\\sigma$, the terminal discrepancy is $O(\\sigma^8\\sqrt{n})$ with probability at least $1-\\exp(-\\Omega(\\sigma^3\\sqrt{n}))$, for every prescribed finite horizon $T$. This extends a guarantee previously known only for Rademacher entries to Gaussian, bounded, and other sub-Gaussian inputs, and supplies the efficient $O(\\sqrt{n})$ bound that had been conjectured for Gaussian inputs. In the Bernoulli-masked sparse model with expected support $k \\gtrsim (\\log n)^2$, the same algorithm achieves $O(\\sigma^8\\sqrt{k})$ with failure probability $\\exp(-\\Omega(\\sigma^3\\sqrt{k}))$, replacing ambient dimension by expected support. The proof works by regularizing the $\\ell_\\infty$-norm with a concave square-root term, restricting it to an adaptively chosen active coordinate set, and paying for set changes through a capped accounting balance, then converting a one-step negative drift into horizon-independent exponential-moment bounds.","feed_headline":"Sub-Gaussian inputs get O(sqrt n) online discrepancy","feed_subtitle":"A horizon-independent potential method extends the Rademacher guarantee to Gaussians and sparse inputs.","key_machinery":"The central object is the $\\ell_{1/2}$-regularization of the $\\ell_\\infty$-norm: $\\Phi(y)=\\max_{(p,q)\\in S_n}\\{\\langle p-q,y\\rangle + (2/\\eta)\\sum_i(p_i^{1/2}+q_i^{1/2})\\}$, a twice-differentiable function that stays within $O(\\sqrt{n}/\\eta)$ of $\\|y\\|_\\infty$, with its optimizer encoded by a one-dimensional Lagrange multiplier $\\lambda(y)$. The algorithm restricts this potential to an adaptively chosen active set $I_t$ containing all leading coordinates, using a pre-leading zone with hysteresis so that unbounded sub-Gaussian entries never push the Taylor analysis outside a controlled neighborhood of the maximum. Active-set changes are financed by a variable-cost accounting balance with ordered levels, exchange pairs, and a cap at $4\\sqrt{n}/\\eta$, giving an amortized process $\\Psi_t=\\Phi|_{I_t}(d_t)+\\beta_t$ that dominates the discrepancy. A one-step drift estimate is converted into the contraction $\\mathbb{E}\\exp(\\lambda\\Psi_{t+1})\\le A+\\exp(-\\delta)\\mathbb{E}\\exp(\\lambda\\Psi_t)$, which iterates to horizon-independent exponential moments and Chernoff tail bounds.","core_discovery":"The central claim is that a simple potential-driven rule—choose the sign minimizing a restricted smooth $\\ell_\\infty$ proxy, then update the active set by hysteresis and exchange—has negative drift above a threshold of order $\\sigma^7\\sqrt{n}$, with increments whose tails are controlled well enough that exponential moments stay bounded uniformly in time. Theorem 1 states that for i.i.d. inputs with independent, symmetric, centered, unit-variance sub-Gaussian coordinates, the algorithm outputs signs with terminal discrepancy at most $C\\sigma^8\\sqrt{n}$ with probability at least $1-\\exp(-c\\sigma^3\\sqrt{n})$. Theorem 2 states that if each coordinate is independently masked by a Bernoulli variable of mean $k/n$ and $k \\gtrsim (\\log n)^2$, the bound improves to $O(\\sigma^8\\sqrt{k})$ with failure probability $\\exp(-\\Omega(\\sigma^3\\sqrt{k}))$. The paper also argues that the $\\sqrt{n}$ scale is essentially unavoidable online and, under worst-case lattice-hardness assumptions, cannot be improved offline by a fixed polynomial factor in $T/n$ when $T$ is polynomially larger than $n$.","pith_inferences":["The paper's own remark that symmetry is used only in the comparison-walk argument suggests a testable extension: the same algorithm should keep centered non-symmetric sub-Gaussian coordinates within the same discrepancy scale.","The gap between the $k=o(\\log n)$ lower-bound example and the assumed $k \\gtrsim (\\log n)^2$ suggests the accounting-rescaling analysis might be refined to close the logarithmic threshold gap.","The same combination of a smooth restricted $\\ell_\\infty$ proxy, hysteresis, and capped accounting could transfer to prefix-discrepancy objectives or to oblivious online settings where coordinate independence is replaced by other assumptions."],"forward_implications":["For Gaussian inputs in the proportional regime $T=\\Theta(n)$, the online algorithm achieves terminal discrepancy $O(\\sigma^8\\sqrt{n})$, matching the optimal offline order up to constants.","For the symmetric binary perceptron, the algorithm finds a signing whenever the inverse aspect ratio satisfies $\\alpha \\gtrsim \\kappa^{-2}$, determining the online threshold up to constants together with the known online lower bound.","Both the discrepancy bound and the failure probability are independent of the prescribed finite horizon $T$.","In the Bernoulli-masked sparse model with expected support $k \\gtrsim (\\log n)^2$, the bound becomes $O(\\sigma^8\\sqrt{k})$ with failure probability $\\exp(-\\Omega(\\sigma^3\\sqrt{k}))$, and the same holds for uniform exact-support masks.","Under standard worst-case lattice-hardness assumptions, no polynomial-time offline algorithm can improve the $\\sqrt{n}$ scale by a fixed polynomial factor in $T/n$, so the online guarantee is conditionally near-optimal in superlinear regimes."],"supporting_citations":[{"why":"supplies the Rademacher baseline and the potential-function framework that the paper extends to sub-Gaussian inputs.","marker":"[BS20]"},{"why":"introduces the one-sided $\\ell_{1/2}$ regularization used as a smooth proxy for the $\\ell_\\infty$ norm.","marker":"[PV23]"},{"why":"states the conjecture of an efficient $O(\\sqrt{n})$ Gaussian guarantee that Theorem 1 resolves.","marker":"[GKPX22]"},{"why":"provides online lower bounds showing the $\\sqrt{n}$ scale cannot be improved uniformly over horizons.","marker":"[GKPX23]"},{"why":"gives the conditional lattice-hardness lower bound for offline polynomial-time algorithms that anchors the optimality discussion.","marker":"[VV25]"},{"why":"characterizes typical Gaussian discrepancy and the offline regime the paper's $O(\\sqrt{n})$ result complements.","marker":"[TMR20]"},{"why":"supplies the negative-drift exponential-moment theorem underlying the contraction argument.","marker":"[Haj82]"},{"why":"supplies the sub-Gaussian and sub-exponential norm facts used throughout the proof.","marker":"[Ver18]"}],"fun_headline_variants":["Sub-Gaussian online discrepancy tamed to O(√n)","O(√n) online discrepancy for sub-Gaussian vectors","Horizon-free O(√n) discrepancy for sub-Gaussian streams","Sparse sub-Gaussian inputs get O(√k) online discrepancy","Polynomial-time O(√n) online discrepancy for sub-Gaussians"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that three technical estimates in the contraction step hold—the exponential bound on the number of exchange pairs, the weighted interface-count estimate for exchange displacements, and the sub-Gaussian concentration of the adjusted account increment—and each is currently justified only by a heuristic argument or an omitted technical proof; if any fails, the high-probability $O(\\sigma^8\\sqrt{n})$ guarantee is not established.","fun_headline_variants_meta":{"raw":{"variants":["Sub-Gaussian online discrepancy tamed to O(√n)","O(√n) online discrepancy for sub-Gaussian vectors","Horizon-free O(√n) discrepancy for sub-Gaussian streams","Sparse sub-Gaussian inputs get O(√k) online discrepancy","Polynomial-time O(√n) online discrepancy for sub-Gaussians"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000372,"raw_usage":{"total_tokens":2070,"prompt_tokens":1106,"completion_tokens":964,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":722,"completion_tokens_details":{"reasoning_tokens":871}},"tokens_in":722,"tokens_out":964,"duration_ms":7873,"temperature":1.0,"reasoning_tokens":871,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T04:14:38.678611+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the restriction procedure on Rademacher or Gaussian inputs at dimension $n=10^4$ and record the exchange count $r$ and active-set size $m$ at each step; if $\\log \\mathbb{E}\\exp(\\theta r/m)$ grows faster than the claimed $\\theta/(C\\sigma^7\\sqrt{n})$ scale for admissible $\\theta$, Lemma 24 is false and with it the contraction argument. Separately, a direct disproof of the main theorem would exhibit unit-variance sub-Gaussian inputs for which the algorithm's terminal discrepancy exceeds $C\\sigma^8\\sqrt{n}$ with probability larger than $\\exp(-\\Omega(\\sigma^3\\sqrt{n}))$.","supporting_citations":[],"review_version":1}