12 citations · 32 across the 12 of their papers we have counts for
13 papers
Adversarial Resilience in Sequential Prediction via Abstention
Surbhi Goel, Steve Hanneke, Shay Moran +1
We study the problem of sequential prediction in the stochastic setting with an adversary that is allowed to inject clean-label adversarial (or out-of-distribution) examples. Algor…
Optimal PAC Bounds Without Uniform Convergence
Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty +1
In statistical learning theory, determining the sample complexity of realizable binary classification for VC classes was a long-standing open problem. The results of Simon and Hann…
Smoothed Analysis of Sequential Probability Assignment
Alankrita Bhatt, Nika Haghtalab, Abhishek Shetty
We initiate the study of smoothed analysis for the sequential probability assignment problem with contexts. We study information-theoretically optimal minmax rates as well as a fra…
Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries
Nika Haghtalab, Yanjun Han, Abhishek Shetty +1
In this paper, we study oracle-efficient algorithms for beyond worst-case analysis of online learning. We focus on two settings. First, the smoothed analysis setting of [RST11,HRS2…
Distribution Compression in Near-linear Time
Abhishek Shetty, Raaz Dwivedi, Lester Mackey
In distribution compression, one aims to accurately summarize a probability distribution using a small number of representative points. Near-optimal thinning procedure…
Matrix Discrepancy from Quantum Communication
Samuel B. Hopkins, Prasad Raghavendra, Abhishek Shetty
We develop a novel connection between discrepancy minimization and (quantum) communication complexity. As an application, we resolve a substantial special case of the Matrix Spence…
Smoothed Analysis with Adaptive Adversaries
Nika Haghtalab, Tim Roughgarden, Abhishek Shetty
We prove novel algorithmic guarantees for several online problems in the smoothed analysis model. In this model, at each time an adversary chooses an input distribution with densit…
Fractional Pseudorandom Generators from Any Fourier Level
Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee +2
We prove new results on the polarizing random walk framework introduced in recent works of Chattopadhyay {et al.} [CHHL19,CHLT19] that exploit Fourier tail bounds for classes…
Smoothed Analysis of Online and Differentially Private Learning
Nika Haghtalab, Tim Roughgarden, Abhishek Shetty
Practical and pervasive needs for robustness and privacy in algorithms have inspired the design of online adversarial and differentially private learning algorithms. The primary qu…
Effect of Activation Functions on the Training of Overparametrized Neural Nets
Abhishek Panigrahi, Abhishek Shetty, Navin Goyal
It is well-known that overparametrized neural networks trained using gradient-based methods quickly achieve small training error with appropriate hyperparameter settings. Recent pa…
Sampling and Optimization on Convex Sets in Riemannian Manifolds of Non-Negative Curvature
Navin Goyal, Abhishek Shetty
The Euclidean space notion of convex sets (and functions) generalizes to Riemannian manifolds in a natural sense and is called geodesic convexity. Extensively studied computational…
Non-Gaussian Component Analysis using Entropy Methods
Navin Goyal, Abhishek Shetty
Non-Gaussian component analysis (NGCA) is a problem in multidimensional data analysis which, since its formulation in 2006, has attracted considerable attention in statistics and m…
Exponential Weights on the Hypercube in Polynomial Time
Sudeep Raja Putta, Abhishek Shetty
We study a general online linear optimization problem(OLO). At each round, a subset of objects from a fixed universe of objects is chosen, and a linear cost associated with the…