Alternating Minimization for Regression Problems with Vector-valued Outputs

Prateek Jain, Ambuj Tewari

Introduction

This paper provides the first rigorous finite-sample guarantees for Alternating Minimization (AltMin) in multi-output regression problems. The authors prove that AltMin—a computationally efficient heuristic—achieves the same statistical accuracy as the Maximum Likelihood Estimator (MLE). Crucially, it significantly outperforms standard Ordinary Least Squares (OLS) when the noise across different outputs is correlated.

The Challenge of Vector-Valued Regression

In many real-world scenarios, we want to predict multiple related variables simultaneously, such as forecasting various economic indicators or identifying genomic markers. This is known as vector-valued regression.

The standard approach is Ordinary Least Squares (OLS), which treats each output independently. However, if the "noise" or errors in these outputs are correlated (which is common in related tasks), OLS becomes statistically inefficient. The Maximum Likelihood Estimator (MLE) accounts for this noise structure and is much more accurate.

The catch? Computing the MLE for these models involves solving a non-convex optimization problem. While practitioners often use an "Alternating Minimization" heuristic—iteratively estimating the regression weights and then the noise covariance—there was previously no theoretical guarantee that this approach would actually converge to a good solution or match the MLE's performance in finite samples.

Methodology: The AltMin Algorithm

The authors analyze two popular models:

  1. The Pooled Model: A single coefficient vector is shared across all tasks.
  2. Seemingly Unrelated Regression (SUR): A more general model where each task has its own coefficient vector, but errors remain correlated.

The core method is the AltMin algorithm, which alternates between two steps:

  • Step A (Covariance Estimation): Use current regression weights to estimate the noise covariance matrix ($\Sigma$).
  • Step B (Weighted Least Squares): Use the estimated $\Sigma$ to "de-noise" the data and update the regression weights.
Algorithm 1: Alternating Minimization for the Pooled Model

The Novelty: To provide a rigorous proof, the authors use a "sample-splitting" technique, where fresh data is used at each iteration to avoid tricky statistical dependencies. They prove that this process creates a "virtuous circle": better weights lead to a better covariance estimate, which in turn leads to even more accurate weights.

Experimental Validation and Key Results

The paper is primarily theoretical and uses synthetic datasets to validate its mathematical bounds. Data is generated using multivariate Gaussian distributions with varying levels of noise correlation ($\epsilon$). The authors also explore high-dimensional settings where the number of features ($d$) and tasks ($m$) are varied to show how the error scales.

Simulation results comparing OLS, MLE, and AltMin across different parameters

The theoretical and empirical findings yield several key insights:

  • Matching MLE: The authors prove that the output of AltMin enjoys the same performance guarantees as the MLE (up to universal constants).
  • The Efficiency Gap: OLS can be "arbitrarily worse" than MLE. If two noise terms are perfectly correlated, you can subtract the equations to cancel the noise entirely—a trick OLS completely misses. In a 2-task example with noise correlation $1-\epsilon$, the improvement factor of AltMin over OLS is roughly $1/\epsilon$. As the noise becomes more correlated ($\epsilon \to 0$), AltMin's error vanishes while OLS's error remains high.
  • Geometric Convergence: AltMin doesn't just converge; it converges fast. The estimation error reduces by a constant factor in each iteration.
  • Logarithmic Dependence: In high-dimensional settings, the error bound depends only logarithmically on the data dimensionality, making the method robust for "big data" problems.
  • Consistency: Explicit sample complexity bounds (e.g., $n \geq C \cdot (m + d)$) are provided, detailing the requirements for the algorithm to succeed with high probability.

Limitations and Future Work

While the paper establishes strong foundational guarantees, it notes a few limitations:

  • Sample Splitting: The theoretical proof relies on using fresh samples for each iteration. While AltMin works fine in practice without this, a proof for the "re-used sample" case remains an open challenge.
  • Gaussian Assumptions: The current analysis assumes sub-Gaussian noise. Extending these guarantees to heavy-tailed distributions or specific non-linear models would be a natural next step.
  • Structural Priors: Future work could explore adding structural assumptions (like low-rank or sparsity) to the regression weight matrix $W$ within this AltMin framework.

Summary updated

Abstract

In regression problems involving vector-valued outputs (or equivalently, multiple responses), it is well known that the maximum likelihood estimator (MLE), which takes noise covariance structure into account, can be significantly more accurate than the ordinary least squares (OLS) estimator. However, existing literature compares OLS and MLE in terms of their asymptotic, not finite sample, guarantees. More crucially, computing the MLE in general requires solving a non-convex optimization problem and is not known to be efficiently solvable. We provide finite sample upper and lower bounds on the estimation error of OLS and MLE, in two popular models: a) Pooled model, b) Seemingly Unrelated Regression (SUR) model. We provide precise instances where the MLE is significantly more accurate than OLS. Furthermore, for both models, we show that the output of a computationally efficient alternating minimization procedure enjoys the same performance guarantee as MLE, up to universal constants. Finally, we show that for high-dimensional settings as well, the alternating minimization procedure leads to significantly more accurate solutions than the corresponding OLS solutions but with error bound that depends only logarithmically on the data dimensionality.
BibTeX
@inproceedings{jain2015alternating,
  author = {Prateek Jain and Ambuj Tewari},
  title = {{Alternating Minimization for Regression Problems with Vector-valued Outputs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
}
Figure