# Gradient descent oscillating a lot. Have I chosen my step direction incorrectly?

I'm trying to run a basic gradient descent algorithm with a absolute loss function. I can get it to converge to a good solution by it requires a much lower step size and more iterations than had I used square loss. Is this normal? Should I expect absolute loss to take a longer time to come to a good solution or potentially oscillate around a solution more than say squared loss?

-

When you say 'a absolute loss function', do you mean you're using least absolute deviations (LAD) instead of the more usual ordinary least squares (OLS)? As that wikipedia article says, although LAD is more robust to outliers than OLS it can be unstable and even have multiple solutions, so it doesn't seem that surprising if it's harder to find the minimum of the objective function even when there's only one.

If you're trying this because you're after some sort of robust regression, I think there are several more attractive alternatives than LAD.

-

This is possibly a consequence of a known deficiency of steepest descent algorithms in general. Using a conjugate gradient algorithm may improve convergence.

-

I think you should definitely try other methods there is for example Lasso:

In some contexts a regularized version of the least squares solution may be preferable. The LASSO (least absolute shrinkage and selection operator) algorithm, for example, finds a least-squares solution with the constraint that | β | 1, the L1-norm of the parameter vector, is no greater than a given value. Equivalently, it may solve an unconstrained minimization of the least-squares penalty with α | β | 1 added, where α is a constant (this is the Lagrangian form of the constrained problem.) This problem may be solved using quadratic programming or more general convex optimization methods, as well as by specific algorithms such as the least angle regression algorithm. The L1-regularized formulation is useful in some contexts due to its tendency to prefer solutions with fewer nonzero parameter values, effectively reducing the number of variables upon which the given solution is dependent. For this reason, the LASSO and its variants are fundamental to the field of compressed sensing.

NEvertheless though the idea of least absolute deviations regression is just as straightforward as that of least squares regression, the least absolute deviations line is not as simple to compute efficiently. Unlike least squares regression, least absolute deviations regression does not have an analytical solving method. Therefore, an iterative approach is required. The following is an enumeration of some least absolute deviations solving methods.

Simplex-based methods (such as the Barrodale-Roberts algorithm)

Iteratively re-weighted least squares

Wesolowsky’s direct descent method

Li-Arce’s maximum likelihood approach

Check all combinations of point-to-point lines for minimum sum of errors Simplex-based methods are the “preferred” way to solve the least absolute deviations problem. A Simplex method is a method for solving a problem in linear programming. The most popular algorithm is the Barrodale-Roberts modified Simplex algorithm. The algorithms for IRLS, Wesolowsky's Method, and Li's Method can be found in Appendix A of this document,[7] among other methods. Checking all combinations of lines traversing any two (x,y) data points is another method of finding the least absolute deviations line. Since it is known that at least one least absolute deviations line traverses at least two data points, this method will find a line by comparing the SAE of each line, and choosing the line with the smallest SAE. In addition, if multiple lines have the same, smallest SAE, then the lines outline the region of multiple solutions. Though simple, this final method is inefficient for large sets of data.

-
At risk of being repetitive, could you pls give a proper citation to Wikipedia when you copy/paste entire paragraphs on Lasso (en.wikipedia.org/wiki/Least_squares)? –  chl Nov 19 '10 at 7:54
You are right I will do that next. –  mariana soffer Jan 21 '11 at 19:33