Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise

Explore a 49-minute lecture on the computational complexity of adversarially robust proper learning of halfspaces in the distribution-independent agnostic PAC model, focusing on L_p perturbations. Delve into the findings presented by Pasin Manurangasi of Google Thailand at IPAM's EnCORE Workshop on Computational vs Statistical Gaps in Learning and Optimization. Discover the computationally efficient learning algorithm and nearly matching computational hardness result for this problem. Examine the interesting implication that the L_8 perturbations case is provably computationally harder than the case 2 = p 8. Learn about the joint work with Ilias Diakonikolas and Daniel M. Kane in this informative presentation recorded on February 27, 2024.

Pasin Manurangasi - Complex Adversarially Robust Proper Learning of Halfspaces w/ Agnostic Noise