Solution Path of Time-Varying Markov Random Fields with Discrete Regularization

References

• Ahuja RK, Hochbaum DS, Orlin JB (2004) A cut-based algorithm for the nonlinear dual of the minimum cost network flow problem. Algorithmica 39(3):189–208.Crossref, Google Scholar
• Atamtürk A, Gómez A (2018) Strong formulations for quadratic optimization with m-matrices and indicator variables. Math. Programming 170(1):141–176.Crossref, Google Scholar
• Atamtürk A, Gómez A, Han S (2021) Sparse and smooth signal estimation: Convexification of ℓ0-formulations. J. Machine Learn. Res. 22(52):1–43.Google Scholar
• Bach F (2019) Submodular functions: From discrete to continuous domains. Math. Programming 175(1–2):419–459.Crossref, Google Scholar
• Beck A, Teboulle M (2009) Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems. IEEE Trans. Image Processing 18(11):2419–2434.Crossref, Google Scholar
• Bertsimas D, Lamperski J, Pauphilet J (2020) Certifiably optimal sparse inverse covariance estimation. Math. Programming 184(1):491–530.Crossref, Google Scholar
• Bhathena A, Fattahi S, Gómez A, Küçükyavuz S (2024) A parametric approach for solving convex quadratic optimization with indicators over trees. Preprint, submitted April 12, https://arxiv.org/abs/2404.08178.Google Scholar
• Bresler G, Gamarnik D, Shah D (2014) Hardness of parameter estimation in graphical models. Adv. Neural Inform. Processing Systems 27:1062–1070.Google Scholar
• Cai B, Zhang G, Zhang A, Stephen JM, Wilson TW, Calhoun VD, Wang YP (2018) Capturing dynamic connectivity from resting state fmri using time-varying graphical lasso. IEEE Trans. Biomedical Engrg. 66(7):1852–1862.Crossref, Google Scholar
• Campajola C, Gangi DD, Lillo F, Tantari D (2022) Modelling time-varying interactions in complex systems: The score driven kinetic ising model. Sci. Rep. 12(1):19339.Crossref, Google Scholar
• Chekuri C, Khanna S, Naor J, Zosin L (2004) A linear programming formulation and approximation algorithms for the metric labeling problem. SIAM J. Discrete Math. 18(3):608–625.Crossref, Google Scholar
• Crandall D, Felzenszwalb P, Huttenlocher D (2005) Spatial priors for part-based recognition using statistical models. Proc. IEEE Comput. Soc. Conf. Comput. Vision Pattern Recognition, vol. 1 (IEEE Computer Society, Washington, DC), 10–17.Google Scholar
• Danaher P, Wang P, Witten DM (2014) The joint graphical lasso for inverse covariance estimation across multiple classes. J. Roy. Statist. Soc.: Ser. B (Statist. Methodology) 76(2):373–397.Crossref, Google Scholar
• Fattahi S, Gomez A (2021) Scalable inference of sparsely changing Gaussian Markov random fields. Adv. Neural Inform. Processing Systems 34:6529–6541.Google Scholar
• Fattahi S, Gómez A (2023) Solution path of time-varying markov random fields with discrete regularization. Preprint, submitted July 25, https://arxiv.org/abs/2307.13750.Google Scholar
• Fattahi S, Gomez A (2025) Solution path of time-varying Markov random fields with discrete regularization. https://doi.org/10.1287/ijoc.2024.0850.cd, https://github.com/INFORMSJoC/2024.0850.Google Scholar
• Fattahi S, Sojoudi S (2019) Graphical lasso and thresholding: Equivalence and closed-form solutions. J. Machine Learn. Res. 20(1):364–407.Google Scholar
• Foygel R, Drton M (2010) Extended Bayesian information criteria for Gaussian graphical models. Adv. Neural Inform. Processing Systems 23:604–612.Google Scholar
• Greenewald K, Park S, Zhou S, Giessing A (2017) Time-dependent spatially varying graphical models, with application to brain fmri data analysis. Adv. Neural Inform. Processing Systems 30:5832–5840.Google Scholar
• Hallac D, Park Y, Boyd S, Leskovec J (2017) Network inference via the time-varying graphical lasso. Proc. 23rd ACM SIGKDD Internat. Conf. Knowledge Discovery and Data Mining (Association for Computing Machinery, New York), 205–213.Google Scholar
• Hochbaum DS (2001) An efficient algorithm for image segmentation, Markov random fields and related problems. J. ACM 48(4):686–701.Crossref, Google Scholar
• Hsieh CJ, Sustik MA, Dhillon IS, Ravikumar P (2014) QUIC: Quadratic approximation for sparse inverse covariance estimation. J. Machine Learn. Res. 15(1):2911–2947.Google Scholar
• Hsieh CJ, Sustik MA, Dhillon IS, Ravikumar PK, Poldrack R (2013) BIG & QUIC: Sparse inverse covariance estimation for a million variables. Adv. Neural Inform. Processing Systems 26:3165–3173.Google Scholar
• Kalman RE (1960) A new approach to linear filtering and prediction problems. J. Basic Engrg. 82(1):35–45.Google Scholar
• Kolar M, Xing E (2011) On time varying undirected graphs. Proc. 14th Internat. Conf. Artificial Intelligence Statist. (JMLR.org), 407–415.Google Scholar
• Kolar M, Xing EP (2012) Estimating networks with jumps. Electronic J. Statist. 6:2069.Crossref, Google Scholar
• Lam C, Fan J (2009) Sparsistency and rates of convergence in large covariance matrix estimation. Ann. Statist. 37(6B):4254.Crossref, Google Scholar
• Lauritzen SL (1996) Graphical Models, vol. 17 (Clarendon Press, Oxford, UK).Crossref, Google Scholar
• Liu S, Fukumizu K, Suzuki T (2017) Learning sparse structural changes in high-dimensional Markov networks. Behaviormetrika 44(1):265–286.Crossref, Google Scholar
• Liu P, Fattahi S, Gómez A, Küçükyavuz S (2022) A graph-based decomposition method for convex quadratic optimization with indicators. Math. Programming 200(2):669--701.Google Scholar
• MacKay M, Vicol P, Lorraine J, Duvenaud D, Grosse R (2019) Self-tuning networks: Bilevel optimization of hyperparameters using structured best-response functions. Preprint, submitted March 7, https://arxiv.org/abs/1903.03088.Google Scholar
• Mairal J, Yu B (2012) Complexity analysis of the lasso regularization path. Proc. 29th Internat. Conf. Machine Learn. (JMLR.org), 1835–1842.Google Scholar
• Mohan K, London P, Fazel M, Witten D, Lee SI (2014) Node-based learning of multiple Gaussian graphical models. J. Machine Learn. Res. 15(1):445–488.Google Scholar
• Natarajan BK (1995) Sparse approximate solutions to linear systems. SIAM J. Comput. 24(2):227–234.Crossref, Google Scholar
• Neath AA, Cavanaugh JE (2012) The Bayesian information criterion: Background, derivation, and applications. Wiley Interdisciplinary Rev. Comput. Statist. 4(2):199–203.Crossref, Google Scholar
• Potra FA, Wright SJ (2000) Interior-point methods. J. Comput. Appl. Math. 124(1–2):281–302.Crossref, Google Scholar
• Qiu H, Han F, Liu H, Caffo B (2016) Joint estimation of multiple graphical models from high dimensional time series. J. R Statist. Soc. Ser. B Statist. Methodology 78(2):487.Crossref, Google Scholar
• Ravikumar P, Lafferty J (2006) Quadratic programming relaxations for metric labeling and Markov random field map estimation. Proc. 23rd Internat. Conf. Machine Learn. (Association for Computing Machinery, New York), 737–744.Google Scholar
• Ravikumar V, Xu T, Al-Holou WN, Fattahi S, Rao A (2023) Efficient inference of spatially-varying Gaussian Markov random fields with applications in gene regulatory networks. IEEE/ACM Trans. Comput. Biology Bioinform. 20(5):2920--2932.Crossref, Google Scholar
• Roy S, Atchadé Y, Michailidis G (2017) Change point estimation in high dimensional Markov random-field models. J. Roy. Statist. Soc. Ser. B Statist. Methodology 79(4):1187.Crossref, Google Scholar
• Sinha A, Malo P, Xu P, Deb K (2014) A bilevel optimization approach to automated parameter tuning. Proc. Annual Conf. Genetic Evolutionary Comput. (Association for Computing Machinery, New York), 847–854.Google Scholar
• Spaen Q, Asín-Achá R, Chettih SN, Minderer M, Harvey C, Hochbaum DS (2019) HNCcorr: A novel combinatorial approach for cell identification in calcium-imaging movies. eNeuro 6(2):ENEURO.0304-18.Crossref, Google Scholar
• Talih M, Hengartner N (2005) Structural learning with time-varying components: Tracking the cross-section of financial time series. J. Roy. Statist. Soc.: Ser. B (Statist. Methodology) 67(3):321–341.Crossref, Google Scholar
• Wainwright MJ (2002) Stochastic processes on graphs with cycles: Geometric and variational approaches. PhD thesis, Massachusetts Institute of Technology, Cambridge.Google Scholar
• Wainwright MJ, Jordan MI (2008) Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learn. 1(1–2):1–305.Google Scholar
• Wainwright MJ, Jaakkola TS, Willsky AS (2003) Tree-reweighted belief propagation algorithms and approximate ml estimation by pseudo-moment matching. Internat. Workshop Artificial Intelligence Statist. 3:1–8.Google Scholar
• Wang B, Qi Y, et al. (2018) Fast and scalable learning of sparse changes in high-dimensional gaussian graphical model structure. Proc. Internat. Conf. Artificial Intelligence Statist. (PMLR, New York), 1691–1700.Google Scholar
• Weiss Y, Freeman WT (2000) Correctness of belief propagation in Gaussian graphical models of arbitrary topology. Adv. Neural Inform. Processing Systems 13:673–679.Google Scholar
• Yang E, Lozano AC, Ravikumar PK (2014) Elementary estimators for graphical models. Adv. Neural Inform. Processing Systems 27:2159–2167.Google Scholar
• Yu S, Huang D, Singer W, Nikolić D (2008) A small world of neuronal synchrony. Cerebral Cortex 18(12):2891–2901.Crossref, Google Scholar
• Zhao SD, Cai TT, Li H (2014) Direct estimation of differential networks. Biometrika 101(2):253–268.Crossref, Google Scholar
• Zhou S, Lafferty J, Wasserman L (2010) Time varying undirected graphs. Machine Learn. 80(2–3):295–319.Crossref, Google Scholar