Fully Corrective Updates for Greedy Optimization

30 concepts23 papers1 proposal

Greedy algorithms are the workhorses of high-dimensional optimization, machine learning ensembles, and sparse signal recovery. Whether you are selecting features one by one, adding weak learners to a boosting ensemble, or finding rank-one matrices to approximate a massive tensor, the core strategy remains the same: identify the single best component to add next, assign it a weight, and repeat.

However, standard greedy algorithms suffer from a fundamental flaw: myopia. Once a component's weight is set, traditional methods either leave it fixed or update it using rigid, localized step sizes. As the model grows, weights that were optimal in early iterations become highly suboptimal in the context of the newly added components.

To fix this, a powerful paradigm has emerged across multiple machine learning subfields: fully corrective (or totally corrective) optimization. Instead of fixing past decisions, a fully corrective update re-optimizes the weights of all previously selected components simultaneously at every single iteration.

The Myopia of Pure Greed

To understand why fully corrective updates are necessary, consider how a standard forward selection or boosting algorithm behaves. At iteration $t$, the model has selected a subset of components (or "atoms") from a dictionary. It looks for a new component that aligns best with the current residual error, adds it to the active set, and computes its weight.

As noted by Wang et al., traditional greedy approaches often use fixed or small step sizes when updating weights. This prevents the algorithm from fully clearing the residual error within the subspace spanned by the chosen components. Because the residual is never completely corrected, the algorithm is forced to take many small, redundant steps, leading to slow overall convergence and an unnecessarily large, bloated model.

The Fully Corrective Principle

A fully corrective update eliminates this myopia by treating the active set of components not as a static collection, but as a dynamic basis. Every time a new component is introduced, the algorithm pauses to solve a global optimization problem over the coefficients of the entire active set.

Standard Greedy:
Step 1: Pick Atom A -> Optimize Weight A
Step 2: Pick Atom B -> Optimize Weight B (Weight A is fixed)
Step 3: Pick Atom C -> Optimize Weight C (Weights A & B are fixed)

Fully Corrective Greedy:
Step 1: Pick Atom A -> Optimize Weight A
Step 2: Pick Atom B -> Jointly Optimize [Weight A, Weight B]
Step 3: Pick Atom C -> Jointly Optimize [Weight A, Weight B, Weight C]

In the context of ensemble learning, Akkerman et al. describe how totally corrective boosting leverages linear or quadratic programming to re-optimize the weights of all existing base learners whenever a new one is added. Similarly, in sparse approximation over arbitrary dictionaries, Yuan et al. utilize a fully corrective step to re-optimize the coefficients of all selected dictionary atoms, ensuring the model achieves the highest possible accuracy for a given level of sparsity.

Why Global Re-optimization Works

The intuition behind why this global adjustment works so well boils down to two main phenomena: eliminating the "absorption problem" and purging redundancy.

Breaking the Absorption Problem

In cost-sensitive or asymmetric optimization problems, early components often suffer from what Wang et al. term the absorption problem. When a model faces a strict or highly skewed objective, the very first features selected attempt to satisfy the entire optimization requirement by themselves. This distorts their weights. By re-optimizing all weights at each step, the objective is distributed more effectively across the entire ensemble as it grows, preventing early features from disproportionately dominating the model.

Purging Redundancy and Enhancing Sparsity

As a greedy algorithm explores a feature space, it frequently selects components that are partially correlated or redundant. In a standard greedy setup, these redundant components remain in the model forever with positive weights.

Under a fully corrective regime, however, the global optimization step can adjust the weights of older components downward—or even drive them to zero. For example, Wei et al. show that in rule ensembles, re-fitting a regularized generalized linear model every time a new rule is discovered allows the system to automatically discard older rules that have become redundant.

This capability directly translates to higher model sparsity. Shen et al. demonstrate that re-optimizing the weights of all previously selected weak learners at each iteration yields significantly sparser ensembles compared to coordinate-descent methods. You get the same or better objective value using a fraction of the features.

Algorithmic Acceleration and Convergence

While solving a global optimization problem at every iteration sounds computationally expensive, it actually accelerates convergence dramatically in terms of the number of iterations required.

By extracting the maximum possible utility from the current set of components before adding new complexity, the algorithm avoids taking wandering, zigzagging paths toward the optimum. Liu et al. apply this principle to $k$-support-norm regularized minimization via a Fully Corrective Frank-Wolfe method, proving that global re-optimization shifts the convergence rate from sublinear to linear.

The computational trade-off is highly favorable. As Locatello et al. demonstrate in the context of boosting variational inference, the overhead of performing global weight adjustments is heavily offset by the massive reduction in the total number of mixture components needed to reach target accuracy.

A Unified Framework Across Domains

The beauty of the fully corrective update is its mathematical ubiquity. It manifests across completely different domains to solve the exact same structural limitations of greedy selection:

  • Matrix and Metric Learning: In positive semidefinite (PSD) matrix learning, Shen et al. and Shen et al. decompose complex matrix constraints into a convex combination of rank-one matrices. They use totally corrective updates to re-optimize all matrix weights simultaneously, bypassing slow interior-point solvers. Similarly, Shalev-Shwartz et al. use this in their GECO algorithm to minimize convex functions under low-rank constraints efficiently.
  • Bayesian Coresets: When compressing massive datasets into a small, weighted subset for scalable Bayesian inference, Campbell et al. show that refining the weights of all currently selected coreset points via stochastic gradient descent ensures the subset maintains an optimal fit as it grows.
  • Interpretable Scoring Systems: Sokolovska applies fully corrective optimization to clinical scoring systems, re-optimizing all interval weights simultaneously when a new data bin is added to ensure global consistency.
  • Iterative Thresholding: In structured sparse regression, Jain et al. incorporate a full correction step into iterative hard thresholding by performing a least-squares re-optimization over the entire identified support set at each step, vastly improving convergence speed.

By shifting our perspective from local additive updates to global subspace re-optimization, fully corrective updates transform greedy heuristics into mathematically rigorous, fast-converging, and sparse optimization frameworks.

Key Foundational Work

PSDBoost: Matrix-Generation Linear Programming for Positive Semidefinite Matrices Learning (2008) — contributed 1 concept elements to this direction.
Boosting Algorithms for Maximizing the Soft Margin (2007) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_global_weight_re_optimization_07bdd717,
  title = {global weight re-optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-weight-re-optimization/rdr_07bdd71729db43a3ac37ef16cb17a3f2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_global_weight_re_optimization_07bdd717_v1,
  title = {global weight re-optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-weight-re-optimization/rdr_07bdd71729db43a3ac37ef16cb17a3f2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake