publications

publications by categories in reversed chronological order. generated by jekyll-scholar.

2025

  1. The Space Complexity of Learning-Unlearning Algorithms (extended abstract)
    Yeshwanth Cherapanamjeri, Sumegba Garg, Nived Rajaraman, and 2 more authors
    In The Thirty Eighth Annual Conference on Learning Theory, 30-4 July 2025, Lyon, France, 2025
  2. Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks
    Omar Montasser, Abhishek Shetty, and Nikita Zhivotovskiy
    In The Thirty Eighth Annual Conference on Learning Theory, 30-4 July 2025, Lyon, France, 2025
  3. Small Loss Bounds for Online Learning Separated Function Classes: A Gaussian Process Perspective
    Adam Block and Abhishek Shetty
    CoRR, 2025
    DOI
  4. Low-Rank Thinning
    Annabelle Michael Carrell, Albert Gong, Abhishek Shetty, and 2 more authors
    CoRR, 2025
    DOI
  5. Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks
    Omar Montasser, Abhishek Shetty, and Nikita Zhivotovskiy
    CoRR, 2025
    DOI
  6. The Space Complexity of Learning-Unlearning Algorithms
    Yeshwanth Cherapanamjeri, Sumegha Garg, Nived Rajaraman, and 2 more authors
    CoRR, 2025
    DOI
  7. Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking
    Dhruv Rohatgi, Abhishek Shetty, Donya Saless, and 4 more authors
    CoRR, 2025
    DOI

2024

  1. Learning in a Changing World:}}Covariate Shift, Subset Selection and Optimal PAC Bounds
    Abhishek Shetty
    University of California Berkeley, USA, 2024
  2. Smoothed Analysis with Adaptive Adversaries
    Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty
    J. ACM, 2024
    DOI
  3. On the Performance of Empirical Risk Minimization with Smoothed Data
    Adam Block, Alexander Rakhlin, and Abhishek Shetty
    In The Thirty Seventh Annual Conference on Learning Theory, June 30 - July 3, 2023, Edmonton, Canada, 2024
  4. Smooth Nash Equilibria: Algorithms and Complexity
    Constantinos Daskalakis, Noah Golowich, Nika Haghtalab, and 1 more author
    In 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA, 2024
    DOI
  5. Oracle-Efficient Differentially Private Learning with Public Data
    Adam Block, Mark Bun, Rathin Desai, and 2 more authors
    In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024, 2024
  6. Tolerant Algorithms for Learning with Arbitrary Covariate Shift
    Surbhi Goel, Abhishek Shetty, Konstantinos Stavropoulos, and 1 more author
    In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024, 2024
  7. Omnipredictors for Regression and the Approximate Rank of Convex Functions
    Parikshit Gopalan, Princewill Okoroafor, Prasad Raghavendra, and 2 more authors
    CoRR, 2024
    DOI
  8. Oracle-Efficient Differentially Private Learning with Public Data
    Adam Block, Mark Bun, Rathin Desai, and 2 more authors
    CoRR, 2024
    DOI
  9. On the Performance of Empirical Risk Minimization with Smoothed Data
    Adam Block, Alexander Rakhlin, and Abhishek Shetty
    CoRR, 2024
    DOI
  10. Tolerant Algorithms for Learning with Arbitrary Covariate Shift
    Surbhi Goel, Abhishek Shetty, Konstantinos Stavropoulos, and 1 more author
    CoRR, 2024
    DOI

