Labeled sample compression schemes for complexes of oriented matroids

• URL: http://arxiv.org/abs/2110.15168v3
• Date: Wed, 19 Apr 2023 19:11:05 GMT
• Title: Labeled sample compression schemes for complexes of oriented matroids
• Abstract summary: We show that the topes of a complex of oriented matroids (abbreviated COM) of VC-dimension $d$ admit a proper labeled sample compression scheme of size $d$. This is a step towards the sample compression conjecture -- one of the oldest open problems in computational learning theory.
• Score: 0.04297070083645048
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show that the topes of a complex of oriented matroids (abbreviated COM) of VC-dimension $d$ admit a proper labeled sample compression scheme of size $d$. This considerably extends results of Moran and Warmuth on ample classes, of Ben-David and Litman on affine arrangements of hyperplanes, and of the authors on complexes of uniform oriented matroids, and is a step towards the sample compression conjecture -- one of the oldest open problems in computational learning theory. On the one hand, our approach exploits the rich combinatorial cell structure of COMs via oriented matroid theory. On the other hand, viewing tope graphs of COMs as partial cubes creates a fruitful link to metric graph theory.

Related papers

• Topological resolution of conical intersection seams and the coupled cluster bifurcation via mixed Hodge modules [0.0]
  Conical Intersections (CIs) is the central challenge of non-adiabatic quantum chemistry.<n>Standard Coupled Cluster (CC) theory suffers from root bifurcations near Ground State CIs.<n>We present textbfMorpheus, an open-source computational package that resolves these singularities.
  arXiv  Detail & Related papers  (2025-12-23T14:58:23Z)
• Pair Correlation Factor and the Sample Complexity of Gaussian Mixtures [0.0]
  We introduce the emphPair Correlation Factor (PCF), a geometric quantity capturing the clustering of component means.<n>Unlike the minimum gap, the PCF more accurately dictates the difficulty of parameter recovery.<n>In the uniform spherical case, we give an algorithm with improved sample complexity bounds, showing when more than the usual $epsilon-2$ samples are necessary.
  arXiv  Detail & Related papers  (2025-08-05T16:50:33Z)
• On Multiquantum Bits, Segre Embeddings and Coxeter Chambers [0.0]
  We develop a systematic study of qubit moduli spaces, illustrating the geometric structure of entanglement through hypercube constructions and Coxeter chamber decompositions. This reveals a structure underlying the hierarchy of embeddings, with direct implications for quantum error correction schemes. The symmetry of the Segre variety under the Coxeter group of type $A$ allows us to analyze quantum states and errors through the lens of reflection groups.
  arXiv  Detail & Related papers  (2025-02-01T15:39:28Z)
• GeoMix: Towards Geometry-Aware Data Augmentation [76.09914619612812]
  Mixup has shown considerable success in mitigating the challenges posed by limited labeled data in image classification. We propose Geometric Mixup (GeoMix), a simple and interpretable Mixup approach leveraging in-place graph editing.
  arXiv  Detail & Related papers  (2024-07-15T12:58:04Z)
• Gaussian Entanglement Measure: Applications to Multipartite Entanglement of Graph States and Bosonic Field Theory [50.24983453990065]
  An entanglement measure based on the Fubini-Study metric has been recently introduced by Cocchiarella and co-workers. We present the Gaussian Entanglement Measure (GEM), a generalization of geometric entanglement measure for multimode Gaussian states. By providing a computable multipartite entanglement measure for systems with a large number of degrees of freedom, we show that our definition can be used to obtain insights into a free bosonic field theory.
  arXiv  Detail & Related papers  (2024-01-31T15:50:50Z)
• SC-MAD: Mixtures of Higher-order Networks for Data Augmentation [36.33265644447091]
  The simplicial complex has inspired generalizations of graph neural networks (GNNs) to simplicial complex-based models. We propose data augmentation of simplicial complexes through both linear and nonlinear mixup mechanisms. We theoretically demonstrate that the resultant synthetic simplicial complexes interpolate among existing data with respect to homomorphism densities.
  arXiv  Detail & Related papers  (2023-09-14T06:25:39Z)
• Deep Learning Symmetries and Their Lie Groups, Algebras, and Subalgebras from First Principles [55.41644538483948]
  We design a deep-learning algorithm for the discovery and identification of the continuous group of symmetries present in a labeled dataset. We use fully connected neural networks to model the transformations symmetry and the corresponding generators. Our study also opens the door for using a machine learning approach in the mathematical study of Lie groups and their properties.
  arXiv  Detail & Related papers  (2023-01-13T16:25:25Z)
• A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC Dimension [6.522952386973185]
  This paper presents a construction of a proper and stable labelled sample compression scheme of size $O(VCD2)$ for any finite concept class.
  arXiv  Detail & Related papers  (2022-12-24T01:56:02Z)
• Complex Hyperbolic Knowledge Graph Embeddings with Fast Fourier Transform [29.205221688430733]
  The choice of geometric space for knowledge graph (KG) embeddings can have significant effects on the performance of KG completion tasks. Recent explorations of the complex hyperbolic geometry further improved the hyperbolic embeddings for capturing a variety of hierarchical structures. This paper aims to utilize the representation capacity of the complex hyperbolic geometry in multi-relational KG embeddings.
  arXiv  Detail & Related papers  (2022-11-07T15:46:00Z)
• Geometry Contrastive Learning on Heterogeneous Graphs [50.58523799455101]
  This paper proposes a novel self-supervised learning method, termed as Geometry Contrastive Learning (GCL) GCL views a heterogeneous graph from Euclidean and hyperbolic perspective simultaneously, aiming to make a strong merger of the ability of modeling rich semantics and complex structures. Extensive experiments on four benchmarks data sets show that the proposed approach outperforms the strong baselines.
  arXiv  Detail & Related papers  (2022-06-25T03:54:53Z)
• Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
  Simplicial complexes can be viewed as high dimensional generalizations of graphs that explicitly encode multi-way ordered relations. We propose a graph convolutional model for learning functions parametrized by the $k$-homological features of simplicial complexes.
  arXiv  Detail & Related papers  (2021-10-28T14:59:41Z)
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization [68.8204255655161]
  We show that the MARINA method of Gorbunov et al (2021) can be considered as a state-of-the-art method in terms of theoretical communication complexity. Theory of MARINA to support the theory of potentially em correlated compressors, extends to the method beyond the classical independent compressors setting.
  arXiv  Detail & Related papers  (2021-10-07T09:38:15Z)
• Large sample spectral analysis of graph-based multi-manifold clustering [3.383942690870476]
  We study statistical properties of graph-based algorithms for multi-manifold clustering (MMC) In MMC the goal is to retrieve the multi-manifold structure underlying a given Euclidean data set. We provide an example of a family of similarity graphs, which we call annular proximity graphs with angle constraints.
  arXiv  Detail & Related papers  (2021-07-28T19:39:12Z)
• Motif Learning in Knowledge Graphs Using Trajectories Of Differential Equations [14.279419014064047]
  Knowledge Graph Embeddings (KGEs) have shown promising performance on link prediction tasks. Many KGEs use the flat geometry which renders them incapable of preserving complex structures. We propose a neuro differential KGE that embeds nodes of a KG on the trajectories of Ordinary Differential Equations (ODEs)
  arXiv  Detail & Related papers  (2020-10-13T20:53:17Z)

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.