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

Many conventional learning algorithms rely on loss functions other than thenatural 0-1 loss for computational efficiency and theoretical tractability.Among them are approaches based on absolute loss (L1 regression) and squareloss (L2 regression). The first is proved to be an \textit{agnostic} PAClearner for various important concept classes such as \textit{juntas}, and\textit{half-spaces}. On the other hand, the second is preferable because ofits computational efficiency, which is linear in the sample size. However, PAClearnability is still unknown as guarantees have been proved only underdistributional restrictions. The question of whether L2 regression is anagnostic PAC learner for 0-1 loss has been open since 1993 and yet has to beanswered.  This paper resolves this problem for the junta class on the Boolean cube --proving agnostic PAC learning of k-juntas using L2 polynomial regression.Moreover, we present a new PAC learning algorithm based on the Boolean Fourierexpansion with lower computational complexity. Fourier-based algorithms, suchas Linial et al. (1993), have been used under distributional restrictions, suchas uniform distribution. We show that with an appropriate change, one can applythose algorithms in agnostic settings without any distributional assumption. Weprove our results by connecting the PAC learning with 0-1 loss to the minimummean square estimation (MMSE) problem. We derive an elegant upper bound on the0-1 loss in terms of the MMSE error and show that the sign of the MMSE is a PAClearner for any concept class containing it.

Agnostic PAC Learning of k-juntas Using L2-Polynomial Regression