Optimizing Nondecomposable Data Dependent Regularizers via Lagrangian Reparameterization Offers Significant Performance and Efficiency Gains

Sathya N. Ravi, Abhay Venkatesh, Glenn Moo Fung, Vikas Singh

Introduction

Modern deep learning typically relies on decomposable loss functions, where the total loss is the sum of individual data point losses. This paper, presented at AAAI-20, introduces a mathematically elegant and computationally efficient framework to incorporate "nondecomposable" regularizers. By utilizing Lagrangian reparameterization, the authors enable models to optimize directly for complex global metrics like the F1-score or fairness constraints without the prohibitive computational overhead traditionally associated with these metrics.

The Problem: Nondecomposable Metrics

In standard machine learning, Stochastic Gradient Descent (SGD) thrives on decomposable losses because minibatches provide unbiased gradient estimates. However, many critical performance metrics—such as the F1-score, Precision at a fixed Recall, or demographic fairness—are nondecomposable. These metrics depend on the global data distribution rather than individual points.

Standard classifiers often suffer from biases, such as lower accuracy for smaller objects, because they optimize for decomposable metrics that ignore global distribution properties.

When these metrics are used as regularizers in a standard minibatch setting, gradients become biased, leading to unstable training and poor convergence. Previous solutions often involved complex $O(n^3)$ optimization solvers that do not scale to modern deep learning architectures.

Methodology: Lagrangian Reparameterization

The authors propose a three-step approach to bridge the gap between complex metrics and efficient optimization:

  1. Reparameterization: The $F_\beta$ metric is formulated as a Linear Program (LP) and simplified to be compatible with non-linear Deep Neural Networks (DNNs).
  2. Partial Dualization: Instead of solving the entire primal problem, the authors move problematic constraints into a Lagrangian formulation. This creates a saddle-point (min-max) problem between model weights and dual variables.
  3. Efficient Projection: A specialized projection algorithm reduces complexity from $O(n^3)$ to $O(B \log B)$, where $B$ is the minibatch size.
The proposed optimization framework alternates between SGD on model weights and reparameterized dual ascent on dual variables, modifying only the final layer.

Crucially, the authors prove that projecting dual variables once per epoch is sufficient for convergence, making the additional computational cost negligible compared to standard training.

Experimental Results

The framework was evaluated on two primary benchmarks: S-MNIST (Shape-MNIST), a modified MNIST dataset with varying object sizes, and MSCOCO Stuff, a large-scale semantic segmentation dataset.

Key results include:

  • Performance Gains: On MSCOCO Stuff, the method achieved a mean Intersection over Union (mIoU) of 0.32, a 10% relative improvement over the previous state-of-the-art (0.30).
  • Efficiency: The per-iteration complexity remains nearly optimal by avoiding the "double loop" slowdown common in other Lagrangian methods.
  • Stability: Data-dependent regularizers significantly stabilized the training process in non-convex settings like deep segmentation.

Conclusion

This work provides a robust, practitioner-friendly framework for optimizing nondecomposable metrics. While currently focused on the $F_\beta$ metric and requiring predefined "shape" variables, the approach opens doors for applying Lagrangian reparameterization to complex constraints in Reinforcement Learning and Generative Adversarial Networks.

Summary updated

Abstract

Data dependent regularization is known to benefit a wide variety of problems in machine learning. Often, these regularizers cannot be easily decomposed into a sum over a finite number of terms, e.g., a sum over individual example-wise terms. The Fβ measure, Area under the ROC curve (AUCROC) and Precision at a fixed recall (P@R) are some prominent examples that are used in many applications. We find that for most medium to large sized datasets, scalability issues severely limit our ability in leveraging the benefits of such regularizers. Importantly, the key technical impediment despite some recent progress is that, such objectives remain difficult to optimize via backpropapagation procedures. While an efficient general-purpose strategy for this problem still remains elusive, in this paper, we show that for many data-dependent nondecomposable regularizers that are relevant in applications, sizable gains in efficiency are possible with minimal code-level changes; in other words, no specialized tools or numerical schemes are needed. Our procedure involves a reparameterization followed by a partial dualization – this leads to a formulation that has provably cheap projection operators. We present a detailed analysis of runtime and convergence properties of our algorithm. On the experimental side, we show that a direct use of our scheme significantly improves the state of the art IOU measures reported for MSCOCO Stuff segmentation dataset.
BibTeX
@inproceedings{ravi2020optimizing,
  author = {Sathya N. Ravi and Abhay Venkatesh and Glenn Moo Fung and Vikas Singh},
  title = {{Optimizing Nondecomposable Data Dependent Regularizers via Lagrangian Reparameterization Offers Significant Performance and Efficiency Gains}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i04.5999},
}
Figure