Two algorithms for interpreting and boosting tree-based models using rule covering.
problem Interpreting and boosting tree-based ensemble methods.
method Mathematical programming models constructed from decision tree rules.
result Selects a few rules that closely match the accuracy of the model.
Paper uses integer programming for non-convex boosting in classification.
problem Improving classification performance using non-convex optimization.
method Non-convex boosting via integer programming.
result Results comparable to or better than state-of-the-art.
Classifier evasion consists in finding for a given instance x the nearest instance x′ such that the classifier predictions of x and x′ are different. We present two novel algorithms for systematically computing evasions for tree ensembles such as boosted trees and random forests. Our first algorithm uses a Mixe…
New formulation of MIL using shapelets for better classifier of bags.
problem Finding a good classifier of bags based on shapelets.
method Formulation using all possible shapelets, reduced to DC programs, and heuristic options.
result Richer class of classifiers with theoretical justification and empirical validation.
Boosted Difference of Convex Functions Algorithm solves VaR constrained portfolio optimization.
problem Designing VaR optimal portfolios under financial regulations.
method Boosted Difference of Convex Functions Algorithm (BDCA) with a novel line search framework.
result BDCA linearly converges to a Karush-Kuhn-Tucker point for VaR constrained portfolio problems.
High dimensional sparse learning has imposed a great computational challenge to large scale data analysis. In this paper, we are interested in a broad class of sparse learning approaches formulated as linear programs parametrized by a {\em regularization factor}, and solve them by the parametric simplex method (PSM). O…
We study the task of online boosting--combining online weak learners into an online strong learner. While batch boosting has a sound theoretical foundation, online boosting deserves more study from the theoretical perspective. In this paper, we carefully compare the differences between online and batch boosting, and pr…
This paper considers generalized linear models using rule-based features, also referred to as rule ensembles, for regression and probabilistic classification. Rules facilitate model interpretation while also capturing nonlinear dependences and interactions. Our problem formulation accordingly trades off rule set comple…
dboost optimizes prediction models for convex cone problems.
problem Optimizing prediction models for decision-making.
method Gradient boosting with implicit differentiation for convex quadratic cone programming.
result dboost reduces out-of-sample decision regret.
Contrast trees assess machine learning accuracy, boosting improves performance.
problem Lack of accuracy assessment for machine learning results.
method Contrast trees and distribution boosting methods.
result Distribution boosting provides an assumption-free method for estimating outcome distributions.
New solver MPLP++ outperforms existing solvers for dense graph models.
problem Efficiently solving dense, discrete Graphical Models with pairwise potentials.
method Dual Block-Coordinate Ascent with MPLP++ modification.
result MPLP++ significantly outperforms existing solvers, including TRWS.
Study on L2-boosting behavior as learning rate approaches zero.
problem Understanding the asymptotic behavior of L2-boosting algorithms with vanishing learning rates.
method Analyzes L2-boosting for regression with linear base learners, proving a deterministic limit and characterizing it as a solution to a linear differential equation.
result Proves the existence of a unique solution to the limit problem and analyzes the training and test error.
In this paper we analyze boosting algorithms in linear regression from a new perspective: that of modern first-order methods in convex optimization. We show that classic boosting algorithms in linear regression, namely the incremental forward stagewise algorithm (FSε) and least squares boosting (LS-Boost($…
High-frequency trading strategy boosts battery storage profits.
problem Maximizing revenue for battery energy storage systems in intraday markets.
method Adapted dynamic programming for continuous intraday markets, considering limit order book dynamics.
result Dynamic programming strategy outperforms standard re-optimization methods, increasing profits by 58% and 14% respectively.
We present a heuristic based algorithm to induce \textit{nonmonotonic} logic programs that will explain the behavior of XGBoost trained classifiers. We use the technique based on the LIME approach to locally select the most important features contributing to the classification decision. Then, in order to explain the mo…
Framework learns linear programs from optimal decisions.
problem Learning linear programs from optimal decisions is challenging.
method Gradient-based framework for learning linear programs from optimal decisions.
result Successfully learns linear programs and multi-commodity flow instances.
We prove that L2-Boosting lacks a theoretical property which is central to the behaviour of l1-penalized methods such as basis pursuit and the Lasso: Whereas l1-penalized methods are guaranteed to recover the sparse parameter vector in a high-dimensional linear model under an appropriate restricted nullspace property, …
SnapBoost uses random base hypothesis classes to improve gradient boosting performance.
problem Improving gradient boosting performance.
method Heterogeneous Newton Boosting Machine (HNBM) with variable base hypothesis classes.
result SnapBoost achieves better generalization loss than competing frameworks.
GBMixed boosts mixed models for clustered data, estimating mean and variance flexibly.
problem Flexible estimation of mean and variance components in clustered data.
method Gradient Boosting framework for linear mixed models with likelihood-based gradients.
result GBMixed accurately recovers complex nonlinear fixed effects and covariances.
Enhances genetic programming for stock alpha discovery with warm start and structural constraints.
problem Overwhelming search space and computational burden in traditional genetic programming for alpha factor discovery.
method Proposes a new GP framework with warm start and structural constraints to enhance search performance and interpretability.
result Superior out-of-sample prediction results and higher portfolio returns compared to benchmarks.
Robust boosting improves regression accuracy in noisy data.
problem Handling outliers in non-parametric regression.
method Two-stage approach: robust residual scale minimization followed by bounded loss optimization.
result Robust boosting outperforms standard methods in outlier-prone data.
A method to improve gradient boosting models using stacking.
problem Improving the performance of gradient boosting models.
method Proposes a stacking algorithm to learn a meta-model for ensembles of gradient boosting models.
result The proposed approach can be extended to differentiable combination models like neural networks.
BayesBoost combines boosting and Bayesian methods for linear mixed models, improving uncertainty estimation and variable selection.
problem Lack of straightforward uncertainty estimation for parameters in high-dimensional linear mixed models.
method BayesBoost: Combines boosting and Bayesian inference for linear mixed models.
result Improves uncertainty estimation and variable selection in linear mixed models.
Solving linear programs by using entropic penalization has recently attracted new interest in the optimization community, since this strategy forms the basis for the fastest-known algorithms for the optimal transport problem, with many applications in modern large-scale machine learning. Crucial to these applications h…
This paper presents an acceleration framework for packing linear programming problems where the amount of data available is limited, i.e., where the number of constraints m is small compared to the variable dimension n. The framework can be used as a black box to speed up linear programming solvers dramatically, by two…
Real-world problems of operations research are typically high-dimensional and combinatorial. Linear programs are generally used to formulate and efficiently solve these large decision problems. However, in multi-period decision problems, we must often compute expected downstream values corresponding to current decision…
Unified approach for optimizing predictions in linear programming and inverse problems.
problem Optimizing predictions in linear programming and inverse problems.
method Maximum optimality margin approach.
result Unified approach that balances computational efficiency and theoretical properties.
The paper analyzes boosting and minimum-ℓ1-norm classifiers in high dimensions.
problem Understanding the generalization error and optimal Bayes error in boosting.
method High-dimensional asymptotic theory, Gaussian comparison techniques, uniform deviation argument.
result Precise characterizations of boosting test error and optimal Bayes error.
A framework to boost the efficiency of Bayesian inference in probabilistic programs is introduced by embedding a sampler inside a variational posterior approximation. We call it the refined variational approximation. Its strength lies both in ease of implementation and automatically tuning of the sampler parameters to …
Boosts linear neurons for faster convergence in neural networks.
problem Optimizing neural networks' neurons in function space.
method Reparameterizing network to whiten neuron features using Boosted Backpropagation.
result Equivalent to preconditioned gradient descent, leading to faster convergence.
A new gradient tree boosting framework reduces variance and accelerates performance.
problem High variance in stochastic gradient boosting.
method Combining gradient tree boosting with importance sampling and a regularizer.
result Achieves a linear convergence rate on logistic loss and 2.5x--18x acceleration on LogitBoost and LambdaMART.
Boosting strategies for merging vs. ensembling studies analyzed.
problem Deciding between merging and ensembling studies for boosting.
method Analytical transition point and bias-variance decomposition for boosting with linear learners.
result Theoretical guidelines for merging vs. ensembling studies.
New bounds on hyperbolic surfaces' properties using linear programming.
problem Finding bounds on various geometric and spectral properties of hyperbolic surfaces.
method Adapted linear programming methods from sphere packings to hyperbolic surfaces.
result Obtained new upper and lower bounds on multiple properties of hyperbolic surfaces.
Gradient Boosted Mixed Models estimate mean and variance components for clustered data.
problem Limited flexibility in linear mixed models for complex settings.
method Gradient Boosting extended to mixed models with likelihood-based gradients and flexible base learners.
result Accurate recovery of variance components and improved predictive accuracy.
Boosting algorithms improve delivery time prediction in postal services.
problem Challenges in long-term travel time prediction for postal services.
method Investigated linear regression models, tree-based ensembles (random forest, bagging, boosting), and compared their performance.
result Boosting algorithms, especially light gradient boosting and catboost, outperform other methods in accuracy and runtime efficiency.
Boosting improves ICA for better component recovery.
problem Improving ICA's reliance on prior knowledge of sources.
method Maximizing likelihood via boosting and fixed-point unmixing.
result Boosting-based ICA outperforms existing methods.
Paper uses ensemble learning for more accurate power flow modeling.
problem Improving accuracy and efficiency of power flow modeling.
method Applies polynomial regression and ensemble learning (GB, bagging) to create a more accurate linear power flow model.
result Data-driven model outperforms traditional methods in accuracy and speed.
Gradient tree boosting is a prediction algorithm that sequentially produces a model in the form of linear combinations of decision trees, by solving an infinite-dimensional optimization problem. We combine gradient boosting and Nesterov's accelerated descent to design a new algorithm, which we call AGB (for Accelerated…
Boosting combines weak (biased) learners to obtain effective learning algorithms for classification and prediction. In this paper, we show a connection between boosting and kernel-based methods, highlighting both theoretical and practical applications. In the context of ℓ2 boosting, we start with a weak linear le…
Boosting improves online decision-making for large expert sets.
problem Online convex optimization with many experts is infeasible.
method Generalizes online boosting to online convex optimization and bandit linear optimization settings.
result Near-optimal regret guarantees for various feedback models.
Faster algorithms for structured SVMs reduce computation time.
problem Efficiently solving quadratic programming problems with specific structures.
method Designing nearly-linear time algorithms for quadratic programs with low-rank factorizations and few linear constraints.
result First nearly-linear time algorithms for solving quadratic programs with specific structures.
New method for natural policy gradients converges linearly.
problem Improving natural policy gradient methods for better convergence.
method Fisher-Rao gradient flow applied to state-action distributions.
result Linear convergence rate with geometry-dependent factor.
Max-linear regression problem solved with convex programming.
problem Estimating parameters in max-linear regression models.
method Formulated and analyzed a scalable convex program called anchored regression (AR).
result AR provides high probability recovery of parameters with a sample complexity of k4p. We propose a randomized second-order method for optimization known as the Newton Sketch: it is based on performing an approximate Newton step using a randomly projected or sub-sampled Hessian. For self-concordant functions, we prove that the algorithm has super-linear convergence with exponentially high probability, wi…
LGB+ improves macroeconomic forecasting by combining linear and tree models.
problem Efficiency in small samples for forecasting with mixed linear and nonlinear dynamics.
method LGB+ is a boosting procedure that evaluates both tree and linear candidates at each step, advancing only the winner. It decomposes forecasts into linear and nonlinear contributions.
result LGB+ delivers strong gains for targets with pronounced autoregressive dynamics or mixed signals.
Enhances GBDT robustness with one-hot encoding and regularization.
problem Low robustness of GBDT models against covariate perturbation.
method One-hot encoding to linear framework, risk decomposition, L1 or L2 regularization. result Regularization enhances GBDT robustness.
DILP improves fraud detection explainability without significant performance boost.
problem Improving fraud detection explainability in machine learning.
method Differentiable Inductive Logic Programming (DILP) for fraud detection with data curation.
result DILP provides comparable results to traditional methods but lacks significant advantage.
New algorithm improves convergence of gradient boosting trees.
problem Global convergence of Newton boosting in tabular machine learning.
method Introduces Gradient Regularized Newton Descent for GBDTs, proving linear convergence for smooth, strongly convex losses and O(k21) rate for general convex losses. result Achieves globally convergent second-order GBDT algorithm with rate matching first-order boosting.