The VC-dimension of k-vertex d-polytopes

• URL: http://arxiv.org/abs/2004.04841v2
• Date: Mon, 13 Apr 2020 21:44:18 GMT
• Title: The VC-dimension of k-vertex d-polytopes
• Abstract summary: We show that the VC-dimension of the class of $k$-vertex polytopes in $mathbb Rd$ is at most $8d2klogk$, answering an old question of Long and Warmuth.
• Score: 1.0660480034605242
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this short note, we show that the VC-dimension of the class of $k$-vertex polytopes in $\mathbb R^d$ is at most $8d^2k\log_2k$, answering an old question of Long and Warmuth.

Related papers

• 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)
• Low-degree Lower bounds for clustering in moderate dimension [53.03724383992195]
  We study the fundamental problem of clustering $n$ points into $K$ groups drawn from a mixture of isotropic Gaussians in $mathbbRd$.<n>We show that while the difficulty of clustering for $n leq dK$ is driven by dimension reduction and spectral methods, the moderate-dimensional regime involves more delicate phenomena leading to a "non-optimal rate"<n>We provide a novel non-spectral algorithm matching this rate, shedding new light on the computational limits of the clustering problem in moderate dimension.
  arXiv  Detail & Related papers  (2026-02-26T14:03:55Z)
• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibria is a powerful and flexible framework at the heart of online learning and game theory. We show that an efficient online algorithm incurs average $Phi$-regret at most $epsilon$ using $textpoly(d, k)/epsilon2$ rounds. We also show nearly matching lower bounds in the online setting, thereby obtaining for the first time a family of deviations that captures the learnability of $Phi$-regret.
  arXiv  Detail & Related papers  (2025-02-25T19:08:26Z)
• Dimension-free Remez Inequalities and norm designs [48.5897526636987]
  A class of domains $X$ and test sets $Y$ -- termed emphnorm -- enjoy dimension-free Remez-type estimates. We show that the supremum of $f$ does not increase by more than $mathcalO(log K)2d$ when $f$ is extended to the polytorus.
  arXiv  Detail & Related papers  (2023-10-11T22:46:09Z)
• Higher rank antipodality [2.7309692684728617]
  Motivated by general probability theory, we say that the set $S$ in $mathbbRd$ is emphantipodal of rank $k$. We show that this problem can be connected to a classical question in computer science on finding perfect hashes.
  arXiv  Detail & Related papers  (2023-07-31T17:15:46Z)
• 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)
• Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
  We provide a systematic treatment of boundaries based on subgroups $Ksubseteq G$ with the Kitaev quantum double $D(G)$ model in the bulk. The boundary sites are representations of a $*$-subalgebra $Xisubseteq D(G)$ and we explicate its structure as a strong $*$-quasi-Hopf algebra. As an application of our treatment, we study patches with boundaries based on $K=G$ horizontally and $K=e$ vertically and show how these could be used in a quantum computer
  arXiv  Detail & Related papers  (2022-08-12T15:05:07Z)
• Optimally compressing VC classes [0.0]
  Resolving a conjecture of Littlestone and Warmuth, we show that any concept class of VC-dimension $d$ has a sample compression scheme of size $d$.
  arXiv  Detail & Related papers  (2022-01-11T18:56:08Z)
• Eluder Dimension and Generalized Rank [48.27338656415236]
  We show that eluder dimension can be exponentially larger than $sigma$-rank. When $sigma$ is the $mathrmrelu$ activation, we show that eluder dimension can be exponentially larger than $sigma$-rank.
  arXiv  Detail & Related papers  (2021-04-14T16:53:13Z)
• Binary strings of finite VC dimension [0.0]
  In this paper we investigate subsets named by a predicate $P$ such that the relation $P(x+y)$ has finite VC dimension. We prove that strings of bounded VC dimension are meagre in the topology of the reals, provide simple rules for bounding the VC dimension of a string, and show that the bi-infinite strings of VC dimension $d$ are a non-so shift space.
  arXiv  Detail & Related papers  (2021-01-16T17:51:52Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
  arXiv  Detail & Related papers  (2020-12-14T18:14:08Z)
• A deep network construction that adapts to intrinsic dimensionality beyond the domain [79.23797234241471]
  We study the approximation of two-layer compositions $f(x) = g(phi(x))$ via deep networks with ReLU activation. We focus on two intuitive and practically relevant choices for $phi$: the projection onto a low-dimensional embedded submanifold and a distance to a collection of low-dimensional sets.
  arXiv  Detail & Related papers  (2020-08-06T09:50:29Z)
• 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.