Computer scientists discover limits of gradient descent (2021)

Brouwer’s fixed point theorem. The theorem says that for any continuous function, there is guaranteed to be one point that the function leaves unchanged — a fixed point, as it’s known. This is true in daily life. If you stir a glass of water, the theorem guarantees that there absolutely must be one particle of water that will end up in the same place it started from.

Wait. What if by stirring I shook the glass and at the end set it back down a foot away from its initial location. Is this author claiming that Brouwer’s theorem guarantees a particle floating somewhere where the glass used to be? Unchanged?

I can imagine an unlimited number of scenarios where I can guarantee the water particles are displaced.

This seems like a bad application of the theorem, right?

kadoban• 3 years ago

They left off some qualifiers. According to wikipedia, it's applicable to a continuous function mapping a nonempty compact convex set to itself. Which ends up making a lot more sense to me.

mjfisher• 3 years ago

So is it just a fancy way of saying "every transformation has an axis or origin"?

nerdponx6• 3 years ago

Isn't a container of water actually a good example? Maybe swirling gently (laminar flow) is a better mental image than shaking vigorously (possibly discontinuous).

GeneralMayhem• 3 years ago

It only applies when you're mapping a space onto itself (plus a couple other qualifications), so you have to put the glass back in the same place.

I think of it as a generalization of the intermediate value theorem - some things are going left, some things are going right, one thing must be sitting still in between.

plank• 3 years ago

And: it has to be ‘continuous’. E.g. in ‘real’ water, the molecule of H2O ‘colloquially’ known as ‘number 12345678998776165441’ which sat next to molecule known as ‘number 1’, still has to sit next to it. All be it in a different location. I think something like mayonaise would have been a better example, as water molecules that are ‘next’ to each other can in reality split up quite easily by itself. While something like mayonaise would not.

*off course, quantum mechanics and all that suggesting that it would be impossible to label the individual molecules.

dataflow2• 3 years ago

What's the conceptual difference between this and the hairy ball theorem?

T-A• 3 years ago

As James Bond would say,

https://en.wikipedia.org/wiki/Shaken,_not_stirred

seydor3• 3 years ago

You are not just stirring, then

BorisTheBrave• 3 years ago

A better example I've seen for the theorem is that if you take a paper map of a country, messily schrunch it up into a ball and drop it somewhere in the country, there will be at least one point on the map that is exactly above the corresponding real point in the country.

As others have said, it's meant for mappings of the space to itself. So stirring the water, but not moving the glass.

But anyway, the theorem works only for continiuous mappings. The moment they started mentioning "water particles", instead of some hypothetical fluid that is a continuous block, the theorem no longer applied. You could break it by mirroring the position of every particle. There's still a fixed point (the line of mirroring), but there's no obligation that there's a particle on that line.

chacham15• 3 years ago

This still doesnt make sense to me. Imagine a continuous line whose positions map to the real numbers between 0 and 1. If I "move" the line over 0.1 wrapping the end back to the beginning (i.e. x2 = (x1 + 0.1) % 1), there will be no points that are in the same position as they were in before.

EDIT: If you need a continuous function, wouldnt expanding the space to a line from -Inf to +Inf and then using x2 = x1 + 0.1 do the trick?

drc500free• 3 years ago

Another practical example is that you're guaranteed to have an annoying spot on your head where the hair sticks straight out and you can't brush it down.

That's actually the one that helped me visualize the theorem. If you look at your scalp from above, you can divide all the hairs into "points left" or "points right" and draw a boundary between them of hairs that point neither left or right. Then you can do the same thing with "points up" and "points down." Where the two kinds of boundaries cross, you have a hair that doesn't point up, down, left, or right - it points straight out of your scalp.

sva_• 3 years ago

I wonder how this really applies, since IEEE 754 floating points are not continuous.

rowanG077• 3 years ago

