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.