Links
Modern datasets usually have a large number of features or training samples, and they are usually stored in a distributed manner. Motivated by the need of solving sparse optimization problems with large datasets, we propose two approaches including (i) distributed implementations of prox-linear algorithms and (ii) GRock, a parallel greedy coordinate descent method.
P-FISTA: parallel fast iterative soft-thresholding algorithm
PD-ADMM: parallel dual alternating direction method of multipliers
: dense matrix with 100K rows and 200K columns, 20 billion entries in total, 170GB in size
: 200K entries, 4K nonzeros (2% sparse), Gaussian values
20 “high-memory quadruple extra-large instances”
each instance has 8 cores and 60GB memory
We tried to recover
by solving
in which
and
were set so that
is the exact solution
p D-ADMM: parallelized dual ADMM, solving the dual formulation of LASSO
p FISTA: parallelized FISTA, solving the dual formulation of LASSO
GRock: parallized greedy coordinate-block descent
|
ADMM's performance depends on a certain penalty parameter
. We picked
as the best out of only a few trials (we cannot afford more). It is likely that the performance of PD-ADMM can be further improved
step size for FISTA is evaluated based on the spectral radius of 
stopping creterions include:
maximum number of iterations: 2500
a relative error of 1E-5
The Adult Data Set from the UCI Machine Learning Repository
Rice cluster STIC
We tested our codes on 1, 8, 16, 64, and 128 cores
We tried to recover a hyperplane
for classification with a sparse normal vector
. The model is
for given feature data points
and labels
,
.
p FISTA: our parallel implementation of FISTA. FISTA is a prox-linear algorithm with Nesterov's acceleration by Beck and Toubelle.
GRock: parallized greedy coordinate-block descent
| cores | p FISTA seconds | GRock seconds |
| 1 | 8.74 | 1.74 |
| 8 | 2.24 | 0.48 |
| 16 | 0.6 | 0.13 |
| 64 | 0.24 | 0.05 |
| 128 | 0.24 | 0.07 |
Z. Peng, M. Yan, and W. Yin. Parallel and Distributed Sparse Optimization, preprint, 2013