Robust Distributed Online Prediction
Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir and Lin Xiao Microsoft Research
Abstract
The standard model of online prediction deals with serial processing of inputs by a single processor. However, in large-scale online prediction problems, where inputs arrive at a high rate, an increasingly common necessity is to distribute the computation across several processors. A non-trivial challenge is to design distributed algorithms for online prediction, which maintain good regret guarantees. In [4], we presented the DMB algorithm, which is a generic framework to convert any serial gradient-based online prediction algorithm into a distributed algorithm. Moreover, its regret guarantee is asymptotically optimal for smooth convex loss functions and stochastic inputs. On the flip side, it is fragile to many types of failures that are common in distributed environments. In this companion paper, we present variants of the DMB algorithm, which are resilient to many types of network failures, and tolerant to varying performance of the computing nodes.
中文速览
大规模在线预测场景中，输入数据流速极快，单台处理器根本跟不上，必须把计算分散到多个节点——但如何在分布式环境下保持与串行算法相当的"遗憾值（regret）"上界，是个真正棘手的问题。作者团队此前提出了DMB算法，能把任意基于梯度的串行在线学习算法转化为分布式版本，并在损失函数光滑、输入随机的条件下达到渐近最优的O(√m)遗憾界，但原算法默认所有节点速度一致、网络稳定，在真实分布式环境中极易因节点故障、网络抖动或性能差异而崩溃。本文针对这一脆弱性，提出了两类增强方案：一是引入主节点-工作节点架构的MaWo-DMB算法，支持异构集群、动态网络延迟和随机更新规则，并可借助领导者选举算法或分布式数据库实现故障容错；二是完全去中心化的异步版本，无需主节点协调即可容忍节点失效与网络分区。这两种方案在保持与原DMB算法相同渐近最优遗憾保证的同时，大幅提升了算法在工程实践中的健壮性，使分布式在线学习真正具备在复杂真实环境中落地的可行性。
原文 arXiv:1012.1370;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1012.1370v1