Scalable Dual Coordinate Descent for Kernel Methods

Overview

• This paper introduces new variants of the Dual Coordinate Descent (DCD) and Block Dual Coordinate Descent (BDCD) algorithms for solving kernel-based machine learning problems like Support Vector Machines (SVMs) and Ridge Regression.
• The key challenge addressed is the high communication cost of these algorithms on distributed parallel systems, which can dominate the overall running time.
• The new "s-step" variants reduce the communication frequency by a tunable factor of s, at the expense of slightly more computation and bandwidth.
• Theoretical analysis and experiments demonstrate that the s-step variants achieve significant speedups of up to 9.8x over existing methods, while maintaining numerical stability.

Plain English Explanation

The paper focuses on Dual Coordinate Descent (DCD) and Block Dual Coordinate Descent (BDCD) - important algorithms for solving optimization problems that arise in machine learning, like training Kernel Support Vector Machines (K-SVMs) and Kernel Ridge Regression (K-RR) models.

These algorithms work by iteratively updating small parts of the solution at a time. When running on distributed parallel systems, they need to communicate these updates between processors every iteration, which can become the slowest part of the computation, especially on modern hardware where communication is very expensive compared to computation.

The key innovation in this paper is to develop new "s-step" variants of DCD and BDCD that reduce the communication frequency by a tunable factor of s. This means the algorithms only need to communicate every s iterations, instead of every iteration. This reduces the overall communication cost, but requires a bit more computation and bandwidth per iteration.

The paper proves that these s-step variants compute the exact same final solution as the original algorithms, and shows through experiments that they are also numerically stable, even for large values of s. They were able to achieve speedups of up to 9.8x over the original algorithms when running on up to 512 processor cores.

Technical Explanation

The paper starts by formulating the K-SVM and K-RR problems as convex optimization problems, which can be solved using iterative methods like DCD and BDCD.

The key challenge is that on distributed-memory parallel systems, the scalability of these methods is limited by the need to communicate updates between processors every iteration. To address this, the authors derive new "s-step" variants of DCD and BDCD that reduce the communication frequency by a factor of s.

The s-step variants work by computing s iterations of the original algorithm locally on each processor, and then only communicating the cumulative updates. This reduces the communication costs, but requires more local computation and bandwidth per iteration.

The authors prove that the s-step variants compute the same final solution as the original DCD and BDCD methods, up to floating-point precision. They also perform numerical experiments to demonstrate the stability of the s-step variants, even for large values of s.

Theoretical analysis is provided to bound the computational and communication costs of the s-step variants. The authors develop high-performance C and MPI implementations and present scaling experiments on a Cray EX cluster, demonstrating speedups of up to 9.8x over the original methods using up to 512 cores.

Critical Analysis

The paper presents a well-designed and thorough analysis of the proposed s-step variants of DCD and BDCD. The theoretical and empirical results demonstrate the effectiveness of the approach in reducing communication costs while maintaining numerical stability and convergence.

One potential limitation is that the analysis is focused on the specific K-SVM and K-RR problems, and it's not clear if the s-step approach would generalize well to other optimization problems. The authors mention that the techniques could be applied to other problems, but further research would be needed to validate this.

Additionally, the paper does not explore the trade-offs between the degree of communication reduction (i.e., the value of s) and the computational overhead. It would be interesting to see an analysis of how to choose the optimal value of s for different problem sizes and hardware configurations.

Finally, while the scaling experiments on the Cray EX cluster are impressive, it would be valuable to see results on a more diverse set of hardware platforms to better understand the generalizability of the approach.

Overall, this paper makes a significant contribution to the field of parallel optimization algorithms, and the s-step variants of DCD and BDCD could have important implications for efficiently solving large-scale kernel-based machine learning problems on distributed systems.

Conclusion

This paper introduces new "s-step" variants of the Dual Coordinate Descent (DCD) and Block Dual Coordinate Descent (BDCD) algorithms, which address the high communication costs that can dominate the running time of these methods on distributed parallel systems.

The s-step variants reduce the communication frequency by a tunable factor of s, at the expense of slightly more local computation and bandwidth per iteration. Theoretical analysis and experiments demonstrate that these s-step variants can achieve significant speedups of up to 9.8x over the original algorithms, while maintaining numerical stability.

The techniques developed in this paper could have important implications for efficiently solving large-scale kernel-based machine learning problems, such as Support Vector Machines and Ridge Regression, on modern distributed computing platforms. The work represents an important advancement in the field of parallel optimization algorithms.