1
$\begingroup$

I am trying to maximize a function $f(x)$ of a vector of reals $x=<x_1, x_2, ...x_n>$. In my practical application, I have no expression for $f$ whatsoever, all I can do is given a vector $x$, calculate $f(x)$ via a deterministic experiment.

So, instead of having to set a step size $\alpha$, calculate derivatives, etc, just see whether the move $x_1 ->x_1(1+\alpha)$ increases $f$, or $x_1 ->x_1(1-\alpha)$ increases it, transform $x_1$ accordingly, and then iterate over all coordinates in this manner until some termination criterium is met. Here $\alpha$ is a small positive number like $0.05$.

This is more practical for me than a standard gradient descent, because the value of $f$ is completely different order of magnitude of the $x_i$s, as well its derivative, so it will be harder to choose appropriate step size in a classical text book gradient descent manner.

Does this approach make sense? Does it have a specific name?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

This is called coordinate descent. It is slow, but it works if the function is smooth. You might also consider adaptive coordinate descent, which tries to find a transformation which uncorrelates the descent coordinates in order to speed up convergence (avoiding zig-zags).

A note on step size: Generally for gradient descent type algorithms, you want to choose an additive step size which decreases to zero as the optimization proceeds. That is, if moving in the positive direction, set $$x_1\gets x_1 + \mu(1-\epsilon)^n,$$ where $\mu$ is your initial step size, and $\epsilon \ll 1$ is the decay. As $n$ gets large, your algorithm will converge to a specific value of $x_1$. In your post you use a multiplicative step size, which can be dangerous especially if $\alpha$ is not adaptive. For example, suppose that your function is a Gaussian with mean 100, and you initialize $x = 1$ with $\alpha = 0.2$. Then your algorithm will dance around the optimum, like this: Comparison between multiplicative and additive Note the much better performance of an additive step with decay (in orange)

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks. But I thought in coordinate descent, you have a fixed grid of values you are iterating over for each coordinate, is that not right? Or you actually shifting the grid as you find better and better solutions? Basically, I am asking how do you come up with coordinate candidates. And also, is there a way to dynamically size alpha along the way. $\endgroup$
    – Baron Yugovich
    Jun 20, 2017 at 3:55
  • $\begingroup$ Coordinate descent I think simply refers to breaking the optimization problem into $n$ smaller, single-variable optimization problems. You don't need a grid, meaning the step size $\delta$ could be decreasing as time goes on. I think using a multiplicative step as in your post will give you some unstable behavior, especially if one of the optima has a large coordinate value. $\endgroup$
    – combo
    Jun 20, 2017 at 3:59
  • $\begingroup$ Thanks. Any practical references you can recommend? I am more interested in implementation than theory. $\endgroup$
    – Baron Yugovich
    Jun 20, 2017 at 4:01
  • $\begingroup$ I think google is your friend here - gradient descent approaches are the workhorse for most neural networks these days, and there are many people writing about them. Adding momentum to your updates might help too (distill also has been putting out some quality work, so check out the rest of their site). $\endgroup$
    – combo
    Jun 20, 2017 at 4:22
  • $\begingroup$ Distill? Can you please send me a specific link? $\endgroup$
    – Baron Yugovich
    Jun 20, 2017 at 4:24

Your Answer

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

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