Multivariate normal cholesky optimization?

Developers
1

This is about the code in multi_normal_cholesky_lpdf. Is there good reason to do the inverse of L alone and not in a solve? Specifically this line in stan-math:

  const matrix_partials_t inv_L_dbl
      = mdivide_left_tri<Eigen::Lower>(value_of(L_ref));

I ask because it seems it would be more performant to
\begin{aligned} (Y - \mu)^T \Sigma^{-1} (Y - \mu) &= (Y - \mu)^T L^{-T}L^{-1} (Y - \mu) \\ &= (L^{-1}(Y - \mu)) ^T (L^{-1}(Y - \mu)) \end{aligned}
set X := Y - \mu and use the triangular view in Eigen to solve for Z = L^{-1}X. Something like

Z = L.triangularView<Eigen::Lower>().solve(X)

and then do rows_dot_self(Z).

There’s some precedence for this method in pytorch, see the source

 def log_prob(self, value):
        if self._validate_args:
            self._validate_sample(value)
        diff = value - self.loc
        M = _batch_mahalanobis(self._unbroadcasted_scale_tril, diff)
        half_log_det = self._unbroadcasted_scale_tril.diagonal(dim1=-2, dim2=-1).log().sum(-1)
        return -0.5 * (self._event_shape[0] * math.log(2 * math.pi) + M) - half_log_det
2 Likes
2

Good catch. I’d definitely prefer triangular solves here just for the better numerics.

It looks like the vecorization is handled with loops here so I don’t know if we can go all the way to rows_dot_self (still need to increment the adjoints).

It should be possible to get benchmarks on this using the benchmarks stuff. Something like:

benchmarks/benchmark.py multi_normal_cholesky_lpdf
3

Yea, looking at the gradient calculations gives a reason for the way it’s written. The code defines \operatorname{\mathtt{half}} and \operatorname{\mathtt{scaled-diff}}. Where what I call Z^T is equal to \operatorname{\mathtt{half}}. Then

\begin{align} \operatorname{\mathtt{scaled-diff}} &= L^{-T}Z \\ \operatorname{\mathtt{scaled-diff}} \cdot \operatorname{\mathtt{half}} &= L^{-T} ZZ^{T}\end{align}

It would be interesting to test if doing 2 solves prior to the loop - solving for Z and then solving for W = L^{-T}Z is faster.

  const matrix_partials_t inv_L_dbl
      = mdivide_left_tri<Eigen::Lower>(value_of(L_ref));

  if (include_summand<propto, T_y, T_loc, T_covar_elem>::value) {
    for (size_t i = 0; i < size_vec; i++) {
      const auto& y_col = as_column_vector_or_scalar(y_vec[i]);
      const auto& mu_col = as_column_vector_or_scalar(mu_vec[i]);

      const row_vector_partials_t half
          = (inv_L_dbl.template triangularView<Eigen::Lower>()
             * (value_of(y_col) - value_of(mu_col))
                   .template cast<T_partials_return>())
                .transpose();
      const vector_partials_t scaled_diff
          = (half * inv_L_dbl.template triangularView<Eigen::Lower>())
                .transpose();

      logp -= 0.5 * dot_self(half);

      if (!is_constant_all<T_y>::value) {
        ops_partials.edge1_.partials_vec_[i] -= scaled_diff;
      }
      if (!is_constant_all<T_loc>::value) {
        ops_partials.edge2_.partials_vec_[i] += scaled_diff;
      }
      if (!is_constant_all<T_covar>::value) {
        ops_partials.edge3_.partials_ += scaled_diff * half;
      }
    }
  }
2 Likes
4

Ooooh yeah yeah, that could be big-time more efficient if you had multiple right hand sides. So first copy stuff to a matrix, then do the solves, and then pass the results on to whatever.