I'm misunderstanding the theorem. Take f(x) = x + 1. That is a continuous function. But there does not exist an x where f(x) ~ x holds. What am I missing?

arbitrarybits• 3 years ago

That's because there is also a precondition for the domain to be bounded, and since the real numbers are not bounded, the theorem does not apply here (or for any function R -> R).

vecter• 3 years ago

It must be a compact convex set. The entire reals is not compact.

ninepoints• 3 years ago

I do not understand this comment. In what world does "stirring" fluid in a cup imply any sort of dispacement of the cup itself?

sorokod• 3 years ago

That function is from a compact convex set to itself.

jjtheblunt2• 3 years ago

i remember the example of "you can't comb the hair on a coconut without a whorl".

hgsgm4• 3 years ago

That's a different fixed point theorem.

https://en.m.wikipedia.org/wiki/Brouwer_fixed-point_theorem

taeric• 3 years ago

The full theorem is a continuous mapping back on itself. So, only the water in the glass mapped back to the glass. Pour it out to another glass, and you no longer mapped back to the glass. Pour it back into original glass, and you are back to having a fixed point possible. And, obviously, only with respect to the mapping in the glass.

KolenCh• 3 years ago

The theorem assumes the function has identical domain and codomain. Eg f(x) = x^3 maps [0, 1] to itself.

So that's why they gave the glass stirring example, the domain here is the whole volume of water. So as long as it ends up in the same volume of water, the process of stirring is assumed to be continuous and therefore this theorem applies. Your example changes where it ends up (ie not back to the same domain) and so it cannot be applied.

stormfather• 3 years ago

If you stir a glass of water, the theorem guarantees that there absolutely must be one particle of water that will end up in the same place it started from.

Wait what? If you stir a glass long enough, any configuration of particles should be possible. For instance you can imagine "cutting" the water like a deck of cards.

gauddasa• 3 years ago

From problems that require recognition of patters, whether in images or sounds, a non-linear function represented through neural networks and trained through gradient descent just suffices to produce smoothly distributed fuzzy classification that just works.

This setup is not a good prior for anything that requires more precise solution.

adrian_mrd• 3 years ago

Good to note that the article was published on "August 17, 2021"

antegamisou3• 3 years ago

This site (QuantaMagazine) had really excellent quality content when it first launched,like the one at the OP, now it has become sort of IFLScience in terms of editorializing.

seydor3• 3 years ago

Their articles are often rehashes of press releases, but this one seems to be of the better ones

antegamisou3• 3 years ago

I should’ve clarified I was referring to the old (2021) article at the OP when I was talking about the high quality.

The recent ones haven’t remained in the same pathway unfortunately.

dchftcs• 3 years ago

