Tensor cross interpolation for global discrete optimization with application to Bayesian network inference

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription or Fee Access

Abstract

Global discrete optimization is notoriously difficult due to the lack of gradient information and the curse of dimensionality, making exhaustive search infeasible. Tensor cross approximation is an efficient technique to approximate multivariate tensors (and discretized functions) by tensor product decompositions based on a small number of tensor elements, evaluated on adaptively selected fibers of the tensor, that intersect on submatrices of (nearly) maximum volume. The submatrices of maximum volume are empirically known to contain large elements, hence the entries selected for cross interpolation can also be good candidates for the globally maximal element within the tensor. In this paper we consider evolution of epidemics on networks, and infer the contact network from observations of network nodal states over time. By numerical experiments we demonstrate that the contact network can be inferred accurately by finding the global maximum of the likelihood using tensor cross interpolation. The proposed tensor product approach is flexible and can be applied to global discrete optimization for other problems, e.g. discrete hyperparameter tuning.

About the authors

S. Dolgov

University of Bath

Email: S.Dolgov@bath.ac.uk
Bath, United Kingdom

D. Savostyanov

University of Essex

Email: D.Savostyanov@essex.ac.uk
Colchester, United Kingdom

References

  1. Tu Z., Lu Y. A robust stochastic genetic algorithm (StGA) for global numerical optimization // IEEE Trans Evolutionary Computation 8 (5) (2004) 456–470. https://doi.org/10.1109/TEVC.2004.831258
  2. Venkatraman S., Yen G. A generic framework for constrained optimization using genetic algorithms // IEEE Trans Evolutionary Computation 9 (4) (2005) 424–435. https://doi.org/10.1109/TEVC.2005.846817
  3. Weise T. Global optimization algorithms — theory and application, Self-Published Thomas Weise, 2009.
  4. Ha S.-Y., Jin S., Kim D. Convergence and error estimates for time–discrete consensus–based optimization algorithms // Numer. Math. 147 (2021) 255–282. https://doi.org/10.1007/s00211-021-01174-y
  5. Totzeck C. Trends in consensus–based optimization, in: N. Bellomo, J. A. Carrillo, E. Tadmor (Eds.), Active Particles, Volume 3: Advances in Theory, Models, and Applications, Springer, 2022, pp. 201–226. https://doi.org/10.1007/978-3-030-93302-9_6
  6. Kalise D., Sharma A., Tretyakov M.V. Consensus-based optimization via jump-diffusion stochastic differential equations // Mathematical Models and Methods in Applied Sciences 33 (02) (2023) 289–339. https://doi.org/10.1142/S0218202523500082
  7. Borghi G., Herty M., Pareschi L. Constrained consensus–based optimization // SIAM J Optimization 33 (1) (2023) 211–236. https://doi.org/10.1137/22M1471304
  8. Huang H., Qiu J., Riedl K. Consensus–based optimization for saddle point problems // SIAM J Control and Optimization 62 (2) (2024) 1093–1121. https://doi.org/10.1137/22M1543367
  9. Fornasier M., Klock T., Riedl K. Consensus–based optimization methods converge globally // SIAM J Optimization 34 (3) (2024) 2973–3004. https://doi.org/10.1137/22M1527805
  10. Jensen H., Jerez D., Valdebenito M. An adaptive scheme for reliability–based global design optimization: A Markov chain Monte Carlo approach // Mechanical Systems and Signal Processing 143 (2020) 106836. https://doi.org/10.1016/j.ymssp.2020.106836
  11. Jensen H., Jerez D., Beer M. A general two–phase Markov chain Monte Carlo approach for constrained design optimization: Application to stochastic structural optimization // Computer Methods in Applied Mechanics and Engineering 373 (2021) 113487. https://doi.org/10.1016/j.cma.2020.113487
  12. Oseledets I.V. Tensor-train decomposition // SIAM J. Sci. Comput. 33 (5) (2011) 2295–2317. https://doi.org/10.1137/090752286
  13. Hackbusch W. Tensor Spaces And Numerical Tensor Calculus, Springer–Verlag, Berlin, 2012.
  14. Oseledets I.V., Tyryshnikov E.E. TT-cross approximation for multidimensional arrays // Linear Algebra Appl. 432 (1) (2010) 70–88. https://doi.org/10.1016/j.laa.2009.07.024
  15. Savostyanov D.V. Quasioptimality of maximum–volume cross interpolation of tensors // Linear Algebra Appl. 458 (2014) 217–244. https://doi.org/10.1016/j.laa.2014.06.006
  16. Dolgov S., Savostyanov D. Parallel cross interpolation for high–precision calculation of high–dimensional integrals // Comp. Phys. Comm. 246 (2020) 106869. https://doi.org/10.1016/j.cpc.2019.106869
  17. Harshman R.A. Foundations of the PARAFAC procedure: models and conditions for an explanatory multimodal factor analysis, UCLA Working Papers in Phonetics 16 (1970) 1–84.
  18. Caroll J.D., Chang J.J. Analysis of individual differences in multidimensional scaling via n-way generalization of Eckart–Young decomposition // Psychometrika 35 (1970) 283–319. https://doi.org/10.1007/BF02310791
  19. Kroonenberg P., de Leeuw J. Principal component analysis of three-mode data by means of alternating least squares algorithms // Psychometrika 45 (1) (1980) 69–97.
  20. Wang J.-H., Hopke P.K., Hancewicz T.M., Zhang S.L. Application of modified least squares regression to spectroscopic image analysis // Analyse Chim. Acta. 476 (2003) 93–109.
  21. Schollwöck U. The density-matrix renormalization group in the age of matrix product states // Annals of Physics 326 (1) (2011) 96–192. https://doi.org/10.1016/j.aop.2010.09.012
  22. Dolgov S.V., Savostyanov D.V. Alternating minimal energy methods for linear systems in higher dimensions // SIAM J. Sci. Comput. 36 (5) (2014) A2248–A2271. https://doi.org/10.1137/140953289
  23. Hubig C., McCulloch I.P., Schollwöck U., Wolf F.A. Strictly single-site DMRG algorithm with subspace expansion, Phys. Rev. B 91 (15) (2015) 155115. https://doi.org/10.1103/PhysRevB.91.155115
  24. Goreinov S.A., Zamarashkin N.L., Tyryshnikov E.E. Pseudo–skeleton approximations by matrices of maximum volume // Mathematical Notes 62 (4) (1997) 515–519. https://doi.org/10.1007/BF02358985
  25. Goreinov S.A., Oseledets I.V., Savostyanov D.V., Tyryshnikov E.E., Zamarashkin N.L. How to find a good submatrix, in: V. Olshevsky, E. Tyryshnikov (Eds.), Matrix Methods: Theory, Algorithms, Applications, World Scientific, Hackensack, NY, 2010, pp. 247–256.
  26. Zhelikov D.A., Oferkin I.V., Kaikova E.V., Sulimov A.V., Sulimov V.B., Tyryshnikov E.E. TTDock: a docking method based on tensor train decompositions // Numerical Methods and Programming 14 (3) (2013) 279–291. URL: http://mi.mathnet.ru/vmp114
  27. Suliinov A.V., Zheltkov D.A., Oferkin I.V., Kutov D.C., Katkova E.V., Tyryshnikov E.E., Suliinov V.B. Evaluation of the novel algorithm of flexible ligand docking with moveable target-protein atoms // Computational and Structural Biotechnology Journal 15 (2017) 275–285. https://doi.org/10.1016/j.csbj.2017.02.004
  28. Suliinov A., Kutov D., Ilin I., Zheltkov D., Tyryshnikov E., Suliinov V. Supercomputer docking with a large number of degrees of freedom, SAR and QSAR in Environmental Research 30 (10) (2019) 733–749. https://doi.org/10.1080/1062936X.2019.1659412
  29. Zheltkov D.A., Osinsky A. Global optimization algorithms using tensor trains, in: I. Lirkov, S. Margenov (Eds.), Large-Scale Scientific Computing, Springer International Publishing, Cham, 2020, pp. 197–202.
  30. Zheltkov D., Tyryshnikov E. Global optimization based on TT-decomposition // Russian Journal of Numerical Analysis and Mathematical Modelling 35 (4) (2020) 247–261. https://doi.org/10.1515/mam-2020-0021
  31. Sozykin K., Chertkov A., Schutski R., Phan A.-H., Cichocki A.S., Oseledets I. TTOpt: A maximum volume quantized tensor train-based optimization and its application to reinforcement learning, in: Advances in Neural Information Processing Systems, Vol. 35, 2022, pp. 26052–26065.
  32. Gillespie D.T. A general method for numerically simulating the stochastic time evolution of coupled chemical reactions // J Comput. Phys. 22 (4) (1976) 403–434. https://doi.org/10.1016/0021-9991(76)90041-3
  33. Dolgov S., Savostyanov D. Tensor product algorithms for inference of contact network from epidemiological data, BMC Bioinformatics 25, article no. 285 (2024). https://doi.org/10.1186/s12859-024-05910-7
  34. van Kampen N.G. Stochastic processes in physics and chemistry, North Holland, Amsterdam, 1981.
  35. Chen W.-Y., Bokka S. Stochastic modeling of nonlinear epidemiology // Journal of Theoretical Biology 234 (4) (2005) 455–470. https://doi.org/10.1016/j.jtbi.2004.11.033
  36. Gillespie D.T. Approximate accelerated stochastic simulation of chemically reacting systems // The Journal of Chemical Physics 115 (4) (2001) 1716–1733. https://doi.org/10.1063/1.1378322
  37. Hemberg M., Barahona M. Perfect sampling of the master equation for gene regulatory networks // Biophysical journal 93 (2) (2007) 401–410. https://doi.org/10.1529/biophysj.106.099390
  38. Anderson D.F., Higham D.J. Multilevel Monte Carlo for continuous time Markov chains, with applications in biochemical kinetics // Multiscale Modeling & Simulation 10 (1) (2012) 146–179. https://doi.org/10.1137/110840546
  39. Lester C., Baker R.E., Giles M.B., Yates C.A. Extending the multi-level method for the simulation of stochastic biological systems // Bulletin of Mathematical Biology 78 (8) (2016) 1640–1677. https://doi.org/10.1007/s11538-016-0178-9
  40. Hegland M., Burden C., Santoso L., MacNamara S., Booth H. A solver for the stochastic master equation applied to gene regulatory networks // Journal of Computational and Applied Mathematics 205 (2) (2007) 708–724. https://doi.org/10.1016/j.cam.2006.02.053
  41. Munsky B., Khammash M. The finite state projection algorithm for the solution of the chemical master equation // The Journal of chemical physics 124 (2006) 044104. https://doi.org/10.1063/1.2145882
  42. Jahnke T. An adaptive wavelet method for the chemical master equation // SIAM J. Sci. Comput. 31 (6) (2010) 4373. https://doi.org/10.1137/080742324
  43. Cao Y., Terebus A., Liang J. State space truncation with quantified errors for accurate solutions to discrete chemical master equation // Bulletin of Mathematical Biology 78 (4) (2016) 617–661. https://doi.org/10.1007/s11538-016-0149-1
  44. Kryven I., Roblitz S., Schutte C. Solution of the chemical master equation by radial basis functions approximation with interface tracking // BMC Systems Biology 9 (1) (2015) 67. https://doi.org/10.1186/s12918-015-0210-y
  45. Gupta A., Schwab C., Khammash M. DeepCME: A deep learning framework for computing solution statistics of the chemical master equation // PLoS Comput Biol 17 (12) (2021) e1009623. https://doi.org/10.1371/journal.pcbi.1009623
  46. Sukys A., Öcal K., Grima R. Approximating solutions of the chemical master equation using neural networks, iScience 25 (2022) 105010. https://doi.org/10.1016/j.isci.2022.105010
  47. Jahnke T., Huisinga W. A dynamical low-rank approach to the chemical master equation // Bulletin of Mathematical Biology 70 (2008) 2283--2302. https://doi.org/10.1007/s11538-008-9346-x
  48. Ammar A., Cueto E., Chinesta F. Reduction of the chemical master equation for gene regulatory networks using proper generalized decompositions // Int. J. Numer. Meth. Biomed. Engng. 28 (9) (2012) 960–973. https://doi.org/10.1002/cnm.2476
  49. Hegland M., Garcke J. On the numerical solution of the chemical master equation with sums of rank one tensors, ANZIAM 52 (2011) C628--C643. https://doi.org/10.21914/anziamj.v52i0.3895
  50. Kazeev V., Khammash M., Nip M., Schwab C. Direct solution of the Chemical Master Equation using Quantized Tensor Trains // PLOS Computational Biology 10 (3) (2014) e100359. https://doi.org/10.1371/journal.pcbi.1003359
  51. Dolgov S., Khoromskij B. Simultaneous state-time approximation of the chemical master equation using tensor product formats // Numer. Linear Algebra Appl. 22 (2) (2015) 197–219. https://doi.org/10.1002/nla.1942
  52. Dolgov S.V. A tensor decomposition algorithm for large ODEs with conservation laws // Computational Methods in Applied Mathematics 19 (2019) 23–38. https://doi.org/10.1515/cmam-2018-0023
  53. Vo H.D., Sidje R.B. An adaptive solution to the chemical master equation using tensors // The Journal of Chemical Physics 147 (4) (2017) 044102. https://doi.org/10.1063/1.4994917
  54. Dinh T., Sidje R.B. An adaptive solution to the chemical master equation using quantized tensor trains with sliding windows // Physical Biology 17 (6) (2020) 065014. https://doi.org/10.1088/1478-3975/aba1d2
  55. Ion I.G., Widmer C., Loukrezis D., Koeppl H., De Gersem H. Tensor-train approximation of the chemical master equation and its application for parameter inference // The Journal of Chemical Physics 155 (3) (2021) 034102. https://doi.org/10.1063/5.0045521
  56. GelB P., Matera S., Schütte C. Solving the master equation without kinetic Monte Carlo: Tensor train approximations for a CO oxidation model // Journal of Computational Physics 314 (2016) 489--502. https://doi.org/10.1016/j.jcp.2016.03.025
  57. Dolgov S., Savostyanov D. Tensor product approach to modelling epidemics on networks // Applied Mathematics and Computation 460 (2024) 128290. https://doi.org/10.1016/j.amc.2023.128290
  58. Goreinov S.A., Tyryshnikov E.E., Zamarashkin N.L. A theory of pseudo-skeleton approximations // Linear Algebra Appl. 261 (1997) 1--21. https://doi.org/10.1016/S0024-3795(96)00301-1
  59. Schneider J. Error estimates for two-dimensional cross approximation // J. Approx. Theory 162 (2010) 1685--1700. https://doi.org/10.1016/j.jat.2010.04.012
  60. Goreinov S.A., Tyryshnikov E.E. Quasiopitinality of skeleton approximation of a matrix in the Chebyshev norm // Doklady Math. 83 (3) (2011) 374--375. https://doi.org/10.1134/S1064562411030355
  61. Zamarashkin N.L., Osinsky A.I. New accuracy estimates for pseudoskeleton approximations of matrices // Doklady Mathematics 94 (3) (2016) 643--645. https://doi.org/10.1134/S1064562416060156
  62. Mikhalev A.Y., Oseledets I.V. Rectangular maximum--volume submatrices and their applications // Linear Algebra Appl. 538 (2018) 187--211. https://doi.org/10.1016/j.laa.2017.10.014
  63. Bartholdi III J.J. A good submatrix is hard to find, Operations Research Lett. 1 (5) (1982) 190--193.
  64. Tyryshnikov E.E. Incomplete cross approximation in the mosaic--skeleton method // Computing 64 (4) (2000) 367--380. https://doi.org/10.1007/s006070070031
  65. Rakhuba M.V., Oseledets I.V. Grid-based electronic structure calculations: the tensor decomposition approach // J. Comput. Phys. (2016). https://doi.org/10.1016/j.jcp.2016.02.023 URL: http://arxiv.org/abs/1508.07632
  66. Dolgov S., Anaya-Izquierdo K., Fox C., Scheichl R. Approximation and sampling of multivariate probability distributions in the tensor train decomposition // Statistics and Computing 30 (2020) 603--625. https://doi.org/10.1007/s11222-019-09910-z
  67. Cui T., Dolgov S. Deep composition of Tensor Trains using squared inverse Rosenblatt transports, arXiv preprint 2007.06968 (2020). URL: http://arxiv.org/abs/2007.06968
  68. Dolgov S., Kalise D., Saluzzi L. Data-driven Tensor Train gradient cross approximation for Hamilton–Jacobi–Bellman equations // SIAM Journal on Scientific Computing 45 (5) (2023) A2153–A2184. https://doi.org/10.1137/22M1498401
  69. Antil H., Dolgov S., Onwanta A. TTRISK: Tensor train decomposition algorithm for risk averse optimization // Numerical Linear Algebra with Applications 30 (3) (2023) e2481. https://doi.org/https://doi.org/10.1002/nla.2481
  70. Bebendorf M. Approximation of boundary element matrices // Numer. Math 86 (4) (2000) 565–589. https://doi.org/10.1007/p00005410
  71. Golub G.H., Van Loan C.F. Matrix Computations, Johns Hopkins University Press, Baltimore, MD, 2013.
  72. Neal L., Poole G. A geometric analysis of Gaussian elimination. II // Linear Alg. Appl. 173 (1992) 239–264. https://doi.org/10.1016/0024-3795(92)90432-A
  73. Goreinov S.A., Tyrtyshnikov E.E. The maximal-volume concept in approximation by low-rank matrices // Contemporary Mathematics 280 (2001) 47–51.
  74. Petrov S., Zamarashkin N. Sufficient recovery conditions for noise-buried low rank tensors, Tech. Rep. arXiv:2312.02088, arXiv (2023). URL: https://arxiv.org/abs/2312.02088

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2025 Russian Academy of Sciences