CS Paper Radar

Fourth-Moment Geometry of Rademacher Sums

Peigan Gao, Jian Qian

cs.LG math.PR ·submitted 2026-08-18 14:03 UTC · v1

Abstract

Let $\varepsilon_1,\ldots,\varepsilon_n$ be independent Rademacher signs and let $a=(a_1,\ldots,a_n)\in\R^n$ satisfy the normalization below. For the normalized Rademacher sum, we determine how its higher moments depend on the fourth-order mass. Combining a sharp fixed-q moment envelope with a separate argument below the convexity threshold gives the Gaussian stability inequality for the full range $p\geq4$ of this linear-in-q bound. The same fourth-order framework determines the sharp finite dimensional $L_p/L_4$ Khintchine constant for $p\geq5$, with the flat coefficient vector as the extremizer. These results settle the conjectures of Jakimiuk and of Barański, Murawski, Nayar, and Oleszkiewicz stated below. We also prove Jakimiuk's conjectured quadratic stability estimate at $p=3$. The resulting bounds retain information about sparsity and effective dimension, with applications to Rademacher random projections and randomly signed errors; those applications are not developed further here. Their Laplace-transform form also gives coefficient-sensitive tail bounds. The proofs are discovered with substantial assistance from ChatGPT 5.6 Sol.

Closest papers

Nearest neighbours by meaning across the whole index.

Gaussian Approximation in Wasserstein-p: Markovian Martingale Differences and Stochastic Approximation

cs.LG math.PRstat.ML ·2026-09-08 ·Yixuan Zhang, Qiaomin Xie
similarity 0.60
Abstract · 46 pages. Revised and expanded version with new applications to Markovian stochastic approximation

We establish nonasymptotic Gaussian approximation bounds in higher-order Wasserstein distance $W_p$, $p\geq2$, for deterministic matrix-weighted sums of multivariate Poisson martingale differences generated by uniformly ergodic Markov chains. Under an $L^{(2+η)p}$-moment condition, $η>0$, we obtain the explicit bound $$O\left(p^3\|A\|_4^2+pd^{1/4}\|A\|_2^{1/2}\|A\|_4^2\right),$$ where $A\in\mathbb{R}^n$ collects the moment sizes of the weighted increments. When these sizes are of order $n^{-1/2}$, the bound achieves the first optimal $O(n^{-1/2})$ rate for fixed $p$ and $d$. Consequently, we also obtain the first optimal $O(n^{-1/2})$ $W_p$ Gaussian approximation rate for multivariate additive functionals of uniformly ergodic Markov chains. Our analysis develops two techniques for addressing the interplay between higher-order Wasserstein distance and temporal dependence. First, building on the Ornstein--Uhlenbeck relative-score approach of Fang and Koike (2023), we formulate the bound in terms of antisymmetric Stein couplings while retaining the conditional tensor structure. Second, we develop a refresh-then-maximal coupling that combines an independent first-step resampling, which preserves the desired Stein identity, with a subsequent maximal coupling that provides effective control of the coupling increment. We apply these bounds to nonlinear Markovian stochastic approximation by decomposing normalized errors into matrix-weighted Poisson martingale sums and remainders. This yields the first sharp $W_p$ Gaussian approximation rates for both last iterates and Polyak--Ruppert averages. In particular, the optimized rates are $O(n^{-1/3})$ for polynomial-stepsize last iterates and $O(n^{-1/4})$ for Polyak--Ruppert averages, with an $O(n^{-1/2})$ rate for harmonic-stepsize last iterates under an additional spectral condition.

0.55

Nearly Optimal Strong Coresets for $\ell_p$ Subspace Approximation

cs.DS ·2026-08-26 ·Honghao Lin, Vahab Mirrokni, David P. Woodruff
theory similarity 0.55
Abstract

We study strong coresets for $\ell_p$ subspace approximation. Given a matrix $A\in\mathbb{R}^{n\times d}$, the goal is to sample and rescale a small number of its rows to obtain $SA$ such that $\left\|SA(I-P_F)\right\|_{p,2}^p=(1\pm\varepsilon)\left\|A(I-P_F)\right\|_{p,2}^p$ simultaneously for every subspace $F\subseteq\mathbb{R}^d$ of dimension at most $k$, where $P_F$ is the orthogonal projector onto $F$. Woodruff and Yasuda [WY25] (FOCS 2025) obtained coreset sizes $\widetilde{O}_p(k\varepsilon^{-4/p})$ for $1\leq p<2$ and $\widetilde{O}_p(k^{p/2}\varepsilon^{-p})$ for $p>2$. We improve these bounds to $\widetilde{O}_p(k\varepsilon^{-2})$ and $\widetilde{O}_p(k^{p/2}\varepsilon^{-2})$, respectively. For $1\leq p<2$, our algorithm runs in $\widetilde{O}_p(\mathrm{nnz}(A)+d^ω+k\varepsilon^{-2})$ time. The resulting coreset size matches the sampling lower bound [LWW21] up to logarithmic factors when $k+1\geq C\log(1/\varepsilon)$ for an absolute constant $C$. For $p>2$, our algorithm runs in $\widetilde{O}_p(\mathrm{nnz}(A)+d^ω)$ time, matching the running time of the framework of Woodruff and Yasuda. We use different techniques in the two regimes. For $1\leq p<2$, we combine a bicriteria low-rank split with Lewis-weight sampling and empirical-process bounds independent of the output dimension. For $p>2$, we give a sharper analysis of the Woodruff-Yasuda construction. By retaining the truncation in its sampling probabilities throughout the row-count recurrence, we show that it achieves the improved $\varepsilon^{-2}$ dependence.

