Higher-arity PAC learning, VC dimension and packing lemma

• URL: http://arxiv.org/abs/2510.02420v2
• Date: Wed, 15 Oct 2025 10:06:15 GMT
• Title: Higher-arity PAC learning, VC dimension and packing lemma
• Abstract summary: This note overviews some of our work in Chernikov, Towsner'20 (arXiv:2010.00726) developing higher arity VC theory (VC$_n$ dimension)<n>We also point out how some of the recent results in arXiv:2402.14294, arXiv:2505.15688, arXiv:2509.20404 follow from our work in arXiv:2010.00726.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The aim of this note is to overview some of our work in Chernikov, Towsner'20 (arXiv:2010.00726) developing higher arity VC theory (VC$_n$ dimension), including a generalization of Haussler packing lemma, and an associated tame (slice-wise) hypergraph regularity lemma; and to demonstrate that it characterizes higher arity PAC learning (PAC$_n$ learning) in $n$-fold product spaces with respect to product measures introduced by Kobayashi, Kuriyama and Takeuchi'15. We also point out how some of the recent results in arXiv:2402.14294, arXiv:2505.15688, arXiv:2509.20404 follow from our work in arXiv:2010.00726.

Related papers

• $\mathbb{SL}(n)$ Representation Learning: An Intrinsic Mixed-Curvature Space with Higher Curvature Capacities and Deeper Order-Aware Composition [47.80325814873361]
  Mixed-curvature representation learning seeks to capture rich geometric structures that cannot be adequately modeled by a single curvature regime.<n>We introduce the $mathbbSL(n)$ space, a representation geometry defined by the simple $det(A)variant=1$ constraint and a left in Schatten-$p$ structure.<n>Despite this minimal construction, $mathbbSL(n)$ exhibits pointwise negative, zero, and flag curvature around a common flagpole.
  arXiv  Detail & Related papers  (2026-09-14T05:52:14Z)
• Tangent classes of matroids and wonderful compactifications [0.8138288420049126]
  We produce an integral tangent class $T_M,mathcalGmathbbZin K_mathbbZ(M,mathcalG)$ in the realizable case.<n>It recovers the Hilbert series of the Chow ring through Hirzebruch--Riemann--Roch, and it satisfies the expected Chern-alpha lower bounds.
  arXiv  Detail & Related papers  (2026-07-07T04:56:22Z)
• An Optimal Sauer Lemma Over $k$-ary Alphabets [46.089126569274676]
  We show that the Sauer-Shelah-Perles Lemma bounds are suboptimal for alphabet sizes $k>2$.<n>Our bound is tight for every size $k$, list size $ell$, and dimension value, replacing the exponential dependence on $ell$ in the Natarajan-based bound.<n>In contrast to the classical case, we are not aware of any purely proof in the DS setting.
  arXiv  Detail & Related papers  (2026-04-14T16:50:38Z)
• Uniform Laws of Large Numbers in Product Spaces [60.22626971185653]
  We study uniform convergence phenomena in cartesian product spaces.<n>We show that a uniform law of large numbers holds for a family of events if and only if the linear VC dimension of the family is finite.
  arXiv  Detail & Related papers  (2026-03-25T16:36:09Z)
• The Sample Complexity of Replicable Realizable PAC Learning [20.81839572366504]
  We show a sample complexity lower bound with a close to $(log|H|)3/2$ dependence on the size of the hypothesis class $H$.<n>Our proof uses several novel techniques and works by defining a particular Cayley graph associated with $H$.
  arXiv  Detail & Related papers  (2026-02-23T06:52:11Z)
• Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back [84.81507553557556]
  We show that multiclass PAC sample complexity is governed by two distinct dimensions.<n>Unlike binary or online classification, multiclass learning inherently involves two structural parameters.<n>A key ingredient is a novel online procedure based on a self-adaptive multiplicative-weights algorithm performing a label-space reduction.
  arXiv  Detail & Related papers  (2025-11-16T15:47:47Z)
• A packing lemma for VCN${}_k$-dimension and learning high-dimensional data [1.6114012813668932]
  We prove that non-agnostic high-arity PAC learnability implies a high-arity version of the Haussler packing property.<n>This is done by obtaining direct proofs that classic PAC learnability implies classic Haussler packing property.
  arXiv  Detail & Related papers  (2025-05-21T16:03:12Z)
