0
$\begingroup$

Most (stochastic) "gradient descent" type algorithms (such as Nesterov-accelerated gradient-descent or ADAM) seem to be well-defined only for functions which are either:

  • lower semi-continuous + convex (these sub-gradient methods),
  • non-smooth but locally-lipschitz (Clarke's generalized methods),

The first of these scenarios may admit discontinuities but not the later. So I'm left wondering:

Are there "generaled (stochastic?) gradient-descent type algorithms which can optimize non-smooth and non-convex functions?

Improve this question
$\endgroup$
1
  • $\begingroup$ Have a look at our paper here: proceedings.mlr.press/v119/zhang20p.html -- it discusses a rich enough subclass of non-smooth, nonconvex optimization problems, and shows for instance that even a "stationary point" cannot be guaranteed in finite time; but then it introduces a relaxed notion of stationarity for which non-asymptotic rates of convergence for randomized gradient-descent and stochastic procedures can be guaranteed --- the classes of problems covered here are more general than the "composite objectives" covered in Dirk's answer below. $\endgroup$
    – Suvrit
    Commented Jan 29, 2021 at 18:17

1 Answer 1

Reset to default
1
$\begingroup$

Several splitting methods fit the bill: Often the non-convexity and the non-smoothness come from different parts of the objective and one can split the objective like $ f(x)=g(x) +h(x)$ with a convex but non-smooth $g$ and a non-convex but smooth $h$. In this case one can, for example, try a proximal gradient method which iterates $$ x^{k+1 } = prox_{tg}(x^k - t h'(x^k)) $$ and $prox_{tg}(x) = argmin_y tg(y) + \|y-x\|^2/2$ is the proximal mapping and $t$ is the stepsize. Under some assumptions this can be a descent method and can be shown to converge to critical points. Actually, the proximal mapping is sometimes even defined (and easily computed) for non-convex functions and the method may still be used. There is a lot more to try (going stochastic, split into more terms, try momentum or Nesterov acceleration...). Also, one there are methods that use proximal mappings of all splitted terms (if they are easy to compute) and one could also try to use subgradients instead of gradients of $h$ in case it is not smooth but the proximal mapping is not an option.

Improve this answer
$\endgroup$
4
  • $\begingroup$ The prox of a discontinuous function may still exist and even be helpful. Prominent example is the functional which gives the number of nonzeros (often called "0-norm", although it is not a norm) $\endgroup$
    – Dirk
    Commented Jan 29, 2021 at 20:29
  • $\begingroup$ case in point: arxiv.org/abs/2007.11426 $\endgroup$
    – Christian Clason
    Commented Jan 29, 2021 at 22:55
  • $\begingroup$ I guess there we need $g$ to be smooth; however, if in cases where $g=0$ then $f=h$ (so we cant split the objective function into a smooth and a non-smooth part) then does there exist anything? I mean the linked paper does not apply in this case.. $\endgroup$
    – ABIM
    Commented Jan 30, 2021 at 13:59
  • 1
    $\begingroup$ g does not need to be smooth - the prox need to exist and be simple to compute. Non-smoothness is not a problem for g. $\endgroup$
    – Dirk
    Commented Jan 30, 2021 at 16:22

You must log in to answer this question.