Developer Guide and Reference

  • 2021.2
  • 03/26/2021
  • Public Content
Contents

Stochastic Average Gradient Accelerated Method

The Stochastic Average Gradient Accelerated (SAGA) [Defazio2014] follows the algorithmic framework of an iterative solver with one exception.
The default method (
defaultDense
) of SAGA algorithm is a particular case of the iterative solver method with the batch size
b = 1
.

Details

Algorithmic-specific transformation
T
, the set of intrinsic parameters LaTex Math image. defined for the learning rate LaTex Math image., and algorithm-specific vector
U
and power
d
of Lebesgue space are defined as follows:
LaTex Math image.
LaTex Math image.
LaTex Math image.
LaTex Math image. is a matrix of the gradients of smooth terms at point LaTex Math image., where
  • t
    is defined by the number of iterations the solver runs
  • LaTex Math image. stores the gradient of LaTex Math image.
LaTex Math image.:
  1. LaTex Math image.
  2. LaTex Math image.
Update of the set of intrinsic parameters LaTex Math image.:
LaTex Math image.
The algorithm enables automatic step-length selection if learning rate LaTex Math image. was not provided by the user. Automatic step-length will be computed as LaTex Math image., where
L
is the Lipschitz constant returned by objective function. If the objective function returns
nullptr
to numeric table with
lipschitzConstant
Result ID, the library will use default step size
0.01
.
Convergence checks:
  • LaTex Math image., LaTex Math image.
  • LaTex Math image., LaTex Math image.

Computation

The stochastic average gradient (SAGA) algorithm is a special case of an iterative solver. For parameters, input, and output of iterative solvers, see Iterative Solver > Computation.
Algorithm Input
In addition to the input of the iterative solver, the SAGA optimization solver has the following optional input:
OptionalDataID
Default Value
Description
gradientTable
Not applicable
A numeric table of size LaTex Math image. which represents LaTex Math image. matrix that contains gradients of LaTex Math image., LaTex Math image. at the initial point LaTex Math image..
This input is optional: if the user does not provide the table of gradients for LaTex Math image., LaTex Math image., the library will compute it inside the SAGA algorithm.
This parameter can be an object of any class derived from
NumericTable
, except for
PackedTriangularMatrix
,
PackedSymmetricMatrix
, and
CSRNumericTable
.
Algorithm Parameters
In addition to parameters of the iterative solver, the SAGA optimization solver has the following parameters:
Parameter
Default Value
Description
algorithmFPType
float
The floating-point type that the algorithm uses for intermediate computations. Can be
float
or
double
.
method
defaultDense
Performance-oriented method.
batchIndices
1
A numeric table of size LaTex Math image. with 32-bit integer indices of terms in the objective function. If no indices are provided, the implementation generates random index on each iteration.
This parameter can be an object of any class derived from
NumericTable
, except for
PackedTriangularMatrix
,
PackedSymmetricMatrix
, and
CSRNumericTable
.
learningRateSequence
Not applicable
The numeric table of size LaTex Math image. or LaTex Math image. that contains learning rate for each iterations is first case, otherwise constant step length will be used for all iterations. It is recommended to set diminishing learning rate sequence.
If
learningRateSequence
is not provided, the learning rate will be computed automatically via
constantOfLipschitz
Result ID.
This parameter can be an object of any class derived from
NumericTable
, except for
PackedTriangularMatrix
,
PackedSymmetricMatrix
, and
CSRNumericTable
.
engine
SharedPtr<engines::mt19937::Batch<>
Pointer to the random number generator engine that is used internally for generation of 32-bit integer index of term in the objective function.
Algorithm Output
In addition to the output of the iterative solver, the SAGA optimization solver calculates the following optional result:
OptionalDataID
Default Value
Description
gradientTable
Not applicable
A numeric table of size LaTex Math image. that represents matrix LaTex Math image. updated after all iterations.
This parameter can be an object of any class derived from
NumericTable
, except for
PackedTriangularMatrix
,
PackedSymmetricMatrix
, and
CSRNumericTable
.

Examples

Java*
There is no support for Java on GPU.
Batch Processing:
Python*
Batch Processing:

Product and Performance Information

1

Performance varies by use, configuration and other factors. Learn more at www.Intel.com/PerformanceIndex.