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

We study non-convex empirical risk minimization for learning halfspaces andneural networks. For loss functions that are $L$-Lipschitz continuous, wepresent algorithms to learn halfspaces and multi-layer neural networks thatachieve arbitrarily small excess risk $\epsilon>0$. The time complexity ispolynomial in the input dimension $d$ and the sample size $n$, but exponentialin the quantity $(L/\epsilon^2)\log(L/\epsilon)$. These algorithms run multiplerounds of random initialization followed by arbitrary optimization steps. Wefurther show that if the data is separable by some neural network with constantmargin $\gamma>0$, then there is a polynomial-time algorithm for learning aneural network that separates the training data with margin $\Omega(\gamma)$.As a consequence, the algorithm achieves arbitrary generalization error$\epsilon>0$ with ${\rm poly}(d,1/\epsilon)$ sample and time complexity. Weestablish the same learnability result when the labels are randomly flippedwith probability $\eta<1/2$.

Learning Halfspaces and Neural Networks with Random Initialization