Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization

Xingyu Chen, Bokun Wang, Min Yang, Quanqi Hu, Qihang Lin, Tianbao Yang

Abstract

This paper introduces the first stochastic momentum-based algorithms for a challenging class of non-smooth, non-convex nested optimization problems, specifically Finite-sum Coupled Compositional Optimization (FCCO). By employing "outer" and "nested" smoothing techniques via Moreau envelopes, the authors improve the state-of-the-art iteration complexity from $O(\epsilon^{-6})$ to $O(\epsilon^{-5})$. Crucially, these algorithms enable the use of modern deep learning optimizers like Adam and Heavy-ball momentum, which are shown to significantly outperform standard SGD in tasks such as Group Distributionally Robust Optimization (GDRO) and fairness-constrained AUC maximization.

Introduction

The authors focus on Finite-sum Coupled Compositional Optimization (FCCO), where the objective function is a composition: $\min F(w) = \frac{1}{n} \sum f_i(g_i(w))$. This structure is common in advanced machine learning tasks such as:

  • X-risks: Optimizing non-decomposable metrics like AUC or Precision-Recall.
  • Group Distributionally Robust Optimization (GDRO): Ensuring model performance across diverse subgroups.
  • Constrained Optimization: Handling complex inequality constraints by converting them into penalty functions.

Most existing solvers for this structure assume the functions are smooth. When functions are non-smooth (e.g., hinge loss) and non-convex (e.g., deep neural networks), previous methods were either slow ($O(\epsilon^{-6})$ complexity) or relied on vanilla SGD, which often performs poorly in deep learning compared to momentum-based methods.

Methods

The paper proposes two primary algorithms, SONEX and ALEXR2, which leverage smoothing techniques to make non-smooth problems tractable for momentum updates.

  1. Outer Smoothing (SONEX): For problems where the outer function $f_i$ is non-smooth but the inner function $g_i$ is smooth, the authors use a Moreau envelope. This "blurs" the sharp corners of the non-smooth function, creating a smooth approximation for a single-loop stochastic momentum method.
  2. Nested Smoothing (ALEXR2): When both the outer and inner functions are non-smooth (weakly convex), the authors reformulate the problem into a minimax structure and apply a double-loop momentum method.
Table 2: Comparison of SONEX and ALEXR2 under different non-smoothness assumptions for outer ($f_i$) and inner ($g_i$) functions.

Unlike previous works, these algorithms are designed to work with Heavy-ball momentum or Adam-type updates, making them "plug-and-play" for modern deep learning pipelines.

Key Insights and Complexity Leap

A major theoretical contribution is the reduction of iteration complexity. By carefully choosing a smoothing parameter $\lambda$ related to the target accuracy $\epsilon$, the authors solve a smooth version of the problem while still guaranteeing a solution to the original "sharp" objective.

Table 1: Comparison of iteration complexity and features across various stochastic optimization algorithms for FCCO.

As shown in Table 1, moving from $O(\epsilon^{-6})$ to $O(\epsilon^{-5})$ is a significant win. In optimization, reducing the exponent of the error tolerance $\epsilon$ can drastically reduce the time required to reach high-precision solutions. The paper also introduces a novel notion of "approximate $\epsilon$-stationary solutions" to rigorously measure convergence in these non-smooth landscapes.

Key Results

The authors evaluated their methods across three distinct task types:

  • GDRO (Robustness): On datasets like Camelyon17 and CelebA, SONEX consistently achieved lower training loss and higher test accuracy than the previous state-of-the-art (SONX).
  • AUC Maximization with Fairness: On Adult and COMPAS datasets, ALEXR2 achieved higher AUC values while maintaining better constraint satisfaction (fairness) compared to baseline penalty methods.
  • Efficiency: Momentum-based updates (especially Adam-type) were significantly more effective than standard SGD for training deep architectures like DenseNet and ResNet. For example, on the Amazon dataset, the Adam-type update reached a final loss of ~0.56, while standard momentum stuck at ~0.96.

Conclusion

This work provides a robust theoretical and practical framework for non-smooth nested optimization. While the single-loop SONEX method still has some batch size dependencies, the overall improvement in complexity and the integration of Adam-type updates represent a major step forward. Future work may focus on developing single-loop methods that match the $O(\epsilon^{-5})$ complexity even for non-smooth inner functions.

Summary updated

BibTeX
@inproceedings{chen2025stochastic,
  author = {Xingyu Chen and Bokun Wang and Min Yang and Quanqi Hu and Qihang Lin and Tianbao Yang},
  title = {{Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=kSgZiAAwDU},
}
Figure