2023

  1. The One-Inclusion Graph Algorithm is not Always Optimal
    Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and 1 more author
    In The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India, 2023
  2. Optimal PAC Bounds without Uniform Convergence
    Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and 1 more author
    In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, 2023
    DOI
  3. Smoothed Analysis of Sequential Probability Assignment
    Alankrita Bhatt, Nika Haghtalab, and Abhishek Shetty
    In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023
  4. Progressive Ensemble Distillation: Building Ensembles for Efficient Inference
    Don Kurian Dennis, Abhishek Shetty, Anish Prasad Sevekari, and 2 more authors
    In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023
  5. Adversarial Resilience in Sequential Prediction via Abstention
    Surbhi Goel, Steve Hanneke, Shay Moran, and 1 more author
    In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023
  6. Progressive Knowledge Distillation: Building Ensembles for Efficient Inference
    Don Kurian Dennis, Abhishek Shetty, Anish Sevekari, and 2 more authors
    CoRR, 2023
    DOI
  7. Smoothed Analysis of Sequential Probability Assignment
    Alankrita Bhatt, Nika Haghtalab, and Abhishek Shetty
    CoRR, 2023
    DOI
  8. Optimal PAC Bounds Without Uniform Convergence
    Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and 1 more author
    CoRR, 2023
    DOI
  9. Adversarial Resilience in Sequential Prediction via Abstention
    Surbhi Goel, Steve Hanneke, Shay Moran, and 1 more author
    CoRR, 2023
    DOI
  10. Smooth Nash Equilibria: Algorithms and Complexity
    Constantinos Daskalakis, Noah Golowich, Nika Haghtalab, and 1 more author
    CoRR, 2023
    DOI

2022

  1. Distribution Compression in Near-Linear Time
    Abhishek Shetty, Raaz Dwivedi, and Lester Mackey
    In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022, 2022
  2. Oracle-Efficient Online Learning for Smoothed Adversaries
    Nika Haghtalab, Yanjun Han, Abhishek Shetty, and 1 more author
    In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022, 2022
  3. Matrix discrepancy from Quantum communication
    Samuel B. Hopkins, Prasad Raghavendra, and Abhishek Shetty
    In STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, 2022
    DOI
  4. Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries
    Nika Haghtalab, Yanjun Han, Abhishek Shetty, and 1 more author
    CoRR, 2022
  5. The One-Inclusion Graph Algorithm is not Always Optimal
    Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and 1 more author
    CoRR, 2022
    DOI

2021

  1. Fractional Pseudorandom Generators from Any Fourier Level
    Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, and 2 more authors
    In 36th Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference), 2021
    DOI
  2. Smoothed Analysis with Adaptive Adversaries
    Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty
    In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, 2021
    DOI
  3. Smoothed Analysis with Adaptive Adversaries
    Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty
    CoRR, 2021
  4. Matrix Discrepancy from Quantum Communication
    Samuel B. Hopkins, Prasad Raghavendra, and Abhishek Shetty
    CoRR, 2021
  5. Distribution Compression in Near-linear Time
    Abhishek Shetty, Raaz Dwivedi, and Lester Mackey
    CoRR, 2021

2020

  1. Effect of Activation Functions on the Training of Overparametrized Neural Nets
    Abhishek Panigrahi, Abhishek Shetty, and Navin Goyal
    In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020
  2. Smoothed Analysis of Online and Differentially Private Learning
    Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty
    In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020
  3. Smoothed Analysis of Online and Differentially Private Learning
    Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty
    CoRR, 2020
  4. Fractional Pseudorandom Generators from Any Fourier Level
    Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, and 2 more authors
    CoRR, 2020
  5. Fractional Pseudorandom Generators from the \textdollark\textdollarth Fourier Level
    Eshan Chattopadhyay, Jason Gaitonde, and Abhishek Shetty
    Electron. Colloquium Comput. Complex., 2020

2019

  1. Exponential Weights on the Hypercube in Polynomial Time
    Sudeep Raja Putta and Abhishek Shetty
    In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, 2019
  2. Sampling and Optimization on Convex Sets in Riemannian Manifolds of Non-Negative Curvature
    Navin Goyal and Abhishek Shetty
    In Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, 2019
  3. Non-Gaussian component analysis using entropy methods
    Navin Goyal and Abhishek Shetty
    In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, 2019
    DOI
  4. Sampling and Optimization on Convex Sets in Riemannian Manifolds of Non-Negative Curvature
    Navin Goyal and Abhishek Shetty
    CoRR, 2019
  5. Effect of Activation Functions on the Training of Overparametrized Neural Nets
    Abhishek Panigrahi, Abhishek Shetty, and Navin Goyal
    CoRR, 2019

2018

  1. Non-Gaussian Component Analysis using Entropy Methods
    Navin Goyal and Abhishek Shetty
    CoRR, 2018