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:
- The Pooled Model: A single coefficient vector is shared across all tasks.
- 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.
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.
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