  Coordinate-type subgradient methods for addressing nonsmooth optimization
problems are relatively underexplored due to the set-valued nature of the
subdifferential. In this work, our study focuses on nonsmooth composite
optimization problems, encompassing a wide class of convex and weakly convex
(nonconvex nonsmooth) problems. By utilizing the chain rule of the composite
structure properly, we introduce the Randomized Coordinate Subgradient method
(RCS) for tackling this problem class. To the best of our knowledge, this is
the first coordinate subgradient method for solving general nonsmooth composite
optimization problems. In theory, we consider the linearly bounded subgradients
assumption for the objective function, which is more general than the
traditional Lipschitz continuity assumption, to account for practical
scenarios. We then conduct convergence analysis for RCS in both convex and
weakly convex cases based on this generalized Lipschitz-type assumption.
Specifically, we establish the $\widetilde{\mathcal{O}}$$(1/\sqrt{k})$
convergence rate in expectation and the $\tilde o(1/\sqrt{k})$ almost sure
asymptotic convergence rate in terms of the suboptimality gap when $f$ is
convex. For the case when $f$ is weakly convex and its subdifferential
satisfies the global metric subregularity property, we derive the
$\mathcal{O}(\varepsilon^{-4})$ iteration complexity in expectation. We also
establish an asymptotic convergence result. To justify the global metric
subregularity property utilized in the analysis, we establish this error bound
condition for the concrete (real-valued) robust phase retrieval problem. We
also provide a convergence lemma and the relationship between the global metric
subregularity properties of a weakly convex function and its Moreau envelope.
Finally, we conduct several experiments to demonstrate the possible superiority
of RCS over the subgradient method.
