<commit_before>/*!
 *  Copyright (c) 2015 by Contributors
 * \file lbfgs.h
 * \brief L-BFGS solver for general optimization problem
 *
 * \author <NAME>
 */
#ifndef RABIT_LEARN_LBFGS_H_
#define RABIT_LEARN_LBFGS_H_
#include <cmath>
#include <rabit.h>

namespace rabit {
/*! \brief namespace of solver for general problems */
namespace solver {
/*!
 * \brief objective function for optimizers 
 *  the objective function can also implement save/load
 *  to remember the state parameters that might need to remember
 */
template<typename DType>
class IObjFunction : public rabit::ISerializable {
 public:
  // destructor
  virtual ~IObjFunction(void){}
  /*!
   * \brief evaluate function values for a given weight
   * \param weight weight of the function
   * \param size size of the weight
   */
  virtual double Eval(const DType *weight, size_t size) = 0;
  /*!
   * \return number of feature dimension to be allocated
   * only called once during initialization
   */
  virtual size_t InitNumDim(void) = 0;
  /*!
   * \brief initialize the weight before starting the solver
   * only called once for initialization
   */
  virtual void InitModel(DType *weight, size_t size) = 0;
  /*!
   * \brief calculate gradient for a given weight
   * \param out_grad used to store the gradient value of the function
   * \param weight weight of the function
   * \param size size of the weight
   */
  virtual void CalcGrad(DType *out_grad,
                        const DType *weight,
                        size_t size) = 0;
};

/*! \brief a basic version L-BFGS solver */
template<typename DType>
class LBFGSSolver {
 public:
  LBFGSSolver(void) {
    // set default values
    reg_L1 = 0.0f;
    max_linesearch_iter = 100;
    linesearch_backoff = 0.5f;
    linesearch_c1 = 1e-4;
    min_lbfgs_iter = 5;
    max_lbfgs_iter = 500;
    lbfgs_stop_tol = 1e-5f;
    silent = 0;
  }
  virtual ~LBFGSSolver(void) {}
  /*!
   * \brief set parameters from outside
   * \param name name of the parameter
   * \param val value of the parameter
   */
  virtual void SetParam(const char *name, const char *val) {
    if (!strcmp("num_dim", name)) {
      gstate.num_dim = static_cast<size_t>(atol(val));
    }
    if (!strcmp("size_memory", name)) {
      gstate.size_memory = static_cast<size_t>(atol(val));
    }
    if (!strcmp("reg_L1", name)) {
      reg_L1 = static_cast<float>(atof(val));
    }
    if (!strcmp("lbfgs_stop_tol", name)) {
      lbfgs_stop_tol = static_cast<float>(atof(val));
    }
    if (!strcmp("linesearch_backoff", name)) {
      linesearch_backoff = static_cast<float>(atof(val));
    }
    if (!strcmp("max_linesearch_iter", name)) {
      max_linesearch_iter = atoi(val);
    }
    if (!strcmp("max_lbfgs_iter", name)) {
      max_lbfgs_iter = atoi(val);
    }
    if (!strcmp("min_lbfgs_iter", name)) {
      min_lbfgs_iter = atoi(val);
    }
    if (!strcmp("linesearch_c1", name)) {
      linesearch_c1 = static_cast<float>(atof(val));
    }
  }
  /*!
   * \brief set objective function to optimize
   *  the objective function only need to evaluate and calculate
   *  gradient with respect to current subset of data
   * \param obj the objective function we are looking for
   */
  virtual void SetObjFunction(IObjFunction<DType> *obj) {
    gstate.obj = obj;
  }
  /*!
   * \brief initialize the LBFGS solver
   *  user must already set the objective function
   */
  virtual void Init(void) {
    utils::Check(gstate.obj != NULL,
                 "LBFGSSolver.Init must SetObjFunction first");
    int version = rabit::LoadCheckPoint(&gstate, &hist);
    if (version == 0) {
      gstate.num_dim = gstate.obj->InitNumDim();
    } else {
      printf("restart from version=%d\n", version);
    }
    {
      // decide parameter partition
      size_t nproc = rabit::GetWorldSize();
      size_t rank = rabit::GetRank();
      size_t step = (gstate.num_dim + nproc - 1) / nproc;
      // upper align
      step = (step + 7) / 8 * 8;
      utils::Assert(step * nproc >= gstate.num_dim, "BUG");
      range_begin_ = std::min(rank * step, gstate.num_dim);
      range_end_ = std::min((rank + 1) * step, gstate.num_dim);
    }
    if (version == 0) {
      gstate.Init();
      hist.Init(range_end_ - range_begin_, gstate.size_memory);
      gstate.obj->InitModel(gstate.weight, gstate.num_dim);
      // broadcast initialize model
      rabit::Broadcast(gstate.weight,
                       sizeof(DType) * gstate.num_dim, 0);
      gstate.old_objval = this->Eval(gstate.weight);
      gstate.init_objval = gstate.old_objval;
      
      if (silent == 0 && rabit::GetRank() == 0) {
        rabit::TrackerPrintf
            ("L-BFGS solver starts, num_dim=%lu, init_objval=%g, size_memory=%lu, RAM-approx=%lu\n",
             gstate.num_dim, gstate.init_objval, gstate.size_memory,
             gstate.MemCost() + hist.MemCost());
      }
    }
  }
  /*!
   * \brief get the current weight vector
   *  note that if update function is called
   *  the content of weight vector is no longer valid
   * \return weight vector
   */
  virtual DType *GetWeight(void) {
    return gstate.weight;
  }
  /*!
   * \brief update the weight for one L-BFGS iteration
   * \return whether stopping condition is met
   */
  virtual bool UpdateOneIter(void) {
    bool stop = false;
    GlobalState &g = gstate;
    g.obj->CalcGrad(g.grad, g.weight, g.num_dim);
    rabit::Allreduce<rabit::op::Sum>(g.grad, g.num_dim);
    // find change direction
    double vdot = FindChangeDirection(g.tempw, g.grad, g.weight);
    // line-search, g.grad is now new weight
    int iter = BacktrackLineSearch(g.grad, g.tempw, g.weight, vdot);
    utils::Check(iter < max_linesearch_iter, "line search failed");
    // swap new weight 
    std::swap(g.weight, g.grad);
    // check stop condition
    if (gstate.num_iteration > static_cast<int>(min_lbfgs_iter)) {
      if (g.old_objval - g.new_objval < lbfgs_stop_tol * g.init_objval) {
        return true;
      }
    }
    if (silent == 0 && rabit::GetRank() == 0) {
      rabit::TrackerPrintf
          ("[%d] L-BFGS: linesearch finishes in %d rounds, new_objval=%g, improvment=%g\n",
           gstate.num_iteration, iter,
           gstate.new_objval,
           gstate.old_objval - gstate.new_objval);
    }
    gstate.old_objval = gstate.new_objval;
    rabit::CheckPoint(&gstate, &hist);
    return stop;
  }
  /*! \brief run optimization */
  virtual void Run(void) {
    this->Init();
    while (gstate.num_iteration < static_cast<size_t>(max_lbfgs_iter)) {
      if (this->UpdateOneIter()) break;
    }
    if (silent == 0 && rabit::GetRank() == 0) {
      size_t nonzero = 0;
      for (size_t i = 0; i < gstate.num_dim; ++i) {
        if (gstate.weight[i] != 0.0f) nonzero += 1;
      }
      rabit::TrackerPrintf
          ("L-BFGS: finishes at iteration %d, %lu/%lu active weights\n",
           gstate.num_iteration, nonzero, gstate.num_dim);
    }<commit_msg>minor<commit_after>/*!
 *  Copyright (c) 2015 by Contributors
 * \file lbfgs.h
 * \brief L-BFGS solver for general optimization problem
 *
 * \author <NAME>
 */
#ifndef RABIT_LEARN_LBFGS_H_
#define RABIT_LEARN_LBFGS_H_
#include <cmath>
#include <rabit.h>

namespace rabit {
/*! \brief namespace of solver for general problems */
namespace solver {
/*!
 * \brief objective function for optimizers 
 *  the objective function can also implement save/load
 *  to remember the state parameters that might need to remember
 */
template<typename DType>
class IObjFunction : public rabit::ISerializable {
 public:
  // destructor
  virtual ~IObjFunction(void){}
  /*!
   * \brief evaluate function values for a given weight
   * \param weight weight of the function
   * \param size size of the weight
   */
  virtual double Eval(const DType *weight, size_t size) = 0;
  /*!
   * \return number of feature dimension to be allocated
   * only called once during initialization
   */
  virtual size_t InitNumDim(void) = 0;
  /*!
   * \brief initialize the weight before starting the solver
   * only called once for initialization
   */
  virtual void InitModel(DType *weight, size_t size) = 0;
  /*!
   * \brief calculate gradient for a given weight
   * \param out_grad used to store the gradient value of the function
   * \param weight weight of the function
   * \param size size of the weight
   */
  virtual void CalcGrad(DType *out_grad,
                        const DType *weight,
                        size_t size) = 0;
};

/*! \brief a basic version L-BFGS solver */
template<typename DType>
class LBFGSSolver {
 public:
  LBFGSSolver(void) {
    // set default values
    reg_L1 = 0.0f;
    max_linesearch_iter = 100;
    linesearch_backoff = 0.5f;
    linesearch_c1 = 1e-4;
    min_lbfgs_iter = 5;
    max_lbfgs_iter = 500;
    lbfgs_stop_tol = 1e-5f;
    silent = 0;
  }
  virtual ~LBFGSSolver(void) {}
  /*!
   * \brief set parameters from outside
   * \param name name of the parameter
   * \param val value of the parameter
   */
  virtual void SetParam(const char *name, const char *val) {
    if (!strcmp("num_dim", name)) {
      gstate.num_dim = static_cast<size_t>(atol(val));
    }
    if (!strcmp("size_memory", name)) {
      gstate.size_memory = static_cast<size_t>(atol(val));
    }
    if (!strcmp("reg_L1", name)) {
      reg_L1 = static_cast<float>(atof(val));
    }
    if (!strcmp("lbfgs_stop_tol", name)) {
      lbfgs_stop_tol = static_cast<float>(atof(val));
    }
    if (!strcmp("linesearch_backoff", name)) {
      linesearch_backoff = static_cast<float>(atof(val));
    }
    if (!strcmp("max_linesearch_iter", name)) {
      max_linesearch_iter = atoi(val);
    }
    if (!strcmp("max_lbfgs_iter", name)) {
      max_lbfgs_iter = atoi(val);
    }
    if (!strcmp("min_lbfgs_iter", name)) {
      min_lbfgs_iter = atoi(val);
    }
    if (!strcmp("linesearch_c1", name)) {
      linesearch_c1 = static_cast<float>(atof(val));
    }
  }
  /*!
   * \brief set objective function to optimize
   *  the objective function only need to evaluate and calculate
   *  gradient with respect to current subset of data
   * \param obj the objective function we are looking for
   */
  virtual void SetObjFunction(IObjFunction<DType> *obj) {
    gstate.obj = obj;
  }
  /*!
   * \brief initialize the LBFGS solver
   *  user must already set the objective function
   */
  virtual void Init(void) {
    utils::Check(gstate.obj != NULL,
                 "LBFGSSolver.Init must SetObjFunction first");
    int version = rabit::LoadCheckPoint(&gstate, &hist);
    if (version == 0) {
      gstate.num_dim = gstate.obj->InitNumDim();
    } else {
      printf("restart from version=%d\n", version);
    }
    {
      // decide parameter partition
      size_t nproc = rabit::GetWorldSize();
      size_t rank = rabit::GetRank();
      size_t step = (gstate.num_dim + nproc - 1) / nproc;
      // upper align
      step = (step + 7) / 8 * 8;
      utils::Assert(step * nproc >= gstate.num_dim, "BUG");
      range_begin_ = std::min(rank * step, gstate.num_dim);
      range_end_ = std::min((rank + 1) * step, gstate.num_dim);
    }
    if (version == 0) {
      gstate.Init();
      hist.Init(range_end_ - range_begin_, gstate.size_memory);
      gstate.obj->InitModel(gstate.weight, gstate.num_dim);
      // broadcast initialize model
      rabit::Broadcast(gstate.weight,
                       sizeof(DType) * gstate.num_dim, 0);
      gstate.old_objval = this->Eval(gstate.weight);
      gstate.init_objval = gstate.old_objval;
      
      if (silent == 0 && rabit::GetRank() == 0) {
        rabit::TrackerPrintf
            ("L-BFGS solver starts, num_dim=%lu, init_objval=%g, size_memory=%lu, RAM-approx=%lu\n",
             gstate.num_dim, gstate.init_objval, gstate.size_memory,
             gstate.MemCost() + hist.MemCost());
      }
    }
  }
  /*!
   * \brief get the current weight vector
   *  note that if update function is called
   *  the content of weight vector is no longer valid
   * \return weight vector
   */
  virtual DType *GetWeight(void) {
    return gstate.weight;
  }
  /*!
   * \brief update the weight for one L-BFGS iteration
   * \return whether stopping condition is met
   */
  virtual bool UpdateOneIter(void) {
    bool stop = false;
    GlobalState &g = gstate;
    g.obj->CalcGrad(g.grad, g.weight, g.num_dim);
    rabit::Allreduce<rabit::op::Sum>(g.grad, g.num_dim);
    // find change direction
    double vdot = FindChangeDirection(g.tempw, g.grad, g.weight);
    // line-search, g.grad is now new weight
    int iter = BacktrackLineSearch(g.grad, g.tempw, g.weight, vdot);
    utils::Check(iter < max_linesearch_iter, "line search failed");
    // swap new weight 
    std::swap(g.weight, g.grad);
    // check stop condition
    if (gstate.num_iteration > static_cast<size_t>(min_lbfgs_iter)) {
      if (g.old_objval - g.new_objval < lbfgs_stop_tol * g.init_objval) {
        return true;
      }
    }
    if (silent == 0 && rabit::GetRank() == 0) {
      rabit::TrackerPrintf
          ("[%d] L-BFGS: linesearch finishes in %d rounds, new_objval=%g, improvment=%g\n",
           gstate.num_iteration, iter,
           gstate.new_objval,
           gstate.old_objval - gstate.new_objval);
    }
    gstate.old_objval = gstate.new_objval;
    rabit::CheckPoint(&gstate, &hist);
    return stop;
  }
  /*! \brief run optimization */
  virtual void Run(void) {
    this->Init();
    while (gstate.num_iteration < static_cast<size_t>(max_lbfgs_iter)) {
      if (this->UpdateOneIter()) break;
    }
    if (silent == 0 && rabit::GetRank() == 0) {
      size_t nonzero = 0;
      for (size_t i = 0; i < gstate.num_dim; ++i) {
        if (gstate.weight[i] != 0.0f) nonzero += 1;
      }
      rabit::TrackerPrintf
          ("L-BFGS: finishes at iteration %d, %lu/%lu active weights\n",
           gstate.num_iteration, nonzero, gstate.num_dim);
    }
{'fraction_non_alphanumeric': 0.12482823461343748, 'fraction_numerical': 0.00708758226657988, 'mean_word_length': 2.7525101763907736, 'pattern_counts': {'":': 0, '<': 41, '<?xml version=': 0, '>': 49, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5688270', 'n_tokens_mistral': 4716, 'n_tokens_neox': 4623, 'n_words': 1188}