1
$\begingroup$

The typical coordinate descent (CD) algorithm uses the gradient along each coordinate, or along some hyperplane obtained from a group of coordinates, to find the minimizer along that direction. My question is, does requiring the gradient imply that CD cannot be applied to non-continuous and non-smooth functions? I mean, in the general formulation shown below, there is no limitation on how to obtain the minimizer along a direction. It can, for example, be using a clever search method:

enter image description here

By the way, I'm aware of some special cases where non-smoothness is separable. I'm interested to see if there is any extension to coordinate descent that can handle more general functions, albeit less efficiently and without convergence proofs.

Improve this question
$\endgroup$
10
  • $\begingroup$ Exactly how would you apply any form of "coordinate descent" when a gradient is unavailable? $\endgroup$
    – whuber ♦
    Commented Mar 7, 2016 at 0:47
  • $\begingroup$ @whuber: Well, a crude example would be to test some values for y in the above equation and choose the one that minimizes f. In some applications, there might actually be a finite set of possible values for y to check. $\endgroup$
    – sadeghmir
    Commented Mar 7, 2016 at 1:42
  • $\begingroup$ You haven't described any kind of "coordinate descent" algorithm: that's just a brute-force search. $\endgroup$
    – whuber ♦
    Commented Mar 7, 2016 at 15:22
  • $\begingroup$ @whuber: It may not be coordinate "descent", but it is search along coordinates, and I want it to use an algorithm similar to CD. It would be more like a heuristic than full brute-force, because the solution space we check depends on the set of possible values we check for y. $\endgroup$
    – sadeghmir
    Commented Mar 7, 2016 at 17:10
  • $\begingroup$ When the objective function is discontinuous, what heuristic could possibly work? $\endgroup$
    – whuber ♦
    Commented Mar 7, 2016 at 17:10

2 Answers 2

Reset to default
2
$\begingroup$

To rephrase your question, you are basically asking if you can optimize a black-box function in some way (without any guarantees on what that function is). There is lots of literature out there about hyperparameter optimization, which essentially tries to create some kind of function or prior on a set of input parameters that optimizes some black box function.

Here is an overview paper from NIPS a few years back that addresses some general approaches: http://papers.nips.cc/paper/4443-algorithms-for-hyper-parameter-optimization.pdf

An example of a software package that can do this kind of optimization is HPOlib, which combines a few of the techniques mentioned in the paper above from various other sources.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the response, but what I meant was an extension of coordinate descent that can be applied to a function with slightly higher relaxations. For example one that is convex but has non-continuity. $\endgroup$
    – sadeghmir
    Commented Mar 7, 2016 at 4:26
  • 1
    $\begingroup$ A more philosophical question perhaps is why use coordinate descent when something like bayesopt is available for generalized black-box functions? $\endgroup$
    – mprat
    Commented Mar 7, 2016 at 4:28
1
$\begingroup$

If the function is convex but non-smooth, you can still use CD to get to a global optimum. An example is the CD algorithm for lasso.

If your function is discreete, you don't have any guarantee that e.g. minimizing along each dimension you get to a global optimum.

Improve this answer
$\endgroup$
4
  • $\begingroup$ True, we won't have a guarantee, but is there an algorithm/heuristic out there that let's us approximate the optimal for such cases using the basic idea of CD? $\endgroup$
    – sadeghmir
    Commented Mar 7, 2016 at 17:15
  • 1
    $\begingroup$ Using CD in these cases you will probably get stuck in local optima $\endgroup$
    – Net_Raider
    Commented Mar 7, 2016 at 17:17
  • $\begingroup$ Yes, otherwise you would have a black-box optimization algorithm in your hands. However, there are search-based algorithms (like Genetic Algorithm) out there that can produce good results, but in most cases without guarantees. $\endgroup$
    – sadeghmir
    Commented Mar 7, 2016 at 17:23
  • $\begingroup$ Maybe you can get something that works mixing CD with simulated annealing. But again, if your objective is convex but non-smooth you can still get to the global best only with CD. If the objective is not even continuous, you can still get something, but I'm afraid it will be problem-dependent. $\endgroup$
    – Net_Raider
    Commented Mar 7, 2016 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.