tick.solver.GFB¶

class tick.solver.GFB(step: float = None, tol: float = 1e-10, max_iter: int = 500, surrelax=1.0, verbose: bool = True, print_every: int = 10, record_every: int = 1)[source]¶

Generalized Forward-Backward algorithm

For the minimization of objectives of the form

\[f(x) + \sum_{p=1}^P g_p(x)\]

where \(f\) has a smooth gradient and \(g_1, \ldots, g_P\) are prox-capable. Function \(f\) corresponds to the model.loss method of the model (passed with set_model to the solver) and \(g_1, \ldots, g_P\) correspond to the list of prox passed with the set_prox method. One iteration of GFB is as follows:

\[\begin{split}\begin{align*} &\text{for } p=1, \ldots, P \; \text{ do the following:} \\ & \quad z_p \gets \mathrm{prox}_{P \eta g_p} \Big(2 w - z_p^{\text{old}} - \eta \nabla f(w) \Big) \\ & \quad z_p \gets z_p^{\text{old}} + \beta (z_p - w) \\ &w \gets \frac 1P \sum_{p=1}^P z_p \end{align*}\end{split}\]

where \(\nabla f(w)\) is the gradient of \(f\) given by the model.grad method and \(\mathrm{prox}_{\eta g_p}\) is given by the prox[p].call method. The step-size \(\eta\) can be tuned with step. The iterations stop whenever tolerance tol is achieved, or after max_iter iterations. The obtained solution \(w\) is returned by the solve method, and is also stored in the solution attribute of the solver. The level of sur-relaxation \(\beta\) can be tuned using the surrelax attribute.

Parameters

step : float, default=None

Step-size parameter, the most important parameter of the solver. Whenever possible, this can be tuned as step = 1 / model.get_lip_best()

tol : float, default=1e-10

The tolerance of the solver (iterations stop when the stopping criterion is below it)

max_iter : int, default=500

Maximum number of iterations of the solver.

surrelax : float, default=1

Level of sur-relaxation to use in the algorithm.

verbose : bool, default=True

If True, solver verboses history, otherwise nothing is displayed, but history is recorded anyway

print_every : int, default=10

Print history information every time the iteration number is a multiple of print_every. Used only is verbose is True

record_every : int, default=1

Save history information every time the iteration number is a multiple of record_every

Attributes

model : Model

The model used by the solver, passed with the set_model method

prox : list of Prox

List of proximal operators used by the solver, passed with the set_prox method

solution : numpy.array, shape=(n_coeffs,)

Minimizer found by the solver

history : dict-like

A dict-type of object that contains history of the solver along iterations. It should be accessed using the get_history method

time_start : str

Start date of the call to solve()

time_elapsed : float

Duration of the call to solve(), in seconds

time_end : str

End date of the call to solve()

References

• H. Raguet, J. Fadili, G. Peyré, A generalized forward-backward splitting, SIAM Journal on Imaging Sciences (2013)

__init__(step: float = None, tol: float = 1e-10, max_iter: int = 500, surrelax=1.0, verbose: bool = True, print_every: int = 10, record_every: int = 1)[source]¶

Initialize self. See help(type(self)) for accurate signature.

get_history(key=None)¶

Returns history of the solver

Parameters

key : str, default=None

• If None all history is returned as a dict

• If str, name of the history element to retrieve

Returns

output : list or dict

• If key is None or key is not in history then output is a dict containing history of all keys

• If key is the name of an element in the history, output is a list containing the history of this element

objective(coeffs, loss: float = None)¶

Compute the objective function

Parameters

coeffs : np.array, shape=(n_coeffs,)

Point where the objective is computed

loss : float, default=`None`

Gives the value of the loss if already known (allows to avoid its computation in some cases)

Returns

output : float

Value of the objective at given coeffs

set_model(model: tick.base_model.model.Model)¶

Set model in the solver

Parameters

model : Model

Sets the model in the solver. The model gives the first order information about the model (loss, gradient, among other things)

Returns

output : Solver

The same instance with given model

set_prox(prox_list: list)[source]¶

Parameters

prox_list : list of Prox

List of all proximal operators of the model

solve(x0=None, step=None)¶

Launch the solver

Parameters

x0 : np.array, shape=(n_coeffs,), default=`None`

Starting point of the solver

step : float, default=`None`

Step-size or learning rate for the solver. This can be tuned also using the step attribute

Returns

output : np.array, shape=(n_coeffs,)

Obtained minimizer for the problem, same as solution attribute