# Encoding orders and trees in real-valued functions

arXiv: https://arxiv.org/abs/2607.21761 · HTML: https://mlsanity.com/paper/2607.21761/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 29 references that are in the map.
- First posted on arXiv 23 Jul 2026.

## Builds on (most cited first, 6 of 6)

- [Private PAC learning implies finite Littlestone dimension](https://mlsanity.com/paper/1806.00949/) (2018)
- [Closure Properties for Private Classification and Online Prediction](https://mlsanity.com/paper/2003.04509/) (2020)
- [Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games](https://mlsanity.com/paper/2111.08911/) (2021)
- [On the Equivalence between Online and Private Learnability beyond Binary Classification](https://mlsanity.com/paper/2006.01980/) (2020)
- [Online Learning and Solving Infinite Games with an ERM Oracle](https://mlsanity.com/paper/2307.01689/) (2023)
- [From learnable objects to learnable random objects](https://mlsanity.com/paper/2504.00847/) (2025)

## Abstract (arXiv)

We prove function-theoretic analogues of a quantitative result of Hodges on extracting the order property from a sufficiently large 2-tree coded in a binary relation. Similar analogues for functions were previously obtained by Daskalakis and Golowich and by Anderson and Benedikt. These results are from statistical learning theory, where 2-trees are captured by sequential fat-shattering dimension, and the order property is controlled by various notions of "thresholds". Our first main result (Theorem 1.11) focuses on extracting a less restrictive kind of threshold from a tree, and yields significantly better bounds compared to what can be obtained from earlier results focusing on more restrictive versions. Part of the motivation for Theorem 1.11 lies in a companion paper, where this theorem is used to obtain efficient bounds in quantitative regularity lemmas for "stable functions". Here will use Theorem 1.11 to reprove a result of Anderson and Benedikt in a stronger form and with improved bounds. We also use Theorem 1.11 to prove an at most double-exponential bound on dual sequential fat-shattering, which resolves an open problem. In our second main result (Theorem 1.14), we give a new proof of a result of Daskalakis and Golowich on extracting "tight thresholds" from large sequential fat-shattering dimension, with improved bounds. This resolves another open problem related to correcting the proof of a result claimed by Jung, Kim, and Tewari.