Detailed Description

The class implements the Stochastic MIrror Descent mAde Sparse (SMIDAS) minimizer.

Reference: Shai Shalev-Shwartz and Ambuj Tewari, Stochastic methods for l1 regularized loss minimization. Proceedings of the 26th International Conference on Machine Learning, pages 929-936, 2009.

Definition at line 48 of file SMIDASMinimizer.h.

Inheritance diagram for SMIDASMinimizer:

[legend]

Public Member Functions
	SMIDASMinimizer ()

	SMIDASMinimizer (FirstOrderStochasticCostFunction *fun)

virtual	~SMIDASMinimizer ()

virtual float64_t	minimize ()

virtual void	load_from_context (CMinimizerContext *context)

virtual void	set_mapping_function (MappingFunction *mapping_fun)

virtual bool	supports_batch_update () const

virtual void	set_gradient_updater (DescendUpdater *gradient_updater)

virtual void	set_number_passes (int32_t num_passes)

virtual void	set_learning_rate (LearningRate *learning_rate)

virtual int32_t	get_iteration_counter ()

virtual void	set_cost_function (FirstOrderCostFunction *fun)

virtual CMinimizerContext *	save_to_context ()

virtual void	set_penalty_weight (float64_t penalty_weight)

virtual void	set_penalty_type (Penalty *penalty_type)

Protected Member Functions
virtual void	update_context (CMinimizerContext *context)

virtual void	init_minimization ()

virtual void	do_proximal_operation (SGVector< float64_t >variable_reference)

virtual float64_t	get_penalty (SGVector< float64_t > var)

virtual void	update_gradient (SGVector< float64_t > gradient, SGVector< float64_t > var)

Protected Attributes
SGVector< float64_t >	m_dual_variable

MappingFunction *	m_mapping_fun

DescendUpdater *	m_gradient_updater

int32_t	m_num_passes

int32_t	m_cur_passes

int32_t	m_iter_counter

LearningRate *	m_learning_rate

FirstOrderCostFunction *	m_fun

Penalty *	m_penalty_type

float64_t	m_penalty_weight

Constructor & Destructor Documentation

SMIDASMinimizer ( )

Default constructor

Definition at line 37 of file SMIDASMinimizer.cpp.

SMIDASMinimizer ( FirstOrderStochasticCostFunction * fun )

Constructor

Parameters

fun	stochastic cost function

Definition at line 47 of file SMIDASMinimizer.cpp.

~SMIDASMinimizer ( )

virtual

Destructor

Definition at line 43 of file SMIDASMinimizer.cpp.

Member Function Documentation

virtual void do_proximal_operation ( SGVector< float64_t > variable_reference )

protectedvirtualinherited

Do proximal update in place

Parameters

variable_reference variable_reference to be updated

Definition at line 167 of file FirstOrderStochasticMinimizer.h.

virtual int32_t get_iteration_counter ( )

virtualinherited

How many samples/mini-batch does the minimizer use?

Returns: the number of samples/mini-batches used in optimization

Definition at line 160 of file FirstOrderStochasticMinimizer.h.

virtual float64_t get_penalty ( SGVector< float64_t > var )

protectedvirtualinherited

Get the penalty given target variables For L2 penalty, the target variable is \(w\) and the value of penalty is \(\lambda \frac{w^t w}{2}\), where \(\lambda\) is the weight of penalty

Parameters

var	the variable used in regularization

Definition at line 164 of file FirstOrderMinimizer.h.

void init_minimization ( )

protectedvirtual

init minimization

Reimplemented from SMDMinimizer.

Definition at line 95 of file SMIDASMinimizer.cpp.

virtual void load_from_context ( CMinimizerContext * context )

virtual

Load the given context object to restores mutable variables Usually it is used in deserialization.

Parameters

context a context object

Reimplemented from SMDMinimizer.

Definition at line 73 of file SMIDASMinimizer.h.

float64_t minimize ( )

virtual

Do minimization and get the optimal value

Returns: optimal value

Reimplemented from SMDMinimizer.

Definition at line 53 of file SMIDASMinimizer.cpp.

virtual CMinimizerContext* save_to_context ( )

virtualinherited

Return a context object which stores mutable variables Usually it is used in serialization.

Returns: a context object

Reimplemented in LBFGSMinimizer, and NLOPTMinimizer.

Definition at line 103 of file FirstOrderMinimizer.h.

virtual void set_cost_function ( FirstOrderCostFunction * fun )

virtualinherited

Set cost function used in the minimizer

Parameters

fun	the cost function

