1 September 2020 in Operations Research
In several scientific and industrial applications, it is desirable to build compact, interpretable learning models where the output depends on a small number of input features. Recent work has shown that such best-subset selection-type problems can be solved with modern mixed integer optimization solvers. Despite their promise, such solvers often come at a steep computational price when compared with open-source, efficient specialized solvers based on convex optimization and greedy heuristics. In “Fast Best-Subset Selection: Coordinate Descent and Local Combinatorial Optimization Algorithms,” Hussein Hazimeh and Rahul Mazumder push the frontiers of computation for best-subset-type problems. Their algorithms deliver near-optimal solutions for problems with up to a million features—in times comparable with the fast convex solvers. Their work suggests that principled optimization methods play a key role in devising tools central to interpretable machine learning, which can help in gaining a deeper understanding of their statistical properties.
18 October 2021 in Mathematical Programming
1 January 2023 in Operations Research
Learning Compact High-Dimensional Models in Noisy Environments Building compact, interpretable statistical models where the output depends upon a small number of input features is a well-known problem in modern analytics applications. A fundamental tool used in this context is the prominent best subset selection (BSS) procedure, which seeks to obtain the best linear fit to data subject to a constraint on the number of nonzero features. Whereas the BSS procedure works exceptionally well in some regimes, it performs pretty poorly in out-of-sample predictive performance when the underlying data are noisy, which is quite common in practice. In this paper, we explore this relatively less-understood overfitting behavior of BSS in low-signal noisy environments and propose alternatives that appear to mitigate such shortcomings. We study the theoretical statistical properties of our proposed regularized BSS procedure and show promising computational results on various data sets, using tools from integer programming and first-order methods.
24 January 2017 in IEEE Transactions on Information Theory
We propose a novel high-dimensional linear regression estimator: the Discrete Dantzig Selector, which minimizes the number of nonzero regression coefficients subject to a budget on the maximal absolute correlation between the features and residuals. Motivated by the significant advances in integer optimization over the past 10-15 years, we present a mixed integer linear optimization (MILO) approach to obtain certifiably optimal global solutions to this nonconvex optimization problem. The current state of algorithmics in integer optimization makes our proposal substantially more computationally attractive than the least squares subset selection framework based on integer quadratic optimization, recently proposed by Bertsimas et al. and the continuous nonconvex quadratic optimization framework of Liu et al.. We propose new discrete first-order methods, which when paired with the state-of-the-art MILO solvers, lead to good solutions for the Discrete Dantzig Selector problem for a given computational budget. We illustrate that our integrated approach provides globally optimal solutions in significantly shorter computation times, when compared to off-the-shelf MILO solvers. We demonstrate both theoretically and empirically that in a wide range of regimes the statistical properties of the Discrete Dantzig Selector are superior to those of popular ℓ 1 -based approaches. We illustrate that our approach can handle problem instances with p = 10,000 features with certifiable optimality making it a highly scalable combinatorial variable selection approach in sparse linear modeling.
1 May 2022 in Operations Research
Dual Bounds of Sparse Principal Component Analysis Sparse principal component analysis (PCA) is a widely used dimensionality reduction tool in machine learning and statistics. Compared with PCA, sparse PCA enhances the interpretability by incorporating a sparsity constraint. However, unlike PCA, conventional heuristics for sparse PCA cannot guarantee the qualities of obtained primal feasible solutions via associated dual bounds in a tractable fashion without underlying statistical assumptions. In “Using L1-Relaxation and Integer Programming to Obtain Dual Bounds for Sparse PCA,” Santanu S. Dey, Rahul Mazumder, and Guanyi Wang present a convex integer programming (IP) framework of sparse PCA to derive dual bounds. They show the worst-case results on the quality of the dual bounds provided by the convex IP. Moreover, the authors empirically illustrate that the proposed convex IP framework outperforms existing sparse PCA methods of finding dual bounds.
2 March 2019 in Mathematical Programming