Parallel and Communication Avoiding Least Angle Regression

作者: L. Grigori , J. Demmel , K. Fountoulakis , M. W. Mahoney , S. Das

DOI:

关键词:

摘要: We are interested in parallelizing the Least Angle Regression (LARS) algorithm for fitting linear regression models to high-dimensional data. consider two parallel and communication avoiding versions of basic LARS algorithm. The algorithms have different asymptotic costs practical performance. One offers more speedup other produces accurate output. first is bLARS, a block version algorithm, where we update b columns at each iteration. Assuming that data row-partitioned, bLARS reduces number arithmetic operations, latency, bandwidth by factor b. second Tournament-bLARS (T-bLARS), tournament processors compete running several computations choose new be added solution. column-partitioned, T-bLARS latency Similarly LARS, our proposed methods generate sequence models. present extensive numerical experiments illustrate speedups up 4x compared without any compromise solution quality.

参考文章(43)
John Wawrzynek, Marghoob Mohiyuddin, Tuning hardware and software for multiprocessors University of California at Berkeley. ,(2012)
J. Vanrosendale, Minimizing inner product data dependencies in conjugate gradient iteration international conference on parallel processing. pp. 44- 46 ,(1983)
James Franklin, The elements of statistical learning : data mining, inference,and prediction The Mathematical Intelligencer. ,vol. 27, pp. 83- 85 ,(2005) , 10.1007/BF02985802
John L. Hennessy, David A. Patterson, Computer Organization and Design: the Hardware/Software Interface ,(1993)
Lynn Elliot Cannon, A cellular computer to implement the kalman filter algorithm Montana State University. pp. 1- 229 ,(1969)
John Shalf, Sudip Dosanjh, John Morrison, Exascale computing technology challenges ieee international conference on high performance computing data and analytics. pp. 1- 25 ,(2010) , 10.1007/978-3-642-19328-6_1
James W. Demmel, Michael Heroux, Mark Hoemmen, Marghoob Mohiyuddin, Katherine Yelick, Communication-avoiding krylov subspace methods University of California at Berkeley. ,(2010)
Olivier Fercoq, Peter Richtárik, Accelerated, Parallel, and Proximal Coordinate Descent Siam Journal on Optimization. ,vol. 25, pp. 1997- 2023 ,(2015) , 10.1137/130949993