11 ms·
Computer scientists discover limits of gradient descent (2021)
- ShamelessC 3y agohttps://arxiv.org/abs/2011.01929 https://arxiv.org/abs/2011.01929 TFP
- sockaddr 3y ago> 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?
- stormfather 3y 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.
- kadoban 3y agoThey 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.
- gauddasa 3y agoFrom 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 3y agoGood to note that the article was published on "August 17, 2021"
- antegamisou 3y agoThis 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.
- seydor 3y agoTheir articles are often rehashes of press releases, but this one seems to be of the better ones
- antegamisou 3y agoI 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.
- alimw 3y agoIs this a quality article? It starts badly: > ... elevation of the land is equal to the value of the function (the “profit”) at that particular spot. Gradient descent searches for the function’s local minimum ...
- antegamisou 3y agoOuch. Compared to current ones, I'd unfortunately have to say yes.
- dchftcs 3y agoThis 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.
- cubefox 3y agoNot 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"
- fragmede 3y agoAnything 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.
- cubefox 3y agoI'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.
- bawolff 3y agoWell first off, i think there is an argument that creating & simulating algorithms is CS stuff anyways. Second its often (not always) a lot more work to test scalability with benchmarks than it is to theoretically analyze. Especially because people are often worried about both average case and worst case. The input that takes down your site is not the one you expect, and simulating realistic load is difficult. It can also be pretty hard to compare benchmarks. You probably dont want to test every algorithm known to man yourself, but two separate benchmarks on diff hardware and diff conditions cannot be reasonably compared. More abstract analysis can (to an extent anyways)
- plonk 3y agoDon't a lot of these algorithms come from TCS researchers themselves? They may publish about complexity but if that gives some people a better understanding of algorithms and leads to better ones being invented, it's a win.
- danielEM 3y agoWhat are the alternatives to gradient descent?
- thumbuddy 3y agoThere 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...
- deleted 3y ago[deleted]
- stabbles 3y 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.
- thumbuddy 3y agoMost ML papers I used to read fell into a couple of categories... 1. Baseless empirical result that probably was p hacked. 2. Mostly untested result. 3. A rediscovery of something know for decades without attribution to the source they probably read it from. 4. Incomplete description of problem, resolution, or probably fraud/incompetency. 5. Useless in general. Unverifiable, etc. 6. Review article. 7. A derivation with way more omissions/flaws than say an engineering paper. I'm somewhat seasoned on optimization methods personally, but yea it seems once people go ML they tend to um stop studying the fundamental literature that ML came from. "Online masters program learn AI in 12 weeks from nothing!". Oh okay so calculus won't be included in that... Or statistics... Or... Yep it's going to be scikit learn notebooks ...
- frankreyes 3y agoHobest 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 3y agoHow would you do a binary search on a continuous space without discretizing?
- frankreyes 3y agoReplace 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 https://en.m.wikipedia.org/wiki/Ternary_search
- n2d4 3y agoWhat 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.
- jdthedisciple 3y 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.
- frankreyes 3y agoIEEE 754 is by default limited by 64 bits, so yes.
- eterevsky 3y agoHere's the original paper: https://arxiv.org/abs/2011.01929 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 https://complexityzoo.net/Complexity_Zoo:P#ppad and https://complexityzoo.net/Complexity_Zoo:P#pls https://complexityzoo.net/Complexity_Zoo:P#pls.
- deleted 3y ago[deleted]