{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,10]],"date-time":"2026-09-10T05:12:25Z","timestamp":1789017145187,"version":"build-2803163510"},"reference-count":113,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2026,9,8]],"date-time":"2026-09-08T00:00:00Z","timestamp":1788825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Solomonoff induction mixes all computable explanations with description-length weights, but it is incomputable. This theory-and-position paper argues that practical approximation must be category-native: one should first declare the mathematical category in which a computable shadow will live, then use that category\u2019s native comparison functional, complexity code, and inductive object. The proposal is not an omnibus theorem asserting that all categories are equivalent. It is a research architecture that separates comparison, representation, and prediction and makes the information lost by each projection explicit. The metric\u2013measure branch supplies the developed realization. Compression data define an empirical Solomonoff space; Gromov\u2013Wasserstein (GW) distance supplies relational distortion; minimum description length (MDL) controls candidate complexity; and distance-to-kernel embedding produces a positive-semidefinite predictor. For finite or countable coded classes, we prove existence and stability results, a held-out validation oracle inequality, a Kolmogorov\u2013Solomonoff kernel unification, conditional empirical-GW consistency, and a coding-redundancy bound. Stronger learning-oracle statements remain conditional on marked\/predictive selection, candidate-family adequacy, and kernel stability. Topological, Banach\/Barron, graph, tree, and operator branches are presented as a constructional and testable research programme, with their maturity stated explicitly.<\/jats:p>","DOI":"10.3390\/e28091005","type":"journal-article","created":{"date-parts":[[2026,9,8]],"date-time":"2026-09-08T12:51:48Z","timestamp":1788871908000},"page":"1005","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Category-Native Solomonoff Approximation: From Algorithmic Geometry to Kernels, Operators, and Induction"],"prefix":"10.3390","volume":"28","author":[{"given":"Boumediene","family":"Hamzi","sequence":"first","affiliation":[{"name":"Department of Computing and Mathematical Sciences, California Institute of Technology, Pasadena, CA 91125, USA"},{"name":"The Alan Turing Institute, London NW1 2DB, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3263-4097","authenticated-orcid":false,"given":"Marcus","family":"Hutter","sequence":"additional","affiliation":[{"name":"Google DeepMind, London N1C 4DJ, UK"},{"name":"School of Computing, Australian National University, Canberra 2601, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2026,9,8]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"134153","DOI":"10.1016\/j.physd.2024.134153","article-title":"Bridging algorithmic information theory and machine learning: A new approach to kernel learning","volume":"464","author":"Hamzi","year":"2024","journal-title":"Phys. D Nonlinear Phenom."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"134669","DOI":"10.1016\/j.physd.2025.134669","article-title":"Bridging algorithmic information theory and machine learning: Clustering, density estimation, Kolmogorov complexity-based kernels, and kernel learning in unsupervised learning","volume":"476","author":"Hamzi","year":"2025","journal-title":"Phys. D Nonlinear Phenom."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Hamzi, B., Hutter, M., and Owhadi, H. (2026, August 12). Learning theory from the viewpoint of algorithmic information theory: Kolmogorov complexity meets kernel methods. ResearchGate, Available online: https:\/\/www.researchgate.net\/publication\/394846987_Learning_Theory_from_the_Viewpoint_of_Algorithmic_Information_Theory_Kolmogorov_Complexity_Meets_Kernel_Methods.","DOI":"10.2139\/ssrn.5477437"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Hamzi, B., Hutter, M., Owhadi, H., and Wilson, A.G. (2026). Bridging algorithmic information theory and machine learning, Part IV: Solomonoff Gaussian Hilbert spaces, Solomonoff Gaussian processes, and Solomonoff Gaussian fields. Phys. D Nonlinear Phenom., 135371.","DOI":"10.1016\/j.physd.2026.135371"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Hamzi, B., Hutter, M., Owhadi, H., and Wilson, A.G. (2026, August 12). Bridging algorithmic information theory and machine learning, Part V: Learning theory in Solomonoff Gaussian Hilbert spaces. ResearchGate, Available online: https:\/\/www.researchgate.net\/publication\/402794637_Bridging_Algorithmic_Information_Theory_and_Machine_Learning_Part_V_Learning_Theory_in_Solomonoff_Gaussian_Hilbert_Spaces.","DOI":"10.2139\/ssrn.6792413"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Hamzi, B., Hutter, M., Owhadi, H., and Wilson, A.G. (2026). Bridging Algorithmic Information Theory and Machine Learning, Part VI: Deep Kolmogorov Complexity Kernels, California Institute of Technology.","DOI":"10.1016\/j.physd.2025.134669"},{"key":"ref_7","unstructured":"Hamzi, B., and Hutter, M. (2026, August 12). Toward an Algorithmic Theory of Machine Learning: Unifying Machine Learning and Algorithmic Information Theory via Kernel Methods. ResearchGate, Available online: https:\/\/www.researchgate.net\/profile\/Boumediene-Hamzi\/publication\/411158923_Toward_an_Algorithmic_Theory_of_Machine_Learning_Unifying_Machine_Learning_and_Algorithmic_Information_Theory_via_Kernel_Methods."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Li, M., and Vit\u00e1nyi, P.M.B. (2008). An Introduction to Kolmogorov Complexity and Its Applications, Springer. [3rd ed.].","DOI":"10.1007\/978-0-387-49820-1"},{"key":"ref_9","unstructured":"Hutter, M. (2005). Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability, Springer."},{"key":"ref_10","first-page":"1","article-title":"Three approaches to the quantitative definition of information","volume":"1","author":"Kolmogorov","year":"1965","journal-title":"Probl. Inf. Transm."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0019-9958(64)90223-2","article-title":"A formal theory of inductive inference. Part I","volume":"7","author":"Solomonoff","year":"1964","journal-title":"Inf. Control"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1016\/S0019-9958(64)90131-7","article-title":"A formal theory of inductive inference. Part II","volume":"7","author":"Solomonoff","year":"1964","journal-title":"Inf. Control"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1109\/TIT.1978.1055913","article-title":"Complexity-based induction systems: Comparisons and convergence theorems","volume":"24","author":"Solomonoff","year":"1978","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1070\/RM1970v025n06ABEH001269","article-title":"The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms","volume":"25","author":"Zvonkin","year":"1970","journal-title":"Russ. Math. Surv."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1145\/321892.321894","article-title":"A theory of program size formally identical to information theory","volume":"22","author":"Chaitin","year":"1975","journal-title":"J. ACM"},{"key":"ref_16","first-page":"265","article-title":"Universal sequential search problems","volume":"9","author":"Levin","year":"1973","journal-title":"Probl. Inf. Transm."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Hutter, M., Quarel, D., and Catt, E. (2024). An Introduction to Universal Artificial Intelligence, Chapman & Hall\/CRC Press.","DOI":"10.1201\/9781003460299"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1076","DOI":"10.3390\/e13061076","article-title":"A philosophical treatise of universal induction","volume":"13","author":"Rathmanner","year":"2011","journal-title":"Entropy"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1086\/687257","article-title":"Solomonoff prediction and Occam\u2019s razor","volume":"83","author":"Sterkenburg","year":"2016","journal-title":"Philos. Sci."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Cover, T.M., and Thomas, J.A. (2006). Elements of Information Theory, Wiley.","DOI":"10.1002\/047174882X"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1407","DOI":"10.1109\/18.681318","article-title":"Information distance","volume":"44","author":"Bennett","year":"1998","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"3250","DOI":"10.1109\/TIT.2004.838101","article-title":"The similarity metric","volume":"50","author":"Li","year":"2004","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1523","DOI":"10.1109\/TIT.2005.844059","article-title":"Clustering by compression","volume":"51","author":"Cilibrasi","year":"2005","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"370","DOI":"10.1109\/TKDE.2007.48","article-title":"The Google similarity distance","volume":"19","author":"Cilibrasi","year":"2007","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_25","unstructured":"Gromov, M. (1999). Metric Structures for Riemannian and Non-Riemannian Spaces, Birkh\u00e4user."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/s11511-006-0002-8","article-title":"On the geometry of metric measure spaces I, II","volume":"196","author":"Sturm","year":"2006","journal-title":"Acta Math."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Villani, C. (2009). Optimal Transport: Old and New, Springer.","DOI":"10.1007\/978-3-540-71050-9"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1007\/s10208-011-9093-5","article-title":"Gromov\u2013Wasserstein distances and the metric approach to object matching","volume":"11","year":"2011","journal-title":"Found. Comput. Math."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Sturm, K.-T. (2023). The Space of Spaces: Curvature Bounds and Gradient Flows on the Space of Metric Measure Spaces, Memoirs of the American Mathematical Society.","DOI":"10.1090\/memo\/1443"},{"key":"ref_30","unstructured":"Peyr\u00e9, G., Cuturi, M., and Solomon, J. (2016). Gromov\u2013Wasserstein averaging of kernel and distance matrices. Proceedings of the 33rd International Conference on Machine Learning, Curran Associates, Inc."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1561\/2200000073","article-title":"Computational optimal transport","volume":"11","author":"Cuturi","year":"2019","journal-title":"Found. Trends Mach. Learn."},{"key":"ref_32","unstructured":"Cuturi, M. (2013). Sinkhorn distances: Lightspeed computation of optimal transport. Advances in Neural Information Processing Systems 26, ACM."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"72:1","DOI":"10.1145\/2897824.2925903","article-title":"Entropic metric alignment for correspondence problems","volume":"35","author":"Solomon","year":"2016","journal-title":"ACM Trans. Graph."},{"key":"ref_34","first-page":"1","article-title":"POT: Python optimal transport","volume":"22","author":"Flamary","year":"2021","journal-title":"J. Mach. Learn. Res."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Vayer, T., Chapel, L., Flamary, R., Tavenard, R., and Courty, N. (2020). Fused Gromov\u2013Wasserstein distance for structured objects. Algorithms, 13.","DOI":"10.3390\/a13090212"},{"key":"ref_36","unstructured":"Xu, H., Luo, D., Zha, H., and Carin, L. (2019). Gromov\u2013Wasserstein learning for graph matching and node embedding. Proceedings of the 36th International Conference on Machine Learning, Curran Associates, Inc."},{"key":"ref_37","first-page":"757","article-title":"The Gromov\u2013Wasserstein distance between networks and stable network invariants","volume":"8","author":"Chowdhury","year":"2019","journal-title":"Inf. Inference"},{"key":"ref_38","unstructured":"Bunne, C., Alvarez-Melis, D., Krause, A., and Jegelka, S. (2019). Learning generative models across incomparable spaces. Proceedings of the 36th International Conference on Machine Learning, Curran Associates, Inc."},{"key":"ref_39","unstructured":"Scetbon, M., Peyr\u00e9, G., and Cuturi, M. (2022). Linear-time Gromov\u2013Wasserstein distances using low rank couplings and costs. Proceedings of the 39th International Conference on Machine Learning, Curran Associates, Inc."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"1178","DOI":"10.1017\/jpr.2022.16","article-title":"Gromov\u2013Wasserstein distances between Gaussian distributions","volume":"59","author":"Delon","year":"2022","journal-title":"J. Appl. Probab."},{"key":"ref_41","unstructured":"Le, K., Le, D.Q., Nguyen, H., Do, D., Pham, T., and Ho, N. (2022). Entropic Gromov\u2013Wasserstein between Gaussian distributions. Proceedings of the 39th International Conference on Machine Learning, Curran Associates, Inc."},{"key":"ref_42","first-page":"172","article-title":"Procrustes metrics on covariance operators and optimal transportation of Gaussian processes","volume":"81","author":"Masarotto","year":"2019","journal-title":"Sankhy\u0101 Indian J. Stat."},{"key":"ref_43","unstructured":"Chowdhury, S., and Needham, T. (2021). Generalized spectral clustering via Gromov\u2013Wasserstein learning. Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, Curran Associates, Inc.. PMLR 130."},{"key":"ref_44","unstructured":"Xu, H., Luo, D., and Carin, L. (2019). Scalable Gromov\u2013Wasserstein learning for graph partitioning and matching. Advances in Neural Information Processing Systems 32, ACM."},{"key":"ref_45","unstructured":"Vincent-Cuaz, C., Vayer, T., Flamary, R., Corneli, M., and Courty, N. (2021). Online graph dictionary learning. Proceedings of the 38th International Conference on Machine Learning, Curran Associates, Inc."},{"key":"ref_46","unstructured":"Vincent-Cuaz, C., Flamary, R., Corneli, M., Vayer, T., and Courty, N. (2022). Semi-relaxed Gromov\u2013Wasserstein divergence and applications on graphs. arXiv."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1090\/S0002-9947-1938-1501980-0","article-title":"Metric spaces and positive definite functions","volume":"44","author":"Schoenberg","year":"1938","journal-title":"Trans. Am. Math. Soc."},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Berg, C., Christensen, J.P.R., and Ressel, P. (1984). Harmonic Analysis on Semigroups: Theory of Positive Definite and Related Functions, Springer.","DOI":"10.1007\/978-1-4612-1128-0"},{"key":"ref_49","unstructured":"Wu, L., Yen, I.E., Xu, F., Ravikumar, P., and Witbrock, M. (2018). D2KE: From distance to kernel and embedding. arXiv."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1090\/S0002-9947-1950-0051437-7","article-title":"Theory of reproducing kernels","volume":"68","author":"Aronszajn","year":"1950","journal-title":"Trans. Am. Math. Soc."},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Sch\u00f6lkopf, B., and Smola, A.J. (2002). Learning with Kernels, MIT Press.","DOI":"10.7551\/mitpress\/4175.001.0001"},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Steinwart, I., and Christmann, A. (2008). Support Vector Machines, Springer.","DOI":"10.1007\/978-0-387-77242-4"},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1090\/S0273-0979-09-01249-X","article-title":"Topology and data","volume":"46","author":"Carlsson","year":"2009","journal-title":"Bull. Am. Math. Soc."},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"Edelsbrunner, H., and Harer, J. (2010). Computational Topology: An Introduction, American Mathematical Society.","DOI":"10.1090\/mbk\/069"},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/s00454-004-1146-y","article-title":"Computing persistent homology","volume":"33","author":"Zomorodian","year":"2005","journal-title":"Discret. Comput. Geom."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1007\/s00454-006-1276-5","article-title":"Stability of persistence diagrams","volume":"37","author":"Edelsbrunner","year":"2007","journal-title":"Discret. Comput. Geom."},{"key":"ref_57","doi-asserted-by":"crossref","unstructured":"Chazal, F., de Silva, V., Glisse, M., and Oudot, S. (2016). The Structure and Stability of Persistence Modules, Springer.","DOI":"10.1007\/978-3-319-42545-0"},{"key":"ref_58","doi-asserted-by":"crossref","first-page":"930","DOI":"10.1109\/18.256500","article-title":"Universal approximation bounds for superpositions of a sigmoidal function","volume":"39","author":"Barron","year":"1993","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_59","first-page":"1","article-title":"Breaking the curse of dimensionality with convex neural networks","volume":"18","author":"Bach","year":"2017","journal-title":"J. Mach. Learn. Res."},{"key":"ref_60","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/s00365-021-09549-y","article-title":"The Barron space and the flow-induced function spaces for neural network models","volume":"55","author":"Ma","year":"2022","journal-title":"Constr. Approx."},{"key":"ref_61","first-page":"77","article-title":"Statistical topological data analysis using persistence landscapes","volume":"16","author":"Bubenik","year":"2015","journal-title":"J. Mach. Learn. Res."},{"key":"ref_62","first-page":"1","article-title":"Persistence images: A stable vector representation of persistent homology","volume":"18","author":"Adams","year":"2017","journal-title":"J. Mach. Learn. Res."},{"key":"ref_63","doi-asserted-by":"crossref","unstructured":"Reininghaus, J., Huber, S., Bauer, U., and Kwitt, R. (2015). A stable multi-scale kernel for topological machine learning. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, IEEE.","DOI":"10.1109\/CVPR.2015.7299106"},{"key":"ref_64","unstructured":"Kondor, R.I., and Lafferty, J. (2002). Diffusion kernels on graphs and other discrete structures. Proceedings of the 19th International Conference on Machine Learning, Morgan Kaufmann."},{"key":"ref_65","first-page":"1201","article-title":"Graph kernels","volume":"11","author":"Vishwanathan","year":"2010","journal-title":"J. Mach. Learn. Res."},{"key":"ref_66","doi-asserted-by":"crossref","first-page":"124007","DOI":"10.1088\/0266-5611\/27\/12\/124007","article-title":"Probability measures on the space of persistence diagrams","volume":"27","author":"Mileyko","year":"2011","journal-title":"Inverse Probl."},{"key":"ref_67","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1007\/s00454-014-9604-7","article-title":"Fr\u00e9chet means for distributions of persistence diagrams","volume":"52","author":"Turner","year":"2014","journal-title":"Discret. Comput. Geom."},{"key":"ref_68","unstructured":"Chung, F.R.K. (1997). Spectral Graph Theory, American Mathematical Society."},{"key":"ref_69","doi-asserted-by":"crossref","first-page":"1373","DOI":"10.1162\/089976603321780317","article-title":"Laplacian eigenmaps for dimensionality reduction and data representation","volume":"15","author":"Belkin","year":"2003","journal-title":"Neural Comput."},{"key":"ref_70","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/j.acha.2006.04.006","article-title":"Diffusion maps","volume":"21","author":"Coifman","year":"2006","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"ref_71","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1109\/18.382012","article-title":"The context-tree weighting method: Basic properties","volume":"41","author":"Willems","year":"1995","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_72","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1109\/TIT.1981.1056331","article-title":"The performance of universal encoding","volume":"27","author":"Krichevsky","year":"1981","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_73","doi-asserted-by":"crossref","unstructured":"Cesa-Bianchi, N., and Lugosi, G. (2006). Prediction, Learning, and Games, Cambridge University Press.","DOI":"10.1017\/CBO9780511546921"},{"key":"ref_74","doi-asserted-by":"crossref","unstructured":"Vovk, V.G. (1990). Aggregating strategies. Proceedings of the 3rd Annual Workshop on Computational Learning Theory (COLT), ACM.","DOI":"10.1016\/B978-1-55860-146-8.50032-1"},{"key":"ref_75","doi-asserted-by":"crossref","unstructured":"Rasmussen, C.E., and Williams, C.K.I. (2006). Gaussian Processes for Machine Learning, MIT Press.","DOI":"10.7551\/mitpress\/3206.001.0001"},{"key":"ref_76","doi-asserted-by":"crossref","first-page":"7540","DOI":"10.1109\/TIT.2025.3597092","article-title":"Properties of Algorithmic Information Distance","volume":"71","author":"Hutter","year":"2025","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_77","unstructured":"Almeida, T., and Hidalgo, J. (2026, August 12). SMS Spam Collection. UCI Machine Learning Repository. Available online: https:\/\/archive.ics.uci.edu\/dataset\/228\/sms+spam+collection."},{"key":"ref_78","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/BF02579135","article-title":"On optimal matchings","volume":"4","author":"Ajtai","year":"1984","journal-title":"Combinatorica"},{"key":"ref_79","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1007\/s00440-014-0583-7","article-title":"On the rate of convergence in Wasserstein distance of the empirical measure","volume":"162","author":"Fournier","year":"2015","journal-title":"Probab. Theory Relat. Fields"},{"key":"ref_80","doi-asserted-by":"crossref","first-page":"2620","DOI":"10.3150\/18-BEJ1065","article-title":"Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance","volume":"25","author":"Weed","year":"2019","journal-title":"Bernoulli"},{"key":"ref_81","doi-asserted-by":"crossref","first-page":"1616","DOI":"10.1214\/24-AOS2406","article-title":"Gromov\u2013Wasserstein distances: Entropic regularization, duality and sample complexity","volume":"52","author":"Zhang","year":"2024","journal-title":"Ann. Stat."},{"key":"ref_82","unstructured":"Genevay, A., Chizat, L., Bach, F., Cuturi, M., and Peyr\u00e9, G. (2019). Sample complexity of Sinkhorn divergences. Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, Curran Associates, Inc."},{"key":"ref_83","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-01-00923-5","article-title":"On the mathematical foundations of learning","volume":"39","author":"Cucker","year":"2002","journal-title":"Bull. Am. Math. Soc."},{"key":"ref_84","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/s10208-006-0196-8","article-title":"Optimal rates for the regularized least-squares algorithm","volume":"7","author":"Caponnetto","year":"2007","journal-title":"Found. Comput. Math."},{"key":"ref_85","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","article-title":"Probability inequalities for sums of bounded random variables","volume":"58","author":"Hoeffding","year":"1963","journal-title":"J. Am. Stat. Assoc."},{"key":"ref_86","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1214\/aoms\/1177730196","article-title":"A class of statistics with asymptotically normal distribution","volume":"19","author":"Hoeffding","year":"1948","journal-title":"Ann. Math. Stat."},{"key":"ref_87","doi-asserted-by":"crossref","unstructured":"McDiarmid, C. (1989). On the method of bounded differences. Surveys in Combinatorics, Cambridge University Press. London Mathematical Society Lecture Note Series 141.","DOI":"10.1017\/CBO9781107359949.008"},{"key":"ref_88","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1023\/A:1007618624809","article-title":"Some PAC-Bayesian theorems","volume":"37","author":"McAllester","year":"1999","journal-title":"Mach. Learn."},{"key":"ref_89","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1016\/j.aim.2003.11.008","article-title":"Trees and ultrametric spaces: A categorical equivalence","volume":"189","author":"Hughes","year":"2004","journal-title":"Adv. Math."},{"key":"ref_90","doi-asserted-by":"crossref","first-page":"1378","DOI":"10.1007\/s00454-023-00583-0","article-title":"The ultrametric Gromov\u2013Wasserstein distance","volume":"70","author":"Munk","year":"2023","journal-title":"Discret. Comput. Geom."},{"key":"ref_91","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1112\/S0025579314000059","article-title":"A geometric study of Wasserstein spaces: Ultrametrics","volume":"61","author":"Kloeckner","year":"2015","journal-title":"Mathematika"},{"key":"ref_92","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1007\/BF01083191","article-title":"Any separable ultrametric space can be isometrically imbedded in \u21132","volume":"17","author":"Timan","year":"1983","journal-title":"Funct. Anal. Its Appl."},{"key":"ref_93","first-page":"740","article-title":"Isometric embedding of isosceles (non-Archimedean) spaces in Euclidean spaces","volume":"32","author":"Lemin","year":"1985","journal-title":"Sov. Math. Dokl."},{"key":"ref_94","first-page":"1425","article-title":"Characterization, stability and convergence of hierarchical clustering methods","volume":"11","author":"Carlsson","year":"2010","journal-title":"J. Mach. Learn. Res."},{"key":"ref_95","unstructured":"Kravtsova, N. (2024). The NP-hardness of the Gromov\u2013Wasserstein distance. arXiv."},{"key":"ref_96","first-page":"363","article-title":"Entropic Gromov\u2013Wasserstein distances: Stability and algorithms","volume":"25","author":"Rioux","year":"2024","journal-title":"J. Mach. Learn. Res."},{"key":"ref_97","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.jcp.2019.03.040","article-title":"Kernel Flows: From learning kernels from data into the abyss","volume":"389","author":"Owhadi","year":"2019","journal-title":"J. Comput. Phys."},{"key":"ref_98","doi-asserted-by":"crossref","first-page":"132817","DOI":"10.1016\/j.physd.2020.132817","article-title":"Learning dynamical systems from data: A simple cross-validation perspective, part I: Parametric kernel flows","volume":"421","author":"Hamzi","year":"2021","journal-title":"Phys. D Nonlinear Phenom."},{"key":"ref_99","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1016\/0005-1098(78)90005-5","article-title":"Modeling by shortest data description","volume":"14","author":"Rissanen","year":"1978","journal-title":"Automatica"},{"key":"ref_100","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1093\/comjnl\/11.2.185","article-title":"An information measure for classification","volume":"11","author":"Wallace","year":"1968","journal-title":"Comput. J."},{"key":"ref_101","doi-asserted-by":"crossref","first-page":"1034","DOI":"10.1109\/18.86996","article-title":"Minimum complexity density estimation","volume":"37","author":"Barron","year":"1991","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_102","doi-asserted-by":"crossref","unstructured":"Gr\u00fcnwald, P.D. (2007). The Minimum Description Length Principle, MIT Press.","DOI":"10.7551\/mitpress\/4643.001.0001"},{"key":"ref_103","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1109\/18.825807","article-title":"Minimum description length induction, Bayesianism, and Kolmogorov complexity","volume":"46","author":"Li","year":"2000","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_104","doi-asserted-by":"crossref","unstructured":"Hamzi, B., Hutter, M., and Owhadi, H. (Phys. D Nonlinear Phenom., 2026). Bridging algorithmic information theory and machine learning, Part VII: A bidirectional bridge between kernel discrepancies and algorithmic information theory, Phys. D Nonlinear Phenom., Preprint.","DOI":"10.2139\/ssrn.6792413"},{"key":"ref_105","doi-asserted-by":"crossref","first-page":"602","DOI":"10.1016\/S0019-9958(66)80018-9","article-title":"The definition of random sequences","volume":"9","year":"1966","journal-title":"Inf. Control"},{"key":"ref_106","doi-asserted-by":"crossref","unstructured":"Hamzi, B., Hutter, M., and Owhadi, H. (2026). Bridging Algorithmic Information Theory and Machine Learning, Part VIII: Kernel Flows as Random Dynamical Systems and Algorithmic Randomness, California Institute of Technology.","DOI":"10.2139\/ssrn.6792413"},{"key":"ref_107","doi-asserted-by":"crossref","unstructured":"Hamzi, B., Hutter, M., and Owhadi, H. (Phys. D Nonlinear Phenom., 2026). Bridging algorithmic information theory and machine learning, Part IX: Solomonoff\u2013Barron spaces\u2014Extending Barron spaces with universal inductive bias for neural network function classes, Phys. D Nonlinear Phenom., Preprint.","DOI":"10.2139\/ssrn.6792413"},{"key":"ref_108","doi-asserted-by":"crossref","first-page":"120503","DOI":"10.1103\/PhysRevLett.108.120503","article-title":"Extracting dynamical equations from experimental data is NP hard","volume":"108","author":"Cubitt","year":"2012","journal-title":"Phys. Rev. Lett."},{"key":"ref_109","doi-asserted-by":"crossref","unstructured":"Hamzi, B., Hutter, M., and Owhadi, H. (2026). Bridging Algorithmic Information Theory and Machine Learning, Part X: Hardness and Tractability of Kernel-Method Dynamical-System Identification\u2014A Three-Regime Taxonomy, California Institute of Technology.","DOI":"10.2139\/ssrn.6792413"},{"key":"ref_110","unstructured":"Hamzi, B., and Hutter, M. (Phys. D Nonlinear Phenom., 2026). Rademacher complexity through the lens of Kolmogorov complexity\u2014How hypothesis classes compress random labels, Phys. D Nonlinear Phenom., Preprint."},{"key":"ref_111","doi-asserted-by":"crossref","unstructured":"Owhadi, H., and Scovel, C. (2019). Operator-Adapted Wavelets, Fast Solvers, and Numerical Homogenization, Cambridge University Press.","DOI":"10.1017\/9781108594967"},{"key":"ref_112","doi-asserted-by":"crossref","unstructured":"Hamzi, B., Hutter, M., and Owhadi, H. (2026). Bridging Algorithmic Information Theory and Machine Learning, Part XII: Operator-Adapted Multiresolution for Solomonoff Kernels, California Institute of Technology.","DOI":"10.2139\/ssrn.6792413"},{"key":"ref_113","unstructured":"Hamzi, B., and Hutter, M. (2026, August 12). Computable approaches to Solomonoff induction: A survey from universal prediction to kernels, operators, and metric\u2013measure geometry. ResearchGate, Available online: https:\/\/www.researchgate.net\/publication\/411054925_Computable_Approaches_to_Solomonoff_Induction_A_Survey_from_Universal_Prediction_to_Kernels_Operators_and_Category-Native_Projections."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/28\/9\/1005\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,9,10]],"date-time":"2026-09-10T04:43:39Z","timestamp":1789015419000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/28\/9\/1005"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,9,8]]},"references-count":113,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2026,9]]}},"alternative-id":["e28091005"],"URL":"https:\/\/doi.org\/10.3390\/e28091005","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,9,8]]}}}