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

Despite their many appealing properties, kernel methods are heavily affectedby the curse of dimensionality. For instance, in the case of inner productkernels in $\mathbb{R}^d$, the Reproducing Kernel Hilbert Space (RKHS) norm isoften very large for functions that depend strongly on a small subset ofdirections (ridge functions). Correspondingly, such functions are difficult tolearn using kernel methods. This observation has motivated the study ofgeneralizations of kernel methods, whereby the RKHS norm -- which is equivalentto a weighted $\ell_2$ norm -- is replaced by a weighted functional $\ell_p$norm, which we refer to as $\mathcal{F}_p$ norm. Unfortunately, tractability ofthese approaches is unclear. The kernel trick is not available and minimizingthese norms requires to solve an infinite-dimensional convex problem.  We study random features approximations to these norms and show that, for$p>1$, the number of random features required to approximate the originallearning problem is upper bounded by a polynomial in the sample size. Hence,learning with $\mathcal{F}_p$ norms is tractable in these cases. We introduce aproof technique based on uniform concentration in the dual, which can be ofbroader interest in the study of overparametrized models. For $p= 1$, ourguarantees for the random features approximation break down. We prove insteadthat learning with the $\mathcal{F}_1$ norm is $\mathsf{NP}$-hard under arandomized reduction based on the problem of learning halfspaces with noise.

Minimum complexity interpolation in random features models