Automatic and Harmless Regularization with Constrained and Lexicographic Optimization: A Dynamic Barrier Approach

Chengyue Gong, Xingchao Liu, Qiang LiuNeurIPS 2021 · OpenReview

Introduction

In modern machine learning, optimizing a single objective is rarely sufficient. Practitioners frequently need to balance primary performance metrics, such as accuracy, with auxiliary goals like model sparsity, fairness, or robustness. The conventional approach to this bi-objective trade-off is to optimize a linear combination of the loss functions (e.g., $Loss = f + \lambda g$). However, this requires extensive tuning of the hyperparameter $\lambda$ and is theoretically flawed for non-convex functions.

To address these challenges, researchers at UT Austin introduced Dynamic Barrier Gradient Descent (DBGD). Presented at NeurIPS 2021, this method provides a unified, gradient-based framework for constrained and lexicographic optimization, offering a principled alternative to linear scalarization.

The Pitfalls of Linear Combinations

Most practical machine learning tasks involve a trade-off between a main objective ($f$) and an auxiliary objective ($g$). The standard practice of optimizing $f + \lambda g$ suffers from three major limitations:

  1. Interpretability: The hyperparameter $\lambda$ is notoriously difficult to set, as its impact depends heavily on the relative scales and dynamics of $f$ and $g$.
  2. Pareto Coverage: For non-convex functions—ubiquitous in deep learning—linear combinations can only discover optimal points on the convex envelope of the Pareto front. They mathematically fail to find optimal trade-off points located in concave regions.
  3. The Tuning Tax: Identifying an optimal $\lambda$ typically requires computationally expensive grid searches.

Instead of linear combinations, the authors advocate for constrained optimization (minimizing $f$ while strictly keeping $g$ below a threshold $c$) or lexicographic optimization (minimizing a secondary loss $f$ strictly within the set of parameters that already minimize the primary loss $g$).

Dynamic Barrier Gradient Descent (DBGD)

The core contribution of the paper is the Dynamic Barrier Gradient Descent algorithm. Unlike traditional "dual" methods that attempt to estimate Lagrange multipliers—which often fail in non-convex settings due to the duality gap—DBGD is a primal method.

At each iteration, DBGD updates the model parameters $\theta$ using a dynamically weighted gradient: $$\theta_{t+1} \leftarrow \theta_t - \epsilon_t(\nabla f(\theta_t) + \lambda_t \nabla g(\theta_t))$$

The innovation lies in the computation of $\lambda_t$, which utilizes a dynamic barrier function $\phi(\theta)$ acting as a safety buffer:

  • If the constraint on $g$ is violated, the algorithm prioritizes minimizing $g$.
  • If the constraint is satisfied, it prioritizes minimizing $f$, allowing $g$ to increase only up to the limit permitted by the barrier.

This scale-invariant approach eliminates the need to guess a static $\lambda$. For lexicographic optimization—framed by the authors as "harmless regularization"—practitioners can simply set the target threshold to the minimum possible value of $g$. The algorithm will then use the auxiliary loss merely to "tie-break" among solutions that perform equally well on the primary task.

Empirical Results

The authors validated DBGD across a diverse array of tasks, demonstrating its superiority over traditional methods:

  • Profiling the Pareto Front (Sparsity & Fairness): By linearly varying the constraint threshold $c$, DBGD successfully mapped out the entire Pareto front evenly. In sparsity (using BERT-base on IMDb and NG20) and fairness tasks (Adult Income dataset), DBGD discovered optimal points in concave regions of the Pareto front that linear combination methods were mathematically incapable of reaching.
  • Tuning-Free Regularization (Fine-grained Classification): On the Oxford Flower and Stanford Car datasets using EfficientNet and AlphaNet, the tuning-free lexicographic approach matched or slightly exceeded the performance of the best-tuned linear combination (where $\lambda$ was found via exhaustive grid search).
  • Semi-supervised Learning: Applying DBGD to Unsupervised Data Augmentation (UDA) on CIFAR-10 with only 100 labels improved accuracy from 75.28% to 77.61%. This demonstrates that DBGD can effectively incorporate unsupervised signals without degrading the primary supervised objective.
  • Semantic Segmentation: On the Cityscapes dataset, the lexicographic approach successfully balanced a main UperNet loss with an auxiliary FCN loss, outperforming various linear combination baselines.

Limitations and Future Work

While DBGD presents a significant step forward, the authors note a few limitations. First, the current methodology focuses primarily on bi-objective trade-offs with a single constraint. Extending this to multiple constraints requires solving a computationally expensive quadratic program at each step. Second, the theoretical convergence proofs rely on continuous-time analysis; bridging the gap to discrete-time steps remains an area for future theoretical exploration. Finally, the current analysis assumes exact gradients, leaving the impact of stochasticity and mini-batch noise on the dynamic barrier as an open question for future research.

Summary updated

Abstract

Many machine learning tasks have to make a trade-off between two loss functions, typically the main data-fitness loss and an auxiliary loss. The most widely used approach is to optimize the linear combination of the objectives, which, however, requires manual tuning of the combination coefficient and is theoretically unsuitable for non-convex functions. In this work, we consider constrained optimization as a more principled approach for trading off two losses, with a special emphasis on lexicographic optimization, a degenerated limit of constrained optimization which optimizes a secondary loss inside the optimal set of the main loss. We propose a dynamic barrier gradient descent algorithm which provides a unified solution of both constrained and lexicographic optimization. We establish the convergence of the method for general non-convex functions.
BibTeX
@inproceedings{gong2021automatic,
  author = {Chengyue Gong and Xingchao Liu and Qiang Liu},
  title = {{Automatic and Harmless Regularization with Constrained and Lexicographic Optimization: A Dynamic Barrier Approach}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=l9D8xXgCVuO},
}
Figure