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 Details
Algorithmic-specific transformation
, the set of intrinsic parameters
defined for the learning rate
, and algorithm-specific vector
and power
of Lebesgue space are defined as follows:
is defined by the number of iterations the solver runs
stores the gradient of
Update of the set of intrinsic parameters
:
The algorithm enables automatic step-length selection if learning rate
was not provided by the user.
Automatic step-length will be computed as
,
where
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 Convergence checks:
,
,
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 This input is optional: if the user does not provide the table of gradients for 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 | A numeric table of size 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 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 This parameter can be an object of any class derived from NumericTable ,
except for PackedTriangularMatrix , PackedSymmetricMatrix , and CSRNumericTable . |
Examples
C++ (CPU)
Batch Processing:
Java*
There is no support for Java on GPU.
Batch Processing:
Python*
Batch Processing: