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.
- 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.
- 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.
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.
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