cs.LGNov 7, 2026

Sharp Logarithmic-Product Bounds for List Replicability of Sign Matrices

Authors: Guangjian Zhang

Abstract

List replicability measures how many accurate hypotheses suffice to contain the output of a learning rule with arbitrarily high confidence. We prove that every nonempty class of mm binary concepts on nn domain points has list replicability at most 805ln⁡(2m)ln⁡(2n)805\ln(2m)\ln(2n). This resolves the logarithmic-product conjecture of Blondal, Hatami, Hatami, Lalov, and Tretiak. Hanner matrices give lower bounds of the same order, for square matrices and for explicit families with unequal logarithmic aspect ratios. The upper bound is obtained by constructing nested acyclic sets in the faces of a cube. A critical-point estimate supplies highly connected regions, weighted cell attachments keep the sets compatible across faces, and a cubical carrier theorem converts them into accurate finite covers and learning rules. Appending one constant coordinate turns list replicability into an exact geometric quantity, the face width, and graph-orientation classes satisfy exact product formulas. In particular, there are explicit classes with list replicability 4k+14k+1 and equivariant index 3k3k, so the additive gap between the two is unbounded. We also develop entropy-tilting and two-sided Gibbs constructions, give combinatorial upper bounds adapted to structured matrices, compute exact values on classical families, and study the index of Paley matrices.

Figures & tables

Explore similar work

Oct 14, 2026

A polylogarithmic bound for list replicability

Zhang [Zha26] recently posted a manuscript announcing that the list-replicability number of every class of M≥2M\ge 2 binary concepts on N≥2N\ge 2 domain points is O(log⁡2Mlog⁡N)O(\log^2 M\log N), which would be the first polylogarithmic upper bound on this quantity. In this note, we present a short, self-contained proof of this bound, following the high-level approach of the manuscript but with considerably simpler arguments.
Jun 16, 2026

Sign-Rank, Index, and List Replicability: Connections and Separations

In learning theory, the sign rank of a binary concept class captures the smallest dimension in which it can be represented by points and halfspaces. Despite tremendous interest, lower bounds on sign rank are notoriously difficult to come by. Two recent approaches to the problem establish lower bounds on sign rank by measures that are easier to analyze: the Z2\mathbb{Z}_2-index and the list replicability number. We order these measures, showing that the Z2\mathbb{Z}_2-index is upper-bounded by a linear function of the list replicability number. As a main consequence, we obtain a strong separation between sign rank and Z2\mathbb{Z}_2-index, thereby resolving a question of Frick, Hosseini, and Vasileuski. This motivates a thorough study of list replicability, the stronger of the two lower-bounding measures. We establish upper bounds on the list replicability number by two combinatorial measures: height and minimum star number. We also prove a fundamental composition result, showing that the product of two concept classes has list replicability number bounded by the sum of the list replicability numbers of the two classes.
Oct 23, 2026

Near-Optimal List Replicability from Littlestone Dimension

We study the list replicability number in the realizable PAC learning framework and prove that every concept class HH over a countable domain with Littlestone dimension dd and dual VC dimension v∗v^* satisfies LR(H)≤2O(dmin⁡{log⁡d,v∗}).\mathrm{LR}(H)\leq 2^{O(d\min\{\log d,v^*\})}. This matches the worst-case lower bound of 2Ω(d)2^{Ω(d)} up to a logarithmic factor in the exponent and exponentially improves the previous best upper bound LR(H)≤22O(d)\mathrm{LR}(H)\le 2^{2^{O(d)}} of Bun, Livni, and Moran [FOCS 2020]. Unlike earlier bounds of 2Oε(d2)2^{O_ε(d^2)} for fixed accuracy ε>0ε>0 implied by the work of Ghazi, Golowich, Kumar, and Manurangsi [STOC 2021] and Lyu [STOC 2026], our bound is independent of εε. The 2O(dlog⁡d)2^{O(d\log d)} bound follows from a new inductive framework for bounding list replicability that builds on the recent notion of irreducibility from differentially private learning. The 2O(dv∗)2^{O(dv^*)} bound follows from a simple globally stable learner that takes the majority vote of multiple empirical risk minimizers, with stability established using tools from stable regularity.