SCIENTIA SINICA Informationis, Volume 46, Issue 9: 1276-1287(2016) https://doi.org/10.1360/N112016-00045

Decomposition-based Pareto optimization for subset selection

Chao QIAN1,2,3, Zhi-Hua ZHOU1,2,*
More info
  • ReceivedMar 3, 2016
  • AcceptedApr 22, 2016
  • PublishedSep 2, 2016


In many machine-learning tasks, subset selection, which selects a few variables from a large set, is a fundamental problem; it is, however, NP-hard. The recently emerged Pareto Optimization for Subset Selection (POSS) method is a powerful approximation solver for this problem. However, the POSS running time can be unsatisfactory when the problem size is large, restricting its large-scale applications. In this paper, we propose the DPOSS method, which uses a decomposition strategy. DPOSS decomposes the entire subset space into several subspaces, and then sequentially applies the POSS method. Our theoretical analysis shows that DPOSS can achieve the same approximation guarantee as POSS, while superlinearly reducing its running time with respect to the number of decompositions. Empirical studies show that DPOSS's actual running time decreases superlinearly, and the quality of the produced solution has a little loss. However, it is still better than the greedy algorithm, the previous algorithm with the best known theoretical guarantee.

Funded by




[1] Gu M, Eisenstat S C. Efficient algorithms for computing a strong rank-revealing QR factorization. SIAM J Sci Comput, 1996, 17: 848-869 CrossRef Google Scholar

[2] Zhou Z-H. Ensemble Methods: Foundations and Algorithms. Boca Raton: Chapman and Hall/CRC, 2012. Google Scholar

[3] Xie B, Liu Y, Zhang H, et al. Efficient image representation for object recognition via pivots selection. Front Comput Sci, 2015, 9: 383-391 CrossRef Google Scholar

[4] Zhang Y Q, Xiao J S, Li S H, et al. Learning block-structured incoherent dictionaries for sparse representation. Sci China Inf Sci, 2015, 58: 102302. Google Scholar

[5] Davis G, Mallat S, Avellaneda M. Adaptive greedy approximations. Constr Approx, 1997, 13: 57-98 CrossRef Google Scholar

[6] Gilbert A C, Muthukrishnan S, Strauss M J. Approximation of functions over redundant dictionaries using coherence. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, 2003. 243-252. Google Scholar

[7] Tropp J A. Greed is good: algorithmic results for sparse approximation. IEEE Trans Inf Theory, 2004, 50: 2231-2242 CrossRef Google Scholar

[8] Tibshirani R. Regression shrinkage and selection via the lasso. J Royal Stat Soc: Ser B (Methodological), 1996, 58: 267-288. Google Scholar

[9] Zou H, Hastie T. Regularization and variable selection via the elastic net. J Royal Stat Soc: Ser B (Methodological), 2005, 67: 301-320 CrossRef Google Scholar

[10] Yu Y, Yao X, Zhou Z-H. On the approximation ability of evolutionary optimization with application to minimum set cover. Artif Intell, 2012, 180-181: 20-33 CrossRef Google Scholar

[11] Qian C, Yu Y, Zhou Z-H. Pareto ensemble pruning. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence, Austin, 2015. 2935-2941. Google Scholar

[12] Qian C, Yu Y, Zhou Z-H. On constrained Boolean Pareto optimization. In: Proceedings of the 24th International Joint Conference on Artificial Intelligence, Buenos Aires, 2015. 389-395. Google Scholar

[13] Qian C, Yu Y, Zhou Z-H. Subset selection by Pareto optimization. In: Proceedings of Advances in Neural Information Processing Systems 28, Montreal, 2015. 1765-1773. Google Scholar

[14] Miller A. Subset Selection in Regression. 2nd ed. London: Chapman and Hall/CRC, 2002. Google Scholar

[15] Das A, Kempe D. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. In: Proceedings of the 28th International Conference on Machine Learning, Bellevue, 2011. 1057-1064. Google Scholar

[16] Das A, Kempe D. Algorithms for subset selection in linear regression. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, 2008. 45-54. Google Scholar

[17] Qian C, Shi J-C, Yu Y, et al. Parallel Pareto optimization for subset selection. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence, New York, 2016. 1-7. Google Scholar

[18] Natarajan B K. Sparse approximate solutions to linear systems. SIAM J Sci Comput, 1995, 24: 227-234 CrossRef Google Scholar

[19] Diekhoff G. Statistics for the Social and Behavioral Sciences: Univariate, Bivariate, Multivariate. New York: William C Brown Pub, 1992. Google Scholar

[20] Johnson R A, Wichern D W. Applied Multivariate Statistical Analysis. 6th ed. New York: Pearson, 2007. Google Scholar

[21] Tropp J A, Gilbert A C, Muthukrishnan S, et al. Improved sparse approximation over quasiincoherent dictionaries. In: Proceedings of the 11th International Conference on Image Processing, Barcelona, 2003. 37-40. Google Scholar

[22] Shalev-Shwartz S, Srebro N, Zhang T. Trading accuracy for sparsity in optimization problems with sparsity constraints. SIAM J Optimiz, 2010, 20: 2807-2832 CrossRef Google Scholar

[23] Yuan X-T, Yan S. Forward basis selection for pursuing sparse representations over a dictionary. IEEE Trans Pattern Anal Mach Intell, 2013, 35: 3025-3036 CrossRef Google Scholar

[24] Nemhauser G L, Wolsey L A, Fisher M L. An analysis of approximations for maximizing submodular set functions - I. Math Prog, 1978, 14: 265-294 CrossRef Google Scholar

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1       京公网安备11010102003388号