Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2310.15411 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916330606690304 |
|---|---|
| author | Li, Yinan Zhang, Chicheng |
| author_facet | Li, Yinan Zhang, Chicheng |
| contents | We study the problem of computationally and label efficient PAC active learning $d$-dimensional halfspaces with Tsybakov Noise~\citep{tsybakov2004optimal} under structured unlabeled data distributions. Inspired by~\cite{diakonikolas2020learning}, we prove that any approximate first-order stationary point of a smooth nonconvex loss function yields a halfspace with a low excess error guarantee. In light of the above structural result, we design a nonconvex optimization-based algorithm with a label complexity of $\tilde{O}(d (\frac{1}ε)^{\frac{8-6α}{3α-1}})$, under the assumption that the Tsybakov noise parameter $α\in (\frac13, 1]$, which narrows down the gap between the label complexities of the previously known efficient passive or active algorithms~\citep{diakonikolas2020polynomial,zhang2021improved} and the information-theoretic lower bound in this setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_15411 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach Li, Yinan Zhang, Chicheng Machine Learning We study the problem of computationally and label efficient PAC active learning $d$-dimensional halfspaces with Tsybakov Noise~\citep{tsybakov2004optimal} under structured unlabeled data distributions. Inspired by~\cite{diakonikolas2020learning}, we prove that any approximate first-order stationary point of a smooth nonconvex loss function yields a halfspace with a low excess error guarantee. In light of the above structural result, we design a nonconvex optimization-based algorithm with a label complexity of $\tilde{O}(d (\frac{1}ε)^{\frac{8-6α}{3α-1}})$, under the assumption that the Tsybakov noise parameter $α\in (\frac13, 1]$, which narrows down the gap between the label complexities of the previously known efficient passive or active algorithms~\citep{diakonikolas2020polynomial,zhang2021improved} and the information-theoretic lower bound in this setting. |
| title | Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2310.15411 |