arXiv research

Combinatorial dimensions play an important role in the theory of machine learning. For example, VC dimension characterizes PAC learning, SQ dimension characterizes weak learning with statistical queries, and Littlestone dimension characterizes online learning. In this paper we aim to develop combinatorial dimensions th…

This article deals with the generalization performance of margin multi-category classifiers, when minimal learnability hypotheses are made. In that context, the derivation of a guaranteed risk is based on the handling of capacity measures belonging to three main families: Rademacher/Gaussian complexities, metric entrop…

Proves a conjecture for 3D Artin groups using new combinatorial curvature.

New method classifies spinor orbits in dimensions up to 14.

In 1976, Dodziuk and Patodi employed Whitney forms to define a combinatorial codifferential operator on cochains, and they raised the question whether it is consistent in the sense that for a smooth enough differential form the combinatorial codifferential of the associated cochain converges to the exterior codifferent…

We investigate slicings of combinatorial manifolds as properly embedded co-dimension 1 submanifolds. A focus is given to dimension 3 where slicings are normal surfaces. In the case of 2-neighborly 3-manifolds and quadrangulated slicings, a lower bound on the number of quadrilaterals of normal surfaces depending on the …

Study on Vapnik-Chervonenkis dimension of product intervals in R^d.

Finite subdivision rules in high dimensions can be difficult to visualize and require complex topological structures to be constructed explicitly. In many applications, only the history graph is needed. We characterize the history graph of a subdivision rule, and define a combinatorial subdivision rule based on such gr…

Characterizes learnability of forgiving 0-1 loss functions in multiclass settings.

Every closed oriented PL 4-manifold is a branched cover of the 4-sphere branched over a PL-surface with finitely many singularities by Piergallini [Topology 34(3):497-508, 1995]. This generalizes a long standing result by Hilden and Montesinos to dimension four. Izmestiev and Joswig [Adv. Geom. 3(2):191-225, 2003] gave…

In this article, we discuss the quasiconformal structure of boundaries of right-angled hyperbolic buildings using combinatorial tools. In particular we exhibit some examples of buildings of dimension 3 and 4 whose boundaries satisfy the combinatorial Loewner property. This property is a weak version of the Loewner prop…

We study quasi-isometry invariants of Gromov hyperbolic spaces, focussing on the l_p-cohomology and closely related invariants such as the conformal dimension, combinatorial modulus, and the Combinatorial Loewner Property. We give new constructions of continuous l_p-cohomology, thereby obtaining information about the l…

Characterizes the sample complexity of list regression tasks.

Study improves online learning with adaptable agents in various settings.

If a real value invariant of compact combinatorial manifolds (with or without boundary) depends only on the number of simplices in each dimension on the manifold, then the invariant is completely determined by Euler characteristics of the manifold and its boundary. So essentially, Euler characteristic is the unique inv…

