Distributed block-diagonal approximation methods for regularized empirical risk minimization

By Ching-pei Lee, Kai-Wei Chang. 2017

15 citations recorded by the source corpus.

In recent years, there is a growing need to train machine learning models on a huge volume of data. Therefore, designing efficient distributed optimization algorithms for empirical risk minimization (ERM) has become an active and challenging research topic. In this paper, we propose a flexible framework for distributed ERM training through solving the dual problem, which provides a unified description and comparison of existing methods. Our approach requires only approximate solutions of the sub-problems involved in the optimization process, and is versatile to be applied on many large-scale machine learning problems including classification, regression, and structured prediction. We show that our framework enjoys global linear convergence for a broad class of non-strongly-convex problems, and some specific choices of the sub-problems can even achieve much faster convergence than existing approaches by a refined analysis. This improved convergence rate is also reflected in the superior empirical performance of our method.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research

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. Martin Jaggi
2. Peter Richtárik
3. Virginia Smith
4. Jakub Konecný
5. Martin Takác
6. Michael I. Jordan
7. Matilde Gargiani
8. Chenxin Ma

In Computational Mechanics

1. Martin Jaggi
2. Virginia Smith
3. Jakub Konecný
4. Peter Richtárik
5. Martin Takác
6. Michael I. Jordan
7. Chenxin Ma
8. Matilde Gargiani

In Management Science and Operations Research

1. Virginia Smith
2. Martin Takác
3. Martin Jaggi
4. Chenxin Ma
5. Simone Forte
6. Michael I. Jordan
7. Jakub Konecný
8. Thomas Hofmann

Citations in the corpus

• COLA: Decentralized Linear Learning (2018, methodology): “In the centralized setting, it has recently been shown that the Hessian information of f can be properly utilized to define improved local subproblems [14, 7].”
• CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, methodology): “, 2017), second-order algorithm extensions (Gargiani, 2017; Lee and Chang, 2017; Dünner et al., 2018; Lee et al., 2018), and accelerated methods (Ma et al.”
• A Distributed Second-Order Algorithm You Can Trust (2018, methodology): “Some approaches suggest using a block-diagonal Hessian approximation such as (Hsieh et al., 2016; Lee & Chang, 2017; Lee & Wright, 2018) but they all rely on a line-search approach which is shown to be inferior to our adaptive approach in the experimental section.”