A Sharper Generalization Bound for Divide-and-Conquer Ridge Regression

By Shusen Wang. 2019

12 citations recorded by the source corpus.

We study the distributed machine learning problem where the n feature-response pairs are partitioned among m machines uniformly at random. The goal is to approximately solve an empirical risk minimization (ERM) problem with the minimum amount of communication. The divide-and-conquer (DC) method, which was proposed several years ago, lets every worker machine independently solve the same ERM problem using its local feature-response pairs and the driver machine combine the solutions. This approach is in one-shot and thereby extremely communication-efficient. Although the DC method has been studied by many prior works, reasonable generalization bound has not been established before this work.For the ridge regression problem, we show that the prediction error of the DC method on unseen test samples is at most ε times larger than the optimal. There have been constantfactor bounds in the prior works, their sample complexities have a quadratic dependence on d, which does not match the setting of most real-world problems. In contrast, our bounds are much stronger. First, our 1 + ε error bound is much better than their constant-factor bounds. Second, our sample complexity is merely linear with d.

Subfields: Artificial Intelligence, Computational Mechanics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Zhihua Zhang
2. Xiang Li
3. Wenhao Yang
4. Shusen Wang
5. Jianyu Wang
6. Gauri Joshi
7. Yae Jee Cho
8. Jakub Konecný

In Computational Mechanics

1. Zhihua Zhang
2. Xiang Li
3. Wenhao Yang
4. Shusen Wang

Citations in the corpus

• Communication Efficient Decentralized Training with Multiple Local Updates (2019, background): “An orthogonal one is to pay more local computation for less communication, e.g., one-shot aggregation [53, 54, 16, 21, 46], primal-dual algorithms [37, 38, 7] and distributed Newton methods [33, 52, 29, 35, 25].”
• On the Convergence of FedAvg on Non-IID Data (2019, neutral): “, 2018; Zhang and Lin, 2015) and the one-shot methods (Lee et al., 2017; Lin et al., 2017; Wang, 2019; Zhang et al., 2013; 2015b).”
• Communication-Efficient Local Decentralized SGD Methods (2019, methodology): “, one-shot aggregation [47, 48, 14, 19, 41], primal-dual algorithms [32, 33, 6] and distributed Newton methods [29, 46, 26, 30, 23].”