Skip to content

References

The paper explained here

  • Lotfi, S., Finzi, M., Kuang, Y., Rudner, T. G. J., Goldblum, M., and Wilson, A. G. Non-Vacuous Generalization Bounds for Large Language Models. Proceedings of the 41st International Conference on Machine Learning (ICML), PMLR 235,
  • arXiv:2312.17173v3 (17 July 2024). Code: github.com/Sanaelotfi/SubLoRA-bounds-for-LLMs.

Supporting sources we read and cite

  • Lotfi, S., Finzi, M., Kapoor, S., Potapczynski, A., Goldblum, M., and Wilson, A. G. PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization. NeurIPS 35, 2022. arXiv:2211.13609. (Universal prior, Kronecker projectors, learned quantization with the straight-through estimator, arithmetic-coding size accounting, δ = 0.05, 1 KB = 8192 bits.)
  • Hu, E. J., Shen, Y., Wallis, P., Allen-Zhu, Z., Li, Y., Wang, S., Wang, L., and Chen, W. LoRA: Low-Rank Adaptation of Large Language Models. arXiv:2106.09685, 2021. (Low-rank updates, initialization, α/r scaling, choice of W_q, W_v.)
  • Karpathy, A. nanoGPT (github.com/karpathy/nanoGPT), data/openwebtext/prepare.py: OpenWebText split into 8,009,762 training and 4,007 validation documents; 9,035,582,198 training tokens.
  • The authors' public code (SubLoRA-bounds-for-LLMs): used only to recover values the paper does not state (δ, m, sequence count) and to check how documents are sampled and how long documents are scored.
  • GLUE label statistics for CoLA and QQP, Hugging Face datasets-server (dataset nyu-mll/glue): CoLA training set 6,023 acceptable / 2,528 unacceptable; QQP training set 229,468 not-duplicate / 134,378 duplicate.

Classical results proved in the explainer

  • Markov's and Chebyshev's inequalities; the weak law of large numbers (Chapter 1).
  • Hoeffding, W. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association 58(301):13–30, 1963 — Hoeffding's lemma and inequality (Chapter 9) and Theorem 4 on sampling without replacement (Chapter 17). (The paper cites the 1994 reprint in Hoeffding's collected works.)
  • Kraft's inequality, its converse and McMillan's theorem (Chapter 12); Elias codes (Chapter 12).
  • Kolmogorov, A. N. (1963) and Solomonoff, R. J. (1964): description complexity and the universal prior (Chapter 13).
  • Shannon's source-coding bound and Gibbs' inequality; arithmetic coding (Langdon, 1984) (Chapter 22).
  • Shalev-Shwartz, S. and Ben-David, S. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014 — finite-class and description-length (MDL) bounds (Chapters 10–12).
  • Li, C., Farkhoor, H., Liu, R., and Yosinski, J. Measuring the Intrinsic Dimension of Objective Landscapes. ICLR 2018 (Chapter 18).

Works cited by the paper that we mention

Zhang et al. (2021) on fitting random labels; Catoni (2007), Dziugaite & Roy (2017), Zhou et al. (2019) on PAC-Bayes and compression; Haddouche et al. (2021) on unbounded losses; Kaplan et al. (2020) on scaling laws; Delétang et al. (2023), Language Modeling Is Compression; Goldblum et al. (2023); Wang et al. (2019), GLUE. Full entries are in the paper's reference list (pp. 10–11).