Information for Prospective Theory Students

I'm interested in machine learning theory, economics and computation, and things in the intersection of these two fields. I'll try to list some open questions here that I think are interesting. If you are interested in solving any of these questions, please feel free to contact me.

Open Questions: Precision and Recall Learning

For my precision and recall learning paper (with Lee Cohen, Yishay Mansour, and Shay Moran, NeurIPS 2025), there are a few interesting open questions:

1. Finite input space: Note that the negative result in this paper relies on the assumption that the input space X is infinite and each input has been observed at most once in the training data. If the input space X is finite, what will the results look like? Then the sample complexity will depend on the size of |X|. Or other assumptions such that for some x I can observe the same input more than once and thus get two different answers/labels for this same input.
2. Non-uniform label distribution: What if the label in the training data is not sampled from a uniform distribution, i.e., v_i is not from Unif(g*(x_i))?
3. Pairwise comparison data: If we get pairwise-comparison-type data for post-training, can we learn precision and recall simultaneously?

The first question is more concrete, while the other two require some additional modeling.

Related Papers

1. Density estimation
   This paper is technically related to density estimation.
2. Pairwise comparison data
   For pairwise-comparison-type of data, it has been discussed in this paper.
3. Non-uniform distribution
   For non-uniform distribution, there is one slightly related paper.

Machine Learning Theory Basics

For the basics of machine learning theory, I usually teach a learning theory course in the fall. But I only have handwritten notes. You can refer to lecture notes by Nika Haghtalab or the textbook by Shai and Shai.