Statistical Learning Theory C Convexity

Bibliography

[ABL+22] N. Alon, M. Bun, R. Livni, M. Malliaris, and S. Moran (2022-08) Private and online learnability are equivalent. Journal of the ACM 69 (4). External Links: Document Cited by: §8.2.
[AHR+25] A. Amiri, X. Huang, M. Rofin, and M. Hahn (2025) Lower bounds for chain-of-thought reasoning in hard-attention transformers. In ICML, External Links: 2502.02393 Cited by: §10.4.
[ARO50] N. Aronszajn (1950-05) Theory of reproducing kernels. Transactions of the American Mathematical Society 68 (3), pp. 337–404. External Links: Document Cited by: Theorem 14.2.
[ACG+19a] S. Arora, N. Cohen, N. Golowich, and W. Hu (2019) A convergence analysis of gradient descent for deep linear neural networks. In ICLR, External Links: 1810.02281 Cited by: 5th item.
[ADH+19b] S. Arora, S. S. Du, W. Hu, Z. Li, R. Salakhutdinov, and R. Wang (2019) On exact computation with an infinitely wide neural net. In NeurIPS, External Links: 1904.11955 Cited by: §14.1.
[ADL+20] S. Arora, S. S. Du, Z. Li, R. Salakhutdinov, R. Wang, and D. Yu (2020) Harnessing the power of infinitely wide deep nets on small-data tasks. In ICLR, External Links: Link, 1910.01663 Cited by: 3rd item, §14.6.
[AXL25] S. Axler (2025) Linear algebra done right. 4 edition. External Links: Link Cited by: Appendix A, Appendix B.
[BAC25] F. Bach (2025-05) Learning theory from first principles. External Links: Link Cited by: §1.1, Table 1.1, §10.3.2, §10.5, §13.2, §14.5.1, Statistical Learning Theory.
[BAR93] A. R. Barron (1993) Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information Theory 39, pp. 930–45. Cited by: §10.3.2.
[BM02] P. L. Bartlett and S. Mendelson (2002) Rademacher and gaussian complexities: risk bounds and structural results. Journal of Machine Learning Research 3, pp. 463 – 482. External Links: Link Cited by: footnote 9.
[BLM13] S. Boucheron, G. Lugosi, and P. Massart (2013) Concentration inequalities: a nonasymptotic theory of independence. Oxford University Press. External Links: Link Cited by: footnote 3.
[BE02] O. Bousquet and A. Elisseeff (2002) Stability and generalization. Journal of Machine Learning Research 2, pp. 499–526. External Links: Link Cited by: §15.1, §15.4, Theorem 15.4, footnote 2.
[BKZ20] O. Bousquet, Y. Klochkov, and N. Zhivotovskiy (2020) Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory, External Links: Link Cited by: §15.1.
[BV04] S. Boyd and L. Vandenbreghe (2004) Convex optimization. Cambridge University Press. External Links: Link Cited by: Appendix C, Chapter 11.
[BUB15] S. Bubeck (2015) Convex optimization: algorithms and complexity. Foundations and Trends in Machine Learning 8 (3-4). External Links: 1405.4980 Cited by: Chapter 11.
[CKS23] M. D. Cattaneo, J. M. Klusowski, and B. Shigida (2023) On the implicit bias of adam. External Links: 2309.00079 Cited by: §13.3.
[CHI25] D. Chiang (2025) Transformers in uniform TC⁰. TMLR. External Links: 2409.13629 Cited by: §10.4.
[COB19] L. Chizat, E. Oyallon, and F. Bach (2019) On lazy training in differentiable programming. In NeurIPS, External Links: 1812.07956 Cited by: §14.1.
[CKL+21] J. M. Cohen, S. Kaur, Y. Li, J. Z. Kolter, and A. Talwalkar (2021) Gradient descent on neural networks typically occurs at the edge of stability. In ICLR, External Links: 2103.00065 Cited by: §11.4.
[DNL23] A. Damian, E. Nichani, and J. D. Lee (2023) Self-stabilization: the implicit bias of gradient descent at the edge of stability. In ICLR, External Links: 2209.15594 Cited by: §11.4.
[DFO20] M. P. Deisenroth, A. A. Faisal, and C. S. Ong (2020) Mathematics for machine learning. External Links: Link Cited by: Appendix A, Appendix B.
[DLS20] T. Ding, D. Li, and R. Sun (2020) Sub-optimal local minima exist for neural networks with almost all non-linear activations. External Links: 1911.01413 Cited by: §11.5.
[DJL+17] S. S. Du, C. Jin, J. D. Lee, M. I. Jordan, B. Póczos, and A. Singh (2017) Gradient descent can take exponential time to escape saddle points. In NeurIPS, External Links: 1705.10412 Cited by: 4th item.
[EHS26] A. Ebtekar, M. Hutter, and D. J. Sutherland (2026) Understanding generalization requires universal induction. External Links: 2609.34458 Cited by: §7.2.4, §9.3.2.
[EEP05] A. Elisseeff, T. Evgeniou, and M. Pontil (2005) Stability of randomized learning algorithms. Journal of Machine Learning Research 6 (3), pp. 55–79. External Links: Link Cited by: footnote 2.
[FV18] V. Feldman and J. Vondrak (2018) Generalization bounds for uniformly stable algorithms. In Advances in Neural Information Processing Systems, Vol. 31. External Links: 1812.09859 Cited by: §15.1.
[FV19] V. Feldman and J. Vondrak (2019) High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. In Conference on Learning Theory, External Links: Link Cited by: §15.1, §15.4.
[FDP+20] S. Fort, G. K. Dziugaite, M. Paul, S. Kharaghani, D. M. Roy, and S. Ganguli (2020) Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the neural tangent kernel. In NeurIPS, External Links: 2010.15110 Cited by: §14.6, §14.6.
[FOX23] C. Fox (2023) A study of the edge of stability in deep learning. MSc. Thesis, University of British Columbia. External Links: Document Cited by: §11.4.
[FVB+23] S. Frei, G. Vardi, P. L. Bartlett, N. Srebro, and W. Hu (2023) Implicit bias in leaky relu networks trained on high-dimensional data. In ICLR, External Links: 2210.07082 Cited by: §13.3.
[GG23] G. Garrigos and R. M. Gower (2023) Handbook of convergence theorems for (stochastic) gradient methods. External Links: 2301.11235 Cited by: §11.3.1, Chapter 11.
[GKM+21] S. Goel, A. Klivans, P. Manurangsi, and D. Reichman (2021) Tight hardness results for training depth-2 relu networks. In ITCS, External Links: 2011.13550 Cited by: §10.3.
[GUE26] M. Guerzhoy (2026) Barriers to complexity-theoretic proofs that “agi” using machine learning is impossible. Computational Brain & Behavior. External Links: 2411.06498 Cited by: §7.2.5.
[GLS+18] S. Gunasekar, J. Lee, D. Soudry, and N. Srebro (2018) Characterizing implicit bias in terms of optimization geometry. In ICML, External Links: 1802.08246 Cited by: §13.2.
[HAN16] S. Hanneke (2016) The optimal sample complexity of PAC learning. Journal of Machine Learning Research 17 (38), pp. 1–15. External Links: Link Cited by: footnote 13, §7.3.
[HRS15] M. Hardt, B. Recht, and Y. Singer (2015) Train faster, generalize better: stability of stochastic gradient descent. In Advances in Neural Information Processing Systems, External Links: 1509.01240 Cited by: §15.4.
[HAR23] N. Harvey (2023-03-12) A second course in randomized algorithms. External Links: Link Cited by: footnote 3, footnote 17, §7.3, footnote 13.
[HSW89] K. Hornik, M. Stinchcombe, and H. White (1989) Multilayer feedforward networks are universal approximators. Neural Networks 2, pp. 359 – 366. External Links: Document Cited by: Proposition 10.13.
[HQC24] M. Hutter, D. Quarel, and E. Catt (2024) An introduction to universal artificial intelligence. External Links: Link Cited by: §9.3.2.
[HUT05] M. Hutter (2005) Universal artificial intelligence: sequential decisions based on algorithmic probability. External Links: Document Cited by: §9.3.2.
[ISR15] R. Israel (2015-04-01) Can the ball $B(0,r_{0})$ be covered with a finite number of balls of radius $<r_{0}$ . Note: Mathematics Stack Exchange External Links: Link Cited by: §14.5.1, §4.4.
[JAC26] A. Jacot (2026) Deep learning as a convex paradigm of computation: minimizing circuit size with ResNets. External Links: 2511.20888 Cited by: §10.4.
[JT19] Z. Ji and M. Telgarsky (2019) The implicit bias of gradient descent on nonseparable data. In COLT, External Links: 1803.07300 Cited by: §13.2.
[JT20] Z. Ji and M. Telgarsky (2020) Directional convergence and alignment in deep learning. In NeurIPS, External Links: 2006.06657 Cited by: §13.3.
[JNW+21] S. Jia, E. Nezhadarya, Y. Wu, and J. Ba (2021) Efficient statistical tests: a neural tangent kernel approach. In ICML, External Links: Link Cited by: 3rd item, §14.6.
[KHS+18] M. Kanagawa, P. Hennig, D. Sejdinovic, and B. K. Sriperumbudur (2018) Gaussian processes and kernel methods: a review on connections and equivalences. External Links: 1807.02582 Cited by: §14.5.1.
[KAW16] K. Kawaguchi (2016) Deep learning without poor local minima. In NeurIPS, External Links: 1605.07110 Cited by: 1st item.
[KR23] A. Khaled and P. Richtárik (2023) Better theory for SGD in the nonconvex world. TMLR. External Links: Link Cited by: Proposition 11.6.
[KL20] P. Kidger and T. Lyons (2020) Universal approximation with deep narrow networks. In COLT, External Links: 1905.08539 Cited by: §10.3.2.
[Lv18] T. Laurent and J. von Brecht (2018) Deep linear networks with arbitrary loss: all local minima are global. In ICML, External Links: Link Cited by: 1st item.
[LXS+19] J. Lee, L. Xiao, S. S. Schoenholz, Y. Bahri, R. Novak, J. Sohl-Dickstein, and J. Pennington (2019) Wide neural networks of any depth evolve as linear models under gradient descent. In NeurIPS, External Links: 1902.06720 Cited by: §14.1.
[LSJ+16] J. D. Lee, M. Simchowitz, M. I. Jordan, and B. Recht (2016) Gradient descent only converges to minimizers. In COLT, External Links: Link Cited by: 3rd item.
[LLP+93] M. Leshno, V. Ya. Lin, A. Pinkus, and S. Schocken (1993) Multilayer feedforward networks with a nonpolynomial activation function can approximate any function. Neural Networks 6 (6), pp. 861–867. External Links: Document Cited by: §10.3.2.
[LV19] M. Li and P. Vitányi (2019) An introduction to kolmogorov complexity and its applications. 4 edition. External Links: Document Cited by: §9.3.2.
[LIT88] N. Littlestone (1988) Learning quickly when irrelevant attributes abound: a new linear-threshold algorithm. Machine Learning 2, pp. 285–318. External Links: Document, Link Cited by: §8.2.
[LL20] K. Lyu and J. Li (2020) Gradient descent maximizes the margin of homogeneous neural networks. In ICLR, External Links: 1906.05890 Cited by: §13.3.
[LYU25] X. Lyu (2025) Private learning of littlestone classes, revisited. External Links: 2510.00076 Cited by: §8.2.
[MA22] T. Ma (2022-06) Lecture notes for machine learning theory (cs229m/stats214). External Links: Link Cited by: Statistical Learning Theory.
[MKA+21] E. Malach, P. Kamath, E. Abbe, and N. Srebro (2021) Quantifying the benefit of using differentiable learning over tangent kernels. In ICML, External Links: 2103.01210 Cited by: §14.6.
[MWY+23] S. Malladi, A. Wettig, D. Yu, D. Chen, and S. Arora (2023) A kernel-based view of language model fine-tuning. In ICML, External Links: 2210.05643 Cited by: §14.6.
[MCD89] C. McDiarmid (1989) On the method of bounded differences. In Surveys in Combinatorics, 1989: Invited Papers at the Twelfth British Combinatorial Conference, London Mathematical Society Lecture Note Series, pp. 148–188. External Links: Document Cited by: Theorem 5.6, footnote 17.
[MS23] W. Merrill and A. Sabharwal (2023) The parallelism tradeoff: limitations of log-precision transformers. Transactions of the Association for Computational Linguistics 11, pp. 531–545. External Links: Link, Document Cited by: §10.4.
[MBS22] M. A. Mohamadi, W. Bae, and D. J. Sutherland (2022) Making look-ahead active learning strategies feasible with neural tangent kernels. In NeurIPS, External Links: 2206.12569 Cited by: §14.6, §14.6.
[MBS23] M. A. Mohamadi, W. Bae, and D. J. Sutherland (2023) A fast, well-founded approximation to the empirical neural tangent kernel. In ICML, External Links: 2206.12543 Cited by: §14.6, §14.6, §14.6.
[MLW+24] M. A. Mohamadi, Z. Li, L. Wu, and D. J. Sutherland (2024) Why do you grok? a theoretical analysis on grokking modular addition. In ICML, External Links: 2407.12332 Cited by: §14.6.
[MRT18] M. Mohri, A. Rostamizadeh, and A. Talkwalkar (2018) Foundations of machine learning. 2 edition, MIT Press. External Links: Link Cited by: Appendix C, Table 1.1, footnote 5, footnote 3, §6.4.1, §7.3, §7.3, footnote 12, footnote 13, Statistical Learning Theory.
[NAK21] P. Nakkiran (2021) Turing-universal learners with optimal scaling laws. External Links: 2111.05321 Cited by: §7.2.5, §9.3.2.
[NW06] J. Nocedal and S. J. Wright (2006) Numerical optimization. Springer. External Links: Document Cited by: Chapter 11.
[NXH+20] R. Novak, L. Xiao, J. Hron, J. Lee, A. A. Alemi, J. Sohl-Dickstein, and S. S. Schoenholz (2020) Neural tangents: fast and easy infinite neural networks in python. In ICLR, External Links: 1912.02803, Link Cited by: §14.6.
[PAJ85] A. Pajor (1985) Sous-espaces $l_{1}^{n}$ des espaces de Banach. (16). External Links: ISBN 2-7056-6021-6 Cited by: footnote 12.
[PAR94] I. Parberry (1994) Circuit complexity and neural networks. MIT Press. External Links: Link Cited by: §10.4.
[RAG14] M. Raginsky (2014-09) Concentration inequalities. External Links: Link Cited by: footnote 3.
[RW06] C. E. Rasmussen and C. K. I. Williams (2006) Gaussian processes for machine learning. MIT Press. External Links: Link Cited by: §14.5.1.
[RGB+23] Y. Ren, S. Guo, W. Bae, and D. J. Sutherland (2023) How to prepare your task head for finetuning. In ICLR, External Links: 2302.05779 Cited by: §14.6.
[RGS22] Y. Ren, S. Guo, and D. J. Sutherland (2022) Better supervisory signals by observing learning paths. In ICLR, External Links: 2203.02485 Cited by: §14.6.
[REN25] Y. Ren (2025) Learning dynamics of deep learning – force analysis of deep neural networks. Ph.D. Thesis, University of British Columbia. External Links: 2509.19554 Cited by: §14.1.
[ROC70] R. T. Rockafellar (1970) Convex analysis. Princeton University Press. External Links: Link Cited by: Appendix C.
[ROM07] S. Roman (2007) Advanced linear algebra. 3 edition. External Links: Link Cited by: Appendix A, Appendix B.
[ROM21] M. Romaní (2021-05-01) A short proof of hoeffding’s lemma. External Links: Link Cited by: footnote 3.
[SAM59] A. L. Samuel (1959) Some studies in machine learning using the game of checkers. IBM Journal of Research and Development 44, pp. 206–226. External Links: Document Cited by: footnote 1.
[SHT24] C. Sanford, D. Hsu, and M. Telgarsky (2024) Transformers, parallel computation, and logarithmic depth. In ICML, External Links: 2402.09268 Cited by: §10.4.
[SAU72] N. W. Sauer (1972) On the density of families of sets. Journal of Combinatorial Theory, Series A 13 (1), pp. 145–147. External Links: Document Cited by: footnote 10.
[SSG+13] D. Sejdinovic, B. K. Sriperumbudur, A. Gretton, and K. Fukumizu (2013-10) Equivalence of distance-based and RKHS-based statistics in hypothesis testing. Annals of Statistics 41 (5), pp. 2263–2291. External Links: Document Cited by: §14.5.
[SB14] S. Shalev-Shwartz and S. Ben-David (2014) Understanding machine learning: from theory to algorithms. Cambridge University Press. External Links: Link Cited by: Appendix C, Table 1.1, §10.4, §11.3.1, Chapter 11, §13.2, §15.1, §15.2.2, §15.3.1, §15.3.1, footnote 3, §7.1, §7.1, §7.3, footnote 12, footnote 5, footnote 6, footnote 8, §8.2, Statistical Learning Theory.
[SSS+10] S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan (2010) Learnability, stability and uniform convergence. Journal of Machine Learning Research 11, pp. 2635–2670. External Links: Link Cited by: §15.1, §15.1, §15.4, §15.4, footnote 2.
[SHE72] S. Shelah (1972) A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific Journal of Mathematics 41 (1), pp. 247 – 261. External Links: Link Cited by: footnote 10.
[SHN+18] D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro (2018) The implicit bias of gradient descent on separable data. JMLR. External Links: 1710.10345 Cited by: §13.2.
[SFL11] B. K. Sriperumbudur, K. Fukumizu, and G. R. G. Lanckriet (2011) Universality, characteristic kernels and RKHS embedding of measures. Vol. 12, pp. 2389–2410. External Links: Link Cited by: footnote 2.
[SC08] I. Steinwart and A. Christmann (2008) Support vector machines. Springer. External Links: Document Cited by: §14.5.1.
[TEL21] M. Telgarsky (2021-10) Deep learning theory lecture notes. External Links: Link Cited by: §10.3.1, §10.3.2, Statistical Learning Theory.
[VAL84] L. G. Valiant (1984) A theory of the learnable. Communications of the ACM 27 (11), pp. 1134–1142. External Links: Document Cited by: footnote 3.
[VAN98] A. W. van der Vaart (1998) Asymptotic statistics. Cambridge University Press. External Links: Link Cited by: §2.1.
[vGA+24] I. van Rooij, O. Guest, F. Adolfi, R. de Haan, A. Kolokolova, and P. Rich (2024) Reclaiming ai as a theoretical tool for cognitive science. Computational Brain & Behavior. External Links: Document Cited by: §7.2.5, Theorem 7.12.
[VC68] V. N. Vapnik and A. Ya. Chervonenkis (1968) 181 (4), pp. 781 (russian). Cited by: footnote 3.
[VSS22] G. Vardi, O. Shamir, and N. Srebro (2022) On margin maximization in linear and ReLU networks. In NeurIPS, External Links: 2110.02732 Cited by: §13.3.
[VAR22] G. Vardi (2022) On the implicit bias in deep-learning algorithms. External Links: 2208.12591 Cited by: §13.3.
[WAI19] M. Wainwright (2019) High-dimensional statistics: a non-asymptotic viewpoint. Cambridge University Press. External Links: Link Cited by: footnote 3, footnote 4, footnote 17, Statistical Learning Theory.
[WMC+21] B. Wang, Q. Meng, W. Chen, and T. Liu (2021) The implicit bias for adaptive optimization algorithms on homogeneous neural networks. In ICML, External Links: 2012.06244 Cited by: §13.3.
[WMZ+22] B. Wang, Q. Meng, H. Zhang, R. Sun, W. Chen, Z. Ma, and T. Liu (2022) Does momentum change the implicit regularization on separable data?. In NeurIPS, External Links: 2110.03891 Cited by: §13.3.
[WLF16] Y. Wang, J. Lei, and S. E. Fienberg (2016) Learning with differential privacy: stability, learnability and the sufficiency and necessity of erm principle. Journal of Machine Learning Research 17 (183), pp. 1–40. External Links: Link Cited by: §15.1, §15.4.
[WHS22] A. Wei, W. Hu, and J. Steinhardt (2022) More than a toy: random matrix models predict how real-world neural representations generalize. In ICML, External Links: 2203.06176 Cited by: §14.6, §14.6.
[WMG+23] S. Wei, D. Murfet, M. Gong, H. Li, J. Gell-Redman, and T. Quella (2023-12) Deep learning is singular, and that’s good. IEEE Transactions on Neural Networks and Learning Systems 34 (12), pp. 10473–10486. External Links: ISSN 2162-2388, Document Cited by: §2.1.
[WOL96] D. H. Wolpert (1996-10) The lack of a priori distinctions between learning algorithms. Neural Computation 8 (7), pp. 1341–1390. External Links: Document, Link Cited by: §7.2.3.
[XL24] S. Xie and Z. Li (2024) Implicit bias of adamw: $\ell_{\infty}$ norm constrained optimization. In ICML, External Links: 2404.04454 Cited by: §13.3.
[YL21] G. Yang and E. Littwin (2021) Tensor Programs IIb: architectural universality of neural tangent kernel training dynamics. In ICML, External Links: 2105.03703 Cited by: §14.1.
[YAN19] G. Yang (2019) Tensor Programs I: wide feedforward or recurrent neural networks of any architecture are Gaussian processes. In NeurIPS, External Links: 1910.12478 Cited by: §14.6.
[YS19] G. Yehudai and O. Shamir (2019) On the power and limitations of random features for understanding neural networks. In NeurIPS, External Links: 1904.00687 Cited by: §14.6.
[ZHA23] T. Zhang (2023) Mathematical analysis of machine learning algorithms. Note: Pre-publication version External Links: Link Cited by: Table 1.1, §3.3.1, footnote 9, §7.3.
[ZKS+22] L. Zhou, F. Koehler, P. Sur, D. J. Sutherland, and N. Srebro (2022) A non-asymptotic moreau envelope theory for high-dimensional generalized linear models. In NeurIPS, External Links: 2210.12082 Cited by: §9.1.2.