[mlpack-svn] [MLPACK] #303: Interface for stochastic gradient descent

[MLPACK Trac]

#303: Interface for stochastic gradient descent
--------------------------------------------------------+-------------------
  Reporter:  sumedhghaisas                              |        Owner:              
      Type:  enhancement                                |       Status:  closed      
  Priority:  major                                      |    Milestone:  mlpack 1.0.7
 Component:  mlpack                                     |   Resolution:  wontfix     
  Keywords:  stochastic gradient descent,C++ interface  |     Blocking:              
Blocked By:                                             |  
--------------------------------------------------------+-------------------
Changes (by rcurtin):

  * status:  new => closed
  * resolution:  => wontfix


Comment:

 Hello Sumedh,

 I think I am understanding your idea correctly: you want to provide a
 parent SGDFunction class, so that a user can overload some of the
 functionality.  Then, a user might not have to overload all of the
 functions.  This is the basic object-oriented class structure idea.

 Unfortunately, inheritance does have costs associated with it.  Each time
 I call SGDFunction::Evaluate(), there is a vtable lookup (basically, a
 pointer dereference) to get to the actual function that refers to whatever
 child class of SGDFunction's Evaluate() function.

 In the SGD method, the Evaluate() function is called millions and millions
 of times, and this means that the vtable lookup penalty actually becomes a
 significant cost.  The C++ technical report from around 2004 has some more
 information on vtable lookup penalties somewhere in it (I don't remember
 where).  So, instead of using inheritance, we use templated types.  This
 means that when SGD calls Evaluate(), there is no vtable lookup, because
 the function is bound statically at compile-time.

 For a user writing a function to plug into SGD, they have to refer to this
 documentation in sgd.hpp (or in the Doxygen documentation):

 {{{
 /**
  * ...
  * For SGD to work, a DecomposableFunctionType template parameter is
 required.
  * This class must implement the following function:
  *
  *   size_t NumFunctions();
  *   double Evaluate(const arma::mat& coordinates, const size_t i);
  *   void Gradient(const arma::mat& coordinates,
  *                 const size_t i,
  *                 arma::mat& gradient);
  *
  * NumFunctions() should return the number of functions (\f$n\f$), and in
 the
  * other two functions, the parameter i refers to which individual
 function (or
  * gradient) is being evaluated.  So, for the case of a data-dependent
 function,
  * such as NCA (see mlpack::nca::NCA), NumFunctions() should return the
 number
  * of points in the dataset, and Evaluate(coordinates, 0) will evaluate
 the
  * objective function on the first point in the dataset (presumably, the
 dataset
  * is held internally in the DecomposableFunctionType).
  */
 }}}

 Unfortunately, because C++11 Concepts were not a feature that was included
 in the new language standard, we don't have any way to "enforce" that
 someone writing a DecomposableFunctionType class will actually implement
 all of the methods they need.  The template-based approach we use instead
 gives horribly long, terrifying compiler messages.  But there's not really
 anything we can do about it and it's the price we have to pay to get the
 extra performance by avoiding the vtable lookup.  If you want to do more
 reading, a term to look for would be "policy-based design".

 Thanks,

 Ryan

-- 
Ticket URL: <http://trac.research.cc.gatech.edu/fastlab/ticket/303#comment:1>
MLPACK <www.fast-lab.org>
MLPACK is an intuitive, fast, and scalable C++ machine learning library developed at Georgia Tech.