BacktrackBase

The fundamental class from which all backtrack algorithms are derived is BacktrackBase.

The backtracking process is an adaptive process to find the optimal step size for the gradient descent (\(L^{-1}\)). Backtracking updates self.L until the condition \(F \leq Q_L\) is satisfied. These are defined as

\[F(\mathbf{x}) = f(\mathbf{x}) + g(\mathbf{x}) \;,\]

and

\[Q_L(\mathbf{x},\mathbf{y}) = f(\mathbf{y}) + \langle \mathbf{x} - \mathbf{y}, \nabla f(\mathbf{y}) \rangle + \frac{L}{2} \left\| \mathbf{x} - \mathbf{y} \right\|_2^2 + g(\mathbf{x}) \;.\]

The backtracking process is optional. It is performed when the Backtrack auxiliary class is enabled.

Classes derived from BacktrackBase should override/define the method BacktrackBase.update. The backtrack functionality is defined in terms of calls to PGM.grad_f, PGM.prox_g and PGM.obfn_f. Note that whenever both backtrack and step size classes are enabled, the backtrack class takes precedence.

Backtrack Classes

The PGM backtrack functionality is defined by the following classes:

• BacktrackStandard

This implements the standard PGM variant from [6].

• BacktrackRobust

This implements the robust PGM variant from [22].