Acceleration¶
The pyunlocbox.acceleration
module implements acceleration schemes for
use with the pyunlocbox.solvers
. Pass a given acceleration object as an
argument to your chosen solver during its initialization so that the solver can
use it.
Interface¶
The accel
base class defines a common interface to all acceleration
schemes:
accel.pre (functions, x0) |
Pre-processing specific to the acceleration scheme. |
accel.update_step (solver, objective, niter) |
Update the step size for the next iteration. |
accel.update_sol (solver, objective, niter) |
Update the solution point for the next iteration. |
accel.post () |
Post-processing specific to the acceleration scheme. |
Acceleration schemes¶
Then, derived classes implement various common acceleration schemes.
dummy () |
Dummy acceleration scheme which does nothing. |
backtracking ([eta]) |
Backtracking based on a local quadratic approximation of the smooth part of the objective. |
fista (**kwargs) |
Acceleration scheme for forward-backward solvers. |
fista_backtracking ([eta]) |
Acceleration scheme with backtracking for forward-backward solvers. |
regularized_nonlinear ([k, lambda_, …]) |
Regularized nonlinear acceleration (RNA) for gradient descent. |
-
class
pyunlocbox.acceleration.
accel
[source]¶ Bases:
object
Defines the acceleration scheme object interface.
This class defines the interface of an acceleration scheme object intended to be passed to a solver inheriting from
pyunlocbox.solvers.solver
. It is intended to be a base class for standard acceleration schemes which will implement the required methods. It can also be instantiated by user code and dynamically modified for rapid testing. This class also defines the generic attributes of all acceleration scheme objects.-
pre
(functions, x0)[source]¶ Pre-processing specific to the acceleration scheme.
Gets called when
pyunlocbox.solvers.solve()
starts running.
-
update_step
(solver, objective, niter)[source]¶ Update the step size for the next iteration.
Parameters: solver : pyunlocbox.solvers.solver
Solver on which to act.
objective : list of floats
List of evaluations of the objective function since the beginning of the iterative process.
niter : int
Current iteration number.
Returns: float
Updated step size.
-
update_sol
(solver, objective, niter)[source]¶ Update the solution point for the next iteration.
Parameters: solver : pyunlocbox.solvers.solver
Solver on which to act.
objective : list of floats
List of evaluations of the objective function since the beginning of the iterative process.
niter : int
Current iteration number.
Returns: array_like
Updated solution point.
-
post
()[source]¶ Post-processing specific to the acceleration scheme.
Mainly used to delete references added during initialization so that the garbage collector can free the memory. Gets called when
pyunlocbox.solvers.solve()
finishes running.
-
-
class
pyunlocbox.acceleration.
dummy
[source]¶ Bases:
pyunlocbox.acceleration.accel
Dummy acceleration scheme which does nothing.
Used by default in most of the solvers. It simply returns unaltered the step size and solution point it receives.
-
class
pyunlocbox.acceleration.
backtracking
(eta=0.5, **kwargs)[source]¶ Bases:
pyunlocbox.acceleration.dummy
Backtracking based on a local quadratic approximation of the smooth part of the objective.
Parameters: eta : float
A number between 0 and 1 representing the ratio of the geometric sequence formed by successive step sizes. In other words, it establishes the relation step_new = eta * step_old. Default is 0.5.
Notes
This is the backtracking strategy used in the original FISTA paper, [BT09a].
Examples
>>> import numpy as np >>> from pyunlocbox import functions, solvers, acceleration >>> y = [4, 5, 6, 7] >>> x0 = np.zeros(len(y)) >>> f1 = functions.norm_l1(y=y, lambda_=1.0) >>> f2 = functions.norm_l2(y=y, lambda_=0.8) >>> accel = acceleration.backtracking() >>> solver = solvers.forward_backward(accel=accel, step=10) >>> ret = solvers.solve([f1, f2], x0, solver, atol=1e-32, rtol=None) Solution found after 4 iterations: objective function f(sol) = 0.000000e+00 stopping criterion: ATOL >>> ret['sol'] array([ 4., 5., 6., 7.])
-
class
pyunlocbox.acceleration.
fista
(**kwargs)[source]¶ Bases:
pyunlocbox.acceleration.dummy
Acceleration scheme for forward-backward solvers.
Notes
This is the acceleration scheme proposed in the original FISTA paper, [BT09a].
Examples
>>> import numpy as np >>> from pyunlocbox import functions, solvers, acceleration >>> y = [4, 5, 6, 7] >>> x0 = np.zeros(len(y)) >>> f1 = functions.norm_l2(y=y) >>> f2 = functions.dummy() >>> accel=acceleration.fista() >>> solver = solvers.forward_backward(accel=accel, step=0.5) >>> ret = solvers.solve([f1, f2], x0, solver, atol=1e-5) Solution found after 15 iterations: objective function f(sol) = 4.957288e-07 stopping criterion: ATOL >>> ret['sol'] array([ 4.0002509 , 5.00031362, 6.00037635, 7.00043907])
-
class
pyunlocbox.acceleration.
regularized_nonlinear
(k=10, lambda_=1e-06, adaptive=True, dolinesearch=True, forcedecrease=True, **kwargs)[source]¶ Bases:
pyunlocbox.acceleration.dummy
Regularized nonlinear acceleration (RNA) for gradient descent.
Parameters: k : int, optional
Number of points to keep in the buffer for computing the extrapolation. (Default is 10.)
lambda_ : float or list of floats, optional
Regularization parameter in the acceleration scheme. The user can pass a list of candidates, and the acceleration algorithm will pick the one that provides the best extrapolation. (Default is 1e-6.)
adaptive : boolean, optional
If adaptive = True and the user has not provided a list of regularization parameters, the acceleration algorithm will assemble a grid of possible regularization parameters based on the SVD of the Gram matrix of vectors of differences in the extrapolation buffer. If adaptive = False, the algorithm will simply try to use the value(s) given in lambda_. (Default is True.)
dolinesearch : boolean, optional
If dolinesearch = True, the acceleration scheme will try to return a point in the line segment between the current extrapolation and the previous one that provides a decrease in the value of the objective function. If dolinesearch = False, the algorithm simply returns the current extrapolation. (Default is True.)
forcedecrease : boolean, optional
If forcedecrese = True and we obtain a bad extrapolation, the algorithm returns the unchanged solution produced by the solver. If forcedecrease = False, the algorithm returns the new extrapolation no matter what. (Default is True.)
Notes
This is the acceleration scheme proposed in [SdB16].
See also Damien Scieur’s repository for the Matlab version that inspired this implementation.
Examples
>>> import numpy as np >>> from pyunlocbox import functions, solvers, acceleration >>> dim = 25; >>> np.random.seed(0) >>> xstar = np.random.rand(dim) # True solution >>> x0 = np.random.rand(dim) >>> x0 = xstar + 5.*(x0 - xstar) / np.linalg.norm(x0 - xstar) >>> A = np.random.rand(dim, dim) >>> step = 1/np.linalg.norm(np.dot(A.T, A)) >>> f = functions.norm_l2(lambda_=0.5, A=A, y=np.dot(A, xstar)) >>> fd = functions.dummy() >>> accel = acceleration.regularized_nonlinear(k=5) >>> solver = solvers.gradient_descent(step=step, accel=accel) >>> params = {'rtol':0, 'maxit':200, 'verbosity':'NONE'} >>> ret = solvers.solve([f, fd], x0, solver, **params) >>> pctdiff = 100*np.sum((xstar - ret['sol'])**2)/np.sum(xstar**2) >>> print('Difference: {0:.1f}%'.format(pctdiff)) Difference: 1.3%
-
lambda_
¶
-
-
class
pyunlocbox.acceleration.
fista_backtracking
(eta=0.5, **kwargs)[source]¶ Bases:
pyunlocbox.acceleration.backtracking
,pyunlocbox.acceleration.fista
Acceleration scheme with backtracking for forward-backward solvers.
Notes
This is the acceleration scheme and backtracking strategy proposed in the original FISTA paper, [BT09a].
Examples
>>> import numpy as np >>> from pyunlocbox import functions, solvers, acceleration >>> y = [4, 5, 6, 7] >>> x0 = np.zeros(len(y)) >>> f1 = functions.norm_l2(y=y) >>> f2 = functions.dummy() >>> accel=acceleration.fista_backtracking() >>> solver = solvers.forward_backward(accel=accel, step=0.5) >>> ret = solvers.solve([f1, f2], x0, solver, atol=1e-5) Solution found after 15 iterations: objective function f(sol) = 4.957288e-07 stopping criterion: ATOL >>> ret['sol'] array([ 4.0002509 , 5.00031362, 6.00037635, 7.00043907])