Globally Optimal Learning for Structured Elliptical Losses

Yoav Wald, Nofar Noy, Gal Elidan, Ami WieselNeurIPS 2019

Introduction

In structured prediction tasks—where models must predict multiple correlated variables like stock prices or regional weather patterns—practitioners often rely on the assumption of Gaussian noise. This assumption naturally leads to the Mean Squared Error (MSE) loss, which is mathematically convenient and convex. However, the Gaussian assumption fails miserably when faced with "heavy-tailed" data or outliers.

While robust alternatives like the Huber loss are standard in simple regression, applying robust losses to structured models (such as Markov Random Fields) typically results in non-convex optimization problems. Historically, researchers have avoided these formulations because non-convexity implies that standard optimization algorithms might get trapped in sub-optimal local minima.

This paper bridges the gap between the need for robust statistics and the requirement for reliable optimization guarantees. The authors prove that for a wide class of robust, non-convex loss functions known as elliptical losses, any stationary point is a global optimum in the limit of infinite data. By combining this theoretical guarantee with an efficient algorithm, they demonstrate how to achieve robust structured prediction without the fear of local minima.

Methods: Structured Elliptical Losses

The authors focus on Structured Elliptical Losses, which arise from the elliptical family of distributions. This family includes the Gaussian distribution, the T-distribution, and Tyler’s "angular" loss.

Key Contributions

  1. Global Optimality Proof: The core theoretical result demonstrates that at the population limit (infinite training data), the optimization landscape of these robust losses is surprisingly well-behaved. Specifically, any stationary point (where the gradient is zero) is guaranteed to be a global optimum, up to a scale constant.
  2. Minimization Majorization (Algorithm 1): To solve this non-convex problem in practice, the authors propose an iterative reweighting approach. In each step, the algorithm:
  3. Rescales the data: It calculates a weight for each data point based on the current model fit, effectively scaling down outliers or points with high error.
  4. Solves a Gaussian problem: It then solves a standard, convex Gaussian Markov Random Field (GMRF) problem using the reweighted data.

This elegant approach allows practitioners to leverage existing, highly optimized solvers for Gaussian models while reaping the benefits of robust estimation.

Experimental Validation

The authors evaluated their approach across synthetic and real-world datasets to test the limits of their theory and its practical utility.

Synthetic Data: Robustness to Heavy Tails

Data was generated from Multivariate Generalized Gaussian distributions with varying "tail" thicknesses.

Synthetic data experiments comparing Tyler and GMRF losses across varying tail thicknesses.

In these synthetic experiments, the robust "Tyler" loss was slightly sub-optimal on perfectly Gaussian data but significantly outperformed the standard Gaussian MRF as the data became increasingly heavy-tailed.

Real-World Data: Finance and Hydrology

The models were also tested on two complex, real-world tasks:

  • Stock Market Data: Predicting intra-day returns of 342 stocks using the "Huge Stock Market Dataset" from Kaggle—a classic example of heavy-tailed, correlated financial data.
  • River Discharge Estimation: Estimating daily water volume levels from 34 USGS sites synchronized with satellite rainfall data, requiring the model to capture both spatial and temporal correlations.
Relative MSE performance of structured vs. full models across different training sample sizes.

On the stock market dataset, the robust structured models (Tyler and Laplace) achieved lower Mean Squared Error (MSE) than the standard Gaussian approach, confirming that financial outliers are better handled by elliptical losses. In the river discharge task, the benefit of using a structured robust model was most pronounced when training data was scarce. The robust models learned the spatial dependencies of the river network much more accurately than Gaussian baselines.

Key Insights

  • Non-convexity isn't always a dealbreaker: The paper highlights a fascinating case where a problem is algebraically structured such that non-convexity does not lead to local minima issues.
  • The "Texture" of Data: By viewing data through the lens of Spherically Invariant Random Vectors (SIRV), the authors separate the "direction" of the data (the correlation structure) from its "texture" (the heavy-tailed scaling). Their method effectively ignores the noisy texture to find the true underlying structure.
  • Scale Invariance: For some robust losses (like Tyler’s), the solution is only identifiable up to a multiplicative constant. However, in regression contexts, this constant cancels out, making the ambiguity irrelevant for actual predictions.

Limitations and Future Work

While the results are promising, the authors note a few limitations and directions for future research:

  • The Infinite Data Assumption: The proof for global optimality holds at the "population limit." While empirical results on finite datasets are strong, formally characterizing the optimization landscape for small sample sizes remains an open theoretical challenge.
  • Structure Learning: This work assumes the graph structure (which variables are connected) is known beforehand. A promising future direction is automatically discovering these graph edges while using robust losses, potentially by adding $L_1$ (Lasso-style) regularization.
  • Extension to CRFs: The insights from this paper could naturally be extended to Gaussian Conditional Random Fields (CRFs), which are widely used in computer vision and signal processing.

Summary updated

BibTeX
@inproceedings{wald2019globally,
  author = {Yoav Wald and Nofar Noy and Gal Elidan and Ami Wiesel},
  title = {{Globally Optimal Learning for Structured Elliptical Losses}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
}
Figure