Combinatorial optimization of the coefficient of determination
Robust correlation analysis is among the most critical challenges in statistics. Herein, we develop an efficient algorithm for selecting the $k$- subset of $n$ points in the plane with the highest coefficient of determination $\left( R^2 \right)$. Drawing from combinatorial geometry, we propose a method called the \textit{quadratic sweep} that consists of two steps: (i) projectively lifting the data points into $\mathbb R^5$ and then (ii) iterating over each linearly separable $k$-subset. Its basis is that the optimal set of outliers is separable from its complement in $\mathbb R^2$ by a conic section, which, in $\mathbb R^5$, can be found by a topological sweep in $\Theta \left( n^5 \log n \right)$ time. Although key proofs of quadratic separability remain underway, we develop strong mathematical intuitions for our conjectures, then experimentally demonstrate our method's optimality over several million trials up to $n=30$ without error. Implementations in Julia and fully seeded, reproducible experiments are available at https://github.com/marc-harary/QuadraticSweep.
Code (1)
Tasks
Combinatorial OptimizationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Divide and Learn: A Divide and Conquer Approach for Predict+Optimize
The predict+optimize problem combines machine learning ofproblem coefficients with a combinatorial optimization prob-lem that uses the predicted coefficients. While this problemcan be solved in two separate stages, it is…
Combinatorial OptimizationCombinatorial Auctions and Graph Neural Networks for Local Energy Flexibility Markets
This paper proposes a new combinatorial auction framework for local energy flexibility markets, which addresses the issue of prosumers' inability to bundle multiple flexibility time intervals. To solve the underlying NP-…
Graph Neural NetworkFeature-Specific Coefficients of Determination in Tree Ensembles
Tree ensemble methods provide promising predictions with models difficult to interpret. Recent introduction of Shapley values for individualized feature contributions, accompanied with several fast computing algorithms f…
Computational EfficiencyAutomatic Rank Determination for Low-Rank Adaptation via Submodular Function Maximization
In this paper, we propose SubLoRA, a rank determination method for Low-Rank Adaptation (LoRA) based on submodular function maximization. In contrast to prior approaches, such as AdaLoRA, that rely on first-order (lineari…
Computational EfficiencyManaging Solution Stability in Decision-Focused Learning with Cost Regularization
Decision-focused learning integrates predictive modeling and combinatorial optimization by training models to directly improve decision quality rather than prediction accuracy alone. Differentiating through combinatorial…