# GBM-based Bregman Proximal Algorithms for Constrained Learning

arXiv: https://arxiv.org/abs/2308.10767 · HTML: https://mlsanity.com/paper/2308.10767/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 58 references that are in the map.
- First posted on arXiv 21 Aug 2023.

## Builds on (most cited first, 26 of 26)

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Censoring Representations with an Adversary](https://mlsanity.com/paper/1511.05897/) (2015)
- [An Overview of Deep Semi-Supervised Learning](https://mlsanity.com/paper/2006.05278/) (2020)
- [Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals](https://mlsanity.com/paper/1809.04198/) (2018)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimization](https://mlsanity.com/paper/1908.02734/) (2019)
- [Learning by Minimizing the Sum of Ranked Range](https://mlsanity.com/paper/2010.01741/) (2020)
- [Quadratically Regularized Subgradient Methods for Weakly Convex Optimization with Weakly Convex Constraints](https://mlsanity.com/paper/1908.01871/) (2019)
- [FairGBM: Gradient Boosting with Fairness Constraints](https://mlsanity.com/paper/2209.07850/) (2022)
- [Neyman-Pearson (NP) classification algorithms and NP receiver operating characteristics (NP-ROC)](https://mlsanity.com/paper/1608.03109/) (2016)
- [First-Order Methods for Nonsmooth Nonconvex Functional Constrained Optimization with or without Slater Points](https://mlsanity.com/paper/2212.00927/) (2022)
- ["Relative-Continuity" for Non-Lipschitz Non-Smooth Convex Optimization using Stochastic (or Deterministic) Mirror Descent](https://mlsanity.com/paper/1710.04718/) (2017)
- [Regret Bounds without Lipschitz Continuity: Online Learning with Relative-Lipschitz Losses](https://mlsanity.com/paper/2010.12033/) (2020)
- [Mirror Descent and Convex Optimization Problems With Non-Smooth Inequality Constraints](https://mlsanity.com/paper/1710.06612/) (2017)
- [Penalty Methods with Stochastic Approximation for Stochastic Nonlinear Programming](https://mlsanity.com/paper/1312.2690/) (2013)
- [First-order methods for constrained convex programming based on linearized augmented Lagrangian function](https://mlsanity.com/paper/1711.08020/) (2017)
- [Randomized Gradient Boosting Machine](https://mlsanity.com/paper/1810.10158/) (2018)
- [Neyman-Pearson classification: parametrics and sample size requirement](https://mlsanity.com/paper/1802.02557/) (2018)
- [Level Constrained First Order Methods for Function Constrained Optimization](https://mlsanity.com/paper/2205.08011/) (2022)
- [A New Perspective on Boosting in Linear Regression via Subgradient Optimization and Relatives](https://mlsanity.com/paper/1505.04243/) (2015)
- [Bridging Cost-sensitive and Neyman-Pearson Paradigms for Asymmetric Binary Classification](https://mlsanity.com/paper/2012.14951/) (2020)
- [Testing against a linear regression model using ideas from shape-restricted estimation](https://mlsanity.com/paper/1311.6849/) (2013)
- [A Richer Theory of Convex Constrained Optimization with Reduced Projections and Improved Rates](https://mlsanity.com/paper/1608.03487/) (2016)

## Built on by (most cited first, 1 of 1)

- [Distribution-Free Rates in Neyman-Pearson Classification](https://mlsanity.com/paper/2402.09560/) (2024)

## Abstract (arXiv)

As the complexity of learning tasks surges, modern machine learning encounters a new constrained learning paradigm characterized by more intricate and data-driven function constraints. Prominent applications include Neyman-Pearson classification (NPC) and fairness classification, which entail specific risk constraints that render standard projection-based training algorithms unsuitable. Gradient boosting machines (GBMs) are among the most popular algorithms for supervised learning; however, they are generally limited to unconstrained settings. In this paper, we adapt the GBM for constrained learning tasks within the framework of Bregman proximal algorithms. We introduce a new Bregman primal-dual method with a global optimality guarantee when the learning objective and constraint functions are convex. In cases of nonconvex functions, we demonstrate how our algorithm remains effective under a Bregman proximal point framework. Distinct from existing constrained learning algorithms, ours possess a unique advantage in their ability to seamlessly integrate with publicly available GBM implementations such as XGBoost (Chen and Guestrin, 2016) and LightGBM (Ke et al., 2017), exclusively relying on their public interfaces. We provide substantial experimental evidence to showcase the effectiveness of the Bregman algorithm framework. While our primary focus is on NPC and fairness ML, our framework holds significant potential for a broader range of constrained learning applications. The source code is currently freely available at https://github.com/zhenweilin/ConstrainedGBM}{https://github.com/zhenweilin/ConstrainedGBM.