Solving the Best Subset Selection Problem via Suboptimal Algorithms

• URL: http://arxiv.org/abs/2503.24300v1
• Date: Mon, 31 Mar 2025 16:43:33 GMT
• Title: Solving the Best Subset Selection Problem via Suboptimal Algorithms
• Authors: Vikram Singh, Min Sun,
• Abstract summary: We introduce a new procedure and compare it with other popular algorithms to solve the best selection problem.<n>The new procedure is observed to be a competitive suboptimal algorithm for solving the best subset problem.
• Score: 11.965038181120935
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Best subset selection in linear regression is well known to be nonconvex and computationally challenging to solve, as the number of possible subsets grows rapidly with increasing dimensionality of the problem. As a result, finding the global optimal solution via an exact optimization method for a problem with dimensions of 1000s may take an impractical amount of CPU time. This suggests the importance of finding suboptimal procedures that can provide good approximate solutions using much less computational effort than exact methods. In this work, we introduce a new procedure and compare it with other popular suboptimal algorithms to solve the best subset selection problem. Extensive computational experiments using synthetic and real data have been performed. The results provide insights into the performance of these methods in different data settings. The new procedure is observed to be a competitive suboptimal algorithm for solving the best subset selection problem for high-dimensional data.

Related papers

• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  We introduce a novel greedy-style subset selection algorithm for batch acquisition. Our experiments on the red fluorescent proteins show that our proposed method achieves the baseline performance in 1.69x fewer queries.
  arXiv  Detail & Related papers  (2024-06-21T05:57:08Z)
• Dynamic Incremental Optimization for Best Subset Selection [15.8362578568708]
  Best subset selection is considered the gold standard for many learning problems.<n>An efficient subset-dual algorithm is developed based on the primal and dual problem structures.
  arXiv  Detail & Related papers  (2024-02-04T02:26:40Z)
• Equitable and Fair Performance Evaluation of Whale Optimization Algorithm [4.0814527055582746]
  It is essential that all algorithms are exhaustively, somewhat, and intelligently evaluated. evaluating the effectiveness of optimization algorithms equitably and fairly is not an easy process for various reasons.
  arXiv  Detail & Related papers  (2023-09-04T06:32:02Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Solving integer multi-objective optimization problems using TOPSIS, Differential Evolution and Tabu Search [4.213427823201119]
  This paper presents a method to solve nonlinear integer multiobjective optimization problems. First, the problem is formulated using the Technique for Order Preference by Similarity to Ideal Solution (TOPSIS) Next, the Differential Evolution (DE) algorithm in its three versions (standard DE, DEGL, DEGL) are used as DE best and DEGL. Since the solutions found by the DE algorithms are continuous, the Tabu Search (TS) algorithm is employed to find integer solutions during the optimization process.
  arXiv  Detail & Related papers  (2022-04-05T23:59:33Z)
• High dimensional Bayesian Optimization Algorithm for Complex System in Time Series [1.9371782627708491]
  This paper presents a novel high dimensional Bayesian optimization algorithm. Based on the time-dependent or dimension-dependent characteristics of the model, the proposed algorithm can reduce the dimension evenly. To increase the final accuracy of the optimal solution, the proposed algorithm adds a local search based on a series of Adam-based steps at the final stage.
  arXiv  Detail & Related papers  (2021-08-04T21:21:17Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  In many real world problems, we want to infer some property of an expensive black-box function f, given a budget of T function evaluations. We present a procedure, InfoBAX, that sequentially chooses queries that maximize mutual information with respect to the algorithm's output. On these problems, InfoBAX uses up to 500 times fewer queries to f than required by the original algorithm.
  arXiv  Detail & Related papers  (2021-04-19T17:22:11Z)
• Instance Specific Approximations for Submodular Maximization [45.91235224228292]
  We look for methods to benchmark the performance of algorithms against optimal solutions on real-world instances. A major question is how to measure the performance of an algorithm in comparison to an optimal solution on instances we encounter in practice. Our main contribution is not a new algorithm for submodular minimization but an analytical method that measures how close an algorithm for submodular instance is to optimal.
  arXiv  Detail & Related papers  (2021-02-23T19:39:32Z)
• Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
  The predict+optimize problem combines machine learning ofproblem coefficients with a optimization prob-lem that uses the predicted coefficients. We show how to directlyexpress the loss of the optimization problem in terms of thepredicted coefficients as a piece-wise linear function. We propose a novel divide and algorithm to tackle optimization problems without this restriction and predict itscoefficients using the optimization loss.
  arXiv  Detail & Related papers  (2020-12-04T00:26:56Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  We present a meta-algorithm that adapts to the optimal complexity with $tildeO(L5/6 T2/3)$ regret. We also show that the meta-algorithm automatically admits significantly improved instance-dependent regret bounds.
  arXiv  Detail & Related papers  (2020-11-19T10:00:54Z)
• New Oracle-Efficient Algorithms for Private Synthetic Data Release [52.33506193761153]
  We present three new algorithms for constructing differentially private synthetic data. The algorithms satisfy differential privacy even in the worst case. Compared to the state-of-the-art method High-Dimensional Matrix Mechanism citeMcKennaMHM18, our algorithms provide better accuracy in the large workload.
  arXiv  Detail & Related papers  (2020-07-10T15:46:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.