Uncoupled isotonic regression

Seminar on Theoretical Machine Learning
Topic:Uncoupled isotonic regression
Speaker:Jonathan Niles-Weed
Affiliation:New York University; Member, School of Mathematics
Date:Wednesday, December 4
Time/Room:12:00pm - 1:30pm/Dilworth Room
Video Link:https://video.ias.edu/tml/2019/1204-JonathanNilesWeed

The classical regression problem seeks to estimate a function f on the basis of independent pairs $(x_i,y_i)$ where $\mathbb E[y_i]=f(x_i)$, $i=1,\dotsc,n$. In this talk, we consider statistical and computational aspects of the "uncoupled" version of this problem, where one observes only the unordered sets $\{x_1,…,x_n\}$ and $\{y_1,…,y_n\}$ and still hopes to recover information about $f$. Under the assumption that $f$ is nondecreasing, we give minimax statistical rates under weak moment conditions on $y_i$ and provide an efficient algorithm achieving the optimal rates. Both upper and lower bounds employ moment-matching arguments based on optimal transport theory. Joint work with Philippe Rigollet.