67 citations · 419 across the 35 of their papers we have counts for
36 papers
Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions
Satwik Bhattamishra, Arkil Patel, Varun Kanade +1
Despite the widespread success of Transformers on NLP tasks, recent works have found that they struggle to model several formal languages when compared to recurrent models. This ra…
When are Local Queries Useful for Robust Learning?
Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska +1
Distributional assumptions have been shown to be necessary for the robust learnability of concept classes when considering the exact-in-the-ball robust risk and access to random ex…
Partial Matrix Completion
Elad Hazan, Adam Tauman Kalai, Varun Kanade +2
The matrix completion problem aims to reconstruct a low-rank matrix based on a revealed set of possibly noisy entries. Prior works consider completing the entire matrix with genera…
Beyond Impossibility: Balancing Sufficiency, Separation and Accuracy
Limor Gultchin, Vincent Cohen-Addad, Sophie Giffard-Roisin +2
Among the various aspects of algorithmic fairness studied in recent years, the tension between satisfying both \textit{sufficiency} and \textit{separation} -- e.g. the ratios of po…
Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks
Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska +1
A fundamental problem in adversarial machine learning is to quantify how much training data is needed in the presence of evasion attacks. In this paper we address this issue within…
Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Condition
Varun Kanade, Patrick Rebeschini, Tomas Vaskevicius
The local Rademacher complexity framework is one of the most successful general-purpose toolboxes for establishing sharp excess risk bounds for statistical estimators based on the…