# How to Boost Any Loss Function

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 60 references that are in the map.
- First posted on arXiv 2 Jul 2024.

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

- [Learning with Fenchel-Young Losses](https://mlsanity.com/paper/1901.02324/) (2019)
- [ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization](https://mlsanity.com/paper/1910.06513/) (2019)
- [A Zeroth-Order Block Coordinate Descent Algorithm for Huge-Scale Black-Box Optimization](https://mlsanity.com/paper/2102.10707/) (2021)
- [Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2209.05045/) (2022)
- [On the Convergence of Prior-Guided Zeroth-Order Optimization Algorithms](https://mlsanity.com/paper/2107.10110/) (2021)
- [Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimization](https://mlsanity.com/paper/2106.09082/) (2021)
- [Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits](https://mlsanity.com/paper/2006.07862/) (2020)
- [Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2301.06428/) (2023)
- [Boosting Simple Learners](https://mlsanity.com/paper/2001.11704/) (2020)
- [Towards Gradient Free and Projection Free Stochastic Optimization](https://mlsanity.com/paper/1810.03233/) (2018)
- [Accelerated Stochastic Gradient-free and Projection-free Methods](https://mlsanity.com/paper/2007.12625/) (2020)
- [Efficiently avoiding saddle points with zero order methods: No gradients required](https://mlsanity.com/paper/1910.13021/) (2019)
- [Scalable Subspace Methods for Derivative-Free Nonlinear Least-Squares Optimization](https://mlsanity.com/paper/2102.12016/) (2021)
- [Improve Single-Point Zeroth-Order Optimization Using High-Pass and Low-Pass Filters](https://mlsanity.com/paper/2111.01701/) (2021)
- [Accelerated Gradient Boosting](https://mlsanity.com/paper/1803.02042/) (2018)
- [Boosted Density Estimation Remastered](https://mlsanity.com/paper/1803.08178/) (2018)
- [Supervised Learning: No Loss No Cry](https://mlsanity.com/paper/2002.03555/) (2020)
- [Distributed Zero-Order Optimization under Adversarial Noise](https://mlsanity.com/paper/2102.01121/) (2021)
- [A gradient estimator via L1-randomization for online zero-order optimization with two point feedback](https://mlsanity.com/paper/2205.13910/) (2022)
- [Zeroth-order non-convex learning via hierarchical dual averaging](https://mlsanity.com/paper/2109.05829/) (2021)
- [Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradients](https://mlsanity.com/paper/2210.01496/) (2022)
- [Escaping saddle points in zeroth-order optimization: the power of two-point estimators](https://mlsanity.com/paper/2209.13555/) (2022)
- [Zeroth-order Optimization for Composite Problems with Functional Constraints](https://mlsanity.com/paper/2112.11420/) (2021)
- [Zeroth-Order Hard-Thresholding: Gradient Error vs. Expansivity](https://mlsanity.com/paper/2210.05279/) (2022)
- [Non-Convex Boosting Overcomes Random Label Noise](https://mlsanity.com/paper/1409.2905/) (2014)
- [IPBoost -- Non-Convex Boosting via Integer Programming](https://mlsanity.com/paper/2002.04679/) (2020)
- [The Bregman chord divergence](https://mlsanity.com/paper/1810.09113/) (2018)
- [The column measure and Gradient-Free Gradient Boosting](https://mlsanity.com/paper/1909.10960/) (2019)

## Abstract (arXiv)

Boosting is a highly successful ML-born optimization setting in which one is required to computationally efficiently learn arbitrarily good models based on the access to a weak learner oracle, providing classifiers performing at least slightly differently from random guessing. A key difference with gradient-based optimization is that boosting's original model does not requires access to first order information about a loss, yet the decades long history of boosting has quickly evolved it into a first order optimization setting -- sometimes even wrongfully defining it as such. Owing to recent progress extending gradient-based optimization to use only a loss' zeroth (0th) order information to learn, this begs the question: what loss functions can be efficiently optimized with boosting and what is the information really needed for boosting to meet the original boosting blueprint's requirements? We provide a constructive formal answer essentially showing that any loss function can be optimized with boosting and thus boosting can achieve a feat not yet known to be possible in the classical 0th order setting, since loss functions are not required to be be convex, nor differentiable or Lipschitz -- and in fact not required to be continuous either. Some tools we use are rooted in quantum calculus, the mathematical field -- not to be confounded with quantum computation -- that studies calculus without passing to the limit, and thus without using first order information.