Learning Mixtures of Linear Dynamical Systems

• URL: http://arxiv.org/abs/2201.11211v1
• Date: Wed, 26 Jan 2022 22:26:01 GMT
• Title: Learning Mixtures of Linear Dynamical Systems
• Authors: Yanxi Chen, H. Vincent Poor
• Abstract summary: We develop a two-stage meta-algorithm to efficiently recover each ground-truth LDS model up to error $tildeO(sqrtd/T)$. We validate our theoretical studies with numerical experiments, confirming the efficacy of the proposed algorithm.
• Score: 94.49754087817931
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of learning a mixture of multiple linear dynamical systems (LDSs) from unlabeled short sample trajectories, each generated by one of the LDS models. Despite the wide applicability of mixture models for time-series data, learning algorithms that come with end-to-end performance guarantees are largely absent from existing literature. There are multiple sources of technical challenges, including but not limited to (1) the presence of latent variables (i.e. the unknown labels of trajectories); (2) the possibility that the sample trajectories might have lengths much smaller than the dimension $d$ of the LDS models; and (3) the complicated temporal dependence inherent to time-series data. To tackle these challenges, we develop a two-stage meta-algorithm, which is guaranteed to efficiently recover each ground-truth LDS model up to error $\tilde{O}(\sqrt{d/T})$, where $T$ is the total sample size. We validate our theoretical studies with numerical experiments, confirming the efficacy of the proposed algorithm.

Related papers

• Enhancing Unsupervised Sentence Embeddings via Knowledge-Driven Data Augmentation and Gaussian-Decayed Contrastive Learning [37.54523122932728]
  We propose a pipeline-based data augmentation method via large language models (LLMs) To tackle the issue of low data diversity, our pipeline utilizes knowledge graphs (KGs) to extract entities and quantities. To address high data noise, the GCSE model uses a Gaussian-decayed function to limit the impact of false hard negative samples.
  arXiv  Detail & Related papers  (2024-09-19T16:29:58Z)
• Characterization of Large Language Model Development in the Datacenter [55.9909258342639]
  Large Language Models (LLMs) have presented impressive performance across several transformative tasks. However, it is non-trivial to efficiently utilize large-scale cluster resources to develop LLMs. We present an in-depth characterization study of a six-month LLM development workload trace collected from our GPU datacenter Acme.
  arXiv  Detail & Related papers  (2024-03-12T13:31:14Z)
• Diffusion Model is an Effective Planner and Data Synthesizer for Multi-Task Reinforcement Learning [101.66860222415512]
  Multi-Task Diffusion Model (textscMTDiff) is a diffusion-based method that incorporates Transformer backbones and prompt learning for generative planning and data synthesis. For generative planning, we find textscMTDiff outperforms state-of-the-art algorithms across 50 tasks on Meta-World and 8 maps on Maze2D.
  arXiv  Detail & Related papers  (2023-05-29T05:20:38Z)
• Learning the Dynamics of Sparsely Observed Interacting Systems [0.6021787236982659]
  We address the problem of learning the dynamics of an unknown non-parametric system linking a target and a feature time series. By leveraging the rich theory of signatures, we are able to cast this non-linear problem as a high-dimensional linear regression.
  arXiv  Detail & Related papers  (2023-01-27T10:48:28Z)
• Collaborative Intelligence Orchestration: Inconsistency-Based Fusion of Semi-Supervised Learning and Active Learning [60.26659373318915]
  Active learning (AL) and semi-supervised learning (SSL) are two effective, but often isolated, means to alleviate the data-hungry problem. We propose an innovative Inconsistency-based virtual aDvErial algorithm to further investigate SSL-AL's potential superiority. Two real-world case studies visualize the practical industrial value of applying and deploying the proposed data sampling algorithm.
  arXiv  Detail & Related papers  (2022-06-07T13:28:43Z)
• Distributed Dynamic Safe Screening Algorithms for Sparse Regularization [73.85961005970222]
  We propose a new distributed dynamic safe screening (DDSS) method for sparsity regularized models and apply it on shared-memory and distributed-memory architecture respectively. We prove that the proposed method achieves the linear convergence rate with lower overall complexity and can eliminate almost all the inactive features in a finite number of iterations almost surely.
  arXiv  Detail & Related papers  (2022-04-23T02:45:55Z)
• Statistics and Deep Learning-based Hybrid Model for Interpretable Anomaly Detection [0.0]
  Hybrid methods have been shown to outperform pure statistical and pure deep learning methods at both forecasting tasks. MES-LSTM is an interpretable anomaly detection model that overcomes these challenges.
  arXiv  Detail & Related papers  (2022-02-25T14:17:03Z)
• PIETS: Parallelised Irregularity Encoders for Forecasting with Heterogeneous Time-Series [5.911865723926626]
  Heterogeneity and irregularity of multi-source data sets present a significant challenge to time-series analysis. In this work, we design a novel architecture, PIETS, to model heterogeneous time-series. We show that PIETS is able to effectively model heterogeneous temporal data and outperforms other state-of-the-art approaches in the prediction task.
  arXiv  Detail & Related papers  (2021-09-30T20:01:19Z)
• Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systems [45.17023170054112]
  We consider the setting of vector valued non-linear dynamical systems $X_t+1 = phi(A* X_t) + eta_t$, where $eta_t$ is unbiased noise and $phi : mathbbR to mathbbR$ is a known link function that satisfies certain em expansivity property.
  arXiv  Detail & Related papers  (2021-05-24T22:14:26Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  We adapt an algorithm of Klivans and Meka based on the method of multiplicative weight updates. The algorithm enjoys a sample complexity bound that is qualitatively similar to others in the literature. It has a low runtime $O(mp2)$ in the case of $m$ samples and $p$ nodes, and can trivially be implemented in an online manner.
  arXiv  Detail & Related papers  (2020-02-20T10:50:58Z)

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.