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

Xingyu Chen; Bokun Wang; Ming Yang; Quanqi Hu; Qihang Lin; Tianbao Yang

doi:10.48550/arxiv.2506.02504

Back

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

Preprint

Open access

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

Xingyu Chen, Bokun Wang, Ming Yang, Quanqi Hu, Qihang Lin and Tianbao Yang

ArXiV.org

Cornell University

06/03/2025

DOI: 10.48550/arxiv.2506.02504

Files and links (1)

url

https://doi.org/10.48550/arxiv.2506.02504View

Preprint (Author's original)This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

Abstract

Finite-sum Coupled Compositional Optimization (FCCO), characterized by its coupled compositional objective structure, emerges as an important optimization paradigm for addressing a wide range of machine learning problems. In this paper, we focus on a challenging class of non-convex non-smooth FCCO, where the outer functions are non-smooth weakly convex or convex and the inner functions are smooth or weakly convex. Existing state-of-the-art result face two key limitations: (1) a high iteration complexity of under the assumption that the stochastic inner functions are Lipschitz continuous in expectation; (2) reliance on vanilla SGD-type updates, which are not suitable for deep learning applications. Our main contributions are two fold: (i) We propose stochastic momentum methods tailored for non-smooth FCCO that come with provable convergence guarantees; (ii) We establish a new state-of-the-art iteration complexity of . Moreover, we apply our algorithms to multiple inequality constrained non-convex optimization problems involving smooth or weakly convex functional inequality constraints. By optimizing a smoothed hinge penalty based formulation, we achieve a new state-of-the-art complexity of for finding an (nearly) -level KKT solution. Experiments on three tasks demonstrate the effectiveness of the proposed algorithms.

Computer Science - Learning

Details

Title: Subtitle: Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization
Creators: Xingyu Chen - Texas A&M University
Bokun Wang - Texas A&M University
Ming Yang - Texas A&M University
Quanqi Hu - Texas A&M University
Qihang Lin - University of Iowa
Tianbao Yang - Texas A&M University
Resource Type: Preprint
Publication Details: ArXiV.org
DOI: 10.48550/arxiv.2506.02504
ISSN: 2331-8422
Publisher: Cornell University; Ithaca, New York
Language: English
Date posted: 06/03/2025
Academic Unit: Computer Science; Business Analytics
Record Identifier: 9984827334202771

Metrics

8 Record Views