Definition at line 92 of file FirstOrderMinimizer.h.

virtual void set_gradient_updater ( DescendUpdater * gradient_updater )

virtualinherited

Set a gradient updater

Parameters

gradient_updater the gradient_updater

Definition at line 104 of file FirstOrderStochasticMinimizer.h.

virtual void set_learning_rate ( LearningRate * learning_rate )

virtualinherited

Set the learning rate of a minimizer

Parameters

learning_rate learn rate or step size

Definition at line 151 of file FirstOrderStochasticMinimizer.h.

virtual void set_mapping_function ( MappingFunction * mapping_fun )

virtualinherited

Set projection function

Parameters

mapping_fun mapping/projection function

Definition at line 67 of file SMDMinimizer.h.

virtual void set_number_passes ( int32_t num_passes )

virtualinherited

Set the number of times to go through all data points (samples) For example, num_passes=1 means go through all data points once.

Recall that a stochastic cost function \(f(w)\) can be written as \(\sum_i{ f_i(w) }\), where \(f_i(w)\) is the differentiable function for the i-th sample.

Parameters

num_passes the number of times

Definition at line 125 of file FirstOrderStochasticMinimizer.h.

virtual void set_penalty_type ( Penalty * penalty_type )

virtualinherited

Set the type of penalty For example, L2 penalty

Parameters

penalty_type the type of penalty. If NULL is given, regularization is not enabled.

Definition at line 137 of file FirstOrderMinimizer.h.

virtual void set_penalty_weight ( float64_t penalty_weight )

virtualinherited

Set the weight of penalty

Parameters

penalty_weight the weight of penalty, which is positive

Definition at line 126 of file FirstOrderMinimizer.h.

virtual bool supports_batch_update ( ) const

virtualinherited

Does minimizer support batch update

Returns: whether minimizer supports batch update

Implements FirstOrderMinimizer.

Definition at line 98 of file FirstOrderStochasticMinimizer.h.

virtual void update_context ( CMinimizerContext * context )

protectedvirtual

Update a context object to store mutable variables

Parameters

context a context object

Reimplemented from SMDMinimizer.

Definition at line 89 of file SMIDASMinimizer.h.

virtual void update_gradient	(	SGVector< float64_t >	gradient,
		SGVector< float64_t >	var
	)

protectedvirtualinherited

Add gradient of the penalty wrt target variables to unpenalized gradient For least sqaure with L2 penalty,

\[ L2f(w)=f(w) + L2(w) \]

where \( f(w)=\sum_i{(y_i-w^T x_i)^2}\) is the least sqaure cost function and \(L2(w)=\lambda \frac{w^t w}{2}\) is the L2 penalty

Target variables is \(w\) Unpenalized gradient is \(\frac{\partial f(w) }{\partial w}\) Gradient of the penalty wrt target variables is \(\frac{\partial L2(w) }{\partial w}\)

Parameters

gradient	unpenalized gradient wrt its target variable
var	the target variable

Definition at line 190 of file FirstOrderMinimizer.h.

Member Data Documentation

int32_t m_cur_passes

protectedinherited

current iteration to go through data

Definition at line 215 of file FirstOrderStochasticMinimizer.h.

SGVector<float64_t> m_dual_variable

protected

dual variable

Definition at line 104 of file SMIDASMinimizer.h.

FirstOrderCostFunction* m_fun

protectedinherited

Cost function

Definition at line 205 of file FirstOrderMinimizer.h.

DescendUpdater* m_gradient_updater

protectedinherited

the gradient update step

Definition at line 200 of file FirstOrderStochasticMinimizer.h.

int32_t m_iter_counter

protectedinherited

number of used samples/mini-batches

Definition at line 218 of file FirstOrderStochasticMinimizer.h.

LearningRate* m_learning_rate

protectedinherited

learning_rate object

Definition at line 221 of file FirstOrderStochasticMinimizer.h.

MappingFunction* m_mapping_fun

protectedinherited

mapping function

Definition at line 100 of file SMDMinimizer.h.

int32_t m_num_passes

protectedinherited

iteration to go through data

Definition at line 212 of file FirstOrderStochasticMinimizer.h.

Penalty* m_penalty_type

protectedinherited

the type of penalty

Definition at line 208 of file FirstOrderMinimizer.h.

float64_t m_penalty_weight

protectedinherited

the weight of penalty

Definition at line 211 of file FirstOrderMinimizer.h.

The documentation for this class was generated from the following files:

Detailed Description

Public Member Functions

Protected Member Functions

Protected Attributes

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation