Scrambled Objects for Least-Squares Regression

Odalric-Ambrym Maillard, Rémi MunosNeurIPS 2010 · OpenReview

TL;DR

This paper introduces "scrambled objects"—randomly generated features created by mixing infinite-dimensional basis functions (like wavelets) with Gaussian noise. By performing least-squares regression in these random subspaces, the authors achieve error rates that are remarkably independent of the data distribution, providing a robust and computationally efficient way to approximate complex functions in high-dimensional spaces.

The Problem: Overfitting in Infinite Dimensions

In statistical regression, we try to learn an unknown function $f^*$ from noisy data. When the space of possible functions is infinite-dimensional (like the space of all continuous functions), we face a major hurdle: overfitting.

Traditional solutions involve penalization (like Lasso or Ridge regression) to keep the model simple. An alternative is "Compressed Least Squares," which projects the problem into a smaller, randomly chosen subspace. However, previous work on this was limited to finite-dimensional settings. This paper tackles the challenge of applying random subspaces to infinite-dimensional function spaces (such as Sobolev spaces). Specifically, it addresses how to choose these subspaces so that the model performs well even when we don't know the underlying distribution of the data—a common real-world problem where data might be clustered in small, "peaky" regions.

The Solution: Regression with Scrambled Objects

The authors propose a framework called Regression with Scrambled Objects. The approach follows these steps:

  1. Initial Features: Start with a classic, infinite set of basis functions $\{\phi_i\}$, such as wavelets or "hat" functions.
  2. Scrambling: Create $P$ new "random features" $\psi_p$ by taking random linear combinations of all the initial features, weighted by Gaussian coefficients.
  3. If you use hat functions, the resulting "scrambled objects" are Brownian motions.
  4. If you use wavelets, they are scrambled wavelets.
  5. Least Squares: Perform standard ordinary least squares regression using only these $P$ scrambled features.
  6. Lazy Expansion: To make this computationally feasible, they use a "lazy" numerical implementation. Instead of calculating all infinite features, they only expand the multi-resolution tree (the wavelets) along the paths necessary to evaluate the specific data points provided.

Synthetic Illustrations

Because this is primarily a theoretical paper focused on proving mathematical bounds, it relies on synthetic numerical illustrations rather than large-scale benchmarks. The authors use a 1D periodic target function $f^*$ sampled from a "peaky" Gaussian distribution.

Comparison of Target Functions, BLSR, and LSR

These illustrations demonstrate that scrambled objects (BLSR) can "discover" relevant high-frequency features in localized regions of the input space where standard methods (LSR) might fail to capture the true function dynamics.

Key Insights

  • Distribution Independence: The most striking finding is that the error bounds for this method do not depend on the data distribution $P$. In typical regression, you need to know $P$ to choose the right basis. Here, randomization allows the model to adapt to any distribution automatically.
  • The Power of Scrambling: By mixing wavelets of all scales into a single feature, a "scrambled wavelet" can detect correlations at multiple frequencies simultaneously. This makes the model much more robust to "peaky" data distributions than standard linear approximations.
  • Minimax Optimality: The authors show that for scrambled wavelets, the error rate is $O(\tilde{N}^{-1/2})$, which is arbitrarily close to the theoretical "minimax" limit for these types of function spaces. Essentially, you can't do much better than this, regardless of the method used.
  • Bridge to RKHS: The paper provides a formal link between these random subspaces and Reproducing Kernel Hilbert Spaces (RKHS), showing that these random features effectively approximate the kernel space of Gaussian processes.

Key Results

  • Excess Risk Bounds: The paper proves that the excess risk (how much worse the model is than the best possible function) scales as $O(\frac{\log N}{N} P + \frac{\log N}{P})$.
  • Optimal Subspace Size: By choosing the number of random features $P \approx \sqrt{N}$, the total error becomes roughly $O(\frac{\log N}{\sqrt{N}})$.
  • Computational Efficiency: Using the "lazy expansion" trick, the numerical complexity is kept to $O(N^2 + 2^d N^{3/2} \log N)$, where $N$ is the number of data points and $d$ is the dimension. This makes it practical for moderately high-dimensional problems.

Limitations and Future Work

  • Smoothness Constraints: The current analysis is optimized for functions with a specific level of smoothness ($s > d/2$). The authors note that a more refined analysis is needed for functions that are extremely smooth ($s \gg d/2$).
  • Dimensionality: While the "lazy" approach helps, the complexity still contains a $2^d$ term, which means the method may still struggle with very high-dimensional inputs (the "curse of dimensionality") unless combined with techniques like sparse grids.
  • Brownian Sheets: While they prove bounds for Brownian motions/sheets, they acknowledge that it is currently unknown if these specific objects achieve the minimax optimal rate in dimensions $d > 1$.

Summary updated

Abstract

We consider least-squares regression using a randomly generated subspace G<em>P\subset F of finite dimension P, where F is a function space of infinite dimension, e.g.~L</em>2([0,1]^d). G<em>P is defined as the span of P random features that are linear combinations of the basis functions of F weighted by random Gaussian i.i.d.~coefficients. In particular, we consider multi-resolution random combinations at all scales of a given mother function, such as a hat function or a wavelet. In this latter case, the resulting Gaussian objects are called {\em scrambled wavelets} and we show that they enable to approximate functions in Sobolev spaces H^s([0,1]^d). As a result, given N data, the least-squares estimate \hat g built from P scrambled wavelets has excess risk ||f^* - \hat g||</em>\P^2 = O(||f^<em>||^2_{H^s([0,1]^d)}(\log N)/P + P(\log N )/N) for target functions f^</em>\in H^s([0,1]^d) of smoothness order s&gt;d/2. An interesting aspect of the resulting bounds is that they do not depend on the distribution \P from which the data are generated, which is important in a statistical regression setting considered here. Randomization enables to adapt to any possible distribution. We conclude by describing an efficient numerical implementation using lazy expansions with numerical complexity \tilde O(2^d N^{3/2}\log N + N^2), where d is the dimension of the input space.
BibTeX
@inproceedings{maillard2010scrambled,
  author = {Odalric-Ambrym Maillard and Rémi Munos},
  title = {{Scrambled Objects for Least-Squares Regression}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
  url = {https://openreview.net/forum?id=r1b1XO-_bS},
}
Figure