cs.LGAug 18, 2026

Fourth-Moment Geometry of Rademacher Sums

Authors: Peigan Gao, Jian Qian

Organizations: The University of Hong Kong.

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Let ε1,…,εn\varepsilon_1,\ldots,\varepsilon_n be independent Rademacher signs and let a=(a1,…,an)∈Rna=(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≥4p\geq4 of this linear-in-q bound. The same fourth-order framework determines the sharp finite dimensional Lp/L4L_p/L_4 Khintchine constant for p≥5p\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=3p=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.

Explore similar work

CardsList
Aug 10, 2026

Logarithmic-Free Moment and Generalization Bounds for Uniformly Stable Algorithms

Uniform stability is a classical tool for controlling the generalization error of a learning algorithm. Bousquet, Klochkov, and Zhivotovskiy (2020) showed that the problem can be reduced to a moment inequality for a sum of weakly interacting functions of independent random variables. Their bound contains an additional factor log⁡n\log n, and they asked whether this factor can be removed. We answer this upper-bound question affirmatively. More specifically, let Z=(Z1,…,Zn)Z=(Z_1,\ldots,Z_n) have independent coordinates and let gi(Z)g_i(Z) satisfy E[gi(Z)∣Z−i]=0, ∣E[gi(Z)∣Zi]∣≤M, for every i=1,…,n,\mathbb E[g_i(Z)\mid Z_{-i}]=0, \ \left| \mathbb E[g_i(Z)\mid Z_i]\right|\le M, \ \text{for every } i = 1, \dots, n, where Z−iZ_{-i} denotes all coordinates except ZiZ_i. Assume additionally that changing any coordinate ZjZ_j, j≠ij\neq i, changes gig_i by at most ββ, we prove that, for every p≥2p\ge2, for every p≥2p\ge2, ∥∑i=1ngi(Z)∥p≤16pnβ+M2pn.\left\| \sum_{i=1}^n g_i(Z)\right\|_p \le 16pnβ+M\sqrt{2pn}. This removes the log⁡n\log n factor from the previous bound and matches the lower bound of Bousquet, Klochkov, and Zhivotovskiy up to universal constants in the range covered by their construction. Our proof first establishes the required estimate on the Rademacher cube, then transfers it to arbitrary product distributions by a two-copy randomization argument.

Thanh Nguyen-Cung, Binh T. Nguyen

VinUniversity

Algorithmic StabilityStatistical Learning TheoryGeneralization Bounds
AskPDF
May 6, 2026

Grokability in five inequalities

In this note, we report five mathematical discoveries made in collaboration with Grok, all of which have been subsequently verified by the authors. These include an improved lower bound on the maximal Gaussian perimeter of convex sets in Rn\mathbb{R}^n, sharper L2L_2-L1L_1 moment comparison inequalities on the Hamming cube {−1,1}n\{-1,1\}^n, a strengthened autoconvolution inequality, improved asymptotic bounds on the size of the largest gg-Sidon sets in {1,…,n}\{1,\dots,n\}, and an optimal balanced Szarek's inequality.

Paata Ivanisvili, Xinyuan Xie

University of California, Irvine

AI-Assisted Mathematical Discovery
AskPDF
Jun 5, 2026

Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite LpL_p Moments

While algorithmic stability is a central tool for understanding generalization of learning algorithms, existing high-probability guarantees typically rely on uniform boundedness or sub-Gaussian/sub-Weibull tail assumptions, which can be overly restrictive for modern settings with heavy-tailed or unbounded losses. We develop a stability-based framework that requires only a finite LpL_p moment condition. Our first contribution is sharp concentration inequalities for functions of independent random variables under LpL_p constraints, extending McDiarmid's bounded-differences techniques beyond the classical regime. Leveraging these results, we derive sharp high-probability generalization bounds across a range of learning paradigms, including empirical risk minimization, transductive regression, and meta-learning. These guarantees show that LpL_p stability suffices for robust generalization even when boundedness fails, substantially weakening the standard assumptions in the stability literature.

Qianqian Lei, Soham Bonnerjee, Yuefeng Han +1

Department of Statistics, The University of Chicago, Chicago, IL 60637, USA. · Department of Applied and Computational Mathematics and Statistics, University of Notre Dame, Notre Dame, IN 46556, USA.

Algorithmic StabilityGeneralization Bounds
AskPDF