Centralized and distributed online learning for sparse time-varying optimization

• URL: http://arxiv.org/abs/2001.11939v1
• Date: Fri, 31 Jan 2020 16:29:38 GMT
• Title: Centralized and distributed online learning for sparse time-varying optimization
• Abstract summary: Development of online algorithms to track time-varying systems has drawn a lot of attention in the last years. We propose an online learning approach, which does not employ a given model and is suitable for adversarial frameworks. Specifically, we develop centralized and distributed algorithms, and we theoretically analyze them in terms of dynamic regret.
• Score: 2.7006549420999937
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: The development of online algorithms to track time-varying systems has drawn a lot of attention in the last years, in particular in the framework of online convex optimization. Meanwhile, sparse time-varying optimization has emerged as a powerful tool to deal with widespread applications, ranging from dynamic compressed sensing to parsimonious system identification. In most of the literature on sparse time-varying problems, some prior information on the system's evolution is assumed to be available. In contrast, in this paper, we propose an online learning approach, which does not employ a given model and is suitable for adversarial frameworks. Specifically, we develop centralized and distributed algorithms, and we theoretically analyze them in terms of dynamic regret, in an online learning perspective. Further, we propose numerical experiments that illustrate their practical effectiveness.

Related papers

• Parsimonious Learning-Augmented Online Metric Matching [1.5755923640031846]
  A growing line of work studies the tradeoff between performance guarantees and the number of predictions used in learning-augmented algorithms.<n>We develop parsimonious learning-augmented algorithms and establish lower bounds on their performance.<n>Our approach extends the Follow-the-Prediction framework to the parsimonious setting by filling in a virtual prediction in the absence of an actual prediction.
  arXiv  Detail & Related papers  (2026-05-26T11:47:58Z)
• Online-BLS: An Accurate and Efficient Online Broad Learning System for Data Stream Classification [52.251569042852815]
  We introduce an online broad learning system framework with closed-form solutions for each online update. We design an effective weight estimation algorithm and an efficient online updating strategy. Our framework is naturally extended to data stream scenarios with concept drift and exceeds state-of-the-art baselines.
  arXiv  Detail & Related papers  (2025-01-28T13:21:59Z)
• Handling Delayed Feedback in Distributed Online Optimization : A Projection-Free Approach [1.9797215742507548]
  Learning at the edges has become increasingly important as large quantities of data are continually generated locally. We propose two projection-free algorithms for centralised and distributed settings in which they are carefully designed to achieve a regret bound of O(sqrtB) where B is the sum of delay. We provide an extensive theoretical study and experimentally validate the performance of our algorithms by comparing them with existing ones on real-world problems.
  arXiv  Detail & Related papers  (2024-02-03T10:43:22Z)
• Efficient Methods for Non-stationary Online Learning [67.3300478545554]
  We present efficient methods for optimizing dynamic regret and adaptive regret, which reduce the number of projections per round from $mathcalO(log T)$ to $1$. Our technique hinges on the reduction mechanism developed in parameter-free online learning and requires non-trivial twists on non-stationary online methods.
  arXiv  Detail & Related papers  (2023-09-16T07:30:12Z)
• Online Network Source Optimization with Graph-Kernel MAB [62.6067511147939]
  We propose Grab-UCB, a graph- kernel multi-arms bandit algorithm to learn online the optimal source placement in large scale networks. We describe the network processes with an adaptive graph dictionary model, which typically leads to sparse spectral representations. We derive the performance guarantees that depend on network parameters, which further influence the learning curve of the sequential decision strategy.
  arXiv  Detail & Related papers  (2023-07-07T15:03:42Z)
• Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making [73.48977854003697]
  This work introduces a new notion of complexity, the generalized bracketing numbers, which marries constraints on the adversary to the size of the space. We then instantiate our bounds in several problems of interest, including online prediction and planning of piecewise continuous functions.
  arXiv  Detail & Related papers  (2023-02-10T18:45:52Z)
• Smoothed Online Learning for Prediction in Piecewise Affine Systems [43.64498536409903]
  This paper builds on the recently developed smoothed online learning framework. It provides the first algorithms for prediction and simulation in piecewise affine systems.
  arXiv  Detail & Related papers  (2023-01-26T15:54:14Z)
• Efficient Online Learning with Memory via Frank-Wolfe Optimization: Algorithms with Bounded Dynamic Regret and Applications to Control [15.588080817106563]
  We introduce the first projection-free meta-base learning algorithm with memory that minimizes dynamic regret. We are motivated by artificial intelligence applications where autonomous agents need to adapt to time-varying environments.
  arXiv  Detail & Related papers  (2023-01-02T01:12:29Z)
• Socio-cognitive Optimization of Time-delay Control Problems using Evolutionary Metaheuristics [89.24951036534168]
  Metaheuristics are universal optimization algorithms which should be used for solving difficult problems, unsolvable by classic approaches. In this paper we aim at constructing novel socio-cognitive metaheuristic based on castes, and apply several versions of this algorithm to optimization of time-delay system model.
  arXiv  Detail & Related papers  (2022-10-23T22:21:10Z)
• Learning for Spatial Branching: An Algorithm Selection Approach [0.0]
  We develop a learning framework for branching and show its efficacy in the context of non-linear optimization problems. The proposed learning is performed offline, based on instance-specific features and with no computational overhead when solving new instances. Experiments on different benchmark instances from the show literature that the learning-based branching rule significantly outperforms the standard rules.
  arXiv  Detail & Related papers  (2022-04-22T17:23:43Z)
• Deep Efficient Continuous Manifold Learning for Time Series Modeling [11.876985348588477]
  A symmetric positive definite matrix is being studied in computer vision, signal processing, and medical image analysis. In this paper, we propose a framework to exploit a diffeomorphism mapping between Riemannian manifold and a Cholesky space. For dynamic modeling of time-series data, we devise a continuous manifold learning method by systematically integrating a manifold ordinary differential equation and a gated recurrent neural network.
  arXiv  Detail & Related papers  (2021-12-03T01:38:38Z)
• Supervised DKRC with Images for Offline System Identification [77.34726150561087]
  Modern dynamical systems are becoming increasingly non-linear and complex. There is a need for a framework to model these systems in a compact and comprehensive representation for prediction and control. Our approach learns these basis functions using a supervised learning approach.
  arXiv  Detail & Related papers  (2021-09-06T04:39:06Z)
• Decentralized MCTS via Learned Teammate Models [89.24858306636816]
  We present a trainable online decentralized planning algorithm based on decentralized Monte Carlo Tree Search. We show that deep learning and convolutional neural networks can be employed to produce accurate policy approximators.
  arXiv  Detail & Related papers  (2020-03-19T13:10:20Z)

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.