Transportation maps between probability measures are critical
objects in numerous areas of mathematics and applications such as PDE,
fluid mechanics, geometry, machine learning, computer science, and economics.
Given a pair of source and target measures, one searches for a map that has
suitable properties and transports the source measure to the target one.
Here, we study maps that possess the no-collision property; that is, particles
simultaneously traveling from sources to targets in a unit time with uniform
velocities do not collide. These maps are particularly relevant for
applications in swarm control problems. We characterize these no-collision
maps in terms of half-space preserving property and establish a direct
connection between these maps and binary-space-partitioning (BSP) tree
structures. Based on this characterization, we provide explicit BSP
algorithms, of cost O(n log n), to construct no-collision maps. Moreover,
interpreting these maps as approximations of optimal transportation maps,
we find that they succeed in computing nearly optimal maps for q-Wasserstein
metric (q = 1, 2). In some cases, our maps yield costs that are just a few
percent off from being optimal.
Calibrated Top-1 Uncertainty estimates for classification by score based models
While the accuracy of modern deep learning models has significantly improved in recent years, the ability of these models to generate uncertainty estimates has not progressed to the same degree. Uncertainty methods are designed to provide an estimate of class probabilities when predicting class assignment.
A Langevin dynamics based approach to generating sparse adversarial perturbations
Deep neural networks are vulnerable to small changes in the input that lead to misclassification, calledadversarial images. We present an efficient approach togenerating sparse adversarial images, i.e. small with respect to the cardinality function L0, without using gradient information. The lack of gradient oracle isof interest in the case of adversarial attacks: in a practical setting, one can easily query the model to determine whether the image is misclassified or not but rarely will the full network structure be provided. Our method, ProxWalk, is inspired by Metropolis-Adjusted Langevin dynamics; a method for modeling random walks,and the proximal variant. We present results on MNIST, Fashion-MNIST, CIFAR10, and CIFAR100 datasets, and demonstrate that our decision-based attackis on par with modern sparse white-box attacks.