A note on replacing uniform subsampling by random projections in MCMC for linear regression of tall datasets

Rémi Bardenet, Odalric-Ambrym MaillardHAL 2015

TL;DR

This paper explores whether random projections, a popular dimensionality reduction technique, can replace random subsampling in Markov Chain Monte Carlo (MCMC) methods for analyzing large datasets. While random projections effectively solve the "resampling issue" by allowing consistent use of projections, they struggle to overcome the "budget issue," meaning they still require a significant portion of the dataset to make accurate MCMC decisions.

What Problem Does This Paper Address?

Modern datasets are often "tall," meaning they have a vast number of data points ($n$) but a manageable number of features ($d$). This scale makes traditional MCMC algorithms, which require processing the entire dataset at each step, computationally infeasible. To address this, researchers have developed MCMC variants that subsample the data at each iteration. This paper investigates if random projections, a technique that compresses data while preserving key properties, can offer a more efficient alternative to subsampling for Bayesian linear regression on these tall datasets. Specifically, it examines two critical challenges: the "resampling issue" (needing to access the same data projections across MCMC steps) and the "budget issue" (requiring a limited number of data points for each MCMC decision).

Methods

The authors adapt the "confidence MCMC" framework, which uses subsampling to approximate acceptance ratios, to incorporate random projections. They leverage the Johnson-Lindenstrauss (JL) lemma, which guarantees that random projections can preserve Euclidean norms.

  • Random Projections: Instead of randomly selecting data points, the paper proposes using a random matrix $A$ to project the data $X$ and $Y$ into a lower-dimensional space ($AX$, $AY$). This projection is applied to the log-likelihood ratio calculation within the MCMC algorithm.
  • Uniform JL Lemma: To address the "resampling issue," they utilize a uniform version of the JL lemma (Sarlós, 2006). This allows the same random projection matrix $A$ to be used consistently across multiple MCMC iterations, avoiding the need to re-query the full dataset.
  • Confidence Bounds: The core idea is to use confidence bounds derived from random projections to approximate the true log-likelihood ratio. If the projected log-likelihood ratio falls within a certain confidence interval, the MCMC acceptance decision is made based on this approximation.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and simulations using synthetic data generated from a linear Gaussian model.

Key Insights and Ideas

  • Random Projections Solve Resampling: The paper demonstrates that uniform JL lemmas allow for consistent random projections across MCMC iterations. This effectively solves the "resampling issue," meaning the algorithm doesn't need to re-access the entire dataset for each projection, which is a significant advantage for streaming data.
  • Budget Issue Remains a Hurdle: Despite solving the resampling issue, random projections, in their current form, do not sufficiently address the "budget issue." To achieve the necessary accuracy for MCMC decisions, the number of random projections ($k$) needs to scale with the dataset size ($n$), violating the goal of sublinear memory usage.
  • MLE as a Proxy is Insufficient: While using the Maximum Likelihood Estimator (MLE) of the projected problem as a proxy for the true MLE can help, it doesn't fundamentally resolve the budget issue. The gap between the projected MLE and the true MLE can still be too large, requiring too many projections.
  • Trade-off Between Accuracy and Memory: The paper highlights a fundamental trade-off: achieving high accuracy in MCMC decisions with random projections necessitates a large number of projections, which in turn requires significant memory, defeating the purpose of using random projections for tall datasets.

Key Results

  • The proposed algorithm, "Randomized Projection Metropolis-Hastings" (RPMH), can successfully replace uniform subsampling for the resampling issue.
  • For standard MCMC acceptance criteria and linear regression, achieving high probability of not failing (i.e., making a decision) requires the projection dimension $k$ to be at least $\Omega(n)$ when using naive confidence bounds.
  • Even with more advanced techniques like using the projected MLE as a proxy, the requirement for $k$ still scales with $n$ to ensure accurate credible intervals, thus not meeting the sublinear memory constraint.

Limitations and Future Work

  • Budget Issue Persistence: The primary limitation is the inability of current random projection techniques to solve the "budget issue" for MCMC in a sublinear memory setting.
  • Theoretical Focus: The paper is largely theoretical, with empirical validation limited to synthetic data.
  • Future Work: The authors suggest investigating communication complexity results to derive rigorous lower bounds on memory for one-pass MCMC algorithms. They also propose exploring better control variates than the projected MLE, potentially relaxing the strict one-pass constraint while maintaining controlled memory usage. The fundamental question of whether a win-win scenario exists for random projections in MCMC for tall data remains open.

Summary updated

Abstract

New Markov chain Monte Carlo (MCMC) methods have been proposed to tackle inference with tall datasets, i.e., when the number n of data items is intractably large. A large class of these new MCMC methods is based on randomly subsampling the dataset at each MCMC iteration. We investigate whether random projections can replace this random subsampling for linear regression of big streaming data. In the latter setting, random projections have indeed become standard for non-Bayesian treatments. We isolate two issues for MCMC to apply to streaming regression: 1) a resampling issue; MCMC should access the same random projections across iterations to avoid keeping the whole dataset in memory and 2) a budget issue; making individual MCMC acceptance decisions should require o(n) random projections. While the resampling issue can be satisfyingly tackled, current techniques in random projections and MCMC for tall data do not solve the budget issue, and may well end up showing it is not possible.
BibTeX
@inproceedings{bardenet2015note,
  author = {Rémi Bardenet and Odalric-Ambrym Maillard},
  title = {{A note on replacing uniform subsampling by random projections in MCMC for linear regression of tall datasets}},
  booktitle = {HAL},
  year = {2015},
}
Figure