copt.minimize_svrg

copt.minimize_svrg(f_deriv, A, b, x0, step_size, alpha=0, prox=None, max_iter=500, tol=1e-06, verbose=False, callback=None)

Stochastic average gradient augmented (SAGA) algorithm.

The SAGA algorithm can solve optimization problems of the form

argmin_{x in R^p} sum_{i}^n_samples f(A_i^T x, b_i) + alpha * ||x||_2^2 +

  • beta * ||x||_1

Parameters

  • f_deriv – derivative of f

  • x0 – np.ndarray or None, optional Starting point for optimization.

  • step_size – float or None, optional Step size for the optimization. If None is given, this will be estimated from the function f.

  • n_jobs – int Number of threads to use in the optimization. A number higher than 1 will use the Asynchronous SAGA optimization method described in [Pedregosa et al., 2017]

  • max_iter – int Maximum number of passes through the data in the optimization.

  • tol – float Tolerance criterion. The algorithm will stop whenever the norm of the gradient mapping (generalization of the gradient for nonsmooth optimization) is below tol.

  • verbose – bool Verbosity level. True might print some messages.

  • trace – bool Whether to trace convergence of the function, useful for plotting and/or debugging. If ye, the result will have extra members trace_func, trace_time.

Returns

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.

Return type

opt

References

The SAGA algorithm was originally described in

Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in Neural Information Processing Systems. 2014.

The implemented has some improvements with respect to the original, like support for sparse datasets and is described in

Fabian Pedregosa, Remi Leblond, and Simon Lacoste-Julien. “Breaking the Nonsmooth Barrier: A Scalable Parallel Method for Composite Optimization.” Advances in Neural Information Processing Systems (NIPS) 2017.