- Arnab Bhattacharyya: Hardne...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in May 2017
Arnab Bhattacharyya: Hardness of Learning Noisy Halfspaces Using Polynomial Thresholds
Speaker:
Arnab Bhattacharyya
, IISc
Date: Thursday, May 11, 2017
Time: 2:00 PM to 3:00 PM Note: all times are in the Eastern Time Zone
Public: Yes
Location: 32-G575
Event Type:
Room Description:
Host: Pritish Kamath and Akshay Degwekar, CSAIL MIT
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
Speaker URL: None
Speaker Photo:
None
Reminders to:
seminars@csail.mit.edu, theory-seminars@csail.mit.edu
Reminder Subject:
TALK: Arnab Bhattacharyya: Hardness of Learning Noisy Halfspaces Using Polynomial Thresholds
Abstract:
We prove the hardness of weakly learning halfspaces in the presence of adversarial noise using polynomial threshold functions (PTFs), assuming Khot's Unique Games Conjecture (UGC). In particular, we prove that for any constants d in? the positive integers? and eps > 0, assuming the UGC, it is NP-hard to decide: given a set of {-1,1}-labeled points in R^n whether (YES Case) there exists a halfspace that classifies (1-eps)-fraction of the points correctly, or (NO Case) any degree-d PTF classifies at most (1/2 + eps)-fraction of the points correctly.
This strengthens to all constant degrees the previous NP-hardness of learning using degree-2 PTFs shown by Diakonikolas et al. (2011). The latter result had remained the only progress over the works of Feldman et al. (2006) and Guruswami et al. (2006) ruling out weakly proper learning adversarially noisy halfspaces.
Joint work with Suprovat Ghoshal (IISc) and Rishi Saket (IBM).
Research Areas:
Impact Areas:
Created by Rebecca Yadegar at Monday, May 08, 2017 at 1:18 PM.