It is shown that for any piecewise-linear closed orientable manifold of odd dimension there exists an invariantly defined metric on the determinant line of cohomology with coefficients in an arbitrary flat bundle E over the manifold (E is not required to be unimodular). The construction of this metric (called Poincare …

Let $M$ be an $n$-vertex combinatorial triangulation of a $\ZZ_2$-homology $d$-sphere. In this paper we prove that if $n \leq d + 8$ then $M$ must be a combinatorial sphere. Further, if $n = d + 9$ and $M$ is not a combinatorial sphere then $M$ can not admit any proper bistellar move. Existence of a 12-vertex triangula…

New fractal spaces not quasisymmetric to Loewner spaces discovered.

This paper gives a combinatorial description of spin and spin^c-structures on triangulated PL-manifolds of arbitrary dimension. These formulations of spin and spin^c-structures are established primarily for the purpose of aiding in computations. The novelty of the approach is we rely heavily on the naturality of binary…

Thompson Sampling shows polynomial regret for combinatorial semi-bandits with subgaussian rewards.

We define Discrete Quasi-Einstein metrics (DQE-metrics) as the critical points of discrete total curvature functional on triangulated 3-manifolds. We study DQE-metrics by introducing some combinatorial curvature flows. We prove that these flows produce solutions which converge to discrete quasi-Einstein metrics when th…

New Sauer inequality improves multiclass hypothesis class bounds.

The Vapnik-Chervonenkis (VC) dimension of a collection of subsets of a set is an important combinatorial concept in settings such as discrete geometry and machine learning. In this paper we prove that the VC dimension of the family of $d$-dimensional cubes in $\mathbb R^d$ is $\lfloor(3d+1)/2\rfloor$.

Study apple tasting feedback in online binary classification, providing new insights into minimax expected mistakes.

Tight triangulations are exotic, but highly regular objects in combinatorial topology. A triangulation is tight if all its piecewise linear embeddings into a Euclidean space are as convex as allowed by the topology of the underlying manifold. Tight triangulations are conjectured to be strongly minimal, and proven to be…

This paper investigates stochastic and adversarial combinatorial multi-armed bandit problems. In the stochastic setting under semi-bandit feedback, we derive a problem-specific regret lower bound, and discuss its scaling with the dimension of the decision space. We propose ESCB, an algorithm that efficiently exploits t…

New algorithms for neural bandits learn from context and arm features.

This article defines a pair of combinatorial operations on the combinatorial structure of compact right-angled hyperbolic polyhedra in dimension three called decomposition and edge surgery. It is shown that these operations simplify the combinatorics of such a polyhedron, while keeping it within the class of right-angl…

Characterizes statistical complexity of realizable regression in PAC and online learning.

A combinatorial version of Yamabe flow is presented based on Euclidean triangulations coming from sphere packings. The evolution of curvature is then derived and shown to satisfy a heat equation. The Laplacian in the heat equation is shown to be a geometric analogue of the Laplacian of Riemannian geometry, although the…

In a recent work [2] with Datta, we introduced the mu vector (with respect to a given field) of simplicial complexes and used it to study tightness and lower bounds. In this paper, we modify the definition of mu vectors. With the new definition, most results of [2] become correct without the hypothesis of 2-neighbourli…

In this paper we extend the classical theory of combinatorial manifolds to the non-homogeneous setting. NH-manifolds are polyhedra which are locally like Euclidean spaces of varying dimensions. We show that many of the properties of classical manifolds remain valid in this wider context. NH-manifolds appear naturally w…

Hyperbolic embeddings offer excellent quality with few dimensions when embedding hierarchical data structures like synonym or type hierarchies. Given a tree, we give a combinatorial construction that embeds the tree in hyperbolic space with arbitrarily low distortion without using optimization. On WordNet, our combinat…

A new method reduces both input and output dimensions for better goal-oriented analysis.

The paper classifies compact hyperbolic Coxeter polytopes and improves upper bounds.

Bayesian optimization method tackles combinatorial spaces, scalable for large data.

New equivalence relation for links using cut-diagrams.

In graph theory there are intimate connections between the expansion properties of a graph and the spectrum of its Laplacian. In this paper we define a notion of combinatorial expansion for simplicial complexes of general dimension, and prove that similar connections exist between the combinatorial expansion of a compl…

Moment-angle manifolds provide a wide class of examples of non-Kaehler compact complex manifolds. A complex moment-angle manifold Z is constructed via certain combinatorial data, called a complete simplicial fan. In the case of rational fans, the manifold Z is the total space of a holomorphic bundle over a toric variet…

BIG Laplacians bridge combinatorial and Hodge Laplacians for discrete data.

Automorphisms and subdivisions of Helly graphs are studied, leading to explicit models and rational translation lengths.

It is well known that the Euler characteristic of an odd dimensional compact manifold is zero. An Euler complex is a combinatorial analogue of a compact manifold. We present here an elementary proof of the corresponding result for Euler complexes.

The one-skeleton of a G-manifold M is the set of points p in M where $\dim G_p \geq \dim G -1$; and M is a GKM manifold if the dimension of this one-skeleton is 2. Goresky, Kottwitz and MacPherson show that for such a manifold this one-skeleton has the structure of a ``labeled" graph, $(Γ, α)$, and that the equivariant…

In a previous paper the second author showed that if $M$ is a pseudomanifold with complementarity other than the 6-vertex real projective plane and the 9-vertex complex projective plane, then $M$ must have dimension $\geq 6$, and - in case of equality - $M$ must have exactly 12 vertices. In this paper we prove that suc…

The spaces of Sp(n)-, Sp(n)U(1)- and Sp(n)Sp(1)- invariant, translation invariant, continuous convex valuations on the quaternionic vector space H^n are studied. Combinatorial dimension formulas involving Young diagrams and Schur polynomials are proved.

The article provides formulas for the number of terms in connected sums of sphere products associated with dual-neighborly polytopes.

Tightness of a triangulated manifold is a topological condition, roughly meaning that any simplexwise linear embedding of the triangulation into euclidean space is "as convex as possible". It can thus be understood as a generalization of the concept of convexity. In even dimensions, super-neighborliness is known to be …

With a compact PL manifold X we associate a category T(X). The objects of T(X) are all combinatorial manifolds of type X, and morphisms are combinatorial assemblies. We prove that the homotopy equivalence BT (X) \approx BPL(X) holds, where PL(X) is the simplicial group of PL-homeomorphisms. Thus the space BT(X) is a ca…