More Like this

1. Estimating matching affinity matrices under low-rank constraints

   https://doi.org/10.1093/imaiai/iaz015  

   Dupuy, Arnaud; Galichon, Alfred; Sun, Yifei (August 2019, Information and Inference: A Journal of the IMA)

   null (Ed.)

   Abstract In this paper, we address the problem of estimating transport surplus (a.k.a. matching affinity) in high-dimensional optimal transport problems. Classical optimal transport theory specifies the matching affinity and determines the optimal joint distribution. In contrast, we study the inverse problem of estimating matching affinity based on the observation of the joint distribution, using an entropic regularization of the problem. To accommodate high dimensionality of the data, we propose a novel method that incorporates a nuclear norm regularization that effectively enforces a rank constraint on the affinity matrix. The low-rank matrix estimated in this way reveals the main factors that are relevant for matching. 

   more » « less
2. Episodic Bayesian Optimal Control with Unknown Randomness Distributions

   https://doi.org/10.1287/opre.2023.0446  

   Shapiro, Alexander; Zhou, Enlu; Lin, Yifan; Wang, Yuhao (May 2026, Operations Research)

   Bayesian Learning for Data-Driven Stochastic Optimal Control Stochastic optimal control (SOC) provides a principled approach to dynamic decision making under uncertainty. It models the transition of the system state with a dynamic equation driven by randomness, with the assumption that the distribution of randomness is known. However, in practical problems, modeling randomness frequently depends on data or observations, which introduces uncertainty regarding the distribution of randomness. To address the data-driven SOC problem, in “Episodic Bayesian Optimal Control with Unknown Randomness Distributions,” Shapiro, Zhou, Lin, and Wang propose a new approach that incorporates Bayesian learning with optimal control in an episodic manner. They show the convergence and convergence rate results for their approach. They also develop an efficient computational method for a class of problems that have convex cost functions and linear state dynamics. 

   more » « less
3. Minimax estimation of discontinuous optimal transport maps: The semi-discrete case

   Pooladian, Aram-Alexandre; Divol, Vincent; Niles-Weed, Jonathan (July 2023, Proceedings of Machine Learning Research)

   Krause, Andreas; Brunskill, Emma; Cho, Kyunghyun; Engelhardt, Barbara; Sabato, Sivan; Scarlett, Jonathan (Ed.)

   We consider the problem of estimating the optimal transport map between two probability distributions, P and Q in R^d, on the basis of i.i.d. samples. All existing statistical analyses of this problem require the assumption that the transport map is Lipschitz, a strong requirement that, in particular, excludes any examples where the transport map is discontinuous. As a first step towards developing estimation procedures for discontinuous maps, we consider the important special case where the data distribution Q is a discrete measure supported on a finite number of points in R^d. We study a computationally efficient estimator initially proposed by Pooladian & Niles-Weed (2021), based on entropic optimal transport, and show in the semi-discrete setting that it converges at the minimax-optimal rate n^{−1/2}, independent of dimension. Other standard map estimation techniques both lack finite-sample guarantees in this setting and provably suffer from the curse of dimensionality. We confirm these results in numerical experiments, and provide experiments for other settings, not covered by our theory, which indicate that the entropic estimator is a promising methodology for other discontinuous transport map estimation problems. 

   more » « less
4. Minimax estimation of discontinuous optimal transport maps: The semi-discrete case

   Pooladian, Aram-Alexandre; Divol, Vincent; Niles-Weed, Jonathan (May 2023, Foundations of Computational Mathematics (FoCM), workshop on Computational Optimal Transport, Paris, France)

   We consider the problem of estimating the optimal transport map between two probability distributions, P and Q in Rd, on the basis of i.i.d. samples. All existing statistical analyses of this problem require the assumption that the transport map is Lipschitz, a strong requirement that, in particular, excludes any examples where the transport map is discontinuous. As a first step towards developing estimation procedures for discontinuous maps, we consider the important special case where the data distribution Q is a discrete measure supported on a finite number of points in Rd. We study a computationally efficient estimator initially proposed by Pooladian and Niles-Weed (2021), based on entropic optimal transport, and show in the semi-discrete setting that it converges at the minimax-optimal rate n−1/2, independent of dimension. Other standard map estimation techniques both lack finite-sample guarantees in this setting and provably suffer from the curse of dimensionality. We confirm these results in numerical experiments, and provide experiments for other settings, not covered by our theory, which indicate that the entropic estimator is a promising methodology for other discontinuous transport map estimation problems. 

   more » « less
5. Solving Complex Quadratic Equations with Full-rank Random Gaussian Matrices

   https://doi.org/10.1109/ICASSP.2019.8683280  

   Huang, Shuai; Gupta, Sidharth; Dokmanic, Ivan (April 2019, ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP))

   We tackle the problem of recovering a complex signal $$\vx\in\mathbb{C}^n$$ from quadratic measurements of the form $$y_i=\vx^*\vA_i\vx$$, where $$\{\vA_i\}_{i=1}^m$$ is a set of complex iid standard Gaussian matrices. This non-convex problem is related to the well understood phase retrieval problem where $$\vA_i$$ is a rank-1 positive semidefinite matrix. Here we study a general full-rank case which models a number of key applications such as molecular geometry recovery from distance distributions and compound measurements in phaseless diffractive imaging. Most prior work either addresses the rank-1 case or focuses on real measurements. The several papers that address the full-rank complex case adopt the semidefinite relaxation approach and are thus computationally demanding. In this paper we propose a method based on the standard framework comprising a spectral initialization followed by iterative gradient descent updates. We prove that when the number of measurements exceeds the signal's length by some constant factor, a globally optimal solution can be recovered from complex quadratic measurements with high probability. Numerical experiments on simulated data corroborate our theoretical analysis. 

   more » « less