algorithms/rappor/lasso_runner_test.cc

// Copyright 2018 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "algorithms/rappor/lasso_runner_test.h"

namespace cobalt {
namespace rappor {

void LassoRunnerTest::SetLassoRunner(const InstanceSet* matrix) {
  lasso_runner_.reset(new LassoRunner(matrix));
}

void LassoRunnerTest::CheckFirstRapporStepCorrectness(
    const LabelSet& right_hand_side, const Weights& results) {
  // Get the penalty paramaters.
  const double l1 = lasso_runner_->minimizer_data_.l1;
  const double l2 = lasso_runner_->minimizer_data_.l2;
  const double zero_threshold = lasso_runner_->minimizer_data_.zero_threshold;
  // Reference to the problem matrix.
  const Eigen::SparseMatrix<double, Eigen::RowMajor>* A_matrix(
      lasso_runner_->matrix_);

  // Check that the minimizer converged and that minimizer info makes sense.
  EXPECT_EQ(lasso_runner_->minimizer_data_.converged, true);
  EXPECT_GE(l1, 0);
  EXPECT_GE(l2, 0);
  EXPECT_GT(lasso_runner_->minimizer_data_.convergence_threshold, 1e-16);
  EXPECT_GE(lasso_runner_->minimizer_data_.convergence_threshold,
            lasso_runner_->min_convergence_threshold_);
  EXPECT_GT(lasso_runner_->minimizer_data_.num_epochs_run,
            0);  // this check assumes that the initial guess was not exact
  if (l1 > 0) {
    EXPECT_GT(l1, l2);
  }

  // Check dimensions correctness and compute the
  // gradient = A^T * (A * x - y) / N + l2 * x.
  EXPECT_EQ(right_hand_side.size(), A_matrix->rows());
  EXPECT_EQ(results.size(), A_matrix->cols());
  Eigen::VectorXd residual = *A_matrix * results;
  residual -= right_hand_side;
  Eigen::VectorXd gradient = A_matrix->transpose() * residual;
  // Scale regression part of the gradient
  gradient /= A_matrix->rows();
  gradient += l2 * results;

  // Compute the KKT condition violation.
  Eigen::VectorXd estimate_error;
  estimate_error =
      ((results.array() > zero_threshold).select(gradient.array() + l1, 0))
          .matrix();
  estimate_error +=
      ((results.array() < -zero_threshold).select(gradient.array() - l1, 0))
          .matrix();
  estimate_error += ((abs(results.array()) <= zero_threshold)
                         .select(abs(gradient.array()) - l1, 0)
                         .max(0))
                        .matrix();
  // The correctness check is relatively lax because the algorithm could have
  // converged before reaching the solution. On the other hand, the convergence
  // thresholds should be such that this holds.
  EXPECT_LE(estimate_error.norm() / results.size(), 1e-3);
}

void LassoRunnerTest::CheckNonzeroCandidates(
    const std::vector<int>& nonzero_cols, const Weights& results) {
  for (int i = 0; i < results.size(); i++) {
    if (std::find(nonzero_cols.begin(), nonzero_cols.end(), i) !=
        nonzero_cols.end()) {
      EXPECT_GE(results[i], lasso_runner_->zero_threshold_);
    } else {
      EXPECT_LE(results[i], lasso_runner_->zero_threshold_);
    }
  }
}

void LassoRunnerTest::CheckLassoRunnerParameters() {
  EXPECT_GT(lasso_runner_->zero_threshold_, 1e-15);
  EXPECT_LT(lasso_runner_->zero_threshold_, 1e-2);
  EXPECT_GT(lasso_runner_->alpha_, 0.0);
  EXPECT_LT(lasso_runner_->alpha_, 1.0);
  EXPECT_GT(lasso_runner_->min_convergence_threshold_, 1e-15);
  EXPECT_GE(lasso_runner_->l1_max_to_l1_min_ratio_, 0);
  EXPECT_LT(lasso_runner_->l1_max_to_l1_min_ratio_, 1e-2);
  EXPECT_GT(lasso_runner_->num_lasso_steps_, 10);
}

// Creates a random sparse m x n matrix with positive entries.
InstanceSet LassoRunnerTest::RandomMatrix(const int m, const int n,
                                          const int num_nonzero_entries) {
  std::vector<Eigen::Triplet<double>> triplets(num_nonzero_entries);
  std::uniform_int_distribution<int> m_distribution(0, m - 1);
  std::uniform_int_distribution<int> n_distribution(0, n - 1);
  std::uniform_real_distribution<double> real_distribution(1.0, 2.0);
  for (int k = 0; k < num_nonzero_entries; k++) {
    uint32_t i = m_distribution(random_dev_);
    uint32_t j = n_distribution(random_dev_);
    double entry = real_distribution(random_dev_);
    triplets.push_back(Eigen::Triplet<double>(i, j, entry));
  }
  InstanceSet matrix(m, n);
  matrix.setFromTriplets(triplets.begin(), triplets.end());

  return matrix;
}

}  // namespace rappor
}  // namespace cobalt