Research map / Optimization / Optimizers

How to Boost Any Loss Function

NeurIPS 2024 · Optimization › Optimizers · approach: Randomized gradient estimation · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that boosting can optimize essentially any loss function (non-convex, non-differentiable, even discontinuous on a measure-zero set) using only loss function value queries, via a new boosting algorithm (SecantBoost) built on v-derivatives and Bregman secant distortions from quantum calculus.

Problem

Classical boosting convergence proofs assume the loss is convex, differentiable, Lipschitz, etc., and boosting is often defined as first-order optimization; it is unclear which loss functions can be boosted using only zeroth-order (loss value) information with the original weak-learner blueprint.

Approach

Replaces derivatives in boosting weight updates and leveraging coefficients with v-derivatives (secant slopes with an offset, from quantum calculus), introduces Bregman secant distortions and the Optimal Bregman Information, and uses a per-example offset oracle so that boosting converges for any loss whose discontinuities have Lebesgue measure zero.

Key results

• Theorem gives a boosting-compliant decrease of the empirical loss per iteration, with T iterations sufficient of order 4(F_0 - F(z))/(gamma^2 rho) under WLA and WRA assumptions
• Shows any loss with discontinuities of Lebesgue measure zero can be boosted, without convexity, differentiability or Lipschitz assumptions
• Toy experiments on exotic losses are reported in the supplement (qualitative only per the text)

Surprising findings

• Boosting can optimize non-convex, even discontinuous losses, a feat not known for classical zeroth-order methods
• The ratio of expected squared weights over generalized curvature, not classical convexity, drives convergence

Limitations

• Offset oracle implementation is not computationally optimal; efficient design left open
• Convergence is only empirical (training loss); generalization not studied
• Convergence may stall at local minima unless the weight regularity assumption holds

Experimental setup

Metrics: training loss

Baselines: AdaBoost gradient boosting

Builds on: AdaBoost gradient boosting quantum calculus h-derivative Bregman divergence

Closest papers by meaning

• Lossless or Quantized Boosting with Integer Arithmetic (ICML 2019 · similarity 0.88)
• QuantumBoost: A lazy, yet fast, quantum algorithm for learning with weak hypotheses (ICML 2026 · similarity 0.85)
• Any-stepsize Gradient Descent for Separable Data under Fenchel–Young Losses (NeurIPS 2025 · similarity 0.83)
• Revisiting Agnostic Boosting (NeurIPS 2025 · similarity 0.82)
• Random Function Descent (NeurIPS 2024 · similarity 0.82)
• How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimization (ICML 2024 · similarity 0.82)