Active Local Learning
Active Local Learning
复制标题
积极的本地学习
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Neha Gupta
中科院分区：
文献类型：
--
作者：
A. Backurs;Avrim Blum;Neha Gupta
In this work we consider active local learning: given a query point $x$, and active access to an unlabeled training set $S$, output the prediction $h(x)$ of a near-optimal $h \in H$ using significantly fewer labels than would be needed to actually learn $h$ fully. In particular, the number of label queries should be independent of the complexity of $H$, and the function $h$ should be well-defined, independent of $x$. This immediately also implies an algorithm for distance estimation: estimating the value $opt(H)$ from many fewer labels than needed to actually learn a near-optimal $h \in H$, by running local learning on a few random query points and computing the average error.
For the hypothesis class consisting of functions supported on the interval $[0,1]$ with Lipschitz constant bounded by $L$, we present an algorithm that makes $O(({1 / \epsilon^6}) \log(1/\epsilon))$ label queries from an unlabeled pool of $O(({L / \epsilon^4})\log(1/\epsilon))$ samples. It estimates the distance to the best hypothesis in the class to an additive error of $\epsilon$ for an arbitrary underlying distribution. We further generalize our algorithm to more than one dimensions. We emphasize that the number of labels used is independent of the complexity of the hypothesis class which depends on $L$. Furthermore, we give an algorithm to locally estimate the values of a near-optimal function at a few query points of interest with number of labels independent of $L$.
We also consider the related problem of approximating the minimum error that can be achieved by the Nadaraya-Watson estimator under a linear diagonal transformation with eigenvalues coming from a small range. For a $d$-dimensional pointset of size $N$, our algorithm achieves an additive approximation of $\epsilon$, makes $\tilde{O}({d}/{\epsilon^2})$ queries and runs in $\tilde{O}({d^2}/{\epsilon^{d+4}}+{dN}/{\epsilon^2})$ time.
In this work we consider active local learning: given a query point $x$, and active access to an unlabeled training set $S$, output the prediction $h(x)$ of a near-optimal $h \in H$ using significantly fewer labels than would be needed to actually learn $h$ fully. In particular, the number of label queries should be independent of the complexity of $H$, and the function $h$ should be well-defined, independent of $x$. This immediately also implies an algorithm for distance estimation: estimating the value $opt(H)$ from many fewer labels than needed to actually learn a near-optimal $h \in H$, by running local learning on a few random query points and computing the average error.
For the hypothesis class consisting of functions supported on the interval $[0,1]$ with Lipschitz constant bounded by $L$, we present an algorithm that makes $O(({1 / \epsilon^6}) \log(1/\epsilon))$ label queries from an unlabeled pool of $O(({L / \epsilon^4})\log(1/\epsilon))$ samples. It estimates the distance to the best hypothesis in the class to an additive error of $\epsilon$ for an arbitrary underlying distribution. We further generalize our algorithm to more than one dimensions. We emphasize that the number of labels used is independent of the complexity of the hypothesis class which depends on $L$. Furthermore, we give an algorithm to locally estimate the values of a near-optimal function at a few query points of interest with number of labels independent of $L$.
We also consider the related problem of approximating the minimum error that can be achieved by the Nadaraya-Watson estimator under a linear diagonal transformation with eigenvalues coming from a small range. For a $d$-dimensional pointset of size $N$, our algorithm achieves an additive approximation of $\epsilon$, makes $\tilde{O}({d}/{\epsilon^2})$ queries and runs in $\tilde{O}({d^2}/{\epsilon^{d+4}}+{dN}/{\epsilon^2})$ time.
登录
查看更多内容
通过稀疏化改进集覆盖的局部计算算法
DOI：
10.1137/1.9781611975994.181
发表时间：
2020
期刊：
ACM-SIAM Symposium on Discrete Algorithms (SODA 2020
影响因子：
--
作者：
Grunau, C.;Mitrovic, S.;Rubinfeld, R.;Vakilian, A.
通讯作者：
Vakilian, A.
论在亚线性时间内求解线性系统
DOI：
--
发表时间：
2019
期刊：
Innovations in Theoretical Computer Science
影响因子：
--
作者：
Andoni, Alexandr;Krauthgamer, Robert;Pogrow, Yosef
通讯作者：
Pogrow, Yosef
主动耐受测试
DOI：
--
发表时间：
2018
期刊：
Proceedings of the 31st Conference On Learning Theory
影响因子：
--
作者：
Blum, Avrim;Hu, Lunjia
通讯作者：
Hu, Lunjia
Spanner 的本地计算算法
DOI：
--
发表时间：
2019
期刊：
Innovations in Theoretical Computer Science (ITCS
影响因子：
--
作者：
Parter, Merav;Rubinfeld, Ronitt;Vakilian, Ali;Yodpinyanee, Anak
通讯作者：
Yodpinyanee, Anak
DOI：
--
发表时间：
2018-05
期刊：
--
影响因子：
--
作者：
Weihao Kong;G. Valiant
通讯作者：
Weihao Kong;G. Valiant