squarem: Squared Extrapolation Methods for Accelerating...

In bhtang127/AccelBenchmark: Benchmark Various Accelerating Methods for Fixed Point Iterations

Squared Extrapolation Methods for Accelerating Slowly-Convergent Fixed-Point Iterations

Description

Globally-convergent, partially monotone, acceleration schemes for accelerating the convergence of *any* smooth, monotone, slowly-converging contraction mapping. It can be used to accelerate the convergence of a wide variety of iterations including the expectation-maximization (EM) algorithms and its variants, majorization-minimization (MM) algorithm, power method for dominant eigenvalue-eigenvector, Google's page-rank algorithm, and multi-dimensional scaling. This is a modification of the original squarem in SQUAREM package, including choice of projection and user defined convergence function.

Usage

squarem(par, fixptfn, objfn, ..., control = list())

Arguments

par	Vector for initial parameters
fixptfn	Fixed point updating function
objfn	Objective function
...	Other arguments required by fixptfn and objfn
control	A list containing parameters controlling the algorithm

Details

The task it to minimize objfn. Default values of control are: method=3, step.min0=1, step.max0=1, mstep=4, objfn.inc=1, projection=function(x) x, tol=1e-7, maxiter=2000, convtype="parameter", par.track=FALSE, conv.spec=NULL.

method

An integer variable that denotes the particular SQUAREM scheme to be used. Value should be either 1, 2, or 3. These correspond to the 3 schemes discussed in Varadhan and Roland (2008). Default is 3.

step.min0

A scalar denoting the minimum steplength taken by a SQUAREM algorithm. Default is 1. For contractive fixed-point iterations (e.g. EM and MM), this defualt works well. In problems where an eigenvalue of the Jacobian of $F$ is outside of the interval (0,1), step.min0 should be less than 1 or even negative in some cases.

step.max0

A positive-valued scalar denoting the initial value of the maximum steplength taken by a SQUAREM algorithm. Default is 1. When the steplength computed by SQUAREM exceeds step.max0, the steplength is set equal to step.max0, but then step.max0 is increased by a factor of mstep.

mstep

A scalar greater than 1. When the steplength computed by SQUAREM exceeds step.max0, the steplength is set equal to step.max0, but step.max0 is increased by a factor of mstep. Default is 4.

objfn.inc

A non-negative scalar that dictates the degree of non-montonicity. Default is 1. Set objfn.inc = 0 to obtain monotone convergence. Setting objfn.inc = Inf gives a non-monotone scheme. In-between values result in partially-monotone convergence.

projection

A function projecting the parameter after each iteration. Default is identity function f(x) = x

tol

A small, positive scalar that determines when iterations should be terminated, see convtype for details. Default is 1e-7

maxiter

An integer denoting the maximum limit on the number of evaluations of fixptfn. Default is 2000.

convtype

A string indicating the convergence criteria. If it is "parameter", the algorithm will termenate when L2 norm of parameters difference x_{new} - x_{old} < tol. If it is "objfn", the algorithm will terminate when the absolute difference of objective function |L_{new} - L_{old}| < tol. If it is "user" or conv.spec is not NULL. Then the convergence is guided by the user defined function conv.spec. Default is "parameter".

par.track

An bool value indicating whether to track parameters along the algorithm. TRUE for tracking and FALSE for not. Default is FALSE

conv.spec

A function for user specified convergence criteria. When using "parameter" or "objfn" option in convtype, this should be NULL. The function should have the form f(old_parameter, new_parameter, old_objective, new_objective, tolerance) and return 1 if convergent, 0 if not. Defalut is NULL.

Value

A list of results

par	Parameter values, x* that are the fixed-point of fixptfn F such that x*=F(x*) if convergence is successful.
value.objfn	The objective function value at termination.
fpevals	Number of times the fixed-point function fixptfn was evaluated.
objfevals	Number of times the objective function objfn was evaluated.
iter	Numbers of iteration used at termination. (for different algorithms, multiple fixed point iteration might be evaluated in one iteration)
convergence	An integer code indicating whether the algorithm converges. 1 for convergence and 0 denote failure.
objfn.track	An array tracking objective function values along the algorithm
par.track	A matrix tracking parameters along the algorithm, where each row is an array of parameters at some iteration. If not tracking paramters, this will be NULL

References

R Varadhan and C Roland (2008), Simple and globally convergent numerical schemes for accelerating the convergence of any EM algorithm, Scandinavian Journal of Statistics, 35:335-353.

C Roland, R Varadhan, and CE Frangakis (2007), Squared polynomial extrapolation methods with cycling: an application to the positron emission tomography problem, Numerical Algorithms, 44:159-172.

Y Du and R Varadhan (2020), SQUAREM: An R package for off-the-shelf acceleration of EM, MM, and other EM-like monotone algorithms, Journal of Statistical Software, 92(7): 1-41. <doi:10.18637/jss.v092.i07>

Examples

## Not run: 
set.seed(54321)
prob = lasso_task(lam=1)
squarem(prob$initfn(), prob$fixptfn, prob$objfn, X=prob$X, y=prob$y)

## End(Not run)

bhtang127/AccelBenchmark documentation built on May 30, 2022, 2:21 a.m.