This title is still a bit click baity because ultimately this problem has very little impact on any real world usage of stochastic gradient descent - and especially the more important ones, where getting infinitesimally close to any particular local minimum is specifically and totally not what people care about (and getting to a global minimum is something we've long known to give up on).

It is a theoretically interesting result about the PPAD complexity class itself. Not sure if it should be STOC best paper though, if it was nominated as best paper because of the weak link to machine learning I'd be a bit disappointed.

cubefox4• 3 years ago

Not to sound snarky, but is there any example where theoretical computer science has actually been useful? The results are often like "Here is a proof this will be slow if you scale it up enough" -- "Yeah we knew that for 20 years, it doesn't matter"

fragmede3• 3 years ago

Anything at scale. Anything that uses a database. Anything that uses anything smarter than bubblesort to organize results. Anything that uses a tree (or a trie) internally to represent the data and make some sort of order from it. CS isn't just about "hey this thing is slower than this thing", it's also about making things possible in the first place. If you've used Google (or Facebook or Microsoft or Netflix), they're only possible due to deep computer science work. Which videos gets chosen to be stored on the edge cache? Computer science algorithm.

cubefox4• 3 years ago

I'm not sure how true this is. A lot of "algorithms" can be tested by using them or by running simulations for reasonable input ranges.

dilawar• 3 years ago

I liked a few results. . For example, smooth analysis by Spielman showed why so many algorithms works very well in practice even though their worst case complexity is terrible e.g. simplex method. Second, concave-convex optimization shows that you will definitely reach closer to global optimum at each iteration. I guess its comforting to know a reason algo behave the way they do.

Sampling theorem is also case in point. Also compressed sensing. Information theory will tell you there is no point trying any harder at compression when you reached epsilon closer to the theoretical limit.

bawolff2• 3 years ago

An obvious one that comes to mind - this problem is np-complete so pragmatically i can stop looking for a fast algo.

jdthedisciple2• 3 years ago

Or resort to a SAT solver right away.

nottorp2• 3 years ago

It tends to not matter until it suddenly does and bites your behind.

What was that game that took forever to start up because the code for parsing the config files was accidentally quadratic or exponential?

Edit: also, the standard library of any programming language tends to have quite a bit of theoretical computer science inside.

Adverblessly• 3 years ago

You're thinking of GTA Online, from a quick DDG search: https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times...

fragmede3• 3 years ago

If you haven't seen it, Accidentally Quadratic has a tumblr documenting those kinds of things. https://accidentallyquadratic.tumblr.com/

pravus• 3 years ago

is there any example where theoretical computer science has actually been useful?

Anything requiring extremely optimized algorithms will generally start in academia and work its way outward as the techniques are adopted in commercial software. Sorting and compression algorithms are two examples that come to mind. Even games development which has a history of non-academic roots now borrows heavily from academic research to refine things like culling algorithms or optimized computational methods for specialized physics calculations.

cubefox4• 3 years ago

Ah yes, I heard somewhere that Brian Karis at Epic was partially relying on prior work by an academic when he developed virtualized geometry for Unreal Engine 5. (I can't remember the name of the researcher though.)

danielEM• 3 years ago

What are the alternatives to gradient descent?

thumbuddy4• 3 years ago

There are probably ly a hundred. Many people have asked for research into this for I don't know 20 years. But the hype doesn't die down and modern trends have mostly involved doing more GD with bigger models...

A colleague and myself experimented with some alternatives and passed notes once in a while... For certain modelling problems you can save literal gpu days by going against the grain and get better results.

Oh well...

stabbles2• 3 years ago

Many people have asked for research into this for I don't know 20 years

Sometimes I wonder if people in machine learning ever look at literature.

Basic iteration schemes like the secant method (ok, 1-dimensional) have been known well over 3000 years.

Newton's method is over 300 years old.

Quasi-Newton methods (the secant method being an example) became popular in the early 1960s.

stabbles2• 3 years ago

If you solve f(x) = 0 where f: ℝ^k -> ℝ^k maps vectors to vectors, most schemes are based on Taylor expansion around x_n

    f(x) = f(x_n) + Df(x_n)(x - x_n) + O(||x - x_n||^2)

Drop the quadratic term, equate to 0, and you get an approximate solution for x for the next iteration x_{n+1}:

    x_{n+1} = x_n - Df(x_n)^{-1} * f(x_n)

Like this it's the Newton method. The problem is that the Jacobian Df(x_n) is a matrix of size k x k, and inverting it may require O(k^3) work.

So, pretty much all schemes are based on approximations of the Jacobian.

Gradient descent for example replaces Df(x_n)^{-1} with a scalar a, so it's O(1) work to "compute" it:

    x_{n+1} = x_n - a * f(x_n)

A method like L-BFGS tries to build a relatively cheap approximation to the inverse of the Jacobian during iteration, resulting in O(k) work to compute:

    x_{n+1} = x_n - P * f(x_n)

Other methods may exploit sparsity of the Jacobian, or solve the linear system Df(x_n)z = f(x_n) only approximately for z using e.g. iterative methods.

Note: in optimization problems, the function f is typically a gradient of a cost function, and the jacobian is then the hessian of that cost function.

quickthrower2• 3 years ago

Gradient descent also allows batching, which reduces the memory requirements, can the other methods support that?

nerdponx6• 3 years ago

There's also Coordinate Descent which was traditionally used for fitting LASSO regression.

PartiallyTyped3• 3 years ago

None really.

Gradient descent is great because it is first order, thus cheap to compute since you don’t need a Hessian, points to a descent direction, works with anything that is differentiable or piece-wise differentiable without caveats, and given the millions of parameters in today’s there is always a descent direction.

If you do population methods, you suffer in terms of memory because you need to keep all those candidates, evaluate them individually, and then update them. This bounds the memory you can use.

More memory means more parameters, means you enter the interpolation scheme means your model behaves well in real world.

If you try to go with second order optimisation methods then you need to go for Hessian free methods as computing the Hessian is computationally intractable for large NNs.

You can attempt to build a local model of the loss landscape but that is expensive and has many caveats.

Nocedal et al is a recommended read for numerical optimisation theory.

imtringued• 3 years ago

More memory means more parameters, means you enter the interpolation scheme means your model behaves well in real world.

The surprising thing about large neural networks is that the difference in quality between the local minima goes down and makes it less and less relevant which one you end up in. The global minimum may also lead to overfitting so you probably don't even want to go there.

matteoraso• 3 years ago

If accuracy isn't as important as speed for you, you can sample 1000 points and pick the smallest one. This point will probably be smaller than 99% of the function, but I wouldn't recommend deploying this in production.

frankreyes4• 3 years ago

Hobest question, why not just use a binary/ternary search? It's because there's no known a priori how many local maximum and/or minimums?

Because that's just an iterative/recursive version of binary/ternary search.

alfla• 3 years ago

How would you do a binary search on a continuous space without discretizing?

frankreyes4• 3 years ago

Replace A[x] with f(x) and done.

A modified binary search called ternary search is well known used to find when derivative = 0, numerically.

https://en.m.wikipedia.org/wiki/Ternary_search

n2d4• 3 years ago

What would you search for, the zero/root in the derivative? Imagine the derivative is a function like y=x^2-eps with some small eps, say 0.000001. For binary search like that to work, you need to start with two values x1 and x2 such that sign(y1) != sign(y2). But with the derivative above those values are hard to find with random initialization.

More generally, for binary search to find a value x such that f(x)=0, we need to have f(any value less than x)<0 and f(any value greater than x)>0. We can't guarantee these properties for general derivatives.

jdthedisciple2• 3 years ago

What would you search for

I imagine you could search until the incremental change between your current and last result is below some threshold epsilon, as a kind of stopping criterion.

BazookaMusic• 3 years ago

This is probably what you're thinking of:

https://en.m.wikipedia.org/wiki/Bisection_method

rg111• 3 years ago

Because the search space is tremendously huge.

AbrahamParangi• 3 years ago

Try doing binary search on a space of nontrivial dimensionality (ie, not 1, 2, or 3) and you will have your answer.

eterevsky2• 3 years ago

Binary search only works on sorted data.

amelius• 3 years ago

Because of the dimensionality of the problem. Bracketing is easy to do in 1D space, not so in N-dimensional space, with large N.

whatever1• 3 years ago

We do, it’s called global optimization. It works for small problems with ~ 1000 variables or so. Check BARON and the branch & reduce algorithm

frankreyes4• 3 years ago

Thanks!

geysersam• 3 years ago

Binary search only works in 1D parameter space

eterevsky2• 3 years ago

Here's the original paper: https://arxiv.org/abs/2011.01929

And here are the complexity classes that are mentioned in the abstract: https://complexityzoo.net/Complexity_Zoo:P#ppad and https://complexityzoo.net/Complexity_Zoo:P#pls.

Computer scientists discover limits of gradient descent (2021)

Related Stories