TrenDescent

Work in Progress

This page is a short note, not a finished article. It records the idea behind TrenDescent and the few properties I can prove in a line or two. It reports no benchmarks and makes no performance claims.

The idea

Gradient descent moves against the gradient, so every step depends on both the direction and the size of the slope. Sign-based methods such as Rprop and signSGD keep only the direction: each coordinate moves by a step of its own, against the sign of its partial derivative. TrenDescent asks the same question without the derivative. For each coordinate i at the current point x, it compares the loss L one small step to each side of x along that coordinate:

• If the loss eventually drops on the right side, the step for coordinate i is +1.
• If it eventually drops on the left side, the step is −1.
• If it drops on both sides, either direction descends, and the step takes one of them.
• If it drops on neither side, coordinate i stays where it is.

These comparisons are the one-sided detachments of L along each coordinate, the limits of sgn[L(x ± h·e_i) − L(x)] as h shrinks to 0. Each coordinate then moves by a step size η in the chosen direction. In code the limit is replaced by a small probe h.

What a trend step provably does

It agrees with sign descent wherever the slope is not zero. If the partial derivative ∂L/∂x_i exists and is nonzero, the one-sided difference quotients eventually have its sign, and so do the differences themselves. The trend step for that coordinate is then −sgn(∂L/∂x_i), the step that sign descent takes. The two methods differ only where the partial derivative is zero or does not exist.

It does not care how the loss is scaled. A trend step uses only comparisons between values of L. If φ is any strictly increasing function, then φ(L(y)) > φ(L(x)) exactly when L(y) > L(x), so descent on φ∘L takes exactly the same steps as descent on L. Gradient descent has no such property: the gradient of φ∘L is φ′(L) times the gradient of L, and where φ′ is 0 the direction is lost. For example, φ(y) = y³ turns a loss of the form L(x) = x near a zero of L into one whose derivative there is 0.

It still moves at corners and at flat points. At a corner such as |x| at the origin the derivative does not exist, but the one-sided comparisons do. If the loss rises on both sides of a coordinate, the trend step is 0, and this happens exactly at a strict local minimum along that coordinate, with no smoothness assumed. At a point where the loss is flat to every order, such as e^(−1/x²) at the origin, every derivative is 0, yet the comparisons still see that the values on both sides are larger.

Where it needs care

A fixed step size cannot settle at a corner. Take L(t) = |t| and the update t ↦ t − η·sgn(t). If 0 < |t| < η/2 at some step, the next point has |t| = η − |t| > η/2. So of any two consecutive iterates, at least one stays at distance η/2 or more from the minimum, and the iterates keep bouncing around it, unless an iterate lands exactly on 0. The same is true for any method whose step has a fixed length, including sign descent. The remedy is to shrink the step when the trend flips, which is what Rprop does with its per-coordinate step sizes.

A method that converges stops where its search direction vanishes. A step with the right sign but the wrong length has the same zeros as the true descent direction, so it changes how fast the method gets there and not where it stops. A direction whose zeros differ from the true descent direction’s stops at the wrong place, and a positive step size or a positive-definite preconditioner cannot fix that. A trend step keeps only the direction, so the direction is the one thing it has to get right, and the one-sided comparisons are a way of getting it right where the derivative is unavailable.

Next

The open questions are practical ones: how to choose the probe h, how to combine the trend step with adaptive step sizes, and how it compares with sign descent and Rprop on real problems. I will update this page when there are results to report. The operator itself is developed on the Semi-discrete Calculus page and in arXiv:1012.5751.