0.25

Three Standard Deviations Suffice While One Does Not

cs.DM math.CO ·2026-09-28 ·Victor Reis, Zhao Song
theory similarity 0.54
Abstract · 15 pages

Spencer's 1985 ``six standard deviations suffice'' theorem shows that every $A \in [-1,1]^{n \times n}$ has a sign vector $x \in \{-1,1\}^n$ with $\|Ax\|_\infty \le 6\sqrt{n}$. We show the upper bound $\sqrt{3\operatorname{arsinh}(10)}\sqrt{n}+4 < 2.9992 \sqrt{n} + 4$ by directly rounding the minimizer of a potential function to a vertex of the cube. We also show that, for every power of two $n \ge 2^{50}$, there exists a matrix $A \in \{-1,1\}^{n \times n}$ such that $\|Ax\|_\infty >1.0000002\sqrt{n}$ for every choice of signs $x \in \{-1,1\}^n$. The construction simply replaces a $2^{-22}$ fraction of the columns of a Hadamard matrix with independent random sign vectors. This is the first improvement over the $\sqrt{n}$ lower bound of Olson and Spencer (1978), which uses a Hadamard matrix.

0.11

Centered Permutation Prefixes for SGD with Random Reshuffling: Sharp Rates, Hölder Geometry, and Composite Proximal Extensions

cs.LG math.OC ·2026-09-04 ·Jiaxiang Li
theory similarity 0.53
Abstract

We study stochastic gradient descent with random reshuffling for finite sums \[ F(x)=\frac1n\sum_{i=1}^n f_i(x). \] For fresh reshuffling with a constant component stepsize, if each $f_i$ has an $L$-Lipschitz gradient and the average $F$ is $μ$-strongly convex with a Lipschitz-continuous Hessian, we prove the last-epoch rate \[ \mathbb E[F(y_K)-F(x_\star)] =\widetilde O\!\left(T^{-2}+n^2T^{-3}\right), \qquad T=nK, \] matching the known quadratic lower bound in its $(n,K)$-dependence. The components may be nonconvex, and no componentwise Hessian continuity or separate bounded-iterate assumption is required. More generally, a $ν$-Hölder-continuous average Hessian adds only $\widetilde O(n^{1+ν}T^{-2-2ν})$, so every $ν\ge 1/2$ preserves the quadratic rate. Under convex components, a decreasing-stepsize result removes the large-epoch requirement and recovers the same two-term scale once $nK$ exceeds the condition-number scale. We also analyze epoch-wise ProxRR for $\mathcal P=F+ψ$. Writing $x^\dagger$ for the composite minimizer and $β_\star=\|\nabla F(x^\dagger)\|$, we prove \[ \mathbb E\|y_K-x^\dagger\|^2 =\widetilde O\!\left( \frac{β_\star^2}{K^2} +T^{-2}+n^2T^{-3} +n^{1+ν}T^{-2-2ν} \right). \] For $ν\ge 1/2$, we show that the $β_\star^2/K^2$ splitting term is unavoidable and obtain a matching lower bound up to logarithms in the stated constant-stepsize regime.

0.24

A Hyperplane Bound and Ward's Divisibility Conjecture

cs.IT ·2026-10-19 ·Guanghui Zhang
theoryhot direction similarity 0.53
Abstract · 31 pages

Let $q=p^f$, where $p$ is prime. We prove that every $q$-ary linear code meeting the Griesmer bound, with positive dimension and minimum distance $d\ge1$, is $p^{\max\{0,ν_p(d)-f+1\}}$-divisible, as asserted in Ward's conjecture. Arbitrary projective column multiplicities are allowed. The geometric ingredient is a bound independent of dimension: a nonzero scalar-invariant function $F:\mathbb{F}_q^k\to\mathbb{F}_p$, with $F(0)=0$ and prime-field algebraic degree at most $(f+s)(p-1)$, vanishes identically on at most $p^s(q-1)$ linear hyperplanes when $0\le s<f$. A truncated digit-sum inequality forces selected coefficient polynomials to be homogeneous of ordinary degree less than $q$. Weighted moments on a projective line then bound their linear factors, while a second-moment argument handles the complementary support configuration. An elementary finite-difference calculation supplies the degree bound for divided weight residues. Endpoint shortenings prove the basic divisibility layers; endpoint lifting, a surjective linear functional, and residual-code induction extend the argument to every valuation. We include the proofs of the classical ingredients, identify their sources, and distinguish the present argument from an earlier reported unpublished proof.

