An Improved Analysis of Alternating Minimization for Structured Multi-Response Regression

Sheng Chen, Arindam BanerjeeNeurIPS 2018

Introduction

This paper provides a more realistic theoretical analysis of the Alternating Minimization (AltMin) algorithm for multi-response regression. By removing the common but impractical "resampling" assumption found in previous literature, the authors prove that AltMin converges geometrically to the optimal error. Surprisingly, the study also demonstrates that random initialization can eventually perform just as well as a perfectly chosen starting point, challenging conventional wisdom in non-convex optimization.

The Challenge of Multi-Response Regression

In multi-response linear regression, the goal is to predict multiple outputs simultaneously from the same set of features. A primary challenge is that the noise across these different outputs is often correlated, but the exact structure of that correlation—represented by the covariance matrix, $\Sigma_*$—is unknown.

To achieve optimal results, researchers utilize "joint estimators" that attempt to find the best model parameters ($\theta_*$) and the noise structure ($\Sigma_*$) simultaneously. Because this is a non-convex problem, it is mathematically complex to solve. The standard approach is Alternating Minimization (AltMin): the algorithm fixes the noise estimate to update the model, then fixes the model to update the noise estimate, repeating this process iteratively.

While AltMin is highly effective in practice, its theoretical foundations have historically been shaky. Previous proofs relied heavily on a "resampling" assumption, which posits that a fresh batch of data is available for every single iteration of the algorithm. In reality, practitioners reuse the same dataset for every step. This paper successfully closes the gap between theoretical assumptions and practical application.

Methods and Algorithm

The authors analyze a specific AltMin procedure designed for high-dimensional settings where the parameter $\theta_*$ possesses a specific "structure," such as sparsity.

Algorithm 1: Alternating Minimization for Multi-Response Regression

The algorithm operates in two primary steps per iteration:

  1. $\Sigma$-step: Calculates the empirical covariance of the current model's residuals.
  2. $\theta$-step: Solves a constrained least-squares problem to update the model parameters, utilizing the new noise estimate to appropriately "weight" the importance of different responses.

To bypass the resampling assumption, the authors employ uniform bounds and a sophisticated probability theory tool known as generic chaining. This mathematical toolkit allows them to rigorously account for the statistical dependencies that naturally arise when reusing the same data across multiple iterations. Furthermore, they utilize Gaussian width ($w(C)$) as a complexity measure, providing a modern method to generalize concepts like sparsity to any low-dimensional structure.

Experimental Setup

As a theoretical work, the paper validates its findings using synthetic datasets to precisely control variables:

  • Problem Size: $p = 1000$ dimensions, with a sparsity of $s = 20$ non-zero entries.
  • Responses: $m$ ranging from 10 to 18.
  • Noise: Independent and identically distributed (i.i.d.) standard Gaussian noise, transformed by a block-diagonal covariance matrix $\Sigma_*$.
  • Features: Generated from an isotropic sub-Gaussian distribution.

Key Insights and Results

  • Resampling is Unnecessary: The paper definitively proves that fresh data is not required at every step to guarantee convergence. By leveraging uniform bounds, the authors show the algorithm is robust to the data reuse that occurs in standard practice.
  • Initialization Independence: A particularly notable finding is the algorithm's behavior regarding initialization. While most non-convex optimization theory dictates the need for a "warm start" (a highly accurate initial guess), this paper demonstrates that AltMin with random initialization eventually catches up, achieving the same statistical error as a well-initialized version.
  • Geometric Convergence: The error decreases at a consistent geometric rate ($\rho^T$) until it reaches a fundamental "floor" determined by the inherent noise in the data.
  • Oracle Performance: Under good initialization—or after sufficient iterations of random initialization—the AltMin estimator matches the performance of an "Oracle" estimator that already knows the true noise covariance.
  • The Error Floor: For arbitrary initialization, the minimum achievable error ($e_{min}$) is $O(\frac{w(C) + m}{\sqrt{n}})$. With good initialization, this bound sharpens to $O(\frac{w(C)}{\sqrt{n}})$.
  • Phase Transition: Experimental results revealed a clear "phase transition." When the sample size $n$ reaches a certain threshold (around $n=40$ in their specific tests), the error of the randomly initialized AltMin suddenly drops to match the well-initialized version.

Limitations and Future Work

While the theoretical advancements are significant, the authors note a few limitations. First, the analysis assumes prior knowledge of the "budget" $\lambda$ for the structure-inducing function (e.g., knowing the exact sparsity level), whereas in practice, this requires cross-validation tuning. Second, the theory assumes global optimality can be achieved in the $\theta$-step. While true for convex structures (like $L_1$ norms), it is computationally harder for non-convex structures, though algorithms like Hard Thresholding Pursuit often perform well empirically. Finally, while the analysis extends to sub-Gaussian noise, exploring heavier-tailed noise distributions remains an open challenge for future research.

Summary updated

BibTeX
@inproceedings{chen2018improved,
  author = {Sheng Chen and Arindam Banerjee},
  title = {{An Improved Analysis of Alternating Minimization for Structured Multi-Response Regression}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
}
Figure