5 papers
Smoothed Agnostic Learning of Halfspaces over the Hypercube
Yiwen Kou, Raghu Meka
Agnostic learning of Boolean halfspaces is a fundamental problem in computational learning theory, but it is known to be computationally hard even for weak learning. Recent work [C…
Discrepancy Beyond Additive Functions with Applications to Fair Division
Alexandros Hollender, Pasin Manurangsi, Raghu Meka +1
We consider a setting where we have a ground set together with real-valued set functions , and the goal is to partition into two sets such that $…
Tight Lower Bound for Multicolor Discrepancy
Pasin Manurangsi, Raghu Meka
We prove the following asymptotically tight lower bound for -color discrepancy: For any , there exists a hypergraph with hyperedges such that its -color discrep…
On Convex Optimization with Semi-Sensitive Features
Badih Ghazi, Pritish Kamath, Ravi Kumar +3
We study the differentially private (DP) empirical risk minimization (ERM) problem under the semi-sensitive DP setting where only some features are sensitive. This generalizes the…
Learning Neural Networks with Sparse Activations
Pranjal Awasthi, Nishanth Dikkala, Pritish Kamath +1
A core component present in many successful neural network architectures, is an MLP block of two fully connected layers with a non-linear activation in between. An intriguing pheno…