14
$\begingroup$

Historically, iterative methods for solving relatively simple-structured systems $Ax=b$ with $A$ being a $4\times 4$ matrix or to find the eigenvalues of that matrix assuming in both problems that $A$ is non-singular were not quite popular and were not needed in pre-1950s as stationary methods or perhaps classical iterative algorithms such as Jacobi, Gauss-Seidel would handle the task easily.

Then in the $1950$s the rapid development of computational tools made it possible to deal with large and sparse matrix system (possibly a $100\times 100$ at that time in engineering applications). This is all thanks to the development of Krylov Subspace tools which at that time was considered to be "high-tech". This is seen from various celebrated algorithms such as Arnoldi Iteration (Arnoldi-Lanczos 1950) and Conjugate Gradient (Stiefel,1952). During the 1970s and 1980s when we had tons and tons of transistors inside computers this made it possible for us to witness the birth of GMRES and BiCGSTAB which are known to handle relatively large and sparse systems.

In fact, it was during that period that BLAS and LAPACK were developed and ever since have continued to upgrade various Krylov algorithms and achieve a high level of robustness.

In machine learning, many problems such as regression, neural networks, and even recommender systems can one way or another be formulated as an optimization problem which in turn can be expressed as a linear system $Fx=z$. The apparent default choice for solving such problems is the "Gradient Descent Algorithm" (and its derivatives) a popular optimizer algorithm that seems to be used literally everywhere in machine learning problems (movie recommender system, linear regression,...) even a famous variant is the ADAM Optimizer which in many deep learning libraries is set as the default optimizer.

Given that numerical linear algebra libraries have been for the past 40 years enhancing Krylov algorithms, why haven't they made an impact in today's world of machine learning as they did in engineering communities?

Let's say linear regression is the underlying machine learning problem, why is the gradient descent algorithm preferred over using BiCGSTAB with some restart when rewriting the regression problem as $Fx=z$ where $F$ could be sparse and $10000\times 10000$?

I believe one answer (though it may be biased) is that the majority of the machine learning community is not paying attention to the computational mechanism of the algorithm. For instance, you can go ahead and apply ADAM optimizer to solve a simple regression problem (overkill) or a complicated large regression problem and may end up witnessing your algorithm diverging without properly understanding why. I found a meme from medium.com that jokingly describes this:

enter image description here

Source: https://medium.com/analytics-vidhya/mechanism-of-gradient-descent-optimization-algorithms-7baed9c9c35e

Update 1: I would like to thank davidhigh for the detailed answer. I would like to add that my experience with Krylov methods were mainly focused on modelling dynamical system. Tim Davis has a very interesting collection of sparse matrices with detailed information on where the problem arises from (in particular engineering applications) Krylov methods are highly applicable there.

Update 2: Neil Lindquist made an important correction regarding BLAS and LAPACK not having Krylov solvers.

Final Remark: I welcome any additional answer especially if some users have experience with using Krylov methods in ML applications.

$\endgroup$
8
  • 1
    $\begingroup$ Popularity depends on the method being easily understood by practitioners. Even ADAM is a black box for most, so they depend on authority. There's a lot of work that uses conjugate gradient algorithms, e.g., arxiv-sanity-lite.com/… $\endgroup$ Jun 24 at 21:36
  • 1
    $\begingroup$ Essentially the same question was asked and answered on AI.SE: Why is gradient descent used over the conjugate gradient method? $\endgroup$
    – nanoman
    Jun 25 at 6:37
  • 3
    $\begingroup$ Just a correction: neither BLAS nor LAPACK provide krylov solvers. $\endgroup$ Jun 25 at 14:21
  • 1
    $\begingroup$ Thank you for your recommendation. I have included the source accordingly. medium.com has plenty of interesting articles on optimization algorithms. @QuoraFeans $\endgroup$
    – SPARSE
    Jun 27 at 14:31
  • 1
    $\begingroup$ "In machine learning, many problems such as regression, neural networks, and even recommender systems can one way or another be formulated as an optimization problem which in turn can be expressed as a linear system $Fx = z$." This statement is incorrect. Yes a least squares problem can be reduced to solving the normal equations, but that is a special fact about least squares problems. Training a neural network (or most other machine learning models) can't be reduced to solving a linear system of equations. $\endgroup$
    – littleO
    Jun 27 at 20:09

3 Answers 3

17
$\begingroup$

On a basic level, I don't buy the argument that you have to "solve a linear system for many machine learning algorithms". Much more, you usually have to optimize a non-linear equation which is obtained from a given functional in order to derive the parameters of the applied model.

Thus, the basic problem is, that you have a functional depending on $N$ parameters as well as on the training data,

$$ \min_\alpha L(\alpha_1,\ldots, \alpha_N; \text{data}) $$

How do you solve these kind of problems? In a not all too satisfying way: you pick a start configuration for your parameters, and then go "downhill". That's basically gradient descent, which ADAM is a sophisticated variant of.

As you say, you can formulate this problem as a linear equation. But the whole benefit of this linear system is to derive an "optimal way downhill". And, remember, as the functional is non-linear, this optimal direction holds only for the current parameter configuration (you only go along the current tangent space of the manifold). So you'd have to solve a linear system in each step.

