Writing study: Prediction Under Imperfect Compression: A Theory of Approximate MDL
← NeurIPS 2026 oral writing corpus
Qian Li, Xinyu Mao, Shang-Hua Teng, Guangxu Yang · Official NeurIPS 2026 oral record
Figure, table and section ledger
Editorial contribution type: Theory & formal analysis (primary).
Layout extraction, not a required paper template. Counts are distinct caption labels; a multi-panel figure counts once. Section spans are estimated from heading positions, including floats and whitespace. Method and limitations.
- Canonical PDF
- 26 physical pages
- Before references / appendix
- ≈ 10.65 page-equivalents
- Main figures / tables
- 0 / 1
- Attached appendix figures / tables
- 0 / 0
- Attached appendix span
- ≈ 13.91 page-equivalents
Source-bound correction: Top-level heading and reference/appendix boundaries checked against source PDF text. Bibliography titles/author initials, numbered contribution/property bullets, diagram steps, equations and TOC entries are not substantive headings. Section spans are page-coordinate estimates, not ink area or prose-only length. This is an author manuscript mirror, not a verified accepted-version template. Source layout uses physical single-column y/page-height, including equation-heavy pages.
Section-by-section lengths and source pages
The title/abstract/front matter precede the first numbered heading. A span ends at the next detected top-level heading, not at the last sentence; end-page whitespace is included. References and statements are listed separately. These are not measurements of text-only or artwork area.
| Top-level heading | Starts on PDF page | Estimated span | Share of entire PDF |
|---|---|---|---|
| 1 Introduction | 1 | ≈ 3.72 pp. | 14.31% |
| 2 Preliminaries | 5 | ≈ 3.97 pp. | 15.27% |
| 3 Reliable prediction: MDL under additive approximation | 9 | ≈ 1.23 pp. | 4.73% |
| 4 MDL under multiplicative approximation is not a universal predictor | 10 | ≈ 0.78 pp. | 3% |
| 5 Conclusion | 11 | ≈ 0.21 pp. | 0.81% |
| References | 11 | ≈ 1.44 pp. | 5.54% |
| A Full proofs for additive Approx-MDL | 13 | ≈ 10 pp. | 38.46% |
| B Full proofs for multiplicative Approx-MDL | 23 | ≈ 3.91 pp. | 15.04% |
All detected figure and table locations
Main text
Attached appendix
No recognized caption labels.
Argument and organization
- 1 Introduction and contributions
Contrasts exact MDL with additive and multiplicative selection slack.
- 2 Preliminaries
Defines the realizable sequence-prediction setting and error measure.
- 3 Reliable prediction: MDL under additive approximation
Explains the positive additive guarantee and low-regularization counterexample.
- 4 MDL under multiplicative approximation is not a universal predictor
Explains why multiplicative slack admits persistent bad selectors.
- 5 Conclusion
Summarizes the threshold and quantifier-sensitive implications.
Problem, claim and contribution
The motivation replaces ideal exact MDL optimization with imperfect selection and asks precisely which prediction guarantee survives. The contrast is between fixed additive slack and multiplicative slack that can grow with the observed prefix.
PDF pp.1–4, Introduction and contributions · Main paper
Argument and section order
The introduction states the positive bound, near-sharpness, and two negative results before a compact guarantee table. Formal preliminaries and separate additive/multiplicative proof sketches then explain the source of the separation.
PDF pp.3–11, Theorems 1.1–1.3 and Sections 2–5 · Main paper
Figures, captions and visual explanation
Table 1 is a theory-regime table rather than an empirical leaderboard: approximation type and regularization strength determine which guarantee is available. Its caption explicitly distinguishes a guarantee for every valid selector from existence of a bad selector.
PDF p.4, Table 1 · Main paper
Tables, comparisons and evidence
The theorem statements preserve realizability, countable model class, positive prior weights, and regularization conditions. Pairing a positive upper bound with near-sharpness and a counterexample shows both what the criterion ensures and where that assurance ends.
PDF p.3, Theorem 1.1 and Proposition 1.1; pp.3–4, Theorems 1.2–1.3 · Main paper
Appendix and reproducibility
Appendix A groups full additive-approximation proofs, including the positive result and boundary arguments; Appendix B gives the multiplicative proof. The main text supplies the proof idea before redirecting to the technical derivations.
PDF pp.9–10, proof ideas; pp.13–26, Appendices A–B · Main paper
Clarity and writing conventions
Terms such as valid selector and cumulative expected squared error are retained around the summary table. The strongest lesson is its explicit quantifier legend; without that legend, a counterexample row can be misread as all approximate predictors failing.
PDF pp.3–4, theorem statements and Table 1 caption · Main paper
What to reuse—and what not to infer
Transferable lesson: For impossibility or threshold results, a regime table should encode assumptions and quantifiers, not only green/red or finite/infinite outcomes.
Boundary: The negative statements are existential counterexamples in the specified universal estimable setting, not failure of every multiplicative approximation implementation. This writing audit does not verify all proofs or establish the mirror as the accepted version.
Apply this lesson using the argument and evidence worksheet.
Inspection record and sources
- Checked
- 2026-10-02
- Reading status
- Writing-focused manuscript scan + selected visuals inspected
- Main text
- Writing-oriented source scan of framing, argument roadmap, selected substantive passages, method/theorem statements, main figure/table captions, evidence and limits across PDF pp.1–11. Two selected main-body pages were actually inspected as rendered images. This is not exhaustive line-by-line technical verification or experiment reproduction. Title and all author names compared against official program metadata and manuscript first page; matching authors, with capitalization, middle initials or expanded given names where applicable.
- Appendix / supplement
- Appendix proof grouping, named result references, and selected proof openings were inspected for navigation; full technical verification was not performed.
- Visually inspected PDF pages
- 3, 4
This is a writing-focused scan of the manuscript and the stated supplementary scope: framing, organization, visual explanation, evidence presentation and wording. It is not a line-by-line proof audit, reproduction of results or exhaustive scientific review.