Stochastic Convex Optimization with Multiple Objectives

Mehrdad Mahdavi, Tianbao Yang, Rong JinNeurIPS 2013 · OpenReview

Executive Summary

In machine learning and operations research, practitioners rarely optimize for a single goal. An investor seeks high returns with low risk; a medical diagnostic tool requires high sensitivity alongside low false-positive rates. Traditionally, these competing interests are handled via "scalarization"—combining all goals into a single weighted sum. However, determining the correct weights is notoriously difficult, particularly when relying on noisy, stochastic data samples.

This paper tackles Stochastic Multi-Objective Optimization (SMOO) by introducing an efficient primal-dual algorithm. By treating one goal as the primary objective and the others as constraints, the proposed method achieves an optimal $O(1/\sqrt{T})$ convergence rate for general convex functions. Crucially, it bypasses the restrictive "uniform convergence" assumptions that hinder previous approaches.

The Challenge: Conflicting Goals and Noisy Data

Standard stochastic optimization focuses on minimizing a single expected loss. Real-world problems, however, introduce a two-fold challenge:

  1. Conflicting Goals: Improving one objective inherently risks degrading another.
  2. Stochasticity: Full objective functions are rarely accessible. Instead, algorithms must rely on a "stochastic oracle" that provides noisy glimpses of the data (e.g., a loss calculated on a single random mini-batch).

While Linear Scalarization is the most common workaround, assigning fixed weights to each objective requires extensive tuning and prior knowledge. An alternative is to frame the problem as a constrained optimization task: minimize objective $A$ while ensuring objectives $B$ and $C$ remain below specified thresholds.

Unfortunately, when these constraints are stochastic, standard projection methods fail. They rely on "uniform convergence"—the assumption that an empirical average of a function converges uniformly to its true expectation across the entire search space. In high-dimensional spaces with general Lipschitz continuous functions, this assumption rarely holds, causing naive methods to collapse.

The Proposed Solution: A Primal-Dual Approach

To overcome the uniform convergence trap, the authors abandon simple estimation techniques in favor of Lagrangian duality.

1. Constrained Formulation

The multi-objective problem is rigorously cast as: $$ \min \bar{f}^0(w) \quad \text{subject to} \quad \bar{f}^i(w) \le \gamma_i \quad \text{for } i=1 \dots m $$ Here, $\bar{f}^0$ represents the primary objective, $w$ represents the model parameters, and $\gamma_i$ are user-defined thresholds for the secondary objectives.

2. Stochastic Primal-Dual Algorithm

Instead of attempting to perfectly estimate the constraints upfront, the algorithm simultaneously updates two sets of variables at every iteration:

  • The Primal Variable ($w$): The actual solution (e.g., model weights) is updated via stochastic gradient descent applied to a Lagrangian function.
  • The Dual Variables ($\lambda$): These act as adaptive, dynamic weights for the constraints. If a constraint is violated during training, its corresponding $\lambda$ increases. This feedback loop forces the algorithm to prioritize the violated objective in the subsequent step, effectively "learning" the optimal scalarization weights on the fly.

3. Threshold Tightening for Safety

To guarantee that constraints are strictly met—rather than just satisfied "on average"—the authors introduce a variant of the algorithm that utilizes slightly conservative thresholds. This builds a mathematical safety margin into the optimization process.

Key Theoretical Guarantees

As a purely theoretical paper, the authors focus on rigorous mathematical proofs and algorithmic stability rather than empirical benchmarks on specific datasets. Their analysis yields several critical insights:

  • Optimal Efficiency: The algorithm achieves a convergence rate of $O(1/\sqrt{T})$. In stochastic optimization using only first-order (gradient) information, this is the theoretical "speed limit" for general convex functions.
  • High-Probability Bounds: Many stochastic algorithms only guarantee performance in expectation. In contrast, this paper provides bounds that hold with high probability. This distinction is vital for robust, safety-critical applications (like finance or autonomous driving) where average-case success is insufficient.
  • Simultaneous Convergence: The proofs demonstrate that after $T$ iterations, both the optimality gap (the distance to the true minimum) and the constraint violations shrink at the optimal $1/\sqrt{T}$ rate.

Limitations and Future Directions

While the proposed primal-dual algorithm offers a robust framework for SMOO, the authors note a few limitations and avenues for future research:

  • Slater's Condition: The theoretical proofs require the existence of a "strictly feasible" solution—meaning there must be at least one parameter state $w$ that satisfies all constraints with room to spare. If the constraints are fundamentally incompatible, the algorithm cannot converge.
  • Parameter Sensitivity: The method requires an initial estimate or bound for the dual variables ($\lambda_0$). Although the paper provides a strategy for estimating this bound, it introduces an additional layer of implementation complexity.
  • Exploiting Strong Convexity: The current framework assumes general Lipschitz continuous functions. An open question remains whether functions with stronger properties—such as smoothness or strong convexity—could be leveraged to achieve an even faster convergence rate of $O(1/T)$ in this multi-objective setting.

Summary updated

Abstract

In this paper, we are interested in the development of efficient algorithms for convex optimization problems in the simultaneous presence of multiple objectives and stochasticity in the first-order information. We cast the stochastic multiple objective optimization problem into a constrained optimization problem by choosing one function as the objective and try to bound other objectives by appropriate thresholds. We first examine a two stages exploration-exploitation based algorithm which first approximates the stochastic objectives by sampling and then solves a constrained stochastic optimization problem by projected gradient method. This method attains a suboptimal convergence rate even under strong assumption on the objectives. Our second approach is an efficient primal-dual stochastic algorithm. It leverages on the theory of Lagrangian method in constrained optimization and attains the optimal convergence rate of $[O(1/ \sqrt{T})]$ in high probability for general Lipschitz continuous objectives.
BibTeX
@inproceedings{mahdavi2013stochastic,
  author = {Mehrdad Mahdavi and Tianbao Yang and Rong Jin},
  title = {{Stochastic Convex Optimization with Multiple Objectives}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=HyZBQ_bu-S},
}
Figure