Now, it turned out that the benefit in using the optimal direction at each step is not worth the overhead of solving a linear system. So people still simply go downhill. Stochastic gradient descent and ADAM are more sophisticated approaches based on the same idea.

If you have particular applications in mind where you would expect a linear system to be advantageous, please feel free to add it to the question pr in the comments.

$\endgroup$
9
  • 3
    $\begingroup$ "So you'd have to solve a linear system in each step" -- no, though OP has indeed somewhat confused general optimization with linear solving, there are nonlinear CG-type optimization methods that estimate an "optimal way downhill" with only a small amount of extra work. $\endgroup$
    – nanoman
    Jun 25 at 6:44
  • 3
    $\begingroup$ My answer might sound too distinctive. It's not gradient descent vs. linear solvers -- and gradient descent can be regarded as a linear solver, too, and vice versa. The statement is rather that you have a range from greedy, low-complexity methods to determine the steps over to more complex approaches involving e.g. the solution of linear systems. For the stochastic high-dimensional problems ML is facing, using "some way downhill" (instead of an optimized) currently seems to be advantageous. Which doesn't mean the other end can be applied fruitfully as well to certain problems. No free lunch. $\endgroup$
    – davidhigh
    Jun 25 at 9:49
  • 2
    $\begingroup$ @davidhigh On top of that I'd like to add that finding the "fastest way downhill" does not necessarily help you find a good solution. It could very well be the fastest way to a bad local minimum. I think it's going to take us many many more years before forming a good understanding of what these problems' loss landscapes look like and behave. $\endgroup$
    – orlp
    Jun 26 at 21:42
  • 1
    $\begingroup$ The correct distinction would have been "gradient descent" vs "Newton-like method" for the optimization problem. The latter requires a linear solve, which one could do with Krylov-space methods. But, as the answer here correctly points out, Newton turns out to be more expensive than gradient descent. $\endgroup$ Jun 27 at 3:33
  • 1
    $\begingroup$ I would say the this is another -- good --dimension, and maybe not the definitely right one -- also due to the broadness of the topic. You can also include a Newton-step in your gradient descent to evaluate an optimal step-size. Moreover, you can get around both and still obtain a complex method, think of evolutionary algorithms, Monte Carlo, simulated annealing which could be applied as well. Nevertheless, thanks for the addition! My answer is definitely bot the definite answer -- if I find the time, I'll summarize all the contributions here. $\endgroup$
    – davidhigh
    Jun 27 at 17:04
7
$\begingroup$

They aren't popular because they don't work.

Nicol N. Schraudolph spent a few years on Krylov-like methods for Machine Learning. I first learned of his work at 2004 Machine Learning Summer School in Canberra.

Looking at his later work (A Stochastic Quasi-Newton Method for Online Convex Optimization) you can find the following explanation:

enter image description here

More generally, thousands of people have tried to improve on SGD+momentum in Machine Learning setting, without success. Adam is slightly better on many tasks, but slightly worse on others, like Imagenet training.

Personally I've spent significant time working on ways of improving SGD for ML (contributing to tools like this), and came to believe that for optimized architectures like Resnet-50, optimally preconditioned direction would only give a modest improvement, perhaps $\approx$ 5x reduction in terms of the number of steps needed. This means if your advanced method does more than "5 SGD steps" worth of work per step, it'll lose to SGD. Additionally there's a storage constraint which means you can't store more than a couple gradients worth of statistics throughout training. Models are typically scaled up until gradient computation exceeds GPU memory constraint.

General reasons why it's hard to improve on SGD in ML. Typical problems are:

  • overparameterized and very high-dimensional. SGD in this setting is already pretty good, converging at an exponential rate -- https://arxiv.org/abs/1811.02564

  • non-stationary. Local curvature statistics get stale after a few of steps.

  • not optimized to convergence. Many "advanced methods" are theoretically superior to SGD only in the "tail regime", but we don't get there. For instance, in BigScience model training, the loss went down from $\approx 10$ to 0.13 in the last 12 months of training. So we care about the time it takes to decrease loss by a factor of 100. Meanwhile second-order methods like Newton method starts to pull away in the tail regime, going from $10^{-5}$ loss to $10^{-10}$.

  • tailor made for SGD. If SGD fails to achieve good results, corresponding network architecture won't see the light of day. For instance, autoencoder with a bottleneck layer is near impossible to train with SGD, but easy with a factored Gauss-Newton method. Since advanced optimizers aren't accessible in ML frameworks, such architecture wouldn't get a shot at evaluation.

An example of method which satisfies these constraints is PSGD which:

  1. stores preconditioner $P$ in a factored form, in extreme case, parameterizing it by a single number recovers SGD with "automatic step size"
  2. updates $P$ in an online fashion by taking cheap SGD steps on $P$ to keep $P^{-1}$ close to Hessian $H$, using Hessian-vector products.

(I had no hand in PSGD, other than having evaluated it and found it to be the most promising out of all second-order methods I've used. I think it didn't get attention like KFAC or Shampoo because it didn't come from a famous ML lab)

$\endgroup$
1
$\begingroup$

Posts 3 in the following series on "regret minimization" talks about gradient descent, and the later posts come back to that topic from time to time.

One conclusion of those posts is that gradient descent can be seen as a regret minimization algorithm in the “Follow the Regularized Leader” framework.

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