Multi-Nonsmooth-Nonconvex-Objective Optimization

We study stochastic multi-objective optimization when each objective may be non-smooth and non-convex. We introduce the notion of $(\delta ,ϵ)$-Pareto Goldstein stationary points (PGSP) to characterize the convergence of solving multi objective optimization. The $(\delta ,ϵ)$ generalizes the definition of $(\delta ,ϵ)$-Goldstein stationary point for single objective non-smooth non-convex optimization and the $ϵ$-Pareto stationary point for solving multi objective optimization with smooth objectives. We propose the multi-gradient-free method (MGFM), which finds $(\delta ,ϵ)$-PGSP with $\tilde{\mathcal{O}}(m^2{d}^{3/2}{\delta }^{-1}{ϵ}^{-4})$ oracle complexity to the stochastic function values, where $m$ is the number of objectives and $d$ is the problem dimension. We further propose MGFM+, a faster multi-gradient-free method based on variance reduction, which improves the complexity to $\tilde{\mathcal{O}}(m^2{d}^{3/2}{\delta }^{-1}{ϵ}^{-3})$. These provide the first non-asymptotic analysis for multi-nonsmooth-nonconvex-objective optimization. abstract