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.
Robust Statistics:
A lot of my recent work has been in 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.
Distribution Testing:
Another active 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.
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. The obvious place to
start here is the original paper the defines inference dimension.
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.
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.
Polynomial Threshold Functions:
This is a topic that I haven't done as much work on lately, 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.