2
$\begingroup$

I want to have a better understanding of the weight-optimization process.

I understand the optimizer(e.g., gradient descent) looks for the direction in which to move the parameters to minimize the loss function. Than it makes a move in that direction, the size of this move is determined by the learning rate.

I have an naive question. Why don't we just look for the stationary points instead of an iterative process?

$\endgroup$
4
  • 3
    $\begingroup$ When the dimension is even modestly large, searching for a stationary point a la grid search would be incredibly expensive computationally speaking. $\endgroup$ Oct 9, 2020 at 12:19
  • 3
    $\begingroup$ How would you propose to find the stationary points of an arbitrary function without an iterative process? $\endgroup$
    – Sycorax
    Oct 9, 2020 at 12:35
  • $\begingroup$ Check where the derivative is 0? I am not sure that works multi-dimensional space? $\endgroup$
    – Borut Flis
    Oct 9, 2020 at 13:46
  • 1
    $\begingroup$ Sure, functions in $\mathbb{R}^n$ have gradients. And you certainly can take the gradient and set it equal to zero. But the next step is to crank through the algebra. For some classes of functions, this is very simple. For other classes, this is harder, in the sense that the expression is grotesquely ornate, but still feasible. But we can actually show that it's impossible for still other classes of functions. $\endgroup$
    – Sycorax
    Oct 9, 2020 at 14:31

1 Answer 1

3
$\begingroup$

Root-finding can be framed as an optimization problem because we seek to find $x$ such that $f(x)=0$; if we consider that for some polynomial function $f$ we are seeking a stationary point $f^\prime(x)=0$, then this is just root-finding for $f^\prime$.

Let's restrict consideration to finding the roots of polynomials in one variable. Polynomials are easy, right? The differentiation is nice and simple, and we know how many roots a polynomial has just by looking at its degree. And it's only an optimization in one variable, instead of many variables, so that's also very simple. So we might suppose that this this optimization should be straightforward.

In one dimension, the quadratic equation gives us the roots of a parabola, so we don't need any iterative methods there. There are also (more complex) root-finding formulae for cubic and quartic functions.

However, for quintic or higher-order polynomials, there is no expression using a finite number of algebraic operations (addition, subtraction, multiplication, division and root-extraction) which solves for the roots. This is the Abel-Ruffini theorem. (Also, note that a finite number of steps is even more relaxed than OP's requirement of a non-iterative method.)

So now let's return back to our starting point, which was finding stationary points of some general class of functions. All polynomials are more expansive than polynomials of degree less than 5, and in turn the union of polynomial and non-polynomial functions is more expansive than all polynomials. If we can't even find the roots of degree 5 polynomials using an algebraic expression, neither can we solve the more general problem of root finding for non-polynomial expressions.

$\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.