0.52

The half-rate linear programming bound for binary codes is $\frac12-\frac1π$

cs.IT math.CO ·2026-09-03 ·Andrew Salmon
theory similarity 0.52
Abstract · 33 pages

In their work on sphere packing and the modular bootstrap, Afkhami-Jeddi, Cohn, Hartman, de Laat, and Tajdini conjectured the exact high-dimensional exponent of the Cohn-Elkies sphere-packing linear program. OpenAI's Chapter 1 subsequently proved their conjecture by establishing that both Fourier sign-uncertainty radii are $(1/π+o(1))\sqrt d$. We prove the binary coding analogue: \[ R_D\!\left(\frac12-\frac1π\right)=\frac12. \] We also formulate the two Krawtchouk sign-uncertainty problems and determine both of their asymptotics. If $A^{\mathrm K}_{\pm}(n)$ denotes the smallest radius $r$ for which a nonzero Krawtchouk $(\pm1)$-eigenfunction $f$ exists with $f(0) = 0$ and $f(x) \ge 0$ for all $|x| \ge r$, then \[ \frac{A^{\mathrm K}_{\pm}(n)}n\longrightarrow \frac12-\frac1π. \] The lower bound proves a mass-concentration principle similar to OpenAI's Chapter 1 for Hamming space. The upper bound, on the other hand, follows the approach of the spherical-code construction in OpenAI's Chapter 2. Gay, Jeronimo, and Liu formulated a hierarchy for binary codes analogous to the spherical-code construction and improved the best known binary coding rate bounds by evaluating the first level of the corresponding hierarchy. We prove this hierarchy bounds the Delsarte program and give a construction at arbitrarily deep levels of the hierarchy, attaining the upper bound in the limit. The construction uses an $N$-qubit generalization of the pure-state channel of Alrabiah and Guruswami.

0.52

The determinantal complexity of the 4*4 permanent is 15

cs.CC ·2026-11-04 ·Karthik Sheshadri
theory similarity 0.52
Abstract · 8 pages

The best known lower bound on the determinantal complexity of the 4x4 permanent is 10. In this short note, I prove that this value is exactly 15: the 4x4 permanent is the determinant of a 15x15 matrix of affine linear forms, and cannot be that of any smaller matrix. To do so, I must establish both a lower and upper bound. To establish the upper bound, I use Grenet's construction of size 2^n-1. Hence that construction is optimal at n=4 (and n=3). This now constitutes the first knwon exact value of the determinantal complexity of the permanent at n=4. Only the value at n=3 was exactly known, prior to this note. The general quadratic bound only gives 8 for n=4. To establish the lower bound, I work from a normal form at a zero of the permanent. In the first row (and column) of the normal form, the linear forms vanish on a linear space inside the singular locus of the permanent. A hessian inequality bounds the size of the matrix in terms of that space. Then, a matrix of sie 14 foces the space into any of nine corordinate types. The forcing is either up to symmetry, or else into a family that degenerates to one of them. I then rule out every case. All involved computations are exact. In respect of the claim, I have made all certificates public.

0.25

Improving the Constant in the Aharonov--Regev Theorem

cs.CC ·2026-10-07 ·Shuhong Gao
theory similarity 0.52
Abstract

The Aharonov-Regev proof that $\mathrm{GapCVP}_{c\sqrt n}$ lies in $\mathsf{NP}\cap \mathsf{coNP}$ uses a verifier that tests dual lattice vectors; its proof gives $c=100$. We study this verifier through a linear program in which a certificate is modeled as a sample from a probability distribution on the dual lattice. This viewpoint gives an exact analysis of the close-target tests: adding gradient and Hessian checks increases the certified close radius from $σ^{-1}/4$ to $σ^{-1}\sqrt{3/16}$, and higher derivatives cannot improve it within this framework. With Gaussian certificates for far targets, we obtain $$\mathrm{GapCVP}_{c\sqrt n},\ \mathrm{GapSVP}_{c\sqrt n}\in \mathsf{NP} \cap\mathsf{coNP}$$ for every $c>2/(π\sqrt3)\approx0.3676$. An appendix gives a finite-bit implementation of the verifier. We also show that the Gaussian certificate is not always optimal and solve the unbounded-support program exactly for targets of order two, where its value is determined by the spectral capacity of an odd dual coset.

0.21