A stochastic smoothing framework for nonconvex-nonconcave min-sum-max problems with applications to Wasserstein distributionally robust optimization
This work addresses computational bottlenecks in distributionally robust optimization for machine learning practitioners, offering a more efficient and broadly applicable method compared to existing approaches with restrictive assumptions.
The paper tackles the computational challenges of min-sum-max optimization problems, which arise in applications like Wasserstein distributionally robust optimization, by introducing a stochastic smoothing framework based on the log-sum-exp function; the method guarantees convergence to stationary points with a worst-case iteration complexity of O(ε^{-3}) and outperforms or matches state-of-the-art methods in numerical experiments on problems like the newsvendor problem and adversarially robust deep learning.
Applications such as adversarially robust training and Wasserstein Distributionally Robust Optimization (WDRO) can be naturally formulated as min-sum-max optimization problems. While this formulation can be rewritten as an equivalent min-max problem, the summation of max terms introduces computational challenges, including increased complexity and memory demands, which must be addressed. These challenges are particularly evident in WDRO, where existing tractable algorithms often rely on restrictive assumptions on the objective function, limiting their applicability to state-of-the-art machine learning problems such as the training of deep neural networks. This study introduces a novel stochastic smoothing framework based on the \mbox{log-sum-exp} function, efficiently approximating the max operator in min-sum-max problems. By leveraging the Clarke regularity of the max operator, we develop an iterative smoothing algorithm that addresses these computational difficulties and guarantees almost surely convergence to a Clarke/directional stationary point. We further prove that the proposed algorithm finds an $ε$-scaled Clarke stationary point of the original problem, with a worst-case iteration complexity of $\widetilde{O}(ε^{-3})$. Our numerical experiments demonstrate that our approach outperforms or is competitive with state-of-the-art methods in solving the newsvendor problem, deep learning regression, and adversarially robust deep learning. The results highlight that our method yields more accurate and robust solutions in these challenging problem settings.