{"id":3631,"date":"2025-05-07T07:02:30","date_gmt":"2025-05-07T07:02:30","guid":{"rendered":"https:\/\/mailitics.com\/index.php\/2025\/05\/07\/2505-03223\/"},"modified":"2025-05-07T07:02:30","modified_gmt":"2025-05-07T07:02:30","slug":"2505-03223","status":"publish","type":"post","link":"https:\/\/mailitics.com\/index.php\/2025\/05\/07\/2505-03223\/","title":{"rendered":"Lower Bounds for Greedy Teaching Set Constructions"},"content":{"rendered":"

Lower Bounds for Greedy Teaching Set Constructions
\n \t

\n
<\/BR>
\n
\n \t

\n
<\/BR><\/p>\n

arXiv:2505.03223v1 Announce Type: new
\nAbstract: A fundamental open problem in learning theory is to characterize the best-case teaching dimension $operatorname{TS}_{min}$ of a concept class $mathcal{C}$ with finite VC dimension $d$. Resolving this problem will, in particular, settle the conjectured upper bound on Recursive Teaching Dimension posed by [Simon and Zilles; COLT 2015]. Prior work used a natural greedy algorithm to construct teaching sets recursively, thereby proving upper bounds on $operatorname{TS}_{min}$, with the best known bound being $O(d^2)$ [Hu, Wu, Li, and Wang; COLT 2017]. In each iteration, this greedy algorithm chooses to add to the teaching set the $k$ labeled points that restrict the concept class the most. In this work, we prove lower bounds on the performance of this greedy approach for small $k$. Specifically, we show that for $k = 1$, the algorithm does not improve upon the halving-based bound of $O(log(|mathcal{C}|))$. Furthermore, for $k = 2$, we complement the upper bound of $Oleft(log(log(|mathcal{C}|))right)$ from [Moran, Shpilka, Wigderson, and Yuhudayoff; FOCS 2015] with a matching lower bound. Most consequentially, our lower bound extends up to $k le lceil c d rceil$ for small constant $c>0$: suggesting that studying higher-order interactions may be necessary to resolve the conjecture that $operatorname{TS}_{min} = O(d)$.<\/div>\n

\t

\n
<\/BR>
\n Spencer Compton, Chirag Pabbaraju, Nikita Zhivotovskiy
\n \t

\n
<\/BR>
\nGo to original source<\/a>
\n \t

\n
<\/BR><\/p>\n","protected":false},"excerpt":{"rendered":"

Lower Bounds for Greedy Teaching Set Constructions arXiv:2505.03223v1 Announce Type: new Abstract: A fundamental open problem in learning theory is to characterize the best-case teaching dimension $operatorname{TS}_{min}$ of a concept class $mathcal{C}$ with finite VC dimension $d$. Resolving this problem will, in particular, settle the conjectured upper bound on Recursive Teaching Dimension posed by [Simon […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[62,413,113,2064,112],"tags":[1760,2589,2588],"class_list":["post-3631","post","type-post","status-publish","format-standard","hentry","category-aimldsaimlds","category-cs-ds","category-cs-lg","category-math-co","category-stat-ml","tag-bound","tag-lower","tag-teaching"],"_links":{"self":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/3631"}],"collection":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/comments?post=3631"}],"version-history":[{"count":0,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/3631\/revisions"}],"wp:attachment":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/media?parent=3631"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/categories?post=3631"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/tags?post=3631"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}