NeurIPS 2026 论文列表

For $p \ge 1$, the $p$-Wasserstein distance measures the minimum cost of transporting probability mass, where moving mass between two points costs the $p$th power of their distance. For discrete distributions in one dimension, full transport is especially simple: after sorting, mass is matched in order along the line. By contrast, partial and unbalanced transport on the line remains much less understood. Recently, Chapel and Tavenard [ICLR'25] showed that, for $p=1$, all optimal partial transport plans between distributions supported on $n$ points, with uniform mass at each point, can be computed in $O(n\log n)$ time by exploiting the metric structure of the cost. For $p>1$, this structure no longer applies, and existing approaches require $\Omega(n^2)$ time. Our main contribution is an FFT-based data structure for balanced-interval transport queries, which bypasses this quadratic bottleneck and yields an $O(p\ n\log^2 n)$-time algorithm for computing all optimal partial transports on the line for every finite $p\ge 1$. We also provide an open-source C++ implementation that outperforms the state-of-the-art baseline on a range of synthetic instances. Finally, we establish a conditional lower bound for $p=\infty$: any subquadratic-time algorithm for computing all optimal partial transport plan costs on the line would violate the $(\min,+)$-Convolution Hypothesis. This separates the problem from full optimal transport, which is solvable in $O(n\log n)$ time.

We propose a machine-learning framework based on the principle that learning can be achieved through algebraic decomposition rather than numerical optimization. A learning task is encoded as axioms of an algebra, and learning proceeds by computing a subdirect decomposition of the algebra into subdirectly irreducible components. We show that suitable subsets of these components form models that generalize to unseen data because they approximate the underlying rule in the training data. The method has no dataset-specific hyperparameters to tune and shows no evidence of classical overfitting in our experiments, so we run it without a validation dataset. We compare against multilayer perceptrons as generic parametric baselines without task-specific inductive biases. Across 24 classification datasets, the algebraic method is applied only once to each training set without hyperparameter tuning, whereas the multi-layer perceptrons are selected from many configurations using validation data or cross-validation. Nevertheless, the resulting test accuracies are statistically indistinguishable. Moreover, adding a statistical readout on top of the algebraic representation, using untuned logistic regression, improves over the best multilayer perceptrons selected by validation or cross-validation. More broadly, because task axioms may encode examples, formal knowledge, or both, this approach provides a common algebraic framework and the same algorithm for data-driven problems such as classification, formally specified problems such as computing Hamiltonian cycles from specifications, and mixed settings combining data with formal constraints.