copt.minimize_sfw

copt.minimize_sfw(f_deriv, A, b, x0, lmo, batch_size=1, step_size='sublinear', max_iter=500, tol=1e-06, verbose=False, callback=None, variant='SAGA')

Stochastic Frank-Wolfe (SFW) algorithm.

This implementation of SFW algorithms can solve optimization problems of the form

argmin_{x in constraint} (1/n)sum_{i}^n_samples f(A_i^T x, b_i)

Args:

f_deriv

derivative of f

x0: np.ndarray

Starting point for optimization.

step_size: function or None, optional

Step size for the optimization. If None is given, this will be set as the default for variant. The function should return a tuple of floats. One is needed for SAG and SAGA variants. Two are needed for MHK and LF.

lmo: function

returns the update direction

batch_size: int

Size of the random subset (without replacement) to compute the stochastic gradient estimator.

max_iter: int

Maximum number of passes on the dataset (epochs).

tol: float

Tolerance criterion. The algorithm will stop whenever the difference between two successive iterates is below tol.

verbose: bool

Verbosity level. True might print some messages.

callback: function or None

If not None, callback will be called at each iteration.

variant: str in {‘SAG’, ‘MHK’, ‘LF’}

Controls which variant of SFW to use. ‘SAG’ is described in [NDTELP2020], ‘SAGA’ is yet to be described. ‘MHK’ is described in [MHK2020], ‘LF’ is described in [LF2020].

Returns:

opt: OptimizeResult

The optimization result represented as a scipy.optimize.OptimizeResult object. Important attributes are: x the solution array, success a Boolean flag indicating if the optimizer exited successfully and message which describes the cause of the termination. See scipy.optimize.OptimizeResult for a description of other attributes.

References:

NDTELP2020

Negiar, Geoffrey, Dresdner, Gideon, Tsai Alicia, El Ghaoui, Laurent, Locatello, Francesco, and Pedregosa, Fabian.

“Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization” <https://arxiv.org/abs/2002.11860v2> arxiv:2002.11860v2 (2020).

MHK2018

Mokhtari, Aryan, Hassani, Hamed, and Karbassi, Amin `”Stochastic Conditional Gradient Methods:

From Convex Minimization to Submodular Maximization” <https://arxiv.org/abs/1804.09554>`_, arxiv:1804.09554 (2018)

LF2020

Lu, Haihao, and Freund, Robert `”Generalized Stochastic Frank-Wolfe Algorithm with Stochastic ‘Substitute’ Gradient for Structured Convex Optimization”

<https://arxiv.org/pdf/1806.05123.pdf>`_, Mathematical Programming (2020).