More Like this

1. Wasserstein Proximal Algorithms for the Schr\"{o}dinger Bridge Problem: Density Control with Nonlinear Drift

   https://doi.org/10.1109/TAC.2021.3060704  

   Caluya, Kenneth; Halder, Abhishek (January 2021, IEEE Transactions on Automatic Control)

   null (Ed.)

   We study the Schr{\"o}dinger bridge problem (SBP) with nonlinear prior dynamics. In control-theoretic language, this is a problem of minimum effort steering of a given joint state probability density function (PDF) to another over a finite time horizon, subject to a controlled stochastic differential evolution of the state vector. For generic nonlinear drift, we reduce the SBP to solving a system of forward and backward Kolmogorov partial differential equations (PDEs) that are coupled through the boundary conditions, with unknowns being the ``Schr\"{o}dinger factors". We show that if the drift is a gradient vector field, or is of mixed conservative-dissipative nature, then it is possible to transform these PDEs into a pair of initial value problems (IVPs) involving the same forward Kolmogorov operator. We employ a proximal algorithm developed in our prior work to solve these IVPs and compute the Schr\"{o}dinger factors via weighted scattered point cloud evolution in the state space. We provide the algorithmic details and illustrate the proposed framework of solving the SBPs with nonlinear prior dynamics by numerical examples. 

   more » « less
2. Search versus Search for Collapsing Electoral Control Types

   Carleton, Benjamin; Chavrimootoo, Michael C; Hemaspaandra, Lane A; Narvaez, David; Taliancich, Conor; Welles, Henry B (June 2025, Proceedings of the 21st European Conference on Multi-Agent Systems, Springer Nature)

   A 2024 paper of Carleton et al. [11] building on Hemaspaandra et al. [25] surprisingly shows, for 36 pairs of cases involving plurality, veto, and approval voting, that seemingly different, long-studied partition-based control attack types “collapse”: they are the same set (and so have the same decision complexity). The rather novel open question the 2024 paper concludes with is whether, for the 36 collapsing decision-problem pairs, their search-complexities are linked. In this paper, we completely resolve that question. We build a framework for linking the search complexities and solutions of members of collapsing pairs, and we both link and pinpoint the search complexities of all 36 collapsing cases (in part via linking the search complexities within the 7 “universal” collapsing pairs). This is important because for election problems the search versions are by far the more important versions: they tell one how to perform the desired attack. 

   more » « less
3. Hierarchical Autoregressive Modeling for Neural Video Compression

   Yang, Ruihan; Yang, Yibo; Marino, Joseph; Mandt, Stephan (January 2021, International Conference on Learning Representations)

   null (Ed.)

   Recent work by Marino et al. (2020) showed improved performance in sequential density estimation by combining masked autoregressive flows with hierarchical latent variable models. We draw a connection between such autoregressive generative models and the task of lossy video compression. Specifically, we view recent neural video compression methods (Lu et al., 2019; Yang et al., 2020b; Agustsson et al., 2020) as instances of a generalized stochastic temporal autoregressive transform, and propose avenues for enhancement based on this insight. Comprehensive evaluations on large-scale video data show improved rate-distortion performance over both state-of-the-art neural and conventional video compression methods. 

   more » « less
4. The evidence for and urgency of threats to African wild dogs from prey depletion and climate change

   https://doi.org/10.1016/j.biocon.2023.110209  

   Creel, Scott; Becker, Matthew S.; de Merkle, Johnathan Reyes; Goodheart, Ben (September 2023, Biological Conservation)

   Many African large carnivore populations are declining due to decline of the herbivore populations on which they depend. We recently noted that the densities of true apex carnivores like the lion and spotted hyena correlate strongly with prey density, but competitively subordinate carnivores like the African wild dog benefit from competitive release when density of apex carnivores is low, so the expected effect of a simultaneous decrease in resources and dominant competitors is not obvious. We found that when prey density drops below a tipping point, the relationship of wild dog density to prey density changes sign, and wild dog density declines. We also noted that ‘prey depletion provides a mechanistically direct explanation of patterns in wild dog dynamics that have been attributed to climate change’ (Creel et al., 2023). Woodroffe et al. concur that prey depletion is an important threat, but suggest that we fail to understand the logic of their assertion that “climate change is likely to cause population collapse” (Rabaiotti et al., 2022), because the “identification of climate change as a threat is not based upon observed temporal trends in wild dog demography”. This statement misses our fundamental point. The data that Woodroffe et al. analyzed were collected over a period with rising temperatures and declining prey populations, so whether or not one tests for a time trend in demography, the data themselves are affected by two patterns: 

   more » « less
5. Improved Bounds in Stochastic Matching and Optimization

   Baveja, Alok; Chavan, Amit; Nikiforov, Andrei; Srinivasan, Aravind; Xu, Pan (January 2018, Algorithmica)

   Real-world problems often have parameters that are uncertain during the optimization phase; stochastic optimization or stochastic programming is a key approach introduced by Beale and by Dantzig in the 1950s to address such uncertainty. Matching is a classical problem in combinatorial optimization. Modern stochastic versions of this problem model problems in kidney exchange, for instance. We improve upon the current-best approximation bound of 3.709 for stochastic matching due to Adamczyk et al. (in: Algorithms-ESA 2015, Springer, Berlin, 2015) to 3.224; we also present improvements on Bansal et al. (Algorithmica 63(4):733–762, 2012) for hypergraph matching and for relaxed versions of the problem. These results are obtained by improved analyses and/or algorithms for rounding linear-programming relaxations of these problems. 

   more » « less