59 citations · 88 across the 9 of their papers we have counts for
10 papers
Discovering Data Structures: Nearest Neighbor Search and Beyond
Omar Salemohamed, Laurent Charlin, Shivam Garg +2
We propose a general framework for end-to-end learning of data structures. Our framework adapts to the underlying data distribution and provides fine-grained control over query and…
Testing with Non-identically Distributed Samples
Shivam Garg, Chirag Pabbaraju, Kirankumar Shiragur +1
We examine the extent to which sublinear-sample property testing and estimation apply to settings where samples are independently but not identically distributed. Specifically, we…
What Can Transformers Learn In-Context? A Case Study of Simple Function Classes
Shivam Garg, Dimitris Tsipras, Percy Liang +1
In-context learning refers to the ability of a model to condition on a prompt sequence consisting of in-context examples (input-output pairs corresponding to some task) along with…
On the Statistical Complexity of Sample Amplification
Brian Axelrod, Shivam Garg, Yanjun Han +2
The ``sample amplification'' problem formalizes the following question: Given i.i.d. samples drawn from an unknown distribution , when is it possible to produce a larger set…
How and When Random Feedback Works: A Case Study of Low-Rank Matrix Factorization
Shivam Garg, Santosh S. Vempala
The success of gradient descent in ML and especially for learning neural networks is remarkable and robust. In the context of how the brain learns, one aspect of gradient descent t…
Distributed Algorithms from Arboreal Ants for the Shortest Path Problem
Shivam Garg, Kirankumar Shiragur, Deborah M. Gordon +1
Colonies of the arboreal turtle ant create networks of trails that link nests and food sources on the graph formed by branches and vines in the canopy of the tropical forest. Ants…
Gradient Temporal-Difference Learning with Regularized Corrections
Sina Ghiassian, Andrew Patterson, Shivam Garg +3
It is still common to use Q-learning and temporal difference (TD) learning-even though they have divergence issues and sound Gradient TD alternatives exist-because divergence seems…
Sample Amplification: Increasing Dataset Size even when Learning is Impossible
Brian Axelrod, Shivam Garg, Vatsal Sharan +1
Given data drawn from an unknown distribution, , to what extent is it possible to ``amplify'' this dataset and output an even larger set of samples that appear to have been draw…
A Spectral View of Adversarially Robust Features
Shivam Garg, Vatsal Sharan, Brian Hu Zhang +1
Given the apparent difficulty of learning models that are robust to adversarial perturbations, we propose tackling the simpler problem of developing adversarially robust features.…
Raising The Bar For Vertex Cover: Fixed-parameter Tractability Above A Higher Guarantee
Shivam Garg, Geevarghese Philip
We investigate the following above-guarantee parameterization of the classical Vertex Cover problem: Given a graph and as input, does have a vertex cover o…