7
$\begingroup$

In connection to the question "Who invented the gradient?", I want to know who invented the gradient descent algorithm?

$\endgroup$
7
$\begingroup$

The "gradient descent" algorithm was invented before the gradient. It is described in equivalent form by Cauchy in a 3-page paper in Comptes Rendus, Méthode générale pour la résolution des systèmes d'équations simultanées (1847). Here is an English translation. A good secondary source is Cauchy and the Gradient Method by Lemaréchal, who comments:

"Cauchy is motivated by astronomic calculations which, as everybody knows, are normally very voluminous. To compute the orbit of a heavenly body, he wants to solve "not the differential equations, but the [algebraic] equations rep- resenting the motion of this body, taking as unknowns the elements of the orbit themselves". To solve a system of equations in those days, "one ordinarily starts by reducing them to a single one by successive eliminations, to eventually solve for good the resulting equation, if possible. But it is important to observe that 1◦ in many cases, the elimination cannot be performed in any way; 2◦ the resulting equation is usually very complicated, even though the given equations are rather simple". Something else is wanted."

Instead of the gradient vector Cauchy simply works with the partial derivatives $X=f'_x,Y=f'_y,Z=f'_z,...$. He takes small $\theta$, sets up the equation $$\Theta=f(X-\theta x, Y-\theta y, Z-\theta z,...),$$ and, in one of the variants, recommends finding $\theta$ from $\Theta'_\theta=0$.

[...] One iteration of the gradient method is thus stated, with two variants: (2) (Armijo-type line-search) or (3) (steepest descent)... Convergence is just sloppily mentioned... Cauchy does not seem to believe that the method always finds a solution; yet, he also seems to hope it: see the excerpt of foot note 4. Anyway a simple picture reveals that the least-squares function in (4) may display positive local minima, playing the role of “parasitic” solutions. On the other hand, he seems convinced that, being decreasing, the sequence of u-values has to converge to a (local) minimum, or at least a stationary point. Thus, the above excerpt is fairly interesting, coming from a mathematician among the most rigorous of his century. Admittedly, Cauchy has not given deep thought to the problem: "I’ll restrict myself here to outlining the principles underlying [my method], with the intention to come again over the same subject, in a paper to follow". However, the “paper to follow” does not seem to exist."

See also related post Who invented stochastic gradient descent? on Cross Validated.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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