Distributed Online Linear Regressions

DOI10.1109/TIT.2020.3029304MaRDI QIDQ5151735zbMATH OpenOpenAlexFDO

Authors Deming Yuan, Alexandre Proutiere, Guodong Shi

Publication date 22 February 2021

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.04774

zbMATH Keywords

distributed regression algorithmsdistributed settingonline linear regression problems

Mathematics Subject Classification ID

Applications of graph theory (05C90) Linear regression; mixed models (62J05) Statistical aspects of big data and data science (62R07) Distributed systems (68M14) Convex programming (90C25)

Abstract: We study online linear regression problems in a distributed setting, where the data is spread over a network. In each round, each network node proposes a linear predictor, with the objective of fitting the emph{network-wide} data. It then updates its predictor for the next round according to the received local feedback and information received from neighboring nodes. The predictions made at a given node are assessed through the notion of regret, defined as the difference between their cumulative network-wide square errors and those of the best off-line network-wide linear predictor. Various scenarios are investigated, depending on the nature of the local feedback (full information or bandit feedback), on the set of available predictors (the decision set), and the way data is generated (by an oblivious or adaptive adversary). We propose simple and natural distributed regression algorithms, involving, at each node and in each round, a local gradient descent step and a communication and averaging step where nodes aim at aligning their predictors to those of their neighbors. We establish regret upper bounds typically in $calO(T^{3/4})$ when the decision set is unbounded and in $calO(sqrtT)$ in case of bounded decision set.

Cited in

(7)

• Distributed solver for linear matrix inequalities: an optimization perspective
• Distributed consensus-based solver for semi-definite programming: an optimization viewpoint
• Distributed regularized online optimization using forward-backward splitting
• Distributed online bandit linear regressions with differential privacy
• No-regret learning for repeated non-cooperative games with lossy bandits
• Distributed online constrained convex optimization with event-triggered communication
• Dynamic regret for decentralized online bandit gradient descent with local steps

This page was built for publication: Distributed Online Linear Regressions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5151735)