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,\epsilon)$-Pareto Goldstein stationary points (PGSP) to characterize the convergence of solving multi objective optimization. The $(\delta,\epsilon)$ generalizes the definition of $(\delta,\epsilon)$-Goldstein stationary point for single objective non-smooth non-convex optimization and the $\epsilon$-Pareto stationary point for solving multi objective optimization with smooth objectives. We propose the multi-gradient-free method (MGFM), which finds $(\delta,\epsilon)$-PGSP with $\tilde{\mathcal{O}}(m^2d^{3/2}\delta^{-1}\epsilon^{-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^2d^{3/2}\delta^{-1}\epsilon^{-3})$. These provide the first non-asymptotic analysis for multi-nonsmooth-nonconvex-objective optimization. \end{abstract}