4 ms·
Transformers are special because theoretically you can't make something "weaker" than a transformer without it losing some accuracy: https://arxiv.org/abs/2209.
by logicchains 3y ago
Transformers are special because theoretically you can't make something "weaker" than a transformer without it losing some accuracy: https://arxiv.org/abs/2209.04881 https://arxiv.org/abs/2209.04881 .
- VHRanger 3y agoYes, Transformers are probably close to the Pareto frontier in terms of efficiency if you want to train something that has a sequence as an input. But they're not inherently *special*. There's a bunch of other model types around that pareto frontier. Transformers are just good at saturating memory bandwidth, which is the hardware frontier.
- thesz 3y ago> Despite a remarkable amount of algorithmic effort on Boolean satisfiability (SAT) and related problems, to date no one has invented an algorithm with faster-than-exponential (O(2^n)) running time; indeed, there is no polynomial-time algorithm for SAT unless P = NP. [1] https://www.hindawi.com/journals/complexity/2018/7982851/ [2] http://www.cs.cornell.edu/~sabhar/publications/learnIJCAI03.pdf The [1] shows how to replace numerical problem solving process with the SAT (circuit) based one and obtain exponential speed up. Let me quote the [2]: "We also show that without restarts but with a new learning scheme, clause learning can provide exponentially smaller proofs than regular resolution, which itself is known to be much stronger than ordinary DPLL." So, in my opinion, there are algorithms that work in O(2^(n(1-e))) time.