-Regression in the Arbitrary Partition Model of Communication.

Area of Science:

• Distributed computing
• Information theory
• Machine learning

Background:

• The distributed regression problem involves a coordinator and multiple servers holding data partitions.
• Existing communication complexity bounds for this problem are suboptimal, particularly for general regression.

Purpose of the Study:

• To derive improved randomized communication complexity bounds for the distributed regression problem in the coordinator model.
• To establish optimal bounds for least squares regression and provide new bounds for general regression.

Main Methods:

• Utilizing a randomized approach within the coordinator model for distributed computation.
• Analyzing communication complexity in the arbitrary partition model where data is additively shared.

Main Results:

• Achieved the first optimal bound of O(log(1/δ)) bits for distributed least squares regression.
• Established an O(n^(1/3)) upper bound for general distributed regression.
• Demonstrated that for large n, the leading term depends linearly, not quadratically, on n.
• Proved communication lower bounds of Ω(n^(1/3)) for general regression and Ω(1) for least squares.

Conclusions:

• The new bounds represent significant improvements over existing results.
• The findings offer more efficient communication protocols for distributed regression tasks.