  We propose a primal-dual smoothing framework for finding a near-stationary
point of a class of non-smooth non-convex optimization problems with
max-structure. We analyze the primal and dual gradient complexities of the
framework via two approaches, i.e., the dual-then-primal and primal-the-dual
smoothing approaches. Our framework improves the best-known oracle complexities
of the existing method, even in the restricted problem setting. As an important
part of our framework, we propose a first-order method for solving a class of
(strongly) convex-concave saddle-point problems, which is based on a newly
developed non-Hilbertian inexact accelerated proximal gradient algorithm for
strongly convex composite minimization that enjoys duality-gap convergence
guarantees. Some variants and extensions of our framework are also discussed.
