Degrees of freedom in submodular regularization: A computational perspective of Stein’s unbiased risk estimate

Kentaro Minami

Journal of Multivariate Analysis, 2020, vol. 175, issue C

Abstract: Degrees of freedom is a covariance penalty related to penalized model selection procedures such as Mallows’ Cp and AIC. We study the degrees of freedom of two polyhedral convex regularization classes defined through submodular functions called the Lovász extension regularization and submodular norm regularization. It has been pointed out that submodular regularization contains many existing penalties that induce structural sparsity. In this paper, we show that the degrees of freedom of submodular regularization estimators can be represented in terms of partitions induced by the estimators. Our formula does not depend on the choice of the design matrix and the penalty function. Moreover, if the design matrix has full column rank, calculating an unbiased estimator of the degrees of freedom requires an additional computational cost of only O(plogp) after a solution for the estimator is obtained, where p is the dimension of the parameter. Existing results for some regularization and projection type estimators, such as the lasso, the fused lasso, and the isotonic regression, are also recovered.

Keywords: Degrees of freedom; Fused lasso; Lasso; Mallows’ Cp; SLOPE; Stein’s unbiased risk estimate; Structured sparse estimation; Submodular function (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0047259X18305906
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jmvana:v:175:y:2020:i:c:s0047259x18305906

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.jmva.2019.104546

Access Statistics for this article

Journal of Multivariate Analysis is currently edited by de Leeuw, J.

More articles in Journal of Multivariate Analysis from Elsevier
Bibliographic data for series maintained by Catherine Liu ().