Optimization on a Finer Scale: Bounded Local Subgradient Variation
  Perspective
Jelena Diakonikolas Cristóbal Guzmán
We initiate the study of nonsmooth optimization problems under bounded local
subgradient variation, which postulates bounded difference between
(sub)gradients in small local regions around points, in either average or
maximum sense. The resulting class of objective functions encapsulates the
classes of objective functions traditionally studied in optimization, which are
defined based on either Lipschitz continuity of the objective or
H\"{o}lder/Lipschitz continuity of its gradient. Further, the defined class
contains functions that are neither Lipschitz continuous nor have a H\"{o}lder
continuous gradient. When restricted to the traditional classes of optimization
problems, the parameters defining the studied classes lead to more fine-grained
complexity bounds, recovering traditional oracle complexity bounds in the worst
case but generally leading to lower oracle complexity for functions that are
not ``worst case.'' Some highlights of our results are that: (i) it is possible
to obtain complexity results for both convex and nonconvex problems with the
(local or global) Lipschitz constant being replaced by a constant of local
subgradient variation and (ii) mean width of the subdifferential set around the
optima plays a role in the complexity of nonsmooth optimization, particularly
in parallel settings. A consequence of (ii) is that for any error parameter
$\epsilon > 0$, parallel oracle complexity of nonsmooth Lipschitz convex
optimization is lower than its sequential oracle complexity by a factor
$\tilde{\Omega}\big(\frac{1}{\epsilon}\big)$ whenever the objective function is
piecewise linear with polynomially many pieces in the input size. This is
particularly surprising as existing parallel complexity lower bounds are based
on such classes of functions. The seeming contradiction is resolved by
considering the region in which the algorithm is allowed to query the
objective.