2008-07-09-kwisthout08a.md

title	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_editor	editor	bibtex_author	author	date	note	address	container-title	volume	genre	issued	pdf	extras
The computational complexity of sensitivity analysis and parameter tuning	While known algorithms for sensitivity analysis and parameter tuning in probabilistic networks have a running time that is exponential in the size of the network, the exact computational complexity of these problems has not been established as yet. In this paper we study several variants of the tuning problem and show that these problems are NPPP-complete in general. We further show that the problems remain NP-complete or PP-complete, for a number of restricted variants. These complexity results provide insight in whether or not recent achievements in sensitivity analysis and tuning can be extended to more general, practicable methods.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	kwisthout08a	0	The computational complexity of sensitivity analysis and parameter tuning	349	356	349-356	349	false	McAllester, David A. and Myllym{"a}ki, Petri	given family David A. McAllester given family Petri Myllymäki	Kwisthout, Johan and van der Gaag, Linda C.	given family Johan Kwisthout given family Linda C. van der Gaag	2008-07-09	Reissued by PMLR on 30 October 2024.		Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence	R6	inproceedings	date-parts 2008 7 9	http://proceedings.mlr.press/r6/kwisthout08a/kwisthout08a.pdf