LP-based Construction of DC Decompositions for Efficient Inference of Markov Random Fields

Chaitanya Murti, Dhruva Kashyap, Chiranjib Bhattacharyya
Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:3781-3789, 2024.

Abstract

The success of the convex-concave procedure (CCCP), a widely used technique for non-convex optimization, crucially depends on finding a decomposition of the objective function as a difference of convex functions (dcds). Despite the widespread applicability of CCCP, finding such dcds has attracted little attention in machine learning. For graphical models with polynomial potentials, existing methods for finding dcds require solving a Sum-of-Squares (SOS) program, which is often prohibitively expensive. In this work, we leverage tools from algebraic geometry certifying the positivity of polynomials, to derive LP-based constructions of dcds of polynomials which are particularly suited for graphical model inference. Our experiments demonstrate that using our LP-based technique constructs dcds for polynomial potentials of Markov random fields significantly faster compared to SOS-based approaches used in previous works.

Cite this Paper

BibTeX
@InProceedings{pmlr-v238-murti24a, title = {{LP}-based Construction of {DC} Decompositions for Efficient Inference of {M}arkov Random Fields}, author = {Murti, Chaitanya and Kashyap, Dhruva and Bhattacharyya, Chiranjib}, booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics}, pages = {3781--3789}, year = {2024}, editor = {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen}, volume = {238}, series = {Proceedings of Machine Learning Research}, month = {02--04 May}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v238/murti24a/murti24a.pdf}, url = {https://proceedings.mlr.press/v238/murti24a.html}, abstract = {The success of the convex-concave procedure (CCCP), a widely used technique for non-convex optimization, crucially depends on finding a decomposition of the objective function as a difference of convex functions (dcds). Despite the widespread applicability of CCCP, finding such dcds has attracted little attention in machine learning. For graphical models with polynomial potentials, existing methods for finding dcds require solving a Sum-of-Squares (SOS) program, which is often prohibitively expensive. In this work, we leverage tools from algebraic geometry certifying the positivity of polynomials, to derive LP-based constructions of dcds of polynomials which are particularly suited for graphical model inference. Our experiments demonstrate that using our LP-based technique constructs dcds for polynomial potentials of Markov random fields significantly faster compared to SOS-based approaches used in previous works.} }
Endnote
%0 Conference Paper %T LP-based Construction of DC Decompositions for Efficient Inference of Markov Random Fields %A Chaitanya Murti %A Dhruva Kashyap %A Chiranjib Bhattacharyya %B Proceedings of The 27th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2024 %E Sanjoy Dasgupta %E Stephan Mandt %E Yingzhen Li %F pmlr-v238-murti24a %I PMLR %P 3781--3789 %U https://proceedings.mlr.press/v238/murti24a.html %V 238 %X The success of the convex-concave procedure (CCCP), a widely used technique for non-convex optimization, crucially depends on finding a decomposition of the objective function as a difference of convex functions (dcds). Despite the widespread applicability of CCCP, finding such dcds has attracted little attention in machine learning. For graphical models with polynomial potentials, existing methods for finding dcds require solving a Sum-of-Squares (SOS) program, which is often prohibitively expensive. In this work, we leverage tools from algebraic geometry certifying the positivity of polynomials, to derive LP-based constructions of dcds of polynomials which are particularly suited for graphical model inference. Our experiments demonstrate that using our LP-based technique constructs dcds for polynomial potentials of Markov random fields significantly faster compared to SOS-based approaches used in previous works.
APA
Murti, C., Kashyap, D. & Bhattacharyya, C.. (2024). LP-based Construction of DC Decompositions for Efficient Inference of Markov Random Fields. Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 238:3781-3789 Available from https://proceedings.mlr.press/v238/murti24a.html.

Related Material