A Resilient Distributed Boosting Algorithm

Yuval filmus · Idan Mehalel · Shay Moran

Hall E #1209

Keywords: [ T: Optimization ] [ T: Learning Theory ]

[ Abstract ]
[ Paper PDF
Wed 20 Jul 3:30 p.m. PDT — 5:30 p.m. PDT
Spotlight presentation: T: Online Learning and Bandits/Learning Theory
Wed 20 Jul 10:15 a.m. PDT — 11:45 a.m. PDT


Given a learning task where the data is distributed among several parties, communication is one of the fundamental resources which the parties would like to minimize.We present a distributed boosting algorithm which is resilient to a limited amount of noise. Our algorithm is similar to classical boosting algorithms, although it is equipped with a new component, inspired by Impagliazzo's hard-core lemma (Impagliazzo, 1995), adding a robustness quality to the algorithm. We also complement this result by showing that resilience to any asymptotically larger noise is not achievable by a communication-efficient algorithm.

Chat is not available.