{"id":"e00dc347-ac24-4026-8fb4-bdba8acdf452","arxiv_id":"2608.12490","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"This paper achieves constant prefix discrepancy for online signed balancing of small-coordinate vectors with failure probability about T exp(-c d / ln^2(ed)), and proves the ln^2 scale is a barrier for the compact-potential method.","lead":"Online balancing asks how to assign plus or minus signs to a sequence of vectors so that all prefix sums stay small. This paper proves a near-optimal failure-probability bound for vectors with small coordinates, tightening a known result and showing the limit of the method used.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The main theorems hinge on Lemma 2.3, an externally cited coupling lemma stated without proof; no internal error found, but this unverified dependency is the weakest link and should be settled before full acceptance.","rationale":"I read the paper as proving a sharp online discrepancy bound for vectors with small coordinates, using a three-walk Metropolis construction. I checked the main proof chain: the implicit potential in Section 3, the integral bound in (3.3), the curvature and tail estimates in Lemma 3.2, the exponential concentration in Lemma 3.3, the one-step bound in Proposition 3.4, and the final application of Proposition 2.4. The algebra and estimates are coherent, and the absolute constants do appear to be independent of m, d, and T. The lower-bound tensorization in Proposition 6.2 is standard, and Propositions 6.3 and 6.4 are internally consistent. The most fragile point is not any calculation inside this paper but the external coupling lemma, Lemma 2.3, on which the production of genuine signs depends. The paper cites it without proof, and the source is a recent preprint. I could not produce a counterexample, and the lemma is likely true, but it is exactly the kind of unverified dependency that a careful referee should require to be supplied or independently checked. Because the central claim collapses if Lemma 2.3 fails, I recommend conditional acceptance: the mathematical structure is sound, provided the coupling lemma is established. The lack of a finite-bit implementation is a real caveat for the word 'algorithm', but it does not undermine the probability bound as an existence statement, so I do not base the verdict adjustment on it.","tokens_in":19263,"tokens_out":32318,"duration_ms":282515,"concrete_test":"Verify Lemma 2.3 independently: set up the twelve atomic sign patterns in {−1,0,1}^3 whose coordinate sum is ±1, and solve the linear feasibility problem for nonnegative masses whose marginals equal (a_j,b_j). Test a dense grid of admissible (a_j,b_j) in [0,1/3]^6 with a_j+b_j >= 1/3, or enumerate the extreme points of the marginal polytope. If a feasible coupling is exhibited for every admissible marginal, the proof of Theorem 1.1 goes through; if a feasible point is missing, the lemma is false and the three-walk construction needs repair.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The load-bearing step is the use of Lemma 2.3 (quoted from [1, Lemma 6]) in Proposition 2.4. Theorem 1.1, Theorem 1.2, and Theorem 7.1 all inherit it: without a coupling of three {−1,0,1} variables with marginals a_j, b_j and sum identically ±1, the output sign epsilon_t is not guaranteed to be a genuine sign, and the identity sum_{t<=k} epsilon_t v_t = sum_j (X_{k,j} - X_{0,j}) used for the 6L bound dissolves. The lemma is stated without proof in the present paper, and [1] is an arXiv preprint rather than an established reference. I did not find a counterexample; the lemma appears plausible and holds in simple extreme cases (e.g., a_j=b_j=1/3 via a symmetric mixture of one- and three-nonzero configurations). Nevertheless, the entire randomized-sign construction is conditional on this external fact, so it is the least independently supported premise in the argument. Other caveats (exact sampling from an implicit density, no finite-bit running-time) affect the algorithmic interpretation of Theorem 1.1 but not the correctness of the probability bound.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies online vector balancing for deterministic sequences v_t satisfying ||v_t||_2≤1 and ||v_t||_∞≤d^{-1/2}. It constructs a randomized online signing algorithm based on a Metropolis walk with a d-dependent product potential, and proves that the maximum prefix ℓ∞-discrepancy exceeds 6L only with probability at most CT exp(-c d/ln^2(ed)) (Theorem 1.1). This yields constant prefix discrepancy with probability 1-ε once d is at least C ln(3T/ε)[ln(e+ln(3T/ε))]^2, and an O(√d) discrepancy bound for d-sparse vectors (Corollary 3.5). A second theorem (Theorem 1.2) gives a nonuniform version with individual failure probabilities depending on d_t = ||v_t||_∞^{-2}. The paper also proves a lower bound showing that constant prefix discrepancy is impossible when d=o(ln T), establishes a ln^2 d lower barrier for the compact-potential curvature method, and extends the argument to general symmetric target bodies satisfying a quadratic smoothness estimate. The exposition is detailed; several framework lemmas are reproved, and the main concentration estimates are self-contained.","tokens_in":19522,"tokens_out":20099,"duration_ms":168241,"significance":"The main theorem, if correct, closes the gap between the known ln^{2+η}(ed) loss in the online Beck–Fiala framework and the critical ln^2(ed) scale, and the lower bound Proposition 6.2 shows that the regime d=o(ln T) is genuinely obstructed. The compact-potential barriers in Propositions 6.3 and 6.4 are clean and help explain why the d-dependent construction in Section 3 is needed. The paper is carefully written: the potential construction in Lemma 3.2 is intricate, the concentration estimates (Lemma 3.3 and Theorem 4.3) are proved in detail, and the geometric extension in Section 7 is coherent. The main caveat is that Proposition 2.4 rests on Lemma 2.3, a coupling statement imported from an arXiv preprint without proof; since both main theorems inherit this step, the correctness of the paper as a whole depends on that external fact. The papers also explicitly disclaims finite-bit implementation, so the algorithmic claim should be read in an idealized real-arithmetic model; this does not affect the probability bounds.","major_comments":[{"comment":"Lemma 2.3 is stated without proof and is load-bearing: Proposition 2.4 uses it to couple three Metropolis increments so that their sum is always a genuine sign, and Theorems 1.1, 1.2, and 7.1 all inherit this step. Since the cited source [1] is an arXiv preprint rather than an established peer-reviewed reference, the authors should either provide a self-contained proof of the lemma (e.g., in an appendix) or replace the citation with a published source containing a proof. If the claimed coupling fails in any corner of the parameter region, the identity ε_t = δ_{1,t}+δ_{2,t}+δ_{3,t} in Proposition 2.4 breaks down and the bound ||∑ ε_t v_t||_K ≤ 6 dissolves.","section":"Section 2, Lemma 2.3 and Proposition 2.4"}],"minor_comments":[{"comment":"The notation 'ln ln(e eT)' in the abstract is inconsistent with 'ln ln(e^eT)' in the theorem statement; please standardize the expression.","section":"Abstract and Theorem 1.1"},{"comment":"The algorithm is described as using exact sampling from the implicitly defined density (3.11) and exact evaluation of φ_d in the Metropolis ratios, and the paper explicitly disclaims a finite-bit running-time bound. It would be helpful to state a precise computational model (e.g., the real-RAM model) in which the theorem's algorithmic claim is meant, so that the reader can distinguish the mathematical probability bound from the implementability claim.","section":"Section 1 and Theorem 1.1"},{"comment":"The sentence 'Proposition 6.2 shows that constant prefix discrepancy cannot hold uniformly when d=o(ln T)' could be sharpened to say 'against every randomized online algorithm there is an oblivious hard input distribution', since the lower bound is proved in the oblivious-adversary model; this is already clear from the proof but should be stated in the text.","section":"Section 6, final paragraph"}],"recommendation":"major_revision","confidential_remarks":"The only substantive obstacle is the unproved external coupling lemma, Lemma 2.3. If the authors provide a proof or a peer-reviewed reference for it, I would support acceptance. The rest of the argument appears sound and the paper makes a valuable contribution. The exact-sampling issue is honestly disclosed and, in my view, does not block publication in a mathematics journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing you should know: this is a real advance, not a repackaging. It takes the Altschuler-Tikhomirov compact Metropolis framework and removes the arbitrary eta in the failure exponent, from exp(-c d/ln^{2+eta}(ed)) to exp(-c d/ln^2(ed)), and it drops the support restriction. The d-dependent potential phi_d in Section 3 is the core of the proof, and it is done carefully; Lemmas 3.1-3.3 and Proposition 3.4 check out on my reading. The lower bound tensorizing the KRR two-dimensional construction and the two barrier propositions (fixed compact potential requires exponent >2; d-dependent potential requires curvature at least ln^2 d) are nice, and they show the ln^2 scale is not a numerical accident.\n\nThe soft spot is the same one the stress-test flagged: Lemma 2.3, quoted from [1, Lemma 6] and stated without proof. The entire randomized signing rests on that coupling of three {−1,0,1} variables with sum ±1. If the lemma is false, both main theorems collapse. I did not find a counterexample and the lemma looks plausible, but in a paper this tight you would expect either a proof or a citation to a published source. [1] is itself an arXiv preprint, so the dependency is not as solid as it could be. That is a genuine weakness, not a demonstrated error. A second caveat, acknowledged by the author, is that the algorithm uses exact sampling from an implicitly defined density and exact potential evaluation; there is no finite-bit running time. This limits the algorithmic interpretation of Theorem 1.1 but does not affect the probability bound.\n\nOther remarks: the citation pattern is clean. The author credits [3] and [1] properly, reproves the framework lemmas that are used, and there is no self-citation issue. The geometric extension in Section 7 is a bonus; I have not checked it line by line, but it follows the same pattern and looks plausible.\n\nVerdict: for someone working in discrepancy, this deserves serious referee time. I would send it to review, with the instruction that the referee either verify Lemma 2.3 or ask the author to include a proof. My own inclination is to accept once that dependency is settled. I would bring it to our reading group if anyone is interested in online discrepancy.","headline":"A genuine improvement that removes the arbitrary eta in the online Beck-Fiala failure exponent; the proof is careful, but the unproved external coupling lemma deserves verification before you rely on it.","tokens_in":20048,"tokens_out":2112,"would_cite":true,"duration_ms":19485,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["11K38","46B20","60J05","68W27"],"pacs":[],"model":"deepseek-v4-flash","headline":"A randomized online signer balances every fixed sequence of small-coordinate vectors to constant prefix discrepancy, with failure probability exponential in d/log^2(ed).","keywords":["discrepancy theory","online vector balancing","Komlós problem","convex bodies","Metropolis walk","prefix discrepancy","sparse vectors","small coordinates"],"falsifier":"Attempt to construct the coupling promised by Lemma 2.3: for any $a_j,b_j\\in[0,1/3]$ with $a_j+b_j\\ge 1/3$, exhibit $\\delta_1,\\delta_2,\\delta_3\\in\\{-1,0,1\\}$ with $\\delta_1+\\delta_2+\\delta_3\\in\\{\\pm1\\}$ almost surely; a single triple of marginals for which no such coupling exists would falsify both main theorems, since every successful step uses it.","tokens_in":19080,"feed_emoji":"⚖️","tokens_out":14352,"duration_ms":109436,"temperature":0.7,"pith_summary":"This paper proves that online vector balancing becomes essentially free once the revealed vectors have small coordinates: if each $v_t$ has Euclidean norm at most $1$ and no coordinate larger than $d^{-1/2}$, a randomized online signer keeps every prefix sum within a constant-width box, failing with probability at most $CT\\exp(-cd/\\ln^2(ed))$. The result covers all vectors with bounded $\\infty$-norm, not only $d$-sparse ones, and it matches the critical $\\ln^2(ed)$ rate for the $d$-sparse online signing problem. A direct corollary gives $O(\\sqrt d)$ prefix discrepancy for $d$-sparse vectors in $[-1,1]^m$ with failure probability $CT\\exp(-cd/\\ln^2(ed))$, so high probability follows once $d\\ge C\\ln T(\\ln\\ln T)^2$. The paper also proves a lower bound showing that no universal constant discrepancy is possible when $d=o(\\ln T)$, and it identifies a $\\ln^2 d$ barrier intrinsic to the compact-potential method. A geometric extension treats general symmetric target bodies satisfying a quadratic smoothness estimate, with the sufficient scale $d\\ge C A^2\\sigma(m+\\ln(T/\\varepsilon))$ in the intrinsic norm.","feed_headline":"Constant online discrepancy for small-coordinate vectors","feed_subtitle":"A random signer keeps every prefix inside a bounded cube, failing with probability exponential in d/log²(ed).","key_machinery":"The load-bearing object is a compactly supported one-dimensional density $\\rho_d(y)\\propto e^{-\\varphi_d(y)}$ on $(-1,1)$, with the potential $\\varphi_d$ defined implicitly by $\\int_1^{\\varphi_d(y)} du/(u\\sqrt{H_d(u)}) = a_d y^2$, where $H_d(u)$ grows like $u^2$ up to $\\ln(ed)$, stays constant at $\\ln^2(ed)$ up to scale $d$, and then grows slowly. This finite-scale potential gives the curvature bound $\\varphi_d''(y)\\le C\\varphi_d(y)H_d(\\varphi_d(y))$, which controls the central second difference $D_v(X)$ and, through Lemma 2.2, makes each coordinate $v$-balanced except on an event of probability $\\exp(-cd/\\ln^2(ed))$. The product law over coordinates is combined with a concentration estimate for weighted sums of $W_d(Y_d)$, and actual signs are produced by coupling three Metropolis steps so that their sum is always $\\pm1$. The lower-bound part tensorizes a two-dimensional oblivious lower bound and proves integral-divergence obstructions that force the $\\ln^2 d$ factor for compact potentials.","core_discovery":"The central claim is that the online signing problem for fixed vectors in $B_2^m \\cap d^{-1/2}B_\\infty^m$ admits constant prefix discrepancy in the $\\infty$-norm. The algorithm runs three coupled Metropolis walks against an oblivious adversary and, at each arrival, produces a genuine sign whose sum over prefixes stays inside $6L B_\\infty^m$ except on an event of probability at most $CT\\exp(-cd/\\ln^2(ed))$. The paper further claims this $\\ln^2(ed)$ loss is forced for the method used: any fixed compact one-dimensional potential with pointwise curvature control must have logarithmic exponent strictly greater than 2, and any $d$-dependent finite-scale potential must have curvature parameter at least $c\\ln^2 d$ (Propositions 6.3 and 6.4). It also claims a nonuniform version with failure probability $C_\\beta \\sum_t \\exp(-c_\\beta d_t/\\ln^{2+2/\\beta}(ed_t))$, and a lower bound obtained by tensorizing a two-dimensional oblivious construction that rules out universal constant discrepancy for $d=o(\\ln T)$. For general symmetric target bodies with a quadratic smoothness estimate, it claims constant $K$-prefix discrepancy once $d\\ge C A^2\\sigma (m+\\ln(3T/\\varepsilon))$.","pith_inferences":["The sufficient scale $d\\approx \\ln T\\cdot(\\ln\\ln T)^2$ and the obstruction $d=o(\\ln T)$ leave a gap of one log-log-squared factor; a natural next step is to decide whether the true threshold for uniform constant prefix discrepancy is simply $d\\approx\\ln T$.","Because $\\ln^2 d$ is shown to be forced for compact one-dimensional potentials, removing the $\\ln^2(ed)$ loss from the failure probability would likely require a non-compact invariant law or a genuinely multidimensional curvature argument, neither of which the paper rules out.","For the $d$-sparse subclass, the corollary improves the failure exponent from $\\ln^{2+\\eta}$ to $\\ln^2$; it would be informative to test whether the lower bound can be sharpened to exclude failure probability $\\exp(-cd)$ on that subclass.","The geometric extension predicts an explicit cost $A^2\\sigma$ for departing from Euclidean geometry; specializing to $\\ell_p^m$ target bodies for large $p$ would directly test whether the factor $\\sigma\\approx\\ln(em)$ is unavoidable."],"forward_implications":["Every fixed sequence of $d$-sparse vectors in $[-1,1]^m$ admits an online signing with prefix discrepancy $O(\\sqrt d)$, with failure probability at most $CT\\exp(-cd/\\ln^2(ed))$.","Once $d\\ge C\\ln(3T/\\varepsilon)[\\ln(e+\\ln(3T/\\varepsilon))]^2$, the prefix discrepancy is constant with probability at least $1-\\varepsilon$.","No online algorithm can guarantee universal constant prefix discrepancy when $d=o(\\ln T)$, even against an oblivious adversary.","In the nonuniform version, vectors with larger individual $d_t=\\|v_t\\|_\\infty^{-2}$ contribute exponentially smaller risk, with the sum governed by $\\exp(-c_\\beta d_t/\\ln^{2+2/\\beta}(ed_t))$.","For a general symmetric target body with norm equivalence factor $A$ and quadratic smoothness parameter $\\sigma$, constant $K$-prefix discrepancy holds once $d\\ge C A^2\\sigma(m+\\ln(3T/\\varepsilon))$."],"supporting_citations":[{"why":"Supplies the compact Metropolis framework, the balanced-state and curvature criteria, and the bump-density estimates used in Theorems 1.1 and 1.2.","marker":"[3]"},{"why":"Supplies Lemma 6, the three-way coupling of {-1,0,1} steps whose sum is almost surely ±1; every successful algorithm step uses it.","marker":"[1]"},{"why":"Supplies the two-dimensional oblivious lower bound that Proposition 6.2 tensorizes to rule out constant discrepancy for d=o(ln T).","marker":"[15]"},{"why":"Supplies the sharp uniform-convexity inequality for p-norms used in Corollary 7.3 to obtain the polytope target-body result.","marker":"[5]"},{"why":"Supplies the Gaussian-measure theorem giving the offline Euclidean balancing bound of order sqrt(ln(eT)) that the online result is compared against.","marker":"[6]"}],"fun_headline_variants":["Constant online prefix discrepancy for small-coordinate vectors","Small-coordinate vectors: online signer with bounded prefixes","Exponential tail bounds for online balancing of tiny-coordinate vectors","Randomized online signing achieves constant prefix discrepancy"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on Lemma 2.3, an imported coupling result stated without proof, which asserts that three lazy sign-steps with arbitrary marginal probabilities in $[0,1/3]$ can be jointly sampled so that their sum is always a genuine sign; if that coupling fails, the three-walk construction and both main probability bounds collapse.","fun_headline_variants_meta":{"raw":{"variants":["Constant online prefix discrepancy for small-coordinate vectors","Small-coordinate vectors: online signer with bounded prefixes","Exponential tail bounds for online balancing of tiny-coordinate vectors","Randomized online signing achieves constant prefix discrepancy"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000613,"raw_usage":{"total_tokens":2939,"prompt_tokens":1123,"completion_tokens":1816,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":739,"completion_tokens_details":{"reasoning_tokens":1753}},"tokens_in":739,"tokens_out":1816,"duration_ms":12432,"temperature":1.0,"reasoning_tokens":1753,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T00:07:55.179216+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Attempt to construct the coupling promised by Lemma 2.3: for any $a_j,b_j\\in[0,1/3]$ with $a_j+b_j\\ge 1/3$, exhibit $\\delta_1,\\delta_2,\\delta_3\\in\\{-1,0,1\\}$ with $\\delta_1+\\delta_2+\\delta_3\\in\\{\\pm1\\}$ almost surely; a single triple of marginals for which no such coupling exists would falsify both main theorems, since every successful step uses it.","supporting_citations":[{"cited_title":"Optimal Online Discrepancy Minimization in Linear Time","cited_arxiv_id":"2607.04388","evidence_quote":"Supplies Lemma 6, the three-way coupling of {-1,0,1} steps whose sum is almost surely ±1; every successful algorithm step uses it."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the sharp uniform-convexity inequality for p-norms used in Corollary 7.3 to obtain the polytope target-body result."},{"cited_title":"Banaszczyk,Balancing vectors and Gaussian measures ofn-dimensional convex bodies, Random Structures & Algorithms12(1998), no","cited_arxiv_id":null,"evidence_quote":"Supplies the Gaussian-measure theorem giving the offline Euclidean balancing bound of order sqrt(ln(eT)) that the online result is compared against."}],"review_version":1}