A packing lemma for VCN${}_k$-dimension and learning high-dimensional data

• URL: http://arxiv.org/abs/2505.15688v1
• Date: Wed, 21 May 2025 16:03:12 GMT
• Title: A packing lemma for VCN${}_k$-dimension and learning high-dimensional data
• Abstract summary: 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.
• Score: 1.6114012813668932
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, the authors introduced the theory of high-arity PAC learning, which is well-suited for learning graphs, hypergraphs and relational structures. In the same initial work, the authors proved a high-arity analogue of the Fundamental Theorem of Statistical Learning that almost completely characterizes all notions of high-arity PAC learning in terms of a combinatorial dimension, called the Vapnik--Chervonenkis--Natarajan (VCN${}_k$) $k$-dimension, leaving as an open problem only the characterization of non-partite, non-agnostic high-arity PAC learnability. In this work, we complete this characterization by proving that non-partite non-agnostic high-arity PAC learnability implies a high-arity version of the Haussler packing property, which in turn implies finiteness of VCN${}_k$-dimension. This is done by obtaining direct proofs that classic PAC learnability implies classic Haussler packing property, which in turn implies finite Natarajan dimension and noticing that these direct proofs nicely lift to high-arity.

Related papers

• Partial Skeleton Visibility for Action Recognition: A Constrained Field-of-View Approach [60.596944437968524]
  PartialVisGraph is a novel framework for robust skeleton-based action recognition under constrained field-of-view.<n>It consistently achieves state-of-the-art accuracy under partial visibility, with gains of up to 68.8% on subsets with severe FoV restrictions.<n>Our approach offers a principled and practical pathway toward deployable skeleton-based action understanding in unconstrained environments.
  arXiv  Detail & Related papers  (2026-07-01T10:03:11Z)
• Strategic PAC Learnability via Geometric Definability [69.34283267701421]
  Strategic classification studies learning settings in which individuals can modify their features, at a cost, in order to influence the classifier's decision.<n>A central question is how the sample complexity of the induced (strategic) hypothesis class depends on the complexities of the underlying hypothesis class and the cost structure governing feasible manipulations.<n>We introduce structure via a geometric definability assumption: both the hypothesis class and the cost-induced neighborhood relation can be defined by first-order formulas over $mathbbR_mathttexp$.<n>We prove that learnability is preserved, with sample complexity controlled by the complexity
  arXiv  Detail & Related papers  (2026-05-13T12:21:56Z)
• Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness [63.833913892018536]
  We study sequential decision making under distributional adversaries that can adaptively choose data-generating distributions from a fixed family $U$.<n>We provide a near complete characterization of families $U$ that admit learnability in terms of a notion known as generalized smoothness.<n>We show that the generalized smoothness also characterizes private learnability under distributional constraints.
  arXiv  Detail & Related papers  (2026-02-24T06:15:59Z)
• Neural Paging: Learning Context Management Policies for Turing-Complete Agents [9.896253083170066]
  We introduce textitNeural Paging, a hierarchical architecture that decouples symbolic reasoning from information resource management.<n>We provide theoretical analysis showing that, under bounded context window size$K$, Neural Paging reduces the complexity of long-horizon reasoning from quadratic $O(N2)$ to $O(N cdot K2)$.
  arXiv  Detail & Related papers  (2026-02-11T22:35:08Z)
• 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)
• Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning [0.0]
  We study computable probably approximately correct (CPAC) learning, where learners are required to be computable functions.<n>Recent works recovered analogs of the Fundamental Theorem in the computable setting.
  arXiv  Detail & Related papers  (2025-11-04T15:12:38Z)
• Higher-arity PAC learning, VC dimension and packing lemma [0.0]
  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.
  arXiv  Detail & Related papers  (2025-10-02T15:54:50Z)
• Towards Efficient Contrastive PAC Learning [6.209600119671225]
  We study contrastive learning under the PAC learning framework.<n>In this paper, we consider contrastive learning of the fundamental concept of linear representations.<n>We establish guarantees based on Rademacher complexity, and connect it to PAC guarantees under certain contrastive large-margin conditions.
  arXiv  Detail & Related papers  (2025-02-21T21:51:01Z)
• Is Transductive Learning Equivalent to PAC Learning? [0.9012198585960443]
  We show that the PAC and transductive models are essentially equivalent for agnostic binary classification. We leave as an intriguing open question whether our second result can be extended beyond binary classification to show the transductive and PAC models equivalent more broadly.
  arXiv  Detail & Related papers  (2024-05-08T16:26:49Z)
• High-arity PAC learning via exchangeability [1.6114012813668932]
  We develop a theory of high-arity PAC learning, which is statistical learning in the presence of "structured correlation" Our main theorems establish a high-arity (agnostic) version of the fundamental theorem of statistical learning.
  arXiv  Detail & Related papers  (2024-02-22T05:16:04Z)
