copt.minimize_SAGA

copt.minimize_SAGA(f, g=None, x0=None, step_size=None, max_iter=500, tol=1e-06, verbose=False, trace=False)[source]

Stochastic average gradient augmented (SAGA) algorithm.

The SAGA algorithm can solve optimization problems of the form

argmin_x f(x) + g(x)
Parameters:
  • g (f,) – loss functions. g can be none
  • 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 [Leblond 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.
Return type:

OptimizeResult
Returns:

opt – 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:

OptimizeResult

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 version, such as better support for sparse datasets and is described in

Pedregosa, Fabian, Rémi Leblond, and Simon Lacoste-Julien. “Breaking the Nonsmooth Barrier: A Scalable Parallel Method for Composite Optimization.” arXiv preprint arXiv:1707.06468 (2017).