skglm.experimental.PDCD_WS#

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

Primal-Dual Coordinate Descent solver with working sets.

It solves

${\displaystyle \underset{w}{min}F\left(Xw\right)+G\left(w\right)}$

using a primal-dual method on the saddle point problem

${\displaystyle \underset{w}{min}\underset{z}{max}\langle Xw,z\rangle +G\left(w\right)-F^{\ast }\left(z\right)}$

where ${\displaystyle F}$ is the datafit term (${\displaystyle F^{\ast }}$ its Fenchel conjugate) and ${\displaystyle 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

${\displaystyle {\text{score}}_j=\left|w_j-{\text{prox}}_{{\tau }_j,G_j}(w_j-{\tau }_j\langle X_j,z\rangle )\right|}$

where ${\displaystyle {\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: 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, fit_intercept=False, warm_start=True, verbose=False)[source]#

Methods

__init__([max_iter, max_epochs, dual_init, ...])
custom_checks(X, y, datafit, penalty)	Ensure the solver is suited for the datafit + penalty problem.
solve(X, y, datafit, penalty[, w_init, ...])	Solve the optimization problem after validating its compatibility.