• Towards Continual Learning Desiderata via HSIC-Bottleneck Orthogonalization and Equiangular Embedding [55.107555305760954]
  We propose a conceptually simple yet effective method that attributes forgetting to layer-wise parameter overwriting and the resulting decision boundary distortion. Our method achieves competitive accuracy performance, even with absolute superiority of zero exemplar buffer and 1.02x the base model.
  arXiv  Detail & Related papers  (2024-01-17T09:01:29Z)
• Relative intrinsic dimensionality is intrinsic to learning [49.5738281105287]
  We introduce a new notion of the intrinsic dimension of a data distribution, which precisely captures the separability properties of the data. For this intrinsic dimension, the rule of thumb above becomes a law: high intrinsic dimension guarantees highly separable data. We show thisRelative intrinsic dimension provides both upper and lower bounds on the probability of successfully learning and generalising in a binary classification problem.
  arXiv  Detail & Related papers  (2023-10-10T10:41:45Z)
• Optimal Learners for Realizable Regression: PAC Learning and Online Learning [52.37726841759983]
  We aim to characterize the statistical complexity of realizable regression both in the PAC learning setting and the online learning setting. We first introduce a minimax instance optimal learner for realizable regression and propose a novel dimension that both qualitatively and quantitatively characterizes which classes of real-valued predictors are learnable. In the context of online learning we provide a dimension that characterizes the minimax optimal instance optimal cumulative loss up to a constant factor and design an optimal online learner for realizable regression.
  arXiv  Detail & Related papers  (2023-07-07T21:39:25Z)
• Multiclass Boosting: Simple and Intuitive Weak Learning Criteria [72.71096438538254]
  We give a simple and efficient boosting algorithm, that does not require realizability assumptions. We present a new result on boosting for list learners, as well as provide a novel proof for the characterization of multiclass PAC learning.
  arXiv  Detail & Related papers  (2023-07-02T19:26:58Z)
• Understanding Augmentation-based Self-Supervised Representation Learning via RKHS Approximation and Regression [53.15502562048627]
  Recent work has built the connection between self-supervised learning and the approximation of the top eigenspace of a graph Laplacian operator. This work delves into a statistical analysis of augmentation-based pretraining.
  arXiv  Detail & Related papers  (2023-06-01T15:18:55Z)
• Large-scale Pre-trained Models are Surprisingly Strong in Incremental Novel Class Discovery [76.63807209414789]
  We challenge the status quo in class-iNCD and propose a learning paradigm where class discovery occurs continuously and truly unsupervisedly. We propose simple baselines, composed of a frozen PTM backbone and a learnable linear classifier, that are not only simple to implement but also resilient under longer learning scenarios.
  arXiv  Detail & Related papers  (2023-03-28T13:47:16Z)
• Confident Sinkhorn Allocation for Pseudo-Labeling [40.883130133661304]
  Semi-supervised learning is a critical tool in reducing machine learning's dependence on labeled data. This paper studies theoretically the role of uncertainty to pseudo-labeling and proposes Confident Sinkhorn Allocation (CSA) CSA identifies the best pseudo-label allocation via optimal transport to only samples with high confidence scores.
  arXiv  Detail & Related papers  (2022-06-13T02:16:26Z)
• A Characterization of Multiclass Learnability [18.38631912121182]
  We characterize multiclass PAC learnability through the DS dimension, a dimension defined by Daniely and Shalev-Shwartz 2014. In the list learning setting, instead of predicting a single outcome for a given unseen input, the goal is to provide a short menu of predictions. Our second main result concerns the Natarajan dimension, which has been a central candidate for characterizing multiclass learnability.
  arXiv  Detail & Related papers  (2022-03-03T07:41:54Z)
• A General Framework for the Practical Disintegration of PAC-Bayesian Bounds [2.516393111664279]
  We introduce new PAC-Bayesian generalization bounds that have the originality to provide disintegrated bounds. Our bounds are easily optimizable and can be used to design learning algorithms.
  arXiv  Detail & Related papers  (2021-02-17T09:36:46Z)
• The Polynomial Method is Universal for Distribution-Free Correlational SQ Learning [9.036124518750732]
  Generalizing Malach and Shalev-Shwartz (2022) that gave tight correlational SQ (CSQ) lower bounds for learning formulas. Lower bounds on the threshold or approximate degree of any function class directly imply CSQ lower bounds for PAC or DNF learning.
  arXiv  Detail & Related papers  (2020-10-22T17:55:26Z)
• CSNE: Conditional Signed Network Embedding [77.54225346953069]
  Signed networks encode positive and negative relations between entities such as friend/foe or trust/distrust. Existing embedding methods for sign prediction generally enforce different notions of status or balance theories in their optimization function. We introduce conditional signed network embedding (CSNE) Our probabilistic approach models structural information about the signs in the network separately from fine-grained detail.
  arXiv  Detail & Related papers  (2020-05-19T19:14:52Z)

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.