English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The increased availability of data in recent years has led several authors toask whether it is possible to use data as a {\em computational} resource. Thatis, if more data is available, beyond the sample complexity limit, is itpossible to use the extra examples to speed up the computation time required toperform the learning task?  We give the first positive answer to this question for a {\em naturalsupervised learning problem} --- we consider agnostic PAC learning ofhalfspaces over $3$-sparse vectors in $\{-1,1,0\}^n$. This class isinefficiently learnable using $O\left(n/\epsilon^2\right)$ examples. Our maincontribution is a novel, non-cryptographic, methodology for establishingcomputational-statistical gaps, which allows us to show that, under a widelybelieved assumption that refuting random $\mathrm{3CNF}$ formulas is hard, itis impossible to efficiently learn this class using only$O\left(n/\epsilon^2\right)$ examples. We further show that under strongerhardness assumptions, even $O\left(n^{1.499}/\epsilon^2\right)$ examples do notsuffice. On the other hand, we show a new algorithm that learns this classefficiently using $\tilde{\Omega}\left(n^2/\epsilon^2\right)$ examples. Thisformally establishes the tradeoff between sample and computational complexityfor a natural supervised learning problem.

More data speeds up training time in learning halfspaces over sparse vectors