Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2503.15294 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915574482731008 |
|---|---|
| author | Blondal, Ari Hatami, Hamed Hatami, Pooya Lalov, Chavdar Tretiak, Sivan |
| author_facet | Blondal, Ari Hatami, Hamed Hatami, Pooya Lalov, Chavdar Tretiak, Sivan |
| contents | We prove that the list replicability number of $d$-dimensional $γ$-margin half-spaces satisfies \[ \frac{d}{2}+1 \le \mathrm{LR}(H^d_γ) \le d, \] which grows with dimension. This resolves several open problems:
$\bullet$ Every disambiguation of infinite-dimensional large-margin half-spaces to a total concept class has unbounded Littlestone dimension, answering an open question of Alon, Hanneke, Holzman, and Moran (FOCS '21).
$\bullet$ Every disambiguation of the Gap Hamming Distance problem in the large gap regime has unbounded public-coin randomized communication complexity. This answers an open question of Fang, Göös, Harms, and Hatami (STOC '25).
$\bullet$ There is a separation of $O(1)$ vs $ω(1)$ between randomized and pseudo-deterministic communication complexity.
$\bullet$ The maximum list-replicability number of any finite set of points and homogeneous half-spaces in $d$-dimensional Euclidean space is $d$, resolving a problem of Chase, Moran, and Yehudayoff (FOCS '23).
$\bullet$ There exists a partial concept class with Littlestone dimension $1$ such that all its disambiguations have infinite Littlestone dimension. This resolves a problem of Cheung, H. Hatami, P. Hatami, and Hosseini (ICALP '23).
Our lower bound follows from a topological argument based on a local Borsuk-Ulam theorem. For the upper bound, we construct a list-replicable learning rule using the generalization properties of SVMs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_15294 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces Blondal, Ari Hatami, Hamed Hatami, Pooya Lalov, Chavdar Tretiak, Sivan Machine Learning We prove that the list replicability number of $d$-dimensional $γ$-margin half-spaces satisfies \[ \frac{d}{2}+1 \le \mathrm{LR}(H^d_γ) \le d, \] which grows with dimension. This resolves several open problems: $\bullet$ Every disambiguation of infinite-dimensional large-margin half-spaces to a total concept class has unbounded Littlestone dimension, answering an open question of Alon, Hanneke, Holzman, and Moran (FOCS '21). $\bullet$ Every disambiguation of the Gap Hamming Distance problem in the large gap regime has unbounded public-coin randomized communication complexity. This answers an open question of Fang, Göös, Harms, and Hatami (STOC '25). $\bullet$ There is a separation of $O(1)$ vs $ω(1)$ between randomized and pseudo-deterministic communication complexity. $\bullet$ The maximum list-replicability number of any finite set of points and homogeneous half-spaces in $d$-dimensional Euclidean space is $d$, resolving a problem of Chase, Moran, and Yehudayoff (FOCS '23). $\bullet$ There exists a partial concept class with Littlestone dimension $1$ such that all its disambiguations have infinite Littlestone dimension. This resolves a problem of Cheung, H. Hatami, P. Hatami, and Hosseini (ICALP '23). Our lower bound follows from a topological argument based on a local Borsuk-Ulam theorem. For the upper bound, we construct a list-replicable learning rule using the generalization properties of SVMs. |
| title | Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2503.15294 |