Stochastic Learning of Computational Resource Usage as Graph Structured Multimarginal Schrödinger Bridge

• URL: http://arxiv.org/abs/2405.12463v1
• Date: Tue, 21 May 2024 02:39:45 GMT
• Title: Stochastic Learning of Computational Resource Usage as Graph Structured Multimarginal Schrödinger Bridge
• Authors: Georgiy A. Bondar, Robert Gifford, Linh Thi Xuan Phan, Abhishek Halder,
• Abstract summary: We propose to learn the time-varying computational resource usage of software as a graph structured Schr"odinger bridge problem. We provide detailed algorithms for learning in both single and multi-core cases, discuss the convergence guarantees, computational complexities, and demonstrate their practical use.
• Score: 1.6111903346958474
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Path Structured Multimarginal Schr\"odinger Bridge for Probabilistic Learning of Hardware Resource Usage by Control Software [1.7601096935307592]
  The solution of the path structured multimarginal Schr"odinger bridge problem (MSBP) is the most-likely measure-valued trajectory. We leverage recent algorithmic advances in solving such MSBPs for learning hardware resource usage by control software.
  arXiv  Detail & Related papers  (2023-10-01T07:35:12Z)
• Randomized Polar Codes for Anytime Distributed Machine Learning [66.46612460837147]
  We present a novel distributed computing framework that is robust to slow compute nodes, and is capable of both approximate and exact computation of linear operations. We propose a sequential decoding algorithm designed to handle real valued data while maintaining low computational complexity for recovery. We demonstrate the potential applications of this framework in various contexts, such as large-scale matrix multiplication and black-box optimization.
  arXiv  Detail & Related papers  (2023-09-01T18:02:04Z)
• Bootstrap aggregation and confidence measures to improve time series causal discovery [0.0]
  We introduce a novel bootstrap approach designed for time series causal discovery that preserves the temporal dependencies and lag structure. We combine this approach with the state-of-the-art conditional-independence-based algorithm PCMCI+.
  arXiv  Detail & Related papers  (2023-06-15T08:37:16Z)
• Learnability with Time-Sharing Computational Resource Concerns [65.268245109828]
  We present a theoretical framework that takes into account the influence of computational resources in learning theory. This framework can be naturally applied to stream learning where the incoming data streams can be potentially endless. It may also provide a theoretical perspective for the design of intelligent supercomputing operating systems.
  arXiv  Detail & Related papers  (2023-05-03T15:54:23Z)
• A two stages Deep Learning Architecture for Model Reduction of Parametric Time-Dependent Problems [0.0]
  Parametric time-dependent systems are of crucial importance in modeling real phenomena. We present a general two-stages deep learning framework able to perform that generalization with low computational effort in time. Results are obtained applying the framework to incompressible Navier-Stokes equations in a cavity.
  arXiv  Detail & Related papers  (2023-01-24T11:24:18Z)
• A heuristic method for data allocation and task scheduling on heterogeneous multiprocessor systems under memory constraints [14.681986126866452]
  This paper focuses on the data allocation and task scheduling problem under memory constraints. We propose a tabu search algorithm (TS) which combines several distinguished features. Experimental results show that the the proposed TS algorithm can obtain relatively high-quality solutions in a reasonable computational time.
  arXiv  Detail & Related papers  (2022-05-09T10:46:08Z)
• AsySQN: Faster Vertical Federated Learning Algorithms with Better Computation Resource Utilization [159.75564904944707]
  We propose an asynchronous quasi-Newton (AsySQN) framework for vertical federated learning (VFL) The proposed algorithms make descent steps scaled by approximate without calculating the inverse Hessian matrix explicitly. We show that the adopted asynchronous computation can make better use of the computation resource.
  arXiv  Detail & Related papers  (2021-09-26T07:56:10Z)
• Resource Allocation in Multi-armed Bandit Exploration: Overcoming Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
  We study exploration in multi-armed bandits when we have access to a divisible resource that can be allocated in varying amounts to arm pulls. We focus in particular on the allocation of distributed computing resources, where we may obtain results faster by allocating more resources per pull.
  arXiv  Detail & Related papers  (2020-10-31T18:19:29Z)
• A Constraint-Based Algorithm for the Structural Learning of Continuous-Time Bayesian Networks [70.88503833248159]
  We propose the first constraint-based algorithm for learning the structure of continuous-time Bayesian networks. We discuss the different statistical tests and the underlying hypotheses used by our proposal to establish conditional independence.
  arXiv  Detail & Related papers  (2020-07-07T07:34:09Z)
• Learned Factor Graphs for Inference from Stationary Time Sequences [107.63351413549992]
  We propose a framework that combines model-based algorithms and data-driven ML tools for stationary time sequences. neural networks are developed to separately learn specific components of a factor graph describing the distribution of the time sequence. We present an inference algorithm based on learned stationary factor graphs, which learns to implement the sum-product scheme from labeled data.
  arXiv  Detail & Related papers  (2020-06-05T07:06:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.