mlpack  git-master
SCD< DescentPolicyType > Class Template Reference

Stochastic Coordinate descent is a technique for minimizing a function by doing a line search along a single direction at the current point in the iteration. More...

Public Member Functions

 SCD (const double stepSize=0.01, const size_t maxIterations=100000, const double tolerance=1e-5, const size_t updateInterval=1e3, const DescentPolicyType descentPolicy=DescentPolicyType())
 Construct the SCD optimizer with the given function and parameters. More...

 
DescentPolicyType DescentPolicy () const
 Get the descent policy. More...

 
DescentPolicyType & DescentPolicy ()
 Modify the descent policy. More...

 
size_t MaxIterations () const
 Get the maximum number of iterations (0 indicates no limit). More...

 
size_t & MaxIterations ()
 Modify the maximum number of iterations (0 indicates no limit). More...

 
template
<
typename
ResolvableFunctionType
>
double Optimize (ResolvableFunctionType &function, arma::mat &iterate)
 Optimize the given function using stochastic coordinate descent. More...

 
double StepSize () const
 Get the step size. More...

 
double & StepSize ()
 Modify the step size. More...

 
double Tolerance () const
 Get the tolerance for termination. More...

 
double & Tolerance ()
 Modify the tolerance for termination. More...

 
size_t UpdateInterval () const
 Get the update interval for reporting objective. More...

 
size_t & UpdateInterval ()
 Modify the update interval for reporting objective. More...

 

Detailed Description


template
<
typename
DescentPolicyType
=
RandomDescent
>

class mlpack::optimization::SCD< DescentPolicyType >

Stochastic Coordinate descent is a technique for minimizing a function by doing a line search along a single direction at the current point in the iteration.

The direction (or "coordinate") can be chosen cyclically, randomly or in a greedy fashion(depending on the DescentPolicy).

This optimizer is useful for problems with a smooth multivariate function where computing the entire gradient for an update is infeasable. CD method typically significantly outperform GD, especially on sparse problems with a very large number variables/coordinates.

For more information, see the following.

@inproceedings{Shalev-Shwartz2009,
author = {Shalev-Shwartz, Shai and Tewari, Ambuj},
title = {Stochastic Methods for L1 Regularized Loss Minimization},
booktitle = {Proceedings of the 26th Annual International Conference on
Machine Learning},
series = {ICML '09},
year = {2009},
isbn = {978-1-60558-516-1}
}

For SCD to work, the class must implement the following functions:

size_t NumFeatures(); double Evaluate(const arma::mat& coordinates); void PartialGradient(const arma::mat& coordinates, const size_t j, arma::sp_mat& gradient);

NumFeatures() should return the number of features in the decision variable. Evaluate gives the value of the loss function at the current decision variable and PartialGradient is used to evaluate the partial gradient with respect to the jth feature.

Template Parameters
DescentPolicyDescent policy to decide the order in which the coordinate for descent is selected.

Definition at line 62 of file scd.hpp.

Constructor & Destructor Documentation

◆ SCD()

SCD ( const double  stepSize = 0.01,
const size_t  maxIterations = 100000,
const double  tolerance = 1e-5,
const size_t  updateInterval = 1e3,
const DescentPolicyType  descentPolicy = DescentPolicyType() 
)

Construct the SCD optimizer with the given function and parameters.

The default value here are not necessarily good for every problem, so it is suggested that the values used are tailored for the task at hand. The maximum number of iterations refers to the maximum number of "descents" the algorithm does (in one iteration, the algorithm updates the decision variable numFeatures times).

Parameters
stepSizeStep size for each iteration.
maxIterationsMaximum number of iterations allowed (0 means to limit).
toleranceMaximum absolute tolerance to terminate the algorithm.
updateIntervalThe interval at which the objective is to be reported and checked for convergence.
descentPolicyThe policy to use for picking up the coordinate to descend on.

Member Function Documentation

◆ DescentPolicy() [1/2]

DescentPolicyType DescentPolicy ( ) const
inline

Get the descent policy.

Definition at line 122 of file scd.hpp.

◆ DescentPolicy() [2/2]

DescentPolicyType& DescentPolicy ( )
inline

Modify the descent policy.

Definition at line 124 of file scd.hpp.

◆ MaxIterations() [1/2]

size_t MaxIterations ( ) const
inline

Get the maximum number of iterations (0 indicates no limit).

Definition at line 107 of file scd.hpp.

◆ MaxIterations() [2/2]

size_t& MaxIterations ( )
inline

Modify the maximum number of iterations (0 indicates no limit).

Definition at line 109 of file scd.hpp.

◆ Optimize()

double Optimize ( ResolvableFunctionType &  function,
arma::mat &  iterate 
)

Optimize the given function using stochastic coordinate descent.

The given starting point will be modified to store the finishing point of the optimization, and the final objective value is returned.

Template Parameters
ResolvableFunctionTypeType of the function to be optimized.
Parameters
functionFunction to optimize.
iterateStarting point (will be modified).
Returns
Objective value at the final point.

◆ StepSize() [1/2]

double StepSize ( ) const
inline

Get the step size.

Definition at line 102 of file scd.hpp.

◆ StepSize() [2/2]

double& StepSize ( )
inline

Modify the step size.

Definition at line 104 of file scd.hpp.

◆ Tolerance() [1/2]

double Tolerance ( ) const
inline

Get the tolerance for termination.

Definition at line 112 of file scd.hpp.

◆ Tolerance() [2/2]

double& Tolerance ( )
inline

Modify the tolerance for termination.

Definition at line 114 of file scd.hpp.

◆ UpdateInterval() [1/2]

size_t UpdateInterval ( ) const
inline

Get the update interval for reporting objective.

Definition at line 117 of file scd.hpp.

◆ UpdateInterval() [2/2]

size_t& UpdateInterval ( )
inline

Modify the update interval for reporting objective.

Definition at line 119 of file scd.hpp.


The documentation for this class was generated from the following file:
  • /var/www/www.mlpack.org/mlpack-git/src/mlpack/core/optimizers/scd/scd.hpp