cs.DS — Data Structures and Algorithms

What Does the Refutation of the Exponential Time Hypothesis Mean for Learning Theory?

Contributed by Xiaoyu Li

Two recent works by OpenAI and Anthropic refuted the Exponential Time Hypothesis (ETH). They count the satisfying assignments of a $k$-CNF on $n$ variables in time $2^{n/(\log n)^{1/2-o(1)}}$. Many fine-grained lower bounds in learning theory rest on ETH and its relatives. We determine what the refutation changes for learning. The answer is a locality principle: the new algorithms speed up learning when each labeled example constrains few bits of the hypothesis, and under the CNF form of the Strong Exponential Time Hypothesis, which survives, the speed-up ends at $\Theta(\log N)$ bits. Three transitions make the principle precise. Locality. Call a class with $N$-bit descriptions $\kappa$-local if each label depends on at most $\kappa$ description bits, as for quantized models on sparse data. Then proper PAC learning, exact version-space counting and sampling, and the halving algorithm run in time $\mathrm{poly}(m)\cdot 2^{o(N)}$ on samples of size $m$ for $\kappa=o((\log N)^{1/4}/\sqrt{\log\log N})$, and proper PAC learning at constant accuracy does so for $\kappa=o(\sqrt{\log N})$. At inverse-polynomial accuracy, proper learning of $\kappa$-local classes is equivalent to $\kappa$-SAT, up to a factor $2$ in the locality. Under CNF-SETH, consistency for binarized perceptrons on $O(\log N)$-sparse data needs time $2^{(1-\gamma)N}$ for every $\gamma>0$. Accuracy. Exact empirical risk minimization, proper agnostic learning and the exponential mechanism reduce to tensor contractions over a truncated polynomial ring. As a consequence, the Sparse Max-SAT Hypotheses of Alman and Vassilevska Williams are false. At constant accuracy, proper learning is SAT parameterized by formula length. With quasi-linear PCPs this gives a $2^{N/\mathrm{polylog}\,N}$ lower bound under a length form of ETH, which replaces Gap-ETH for reductions of quasi-linear size. At accuracy $N^{-3}/8$, the Max-3-SAT Hypothesis forces time $2^{(1-o(1))N}$. Treewidth. Exact inference in graphical models of bounded degree and arity takes time $2^{O(n/\sqrt{\log n})}$. On expanders this beats every elimination order and every structured DNNF. Under $\#$CNF-SETH, time $2^{(1-\gamma)\mathrm{tw}}$ is again necessary once a model may have $\mathrm{tw}^{O(1)}$ variables. We also take stock of the conditional lower bounds of learning theory: which ones fall, and which ones survive on which hypothesis. The next obstacle is a permutation problem. On difference vectors $e_i-e_j$, empirical risk minimization for real-valued halfspaces is weighted Feedback Arc Set, which the new algorithms do not reach.