skglm.experimental.PDCD_WS#

class skglm.experimental.PDCD_WS(max_iter=1000, max_epochs=1000, dual_init=None, p0=100, tol=1e-06, verbose=False)[source]#

Primal-Dual Coordinate Descent solver with working sets.

It solves

`\min_w F(Xw) + G(w)`

using a primal-dual method on the saddle point problem

`min_w max_z (:Xw, z:) + G(w) - F^**(z)`

where `F` is the datafit term (`F^**` its Fenchel conjugate) and `G` is the penalty term.

The datafit is required to be convex and proximable. Also, the penalty is required to be convex, separable, and proximable.

The solver is an adaptation of algorithm [1] to working sets [2]. The working sets are built using a fixed point distance strategy where each feature is assigned a score based how much its coefficient varies when performing a primal update

`"score"_j = abs(w_j - "prox"_(tau_j, G_j)(w_j - tau_j (:X_j, z:)))`

where `tau_j` is the primal step associated with the j-th feature.

Parameters:
max_iterint, optional

The maximum number of iterations or equivalently the the maximum number of solved subproblems.

max_epochsint, optional

Maximum number of primal CD epochs on each subproblem.

dual_initarray, shape (n_samples,) default None

The initialization of dual variables. If None, they are initialized as the 0 vector np.zeros(n_samples).

p0int, optional

First working set size.

tolfloat, optional

The tolerance for the optimization.

verbosebool or int, default False

Amount of verbosity. 0/False is silent.

References

[1]

Olivier Fercoq and Pascal Bianchi, “A Coordinate-Descent Primal-Dual Algorithm with Large Step Size and Possibly Nonseparable Functions”, SIAM Journal on Optimization, 2020, https://epubs.siam.org/doi/10.1137/18M1168480, code: https://github.com/Badr-MOUFAD/Fercoq-Bianchi-solver

[2]

Bertrand, Q. and Klopfenstein, Q. and Bannier, P.-A. and Gidel, G. and Massias, M. “Beyond L1: Faster and Better Sparse Models with skglm”, NeurIPS, 2022 https://arxiv.org/abs/2204.07826

__init__(max_iter=1000, max_epochs=1000, dual_init=None, p0=100, tol=1e-06, verbose=False)[source]#

Methods

__init__([max_iter, max_epochs, dual_init, ...])

solve(X, y, datafit_, penalty_[, w_init, ...])