# Stochastic Learning of Computational Resource Usage as Graph Structured Multimarginal Schr"odinger Bridge

arXiv: https://arxiv.org/abs/2405.12463 · HTML: https://mlsanity.com/paper/2405.12463/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 64 references that are in the map.
- First posted on arXiv 21 May 2024.

## Builds on (most cited first, 23 of 23)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Learning Generative Models with Sinkhorn Divergences](https://mlsanity.com/paper/1706.00292/) (2017)
- [A survey of the Schr"odinger problem and some of its connections with optimal transport](https://mlsanity.com/paper/1308.0215/) (2013)
- [Wasserstein Proximal Algorithms for the Schr"odinger Bridge Problem: Density Control with Nonlinear Drift](https://mlsanity.com/paper/1912.01244/) (2019)
- [Multi-marginal optimal transport: theory and applications](https://mlsanity.com/paper/1406.0026/) (2014)
- [An Optimal Transport approach for the Schr"odinger bridge problem and convergence of Sinkhorn algorithm](https://mlsanity.com/paper/1911.06850/) (2019)
- [Reflected Schr"odinger Bridge: Density Control with Path Constraints](https://mlsanity.com/paper/2003.13895/) (2020)
- [Tree-Based Diffusion Schr"odinger Bridge with Applications to Wasserstein Barycenters](https://mlsanity.com/paper/2305.16557/) (2023)
- [Polynomial-time algorithms for Multimarginal Optimal Transport problems with structure](https://mlsanity.com/paper/2008.03006/) (2020)
- [On the complexity of the optimal transport problem with graph-structured cost](https://mlsanity.com/paper/2110.00627/) (2021)
- [Finite Horizon Density Steering for Multi-input State Feedback Linearizable Systems](https://mlsanity.com/paper/1909.12511/) (2019)
- [Neural Schr"odinger Bridge with Sinkhorn Losses: Application to Data-driven Minimum Effort Control of Colloidal Self-assembly](https://mlsanity.com/paper/2307.14442/) (2023)
- [Generalized incompressible flows, multi-marginal transport and Sinkhorn algorithm](https://mlsanity.com/paper/1710.08234/) (2017)
- [A Physics-informed Deep Learning Approach for Minimum Effort Stochastic Control of Colloidal Self-Assembly](https://mlsanity.com/paper/2208.09182/) (2022)
- [Schr"odinger Meets Kuramoto via Feynman-Kac: Minimum Effort Distribution Steering for Noisy Nonuniform Kuramoto Oscillators](https://mlsanity.com/paper/2202.09734/) (2022)
- [Accelerating the Sinkhorn algorithm for sparse multi-marginal optimal transport by fast Fourier transforms](https://mlsanity.com/paper/2208.03120/) (2022)
- [Monge-Kantorovich Optimal Transport Through Constrictions and Flow-rate Constraints](https://mlsanity.com/paper/2212.14509/) (2022)
- [Performance Analysis of Machine Learning Centered Workload Prediction Models for Cloud](https://mlsanity.com/paper/2302.02452/) (2023)
- [Density-based Stochastic Reachability Computation for Occupancy Prediction in Automated Driving](https://mlsanity.com/paper/2006.12581/) (2020)
- [Path Structured Multimarginal Schr"odinger Bridge for Probabilistic Learning of Hardware Resource Usage by Control Software](https://mlsanity.com/paper/2310.00604/) (2023)
- [An excursion onto Schr"odinger's bridges: Stochastic flows with spatio-temporal marginals](https://mlsanity.com/paper/2404.07402/) (2024)
- [Estimating Probabilistic Safe WCET Ranges of Real-Time Systems at Design Stages](https://mlsanity.com/paper/2007.10490/) (2020)
- [Robust risk management via multi-marginal optimal transport](https://mlsanity.com/paper/2211.07694/) (2022)

## Built on by (most cited first, 3 of 3)

- [Optimal Multimarginal Schr"odinger Bridge: Minimum Spanning Tree over Measure-valued Vertices](https://mlsanity.com/paper/2509.10626/) (2025)
- [Generative Profiling for Soft Real-Time Systems and its Applications to Resource Allocation](https://mlsanity.com/paper/2604.01441/) (2026)
- [On the Equivalence of Stochastic Control and Path Space Formulations for Schr"odinger Bridges over Compact Connected Lie Groups](https://mlsanity.com/paper/2609.13758/) (2026)

## Abstract (arXiv)

We propose to learn the time-varying stochastic computational resource usage of software as a graph structured Schr"odinger bridge problem. In general, learning the computational resource usage from data is challenging because resources such as the number of CPU instructions and the number of last level cache requests are both time-varying and statistically correlated. Our proposed method enables learning the joint time-varying stochasticity in computational resource usage from the measured profile snapshots in a nonparametric manner. The method can be used to predict the most-likely time-varying distribution of computational resource availability at a desired time. We provide detailed algorithms for stochastic learning in both single and multi-core cases, discuss the convergence guarantees, computational complexities, and demonstrate their practical use in two case studies: a single-core nonlinear model predictive controller, and a synthetic multi-core software.