
Exponential Weights Algorithms for Selective Learning
We study the selective learning problem introduced by Qiao and Valiant (...
read it

Sinkhorn Label Allocation: SemiSupervised Classification via Annealed SelfTraining
Selftraining is a standard approach to semisupervised learning where t...
read it

On Misspecification in Prediction Problems and Robustness via Improper Learning
We study probabilistic prediction games when the underlying model is mis...
read it

Stronger Calibration Lower Bounds via Sidestepping
We consider an online binary prediction setting where a forecaster obser...
read it

On the Generalization Effects of Linear Transformations in Data Augmentation
Data augmentation is a powerful technique to improve performance in appl...
read it

Sublinear Optimal Policy Value Estimation in Contextual Bandits
We study the problem of estimating the expected reward of the optimal po...
read it

How bad is worstcase data if you know where it comes from?
We introduce a framework for studying how distributional assumptions on ...
read it

A Polynomial Time Algorithm for LogConcave Maximum Likelihood via Locally Exponential Families
We consider the problem of computing the maximum likelihood multivariate...
read it

Making AI Forget You: Data Deletion in Machine Learning
Intense recent discussions have focused on how to provide individuals wi...
read it

A Surprising Density of Illusionable Natural Speech
Recent work on adversarial examples has demonstrated that most natural i...
read it

Sample Amplification: Increasing Dataset Size even when Learning is Impossible
Given data drawn from an unknown distribution, D, to what extent is it p...
read it

Implicit regularization for deep neural networks driven by an OrnsteinUhlenbeck like process
We consider deep networks, trained via stochastic gradient descent to mi...
read it

MemorySample Tradeoffs for Linear Regression with Small Error
We consider the problem of performing linear regression over a stream of...
read it

Maximum Likelihood Estimation for Learning Populations of Parameters
Consider a setting with N independent individuals, each with an unknown ...
read it

A Theory of Selective Prediction
We consider a model of selective prediction, where the prediction algori...
read it

Equivariant Transformer Networks
How can prior knowledge on the transformation invariances of a domain be...
read it

A Spectral View of Adversarially Robust Features
Given the apparent difficulty of learning models that are robust to adve...
read it

An Efficient Algorithm for HighDimensional LogConcave Maximum Likelihood
The logconcave maximum likelihood estimator (MLE) problem answers: for ...
read it

Estimating Learnability in the Sublinear Data Regime
We consider the problem of estimating how well a model class is capable ...
read it

Approximating the Spectrum of a Graph
The spectrum of a network or graph G=(V,E) with adjacency matrix A, cons...
read it

Learning Overcomplete HMMs
We study the problem of learning overcomplete HMMsthose that have man...
read it

Finding HeavilyWeighted Features in Data Streams
We introduce a new sublinear space data structurethe WeightMedian S...
read it

There and Back Again: A General Approach to Learning Sparse Models
We propose a simple and efficient approach to learning sparse models. Ou...
read it

Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers
We introduce a criterion, resilience, which allows properties of a datas...
read it

Orthogonalized ALS: A Theoretically Principled Tensor Decomposition Algorithm for Practical Use
The popular Alternating Least Squares (ALS) algorithm for tensor decompo...
read it

Prediction with a Short Memory
We consider the problem of predicting the next observation given a seque...
read it

Learning from Untrusted Data
The vast majority of theoretical results in machine learning and statist...
read it

Spectrum Estimation from Samples
We consider the problem of approximating the set of eigenvalues of the c...
read it

Testing Closeness With Unequal Sized Samples
We consider the problem of closeness testing for two discrete distributi...
read it

Least Squares Revisited: Scalable Approaches for Multiclass Prediction
This work provides simple algorithms for multiclass (and multilabel) p...
read it
Gregory Valiant
is this you? claim profile
Assistant Professor at Stanford University Computer Science aince 2013, Postdoc at Microsoft Research, New England, and received my PhD from Berkeley in Computer Science 2012, and BA in Math from Harvard 2006.