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

DescentPolicy

Descent 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

stepSize	Step size for each iteration.
maxIterations	Maximum number of iterations allowed (0 means to limit).
tolerance	Maximum absolute tolerance to terminate the algorithm.
updateInterval	The interval at which the objective is to be reported and checked for convergence.
descentPolicy	The 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

ResolvableFunctionType

Type of the function to be optimized.

Parameters

function	Function to optimize.
iterate	Starting 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:

• src/mlpack/core/optimizers/scd/scd.hpp