arXiv 1 Oct 2023 · Econometrics
arXiv:2310.00786 · PDF · DOI · OpenAlex · Extracted main text
Semidiscrete optimal transport is a challenging generalization of the classical transportation problem in linear programming. The goal is to design a joint distribution for two random variables (one continuous, one discrete) with fixed marginals, in a way that minimizes expected cost. We formulate a novel variant of this problem in which the cost functions are unknown, but can be learned through noisy observations; however, only one function can be sampled at a time. We develop a semi-myopic algorithm that couples online learning with stochastic approximation, and prove that it achieves optimal convergence rates, despite the non-smoothness of the stochastic gradient and the lack of strong concavity in the objective function.
appendix boundary found by appendix_titled_section at “Appendix: extension to GLMs” · 51% of the source is main text. Read the extracted text to check this.
The works this paper leans on most, across its whole bibliography — not restricted to papers in our corpus. Ranked by composite intensity, which combines how often a work is mentioned, how many sections mention it, and how much of that falls in the main text rather than the appendix.
| Reference | Intensity | Mentions | Sections | Main text | |
|---|---|---|---|---|---|
| 1 | Genevay, Cuturi, Peyré \ Bach (2016) Stochastic optimization for large-scale optimal transport, in D. Lee, M. Sugiyama, U. von Luxburg, I. Guyon \ R. Garnett, eds, `… | 1.000 | 5 | 3 | 100% |
| 2 | Goldenshluger \ Zeevi (2013) `A linear response bandit problem', Stochastic Systems 3(1), 230–261 | 0.874 | 6 | 2 | 100% |
| 3 | Carlsson, Carlsson \ Devulapalli (2016) `Shadow prices in territory division', Networks and Spatial Economics 16(3), 893–931 | 0.843 | 3 | 3 | 100% |
| 4 | Bastani, Bayati \ Khosravi (2021) `Mostly exploration-free algorithms for contextual bandits', Management Science 67(3), 1329–1349 | 0.811 | 4 | 2 | 100% |
| 5 | McCullagh \ Nelder (1989) Generalized linear models (2nd ed.), Chapman & Hall/CRC | 0.737 | 3 | 3 | 67% |
| 6 | Bastani \ Bayati (2020) `Online decision making with high-dimensional covariates', Operations Research 68(1), 276–294 | 0.737 | 3 | 2 | 100% |
| 7 | Bach \ Moulines (2011) Non-asymptotic analysis of stochastic approximation algorithms for machine learning, in J. Shawe-Taylor, R. Zemel, P. Bartlett,… | 0.644 | 2 | 2 | 100% |
| 8 | Bharadwaj, Ma, Schwarz, Shanmugasundaram, Vee, Xie \ Yang (2010) Pricing guaranteed contracts in online display advertising, in X. J | 0.644 | 2 | 2 | 100% |
| 9 | Boursier \ Perchet (2024) `Utility/privacy trade-off as regularized optimal transport', Mathematical Programming B203(1), 703–726 | 0.644 | 2 | 2 | 100% |
| 10 | Polyak \ Juditsky (1992) `Acceleration of stochastic approximation by averaging', SIAM Journal on Control and Optimization 30(4), 838–855 | 0.644 | 2 | 2 | 100% |
Showing the top 10 of 47 scored citations.
arXiv econ.EM papers that cite this one, ranked by how heavily they lean on it.
| Citing paper | Intensity | Mentions | Sections | |
|---|---|---|---|---|
| 1 | Individual and group fairness in geographical partitioning | 0.405 | 1 | 1 |
| 2 | Quantile optimization in semidiscrete optimal transport | 0.405 | 1 | 1 |