skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: Uncoupled isotonic regression via minimum Wasserstein deconvolution
Abstract Isotonic regression is a standard problem in shape-constrained estimation where the goal is to estimate an unknown non-decreasing regression function $$f$$ from independent pairs $$(x_i, y_i)$$ where $${\mathbb{E}}[y_i]=f(x_i), i=1, \ldots n$$. While this problem is well understood both statistically and computationally, much less is known about its uncoupled counterpart, where one is given only the unordered sets $$\{x_1, \ldots , x_n\}$$ and $$\{y_1, \ldots , y_n\}$$. In this work, we leverage tools from optimal transport theory to derive minimax rates under weak moments conditions on $$y_i$$ and to give an efficient algorithm achieving optimal rates. Both upper and lower bounds employ moment-matching arguments that are also pertinent to learning mixtures of distributions and deconvolution.  more » « less
Award ID(s):
1712596 1838071
PAR ID:
10128161
Author(s) / Creator(s):
 ;  
Publisher / Repository:
Oxford University Press
Date Published:
Journal Name:
Information and Inference: A Journal of the IMA
Volume:
8
Issue:
4
ISSN:
2049-8772
Page Range / eLocation ID:
p. 691-717
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract When k and s are natural numbers and $${\mathbf h}\in {\mathbb Z}^k$$, denote by $$J_{s,k}(X;\,{\mathbf h})$$ the number of integral solutions of the system $$ \sum_{i=1}^s(x_i^j-y_i^j)=h_j\quad (1\leqslant j\leqslant k), $$ with $$1\leqslant x_i,y_i\leqslant X$$. When $$s\lt k(k+1)/2$$ and $$(h_1,\ldots ,h_{k-1})\ne {\mathbf 0}$$, Brandes and Hughes have shown that $$J_{s,k}(X;\,{\mathbf h})=o(X^s)$$. In this paper we improve on quantitative aspects of this result, and, subject to an extension of the main conjecture in Vinogradov’s mean value theorem, we obtain an asymptotic formula for $$J_{s,k}(X;\,{\mathbf h})$$ in the critical case $s=k(k+1)/2$. The latter requires minor arc estimates going beyond square-root cancellation. 
    more » « less
  2. Abstract In the (special) smoothing spline problem one considers a variational problem with a quadratic data fidelity penalty and Laplacian regularization. Higher order regularity can be obtained via replacing the Laplacian regulariser with a poly-Laplacian regulariser. The methodology is readily adapted to graphs and here we consider graph poly-Laplacian regularization in a fully supervised, non-parametric, noise corrupted, regression problem. In particular, given a dataset$$\{x_i\}_{i=1}^n$$ { x i } i = 1 n and a set of noisy labels$$\{y_i\}_{i=1}^n\subset \mathbb {R}$$ { y i } i = 1 n R we let$$u_n{:}\{x_i\}_{i=1}^n\rightarrow \mathbb {R}$$ u n : { x i } i = 1 n R be the minimizer of an energy which consists of a data fidelity term and an appropriately scaled graph poly-Laplacian term. When$$y_i = g(x_i)+\xi _i$$ y i = g ( x i ) + ξ i , for iid noise$$\xi _i$$ ξ i , and using the geometric random graph, we identify (with high probability) the rate of convergence of$$u_n$$ u n togin the large data limit$$n\rightarrow \infty $$ n . Furthermore, our rate is close to the known rate of convergence in the usual smoothing spline model. 
    more » « less
  3. Given finite sets $$X_1,\dotsc,X_m$$ in $$\mathbb{R}^d$$ (with $$d$$ fixed), we prove that there are respective subsets $$Y_1,\dotsc,Y_m$$ with $$\lvert Y_i\rvert \geq \frac{1}{poly(m)}\lvert X_i\rvert$$ such that, for $$y_1\in Y_1,\dotsc,y_m\in Y_m$$, the orientations of the\linebreak $(d+1)$-tuples from $$y_1,\dotsc,y_m$$ do not depend on the actual choices of points $$y_1,\dotsc,y_m$$. This generalizes previously known case when all the sets $$X_i$$ are equal. Furthermore, we give a construction showing that polynomial dependence on $$m$$ is unavoidable, as well as an algorithm that approximates the best-possible constants in this result. 
    more » « less
  4. We consider the allocation problem in which $$m \leq (1-\epsilon) dn $$ items are to be allocated to $$n$$ bins with capacity $$d$$. The items $$x_1,x_2,\ldots,x_m$$ arrive sequentially and when item $$x_i$$ arrives it is given two possible bin locations $$p_i=h_1(x_i),q_i=h_2(x_i)$$ via hash functions $$h_1,h_2$$. We consider a random walk procedure for inserting items and show that the expected time insertion time is constant provided $$\epsilon = \Omega\left(\sqrt{ \frac{ \log d}{d}} \right).$$ 
    more » « less
  5. Abstract An adaptive, adversarial methodology is developed for the optimal transport problem between two distributions $$\mu $$ and $$\nu $$, known only through a finite set of independent samples $$(x_i)_{i=1..n}$$ and $$(y_j)_{j=1..m}$$. The methodology automatically creates features that adapt to the data, thus avoiding reliance on a priori knowledge of the distributions underlying the data. Specifically, instead of a discrete point-by-point assignment, the new procedure seeks an optimal map $T(x)$ defined for all $$x$$, minimizing the Kullback–Leibler divergence between $$(T(x_i))$$ and the target $$(y_j)$$. The relative entropy is given a sample-based, variational characterization, thereby creating an adversarial setting: as one player seeks to push forward one distribution to the other, the second player develops features that focus on those areas where the two distributions fail to match. The procedure solves local problems that seek the optimal transfer between consecutive, intermediate distributions between $$\mu $$ and $$\nu $$. As a result, maps of arbitrary complexity can be built by composing the simple maps used for each local problem. Displaced interpolation is used to guarantee global from local optimality. The procedure is illustrated through synthetic examples in one and two dimensions. 
    more » « less