Timezone: »

 
Poster
Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals
Ilias Diakonikolas · Daniel Kane · Lisheng Ren

Wed Jul 26 05:00 PM -- 06:30 PM (PDT) @ Exhibit Hall 1 #333
in Poster Session 4 »
We study the task of agnostically learning halfspaces under the Gaussian distribution. Specifically, given labeled examples $(\\mathbf{x},y)$ from an unknown distribution on $\\mathbb{R}^n \\times \\{\pm 1 \\}$, whose marginal distribution on $\\mathbf{x}$ is the standard Gaussian and the labels $y$ can be arbitrary, the goal is to output a hypothesis with 0-1 loss $\\mathrm{OPT}+\\epsilon$, where $\\mathrm{OPT}$ is the 0-1 loss of the best-fitting halfspace. We prove a near-optimal computational hardness result for this task, under the widely believed sub-exponential time hardness of the Learning with Errors (LWE) problem. Prior hardness results are either qualitatively suboptimal or apply to restricted families of algorithms. Our techniques extend to yield near-optimal lower bounds for related problems, including ReLU regression.
[ PDF] 

Author Information

Ilias Diakonikolas (University of Wisconsin-Madison)
Ilias Diakonikolas

Ilias Diakonikolas is a faculty member in the CS Department at UW Madison. He obtained a Diploma in electrical and computer engineering from the National Technical University of Athens and a Ph.D. in computer science from Columbia University. Before moving to UW, Ilias was Andrew and Erna Viterbi Early Career Chair at USC, and prior to that he spent two years at UC Berkeley as a Simons fellow in theoretical computer science. His research focuses on designing efficient algorithms for various fundamental problems in machine learning. Ilias is a recipient of a Sloan Fellowship, an NSF CAREER Award, a Google Faculty Research Award, a Marie Curie Fellowship, the best paper award at NeurIPS 2019, the IBM Research Pat Goldberg best paper award, and an honorable mention in the George Nicholson competition from the INFORMS society.

Daniel Kane (UCSD)
Lisheng Ren (University of Wisconsin-Madison Madison)

More from the Same Authors