Randomized Coordinate Subgradient Method for Nonsmooth Optimization
Nonsmooth optimization finds wide applications in many engineering fields. In
this work, we propose to utilize the {Randomized Coordinate Subgradient Method}
(RCS) for solving both nonsmooth convex and nonsmooth nonconvex (nonsmooth
weakly convex) optimization problems. At each iteration, RCS randomly selects
one block coordinate rather than all the coordinates to update. Motivated by
practical applications, we consider the {linearly bounded subgradients
assumption} for the objective function, which is much more general than the
Lipschitz continuity assumption. Under such a general assumption, we conduct
thorough convergence analysis for RCS in both convex and nonconvex cases and
establish both expected convergence rate and almost sure asymptotic convergence
results. In order to derive these convergence results, we establish a
convergence lemma and the relationship between the global metric subregularity
properties of a weakly convex function and its Moreau envelope, which are
fundamental and of independent interests. Finally, we conduct several
experiments to show the possible superiority of RCS over the subgradient
method.