Distributed Newton Methods for Regularized Logistic Regression
Lecture notes in computer sciencePublished 1 January 2015
Yong Zhuang, Wei-Sheng Chin, Yu-Chin Juan, Chih‐Jen Lin
Citations35
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Experiments show that the proposed distributed Newton method for training logistic regression is competitive with or even faster than state-of-the-art approaches such as Alternating Direction Method of Multipliers and Vowpal Wabbit.
Abstract
Regularized logistic regression is a very useful classification method, but for large-scale data, its distributed training has not been investigated much. In this work, we propose a distributed Newton method for training logistic regression. Many interesting techniques are discussed for reducing the communication cost and speeding up the computation. Experiments show that the proposed method is competitive with or even faster than state-of-the-art approaches such as Alternating Direction Method of Multipliers (ADMM) and Vowpal Wabbit (VW). We have released an MPI-based implementation for public use.
Keywords
Computer ScienceEngineering
Foundations and Trends® in Machine LearningDistributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
15,983 Citations2011Stephen Boyd, Neal Parikh +3 more
now publishers, Inc. eBooksDistributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
13,365 Citations2010Stephen Boyd
It is argued that the alternating direction method of multipliers is well suited to distributed convex optimization, and in particular to large-scale problems arising in statistics, machine learning, and related areas.
Adaptive Subgradient Methods for Online Learning and Stochastic Optimization
8,612 Citations2011John C. Duchi, Elad Hazan +1 more
Mathematical ProgrammingOn the limited memory BFGS method for large scale optimization
8,529 Citations1989Dong C. Liu, Jorge Nocedal
The numerical tests indicate that the L-BFGS method is faster than the method of Buckley and LeNir, and is better able to use additional storage to accelerate convergence, and the convergence properties are studied to prove global convergence on uniformly convex problems.
LIBLINEAR: A Library for Large Linear Classification
6,625 Citations2008Rong-En Fan, Kai‐Wei Chang +3 more
Lecture notes in computer scienceOpen MPI: Goals, Concept, and Design of a Next Generation MPI Implementation
1,558 Citations2004Edgar Gabriel, Graham E. Fagg +12 more
Open MPI provides a unique combination of novel features previously unavailable in an open-source, production-quality implementation of MPI, which provides both a stable platform for third-party research as well as enabling the run-time composition of independent software add-ons.
Parallelized Stochastic Gradient Descent
1,074 Citations2010Martin Zinkevich, Markus Weimer +2 more
This paper presents the first parallel stochastic gradient descent algorithm including a detailed analysis and experimental evidence and introduces a novel proof technique — contractive mappings to quantify the speed of convergence of parameter distributions to their asymptotic limits.
SIAM Journal on Numerical AnalysisThe Conjugate Gradient Method and Trust Regions in Large Scale Optimization
830 Citations1983Trond Steihaug
It is shown in this paper that an approximate solution of the trust region problem may be found by the preconditioned conjugate gradient method, and it is shown that the method has the same convergence properties as existing methods based on the dogleg strategy using an approximate Hessian.
Machine LearningDual coordinate descent methods for logistic regression and maximum entropy models
389 Citations2010Hsiang‐Fu Yu, Fang-Lan Huang +1 more
This paper applies coordinate descent methods to solve the dual form of logistic regression and maximum entropy, and shows that many details are different from the situation in linear SVM.
Mathematical ProgrammingParallel coordinate descent methods for big data optimization
374 Citations2015Peter Richtárik, Martin Takáč
This work shows that randomized (block) coordinate descent methods can be accelerated by parallelization when applied to the problem of minimizing the sum of a partially separable smooth convex function and a simple separable conveX function.
SIAM Journal on OptimizationNewton's Method for Large Bound-Constrained Optimization Problems
315 Citations1999Chih‐Jen Lin, Jorge J. Morè
A trust region version of Newton's method for bound-constrained problems that holds for linearly constrained problems and yields global and superlinear convergence without assuming either strict complementarity or linear independence of the active constraints.
Trust region Newton methods for large-scale logistic regression
287 Citations2007Chih‐Jen Lin, Ruby C. Weng +1 more
This paper applies a trust region Newton method to maximize the log-likelihood of the logistic regression model, which uses only approximate Newton steps in the beginning, but achieves fast convergence in the end.
Journal of Machine Learning ResearchTrust Region Newton Method for Logistic Regression
287 Citations2008Chih‐Jen Lin, Ruby C. Weng +1 more
This paper applies a trust region Newton method to maximize the log-likelihood of the logistic regression model, and extends the proposed method to large-scale L2-loss linear support vector machines (SVM).
Journal of Machine Learning ResearchA Modified Finite Newton Method for Fast Solution of Large Scale Linear SVMs
272 Citations2005S. Sathiya Keerthi, Dennis DeCoste
A fast method for solving linear SVMs with L2 loss function that is suited for large scale data mining tasks such as text classification is developed by modifying the finite Newton method of Mangasarian in several ways.
arXiv (Cornell University)A Reliable Effective Terascale Linear Learning System
243 Citations2011Alekh Agarwal, Olivier Chapelle +2 more
arXiv (Cornell University)Parallel Coordinate Descent for L1-Regularized Loss Minimization
216 Citations2011Joseph K. Bradley, Aapo Kyrola +2 more
A Comparison of Optimization Methods and Software for Large-scale L1-regularized Linear Classification
207 Citations2010Guo-Xun Yuan, Kai-Wei Chang +2 more
International Conference on Machine LearningParallel Coordinate Descent for L1-Regularized Loss Minimization
103 Citations2011Aapo Kyrola, Daniel Bickson +2 more
Large-scale logistic regression and linear support vector machines using spark
74 Citations2014Chieh-Yen Lin, Cheng-Hao Tsai +2 more
This work considers a distributed Newton method for solving logistic regression as well linear SVM and implements it on Spark, and releases an efficient and easy-to-use tool for the Spark community.
Efficient Distributed Linear Classification Algorithms via the Alternating Direction Method of Multipliers
57 Citations2012Caoxie Zhang, Honglak Lee +1 more
This paper proposes and implements distributed algorithms that achieve parallel disk loading and access the disk only once that are faster than existing distributed solvers, such as Zinkevich et al.
Lecture notes in computer scienceBundle CDN: A Highly Parallelized Approach for Large-Scale ℓ1-Regularized Logistic Regression
5 Citations2013Yatao Bian, Xiong Li +2 more
Experimental evaluations over five public datasets show that BCDN can better exploit parallelism and outperforms state-of-the-art algorithms in speed, without losing testing accuracy.