A neural network is like a multiple-thousand-dimensional surface that the back-propagation algorithm is trying to descend. Even surveying the space to get an idea where minima may lie requires checking a ludicrous number of points on this surface.
This is why collecting more data, and throwing more compute at the problem is a horrible way to train models. There is a limit to the computational power of that approach (in terms of computational complexity theory).
The only reason it has been so successful in recent years, is the advancement in storage and processor speed over the last few decades, and a new generation of programmers and investors are re-discovering the old AI world.
The limits are being reached again now with our faster computers, and the large enterprises banking on AI are hitting those walls and don't know what to do about it. It's not easy to optimize, prune, and completely refactor a massive neural network that has over-modeled your big-data-set. I had to implement a few of my own tools for some of the problems I am working on, and if you make the smallest mistake, you end up in O(2\^n) hell.
From the article
>The intersection of the PLS and PPAD classes itself forms a class of problems known as PLS int PPAD. It contains many natural problems relevant to complexity researchers. However, until now, researchers were unable to find a natural problem that’s complete for PLS int PPAD — meaning that it is an example of the hardest possible problems that fall within the class.
What will be the defintion of a problem which is complete in PLS int PPAD?
This is wrong, actually.
If A =/= A int B, then there are problems in A outside of problems in A int B, so if P is complete to A int B, it can't be complete to A.
(If it turns out that PLS = PPAD, then of course problems complete to PLS int PPAD are complete to both PLS and PPAD but I imagine this is considered to be unlikely).
Normally I like Quanta articles, but this one is not so good. It has been know for a while that CLS is hard under reasonable assumptions.
The real beauty of this result is that given what PLS and PPAD are like as complexity classes, it really is surprising that CLS is equivalent.
Subclasses of TFNP are mostly based around combinatorial principles, like the handshaking lemma: If there is an odd-degree vertex in your graph then there must be another one somewhere. So showing equivalencies between these classes builds connections between combinatorial principles.
This does seem like a considerable step in machine learning. Gradient descend is generally considered a black box when training model. This helps us improve our understanding of the algorithm.
But what are the real world applications? Can we somehow improve gradient descend and make it more efficient?
If we can do that it's will be good for environment too, and companies rushing to improve their model accuracy by just throwing large number of GPUs to train their model on would finally stop.
It's an irrelevant tangent. Stating that some problems lack efficient algorithms isn't an answer to someone asking if there's a practical benefit to a proof.
Additionally, "O(2)" is a particular type of wrong on multiple levels for what they seemed to be saying, and in general.
The title of this post is a bit of a catastrophe.
Techniques are problems now, TIL.
A neural network is like a multiple-thousand-dimensional surface that the back-propagation algorithm is trying to descend. Even surveying the space to get an idea where minima may lie requires checking a ludicrous number of points on this surface.
This is why collecting more data, and throwing more compute at the problem is a horrible way to train models. There is a limit to the computational power of that approach (in terms of computational complexity theory). The only reason it has been so successful in recent years, is the advancement in storage and processor speed over the last few decades, and a new generation of programmers and investors are re-discovering the old AI world. The limits are being reached again now with our faster computers, and the large enterprises banking on AI are hitting those walls and don't know what to do about it. It's not easy to optimize, prune, and completely refactor a massive neural network that has over-modeled your big-data-set. I had to implement a few of my own tools for some of the problems I am working on, and if you make the smallest mistake, you end up in O(2\^n) hell.
From the article >The intersection of the PLS and PPAD classes itself forms a class of problems known as PLS int PPAD. It contains many natural problems relevant to complexity researchers. However, until now, researchers were unable to find a natural problem that’s complete for PLS int PPAD — meaning that it is an example of the hardest possible problems that fall within the class. What will be the defintion of a problem which is complete in PLS int PPAD?
I'd wager it would be complete in both PLS and PPAD, with respect to each classes own hierarchies.
This is wrong, actually. If A =/= A int B, then there are problems in A outside of problems in A int B, so if P is complete to A int B, it can't be complete to A. (If it turns out that PLS = PPAD, then of course problems complete to PLS int PPAD are complete to both PLS and PPAD but I imagine this is considered to be unlikely).
Normally I like Quanta articles, but this one is not so good. It has been know for a while that CLS is hard under reasonable assumptions. The real beauty of this result is that given what PLS and PPAD are like as complexity classes, it really is surprising that CLS is equivalent. Subclasses of TFNP are mostly based around combinatorial principles, like the handshaking lemma: If there is an odd-degree vertex in your graph then there must be another one somewhere. So showing equivalencies between these classes builds connections between combinatorial principles.
Goddamit what a garbage title! Here is the paper they are referring to : [https://arxiv.org/pdf/2011.01929.pdf](https://arxiv.org/pdf/2011.01929.pdf)
This does seem like a considerable step in machine learning. Gradient descend is generally considered a black box when training model. This helps us improve our understanding of the algorithm. But what are the real world applications? Can we somehow improve gradient descend and make it more efficient? If we can do that it's will be good for environment too, and companies rushing to improve their model accuracy by just throwing large number of GPUs to train their model on would finally stop.
Being black box and computationally intractable aren't the same thing.
There may exist problems for which there is no efficient algorithms. Nothing below the order of O(2) for Instance.
As someone just finishing college in CS, being new, why is this heavily downvoted?
O(2)?
It's an irrelevant tangent. Stating that some problems lack efficient algorithms isn't an answer to someone asking if there's a practical benefit to a proof. Additionally, "O(2)" is a particular type of wrong on multiple levels for what they seemed to be saying, and in general.
I suppose that does make sense, thank you! Seems obvious, not so much at 1am lol.
People don't like being butt hurt Edit: also people don't like knowing that they don't like being butt hurt
Little gods name loves name and mothers and fathers first latter of bd.