Varun Kanade

Publication Activity (10 Years)

Years Active: 2007-2024
Publications (10 Years): 67

Top Topics

Sample Complexity Bounds

Piecewise Constant Functions

Robust Classification

Top Venues

Publications

Satwik Bhattamishra, Arkil Patel, Phil Blunsom, Varun Kanade
Understanding In-Context Learning in Transformers and LLMs by Learning to Learn Discrete Functions. ICLR (2024)
Satwik Bhattamishra, Michael Hahn, Phil Blunsom, Varun Kanade
Separations in the Representational Capabilities of Transformers and Recurrent Architectures. CoRR (2024)
Varun Kanade, Frederik Mallmann-Trenn, Thomas Sauerwald
On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting? ACM Trans. Algorithms 19 (2) (2023)
Satwik Bhattamishra, Arkil Patel, Varun Kanade, Phil Blunsom
Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions. ACL (1) (2023)
Elad Hazan, Adam Tauman Kalai, Varun Kanade, Clara Mohri, Y. Jennifer Sun
Partial Matrix Completion. NeurIPS (2023)
Satwik Bhattamishra, Arkil Patel, Phil Blunsom, Varun Kanade
Understanding In-Context Learning in Transformers and LLMs by Learning to Learn Discrete Functions. CoRR (2023)
Varun Kanade, Elad Hazan, Adam Tauman Kalai
Partial Matrix Completion. CoRR (2022)
Varun Kanade, Patrick Rebeschini, Tomas Vaskevicius
Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Condition. CoRR (2022)
Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, James Worrell
When are Local Queries Useful for Robust Learning? CoRR (2022)
Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, James Worrell
Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks. IJCAI (2022)
Limor Gultchin, Vincent Cohen-Addad, Sophie Giffard-Roisin, Varun Kanade, Frederik Mallmann-Trenn
Beyond Impossibility: Balancing Sufficiency, Separation and Accuracy. CoRR (2022)
Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, James Worrell
When are Local Queries Useful for Robust Learning? NeurIPS (2022)
Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, James Worrell
Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks. CoRR (2022)
Satwik Bhattamishra, Arkil Patel, Varun Kanade, Phil Blunsom
Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions. CoRR (2022)
Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, James Worrell
On the Hardness of Robust Classification. J. Mach. Learn. Res. 22 (2021)
Vincent Cohen-Addad, Benjamin Guedj, Varun Kanade, Guy Rom
Online k-means Clustering. AISTATS (2021)
Adam Tauman Kalai, Varun Kanade
Efficient Learning with Arbitrary Covariate Shift. ALT (2021)
Adam Kalai, Varun Kanade
Efficient Learning with Arbitrary Covariate Shift. CoRR (2021)
Adam Kalai, Varun Kanade
Towards optimally abstaining from prediction with OOD test examples. NeurIPS (2021)
Amartya Sanyal, Puneet K. Dokania, Varun Kanade, Philip H. S. Torr
How Benign is Benign Overfitting ? ICLR (2021)
Adam Tauman Kalai, Varun Kanade
Towards optimally abstaining from prediction. CoRR (2021)
Amartya Sanyal, Puneet K. Dokania, Varun Kanade, Philip H. S. Torr
How benign is benign overfitting? CoRR (2020)
Bryn Elesedy, Varun Kanade, Yee Whye Teh
Lottery Tickets in Linear Models: An Analysis of Iterative Magnitude Pruning. CoRR (2020)
Qiong Wu, Felix Ming Fai Wong, Yanhua Li, Zhenming Liu, Varun Kanade
Adaptive Reduced Rank Regression. NeurIPS (2020)
Limor Gultchin, Matt J. Kusner, Varun Kanade, Ricardo Silva
Differentiable Causal Backdoor Discovery. AISTATS (2020)
Tomas Vaskevicius, Varun Kanade, Patrick Rebeschini
The Statistical Complexity of Early-Stopped Mirror Descent. NeurIPS (2020)
Limor Gultchin, Matt J. Kusner, Varun Kanade, Ricardo Silva
Differentiable Causal Backdoor Discovery. CoRR (2020)
Tomas Vaskevicius, Varun Kanade, Patrick Rebeschini
The Statistical Complexity of Early Stopped Mirror Descent. CoRR (2020)
Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, James Worrell
On the Hardness of Robust Classification. Electron. Colloquium Comput. Complex. 26 (2019)
Varun Kanade, Frederik Mallmann-Trenn, Thomas Sauerwald
On coalescence time in graphs: When is coalescing as fast as meeting?: Extended Abstract. SODA (2019)
Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, James Worrell
On the Hardness of Robust Classification. NeurIPS (2019)
Varun Kanade, Andrea Rocchetto, Simone Severini
mu - biased quantum Fourier sampling. Quantum Inf. Comput. 19 (15&16) (2019)
Vincent Cohen-Addad, Benjamin Guedj, Varun Kanade, Guy Rom
Online k-means Clustering. CoRR (2019)
Qiong Wu, Felix Ming Fai Wong, Zhenming Liu, Yanhua Li, Varun Kanade
Adaptive Reduced Rank Regression. CoRR (2019)
David Martínez-Rubio, Varun Kanade, Patrick Rebeschini
Decentralized Cooperative Stochastic Bandits. NeurIPS (2019)
Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, James Worrell
On the Hardness of Robust Classification. CoRR (2019)
Tomas Vaskevicius, Varun Kanade, Patrick Rebeschini
Implicit Regularization for Optimal Sparse Recovery. CoRR (2019)
Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn, Claire Mathieu
Hierarchical Clustering: Objective Functions and Algorithms. J. ACM 66 (4) (2019)
Quentin Berthet, Varun Kanade
Statistical Windows in Testing for the Initial Distribution of a Reversible Markov Chain. AISTATS (2019)
Tomas Vaskevicius, Varun Kanade, Patrick Rebeschini
Implicit Regularization for Optimal Sparse Recovery. NeurIPS (2019)
Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn
Clustering Redemption-Beyond the Impossibility of Kleinberg's Axioms. NeurIPS (2018)
David Martínez-Rubio, Varun Kanade, Patrick Rebeschini
Decentralized Cooperative Stochastic Multi-armed Bandits. CoRR (2018)
Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn, Claire Mathieu
Hierarchical Clustering: Objective Functions and Algorithms. SODA (2018)
Varun Kanade, Andrea Rocchetto, Simone Severini
Learning DNFs under product distributions via μ-biased quantum Fourier sampling. CoRR (2018)
Amartya Sanyal, Varun Kanade, Philip H. S. Torr
Low Rank Structure of Learned Representations. CoRR (2018)
Amartya Sanyal, Matt J. Kusner, Adrià Gascón, Varun Kanade
TAPAS: Tricks to Accelerate (encrypted) Prediction As a Service. ICML (2018)
Amartya Sanyal, Matt J. Kusner, Adrià Gascón, Varun Kanade
TAPAS: Tricks to Accelerate (encrypted) Prediction As a Service. CoRR (2018)
Quentin Berthet, Varun Kanade
Statistical Windows in Testing for the Initial Distribution of a Reversible Markov Chain. CoRR (2018)
Varun Kanade, Frederik Mallmann-Trenn, Victor Verdugo
Brief Announcement: How Large is your Graph? PODC (2017)
Cheng Li, Felix Ming Fai Wong, Zhenming Liu, Varun Kanade
From which world is your graph. NIPS (2017)
Surbhi Goel, Varun Kanade, Adam R. Klivans, Justin Thaler
Reliably Learning the ReLU in Polynomial Time. COLT (2017)
Vincent Cohen-Addad, Varun Kanade
Online Optimization of Smoothed Piecewise Constant Functions. AISTATS (2017)
Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn
Hierarchical Clustering Beyond the Worst-Case. NIPS (2017)
Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn, Claire Mathieu
Hierarchical Clustering: Objective Functions and Algorithms. CoRR (2017)
Varun Kanade, Frederik Mallmann-Trenn, Victor Verdugo
How large is your graph? CoRR (2017)
Cheng Li, Felix Ming Fai Wong, Zhenming Liu, Varun Kanade
From which world is your graph? CoRR (2017)
Varun Kanade, Frederik Mallmann-Trenn, Victor Verdugo
How Large Is Your Graph?. DISC (2017)
Varun Kanade, Frederik Mallmann-Trenn, Thomas Sauerwald
On coalescence time in graphs-When is coalescing as fast as meeting? CoRR (2016)
Varun Kanade, Reut Levi, Zvi Lotker, Frederik Mallmann-Trenn, Claire Mathieu
Distance in the Forest Fire Model How far are you from Eve? SODA (2016)
Varun Kanade, Elchanan Mossel, Tselil Schramm
Global and Local Information in Clustering Labeled Block Models. IEEE Trans. Inf. Theory 62 (10) (2016)
Surbhi Goel, Varun Kanade, Adam R. Klivans, Justin Thaler
Reliably Learning the ReLU in Polynomial Time. CoRR (2016)
Varun Kanade, Nikos Leonardos, Frédéric Magniez
Stable Matching with Evolving Preferences. APPROX-RANDOM (2016)
Vincent Cohen-Addad, Varun Kanade
Online Optimization of Smoothed Piecewise Constant Functions. CoRR (2016)
Steve Hanneke, Varun Kanade, Liu Yang
Learning with a Drifting Target Concept. CoRR (2015)
Steve Hanneke, Varun Kanade, Liu Yang
Learning with a Drifting Target Concept. ALT (2015)
Varun Kanade, Nikos Leonardos, Frédéric Magniez
Stable Matching with Evolving Preferences. CoRR (2015)
Varun Kanade, Elchanan Mossel
MCMC Learning. COLT (2015)
Varun Kanade, Elchanan Mossel, Tselil Schramm
Global and Local Information in Clustering Labeled Block Models. CoRR (2014)
Varun Kanade, Thomas Steinke
Learning Hurdles for Sleeping Experts. ACM Trans. Comput. Theory 6 (3) (2014)
Elaine Angelino, Varun Kanade
Attribute-efficient evolvability of linear functions. ITCS (2014)
Varun Kanade, Justin Thaler
Distribution-independent Reliable Learning. COLT (2014)
Yasin Abbasi-Yadkori, Peter L. Bartlett, Varun Kanade
Tracking Adversarial Targets. ICML (2014)
Varun Kanade, Justin Thaler
Distribution-Independent Reliable Learning. CoRR (2014)
Varun Kanade, Elchanan Mossel, Tselil Schramm
Global and Local Information in Clustering Labeled Block Models. APPROX-RANDOM (2014)
Pranjal Awasthi, Vitaly Feldman, Varun Kanade
Learning Using Local Membership Queries. COLT (2013)
Elaine Angelino, Varun Kanade
Attribute-Efficient Evolvability of Linear Functions. CoRR (2013)
Yasin Abbasi-Yadkori, Peter L. Bartlett, Varun Kanade, Yevgeny Seldin, Csaba Szepesvári
Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributions. NIPS (2013)
Varun Kanade, Elchanan Mossel
MCMC Learning. CoRR (2013)
Pranjal Awasthi, Varun Kanade
Learning using Local Membership Queries under Smooth Distributions CoRR (2012)
Vitaly Feldman, Varun Kanade
Computational Bounds on Statistical Query Learning. COLT (2012)
Varun Kanade, Zhenming Liu, Bozidar Radunovic
Distributed Non-Stochastic Experts CoRR (2012)
Adam Tauman Kalai, Varun Kanade, Yishay Mansour
Reliable agnostic learning. J. Comput. Syst. Sci. 78 (5) (2012)
Varun Kanade, Thomas Steinke
Learning hurdles for sleeping experts. ITCS (2012)
Varun Kanade, Zhenming Liu, Bozidar Radunovic
Distributed Non-Stochastic Experts. NIPS (2012)
Varun Kanade
Computational Bottlenecks for Evolvability. Electron. Colloquium Comput. Complex. 18 (2011)
Sham M. Kakade, Adam Kalai, Varun Kanade, Ohad Shamir
Efficient Learning of Generalized Linear and Single Index Models with Isotonic Regression. NIPS (2011)
Varun Kanade, Thomas Steinke
Learning Hurdles for Sleeping Experts. Electron. Colloquium Comput. Complex. 18 (2011)
Varun Kanade
Evolution with Recombination. FOCS (2011)
Sham M. Kakade, Adam Tauman Kalai, Varun Kanade, Ohad Shamir
Efficient Learning of Generalized Linear and Single Index Models with Isotonic Regression CoRR (2011)
Varun Kanade, Leslie G. Valiant, Jennifer Wortman Vaughan
Evolution with Drifting Targets CoRR (2010)
Varun Kanade, Leslie G. Valiant, Jennifer Wortman Vaughan
Evolution with Drifting Targets. COLT (2010)
Varun Kanade, H. Brendan McMahan, Brent Bryan
Sleeping Experts and Bandits with Stochastic Action Availability and Adversarial Rewards. AISTATS (2009)
Adam Kalai, Varun Kanade
Potential-Based Agnostic Boosting. NIPS (2009)
Adam Tauman Kalai, Varun Kanade, Yishay Mansour
Reliable Agnostic Learning. COLT (2009)
David A. Bader, Varun Kanade, Kamesh Madduri
SWARM: A Parallel Programming Framework for Multicore Processors. IPDPS (2007)
Varun Kanade, Santosh S. Vempala
Life (and routing) on the Wireless Manifold. HotNets (2007)