• Sparsity dependence of Krylov state complexity in the SYK model [0.0]
  We study the Krylov state complexity of the Sachdev-Ye-Kitaev (SYK) model for $N le 28$ Majorana fermions with $q$-body fermion interaction.<n>We find that the peak value of complexity does not change as we increase $k$ beyond $k ge k_textmin$ at large temperatures.
  arXiv  Detail & Related papers  (2024-07-30T05:57:14Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(varepsilon,delta)$PAC version of the problem.
  arXiv  Detail & Related papers  (2024-06-18T08:54:04Z)
• Dimension-free discretizations of the uniform norm by small product sets [45.85600902330814]
  A classical inequality of Bernstein compares the supremum norm of $f$ over the unit circle to its supremum norm over the sampling set of the $K$-th roots of unity.<n>We show that dimension-free discretizations are possible with sampling sets whose cardinality is independent of $deg(f)$ and is instead governed by the maximum individual degree of $f$.
  arXiv  Detail & Related papers  (2023-10-11T22:46:09Z)
• Provable Advantage in Quantum PAC Learning [3.291862617649511]
  We show that PAC learners can achieve a generic advantage in quantum learning. Up to polylogarithmic factors, this is a square root improvement over the classical learning sample complexity.
  arXiv  Detail & Related papers  (2023-09-19T19:26:20Z)
• The Sample Complexity of Multi-Distribution Learning for VC Classes [25.73730126599202]
  Multi-distribution learning is a generalization of PAC learning to settings with multiple data distributions. There remains a significant gap between the known upper and lower bounds for PAC-learnable classes. We discuss recent progress on this problem and some hurdles that are fundamental to the use of game dynamics in statistical learning.
  arXiv  Detail & Related papers  (2023-07-22T18:02:53Z)
• Prediction, Learning, Uniform Convergence, and Scale-sensitive Dimensions [39.97534972432276]
  We present a new general-purpose algorithm for learning classes of $[0,1]$-valued functions. We prove a general upper bound on the expected absolute error of this algorithm. We show how to apply both packing bounds to obtain improved general bounds on the sample complexity of learning.
  arXiv  Detail & Related papers  (2023-04-21T15:51:35Z)
• Find a witness or shatter: the landscape of computable PAC learning [63.26015736148707]
  This paper contributes to the study of CPAC learnability by solving three open questions from recent papers. Firstly, we prove that every CPAC learnable class is contained in a class which is properly CPAC learnable with a sample complexity. Secondly, we show that there exists a decidable class of hypothesis which is properly learnable, but only with uncomputably fast growing sample complexity.
  arXiv  Detail & Related papers  (2023-02-06T02:52:36Z)
• Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
  We show a new way to relate functions on the hypergrid to their harmonic extensions over the polytorus. We show the supremum of a function $f$ over products of the cyclic group $exp(2pi i k/K)_k=1K$. We extend to new spaces a recent line of work citeEI22, CHP, VZ22 that gave similarly efficient methods for learning low-degrees on hypercubes and observables on qubits.
  arXiv  Detail & Related papers  (2023-01-04T04:15:40Z)
• A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks [99.46182575751271]
  We derive generalization bounds for the two primary classes of graph neural networks (GNNs) Our result reveals that the maximum node degree and spectral norm of the weights govern the generalization bounds of both models.
  arXiv  Detail & Related papers  (2020-12-14T16:41:23Z)
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
  We study the problem of learning one-hidden-layer ReLU networks with $k$ hidden units on $mathbbRd$ under Gaussian marginals. For the case of positive coefficients, we give the first-time algorithm for this learning problem for $k$ up to $tildeOOmega(sqrtlog d)$.
  arXiv  Detail & Related papers  (2020-06-22T17:53:54Z)
• The VC-Dimension of Axis-Parallel Boxes on the Torus [0.0]
  We show that the VC-dimension of the family of $d$-dimensional axis, boxes and cubes are bothparallelally $d log_2(d)$. This is especially surprising as the VC-dimension usually grows linearly with $d$ in similar settings.
  arXiv  Detail & Related papers  (2020-04-28T21:41:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.