Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userVC bounds on the cardinality of nearly orthogonal function classes
116
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We bound the number of nearly orthogonal vectors with fixed VC-dimension over $setpm^n$. Our bounds are of interest in machine learning and empirical process theory and improve previous bounds by Haussler. The bounds are based on a simple projection argument and the generalize to other product spaces. Along the way we derive tight bounds on the sum of binomial coefficients in terms of the entropy function.
rate research
Read More
If A is infinite and well-ordered, then |2^A|<=|Part(A)|<=|A^A|.
Let $H$ be a $k$-uniform $D$-regular simple hypergraph on $N$ vertices. Based on an analysis of the Rodl nibble, Alon, Kim and Spencer (1997) proved that if $k ge 3$, then $H$ contains a matching covering all but at most $ND^{-1/(k-1)+o(1)}$ vertices, and asked whether this bound is tight. In this paper we improve their bound by showing that for all $k > 3$, $H$ contains a matching covering all but at most $ND^{-1/(k-1)-eta}$ vertices for some $eta = Theta(k^{-3}) > 0$, when $N$ and $D$ are sufficiently large. Our approach consists of showing that the Rodl nibble process not only constructs a large matching but it also produces many well-distributed `augmenting stars which can then be used to significantly improve the matching constructed by the Rodl nibble process. Based on this, we also improve the results of Kostochka and Rodl (1998) and Vu (2000) on the size of matchings in almost regular hypergraphs with small codegree. As a consequence, we improve the best known bounds on the size of large matchings in combinatorial designs with general parameters. Finally, we improve the bounds of Molloy and Reed (2000) on the chromatic index of hypergraphs with small codegree (which can be applied to improve the best known bounds on the chromatic index of Steiner triple systems and more general designs).
How can $d+k$ vectors in $mathbb{R}^d$ be arranged so that they are as close to orthogonal as possible? In particular, define $theta(d,k):=min_Xmax_{x eq yin X}|langle x,yrangle|$ where the minimum is taken over all collections of $d+k$ unit vectors $Xsubseteqmathbb{R}^d$. In this paper, we focus on the case where $k$ is fixed and $dtoinfty$. In establishing bounds on $theta(d,k)$, we find an intimate connection to the existence of systems of ${k+1choose 2}$ equiangular lines in $mathbb{R}^k$. Using this connection, we are able to pin down $theta(d,k)$ whenever $kin{1,2,3,7,23}$ and establish asymptotics for general $k$. The main tool is an upper bound on $mathbb{E}_{x,ysimmu}|langle x,yrangle|$ whenever $mu$ is an isotropic probability mass on $mathbb{R}^k$, which may be of independent interest. Our results translate naturally to the analogous question in $mathbb{C}^d$. In this case, the question relates to the existence of systems of $k^2$ equiangular lines in $mathbb{C}^k$, also known as SIC-POVM in physics literature.
We provide a negative resolution to a conjecture of Steinke and Zakynthinou (2020a), by showing that their bound on the conditional mutual information (CMI) of proper learners of Vapnik--Chervonenkis (VC) classes cannot be improved from $d log n +2$ to $O(d)$, where $n$ is the number of i.i.d. training examples. In fact, we exhibit VC classes for which the CMI of any proper learner cannot be bounded by any real-valued function of the VC dimension only.
In this paper, we give a characterization of digraphs $Q, |Q|leq 4$ such that the associated Hecke-Kiselman monoid $H_Q$ is finite. In general, a necessary condition for $H_Q$ to be a finite monoid is that $Q$ is acyclic and its Coxeter components are Dynkin diagram. We show, by constructing examples, that such conditions are not sufficient.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
