Budget-Constrained Bounds for Mini-Batch Estimation of Optimal Transport
Optimal Transport (OT) is a fundamental tool for comparing probability distributions, but its exact computation remains prohibitive for large datasets. In this work, we introduce novel families of upper and lower bounds for the OT problem constructed by aggregating solutions of mini-batch OT problems. The upper bound family contains traditional mini-batch averaging at one extreme and a tight bound found by optimal coupling of mini-batches at the other. In between these extremes, we propose various methods to construct bounds based on a fixed computational budget. Through various experiments, we explore the trade-off between computational budget and bound tightness and show the usefulness of these bounds in computer vision applications.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Budget-Constrained Bandits over General Cost and Reward Distributions
We consider a budget-constrained bandit problem where each arm pull incurs a random cost, and yields a random reward in return. The objective is to maximize the total expected reward under a budget constraint on the tota…
Minibatch Selection for Language Models via Partition Matroid Constrained Gradient Matching
Training large language models (LLMs) on heterogeneous data requires selecting minibatches that balance convergence speed with coverage across domains. Existing methods either select samples independently within each dom…
Information-theoretic lower bounds for distributed statistical estimation with communication constraints
We establish minimax risk lower bounds for distributed statistical estimation given a budget $B$ of the total number of bits that may be communicated. Such lower bounds in turn reveal the minimum amount of communication …
Binary ClassificationGeneral ClassificationregressionHigh-Probability Minimax Adaptive Estimation in Besov Spaces via Online-to-Batch
We study nonparametric regression over Besov spaces from noisy observations under sub-exponential noise, aiming to achieve minimax-optimal guarantees on the integrated squared error that hold with high probability and ad…
DARTS: Targeting Prognostic Covariates in Budget-Constrained Sequential Experiments
Randomized controlled trials typically assume that prognostic covariates are known and available at no cost. In practice, obtaining high-dimensional pretreatment data is costly, forcing a trade-off between covariate-adap…
Causal Inference