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 investigate the complexity of training a two-layer ReLU neural networkwith weight decay regularization. Previous research has shown that the optimalsolution of this problem can be found by solving a standard cone-constrainedconvex program. Using this convex formulation, we prove that the hardness ofapproximation of ReLU networks not only mirrors the complexity of the Max-Cutproblem but also, in certain special cases, exactly corresponds to it. Inparticular, when $\epsilon\leq\sqrt{84/83}-1\approx 0.006$, we show that it isNP-hard to find an approximate global optimizer of the ReLU network objectivewith relative error $\epsilon$ with respect to the objective value. Moreover,we develop a randomized algorithm which mirrors the Goemans-Williamson roundingof semidefinite Max-Cut relaxations. To provide polynomial-time approximations,we classify training datasets into three categories: (i) For orthogonalseparable datasets, a precise solution can be obtained in polynomial-time. (ii)When there is a negative correlation between samples of different classes, wegive a polynomial-time approximation with relative error $\sqrt{\pi/2}-1\approx0.253$. (iii) For general datasets, the degree to which the problem can beapproximated in polynomial-time is governed by a geometric factor that controlsthe diameter of two zonotopes intrinsic to the dataset. To our knowledge, theseresults present the first polynomial-time approximation guarantees along withfirst hardness of approximation results for regularized ReLU networks.

Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes