اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدVC bounds on the cardinality of nearly orthogonal function classes
133
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 ar
e Dynkin diagram. We show, by constructing examples, that such conditions are not sufficient.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
