A lot of my work is fairly technical and often somewhat obscure. For people trying to get an idea of what my research is like, here are some easier to understand and more introductory papers to help give an idea of the kinds of things that I do. These topics are roughly sorted in decreasing order of how much time I have spent on them recently, so the topics that I am most likely to have current projects related to are the ones closest to the top.

Information-Computation Tradeoffs

A topic that has become more prominent in my work recently is the study of information-computation tradeoffs in computational statistics. That is cases where the optimal statistical guarantees seem not to be possible to achieve in an algorithmically efficient manner. A good starting point is the 2017 paper on various statistical query lower bounds for what are known as Non-Gaussian Component Analysis problems. These were later extended (using somewhat more advanced techniques) to lower bounds against PTF tests. I've also included a nice paper about lower bounds for a particular framework for reinforcement learning.

Semi-Random Noise Models:

Another recent topic of mine has been that of learning with semi-random noise. These are some noise models that sit between the fully random noise models where the noise exactly fits some known model with a small number of parameters, and the fully adversarial models where the noise can be arbitrary (if small). A lot of this work is fairly technical and a bit disconnected, but my paper on boosting in the presence of Massart noise should be fairly accessible. Another interesting model is that of entangled mean estimation (where samples come from distributions with the same mean but perhaps wildly different covariances) on which I have a nice recent paper.

Robust Statistics:


Perhaps my biggest impact has been in the area the area of robust statistics. The basic idea is that one wants to answer basic statistical questions even if a small fraction of your samples have been adversarially corrupted. It turns out that while the information-theoretic aspects of this problem have been well understood for decades, finding computationally efficient algorithms with non-trivial guarantees is somewhat more difficult. The first modern algorithms for this kind of problem appeared around 2016, and there has been a flurry of work since then to flesh out these ideas. A good place to start on this topic would be the survey that I wrote with Ilias Diakonikolas on the topic. If you are interested in further information on the subject, you might want to check out the recent book that we wrote on the topic. While this area has been a bit less active recently as the major problems have mostly been solved, there are still some problems off the beaten path, like this paper on coordinate-wise corruptions for linear regression.

Distribution Testing:

Another area of research for me has been distribution property testing. In distribution testing, one has a distribution (or perhaps a few distributions) and by taking samples wants to distinguish between the distribution having some property P or being far (usually in total variational distance) from any distribution with that property. To get a feel for the techniques in this area, a good starting point would be the "New Approach" paper, which gives a clean way of solving many of the basic problems in the field. A slightly more advanced paper is that on Ak-testing which provides an important tool for answering questions about structured one-dimensional distributions.A more recent (and somewhat more complicated) paper in this area is on so-called replicable distribution testing.


Polynomial Threshold Functions:

This is an older topic, but was a major component of my research roughly 2010-2015. These papers roughly work towards trying to understand the behavior of medium degree polynomials in high dimensions when evaluated on random inputs. In order to get at these questions, papers tend to focus on things like noise sensitivity questions (which the first paper below discusses) and pseudorandom generators (like the second paper below). The first of these papers is quite nice and contains some key ideas that proved useful in later works. The latter paper is somewhat more technical, but should help the reader get some understanding of what kinds of ideas go into designing pseudorandom generators.

While there had been a period of little work in this area, there has been renewed interest in this area in the context of proving lower bounds for PTF tests. See the paper below on PTF tests for Non-Gaussian Component Analysis (which is unfortunately, quite technical).

Inference Dimension and Active Learning:

In active learning, one is given a large amount of unlabelled data cheaply, but then one has to pay in order to learn the labels (or perform more general queries) on this data. It turns out that for a number of such problems the query complexity needed to learn the underlying labeling function is fairly well classified by a quantity called the inference dimension of the dataset. This is a somewhat niche topic, but has lead to several quite nice results (though none recently). The obvious place to start here is the original paper the defines inference dimension.

Other Machine Learning:

I also have a bunch of other more one-off papers on the theoretical end of machine learning theory. Here are two of the more readable ones. The first is a technique for showing that realizable learning is enough (information-theoretically at least) to build more complicated learners in many contexts. The other gives a technique for proving lower bounds in the statistical query model, and shows up in a bunch of my other more recent work.