Mitigating the Computational Bottleneck of Greedy Selection

59 concepts57 papers3 proposals

Greedy algorithms are foundational to sparse recovery, subset selection, and large-scale optimization. By design, they make the locally optimal choice at each step—whether that means picking the coordinate with the steepest gradient, selecting the feature that minimizes residual error, or adding the sensor that maximizes marginal utility. This aggressive local strategy often yields excellent global convergence rates, requiring far fewer total iterations than randomized or blind search strategies.

However, this efficiency hides a severe paradox: the per-iteration cost of finding the absolute best candidate scales with the size of the search space. As datasets grow into millions of dimensions or records, the overhead of evaluating every remaining candidate becomes a crippling computational bottleneck.

Anatomy of the Selection Overhead

To understand why greedy selection struggles to scale, we must look at what happens under the hood during a single selection step. The bottleneck manifests across three major domains:

1. Coordinate Descent and Gradient Scans

In greedy coordinate descent (such as the Gauss-Southwell rule), identifying the optimal coordinate requires computing or tracking the full gradient across all dimensions. As Karimireddy et al. point out, this linear cost per iteration can completely negate the theoretical savings in total iterations, making the algorithm behave as poorly as full gradient methods on massive datasets. For complex objective functions where gradient maintenance is expensive, this requirement severely limits scalability (Lu et al.).

2. Dictionary Selection and Projections

In sparse regression or dictionary learning, evaluating a candidate feature often requires more than a simple inner product. Blumensath notes that directly minimizing residual error requires performing partial orthogonal projections for every candidate in the dictionary at each iteration. Fujii et al. echo this, highlighting that high-quality greedy selection requires solving a full linear regression for every possible candidate choice at each step, creating a massive computational bottleneck when candidate pools are high-dimensional.

3. Submodular Maximization and Discrete Selection

When selecting representative subsets, prototypes, or sensors, the objective function itself may be expensive to evaluate. Alieva et al. observe that in large search spaces with expensive evaluation functions, querying every potential candidate to find the best addition becomes financially or computationally prohibitive. This exhaustive search prevents real-time state estimation or decision-making in large-scale systems (Hashemi et al.).

Exact Greedy Step:
[Current State] ---> [Scan ALL Remaining Candidates (N)] ---> [Compute Exact Marginal Gain] ---> [Pick Best]
                     ^--- High computational overhead scales linearly with N ---^

Approximate Greedy Step:
[Current State] ---> [Sample/Filter Sub-set of Candidates]  ---> [Compute Approximate Gain] ---> [Pick Best]
                     ^--- Sub-linear or constant cost ---^

Breaking the Bottleneck via Approximation

The core insight of modern research in this area is that we do not need the perfect greedy choice to maintain fast global convergence; a sufficiently good choice is often enough. By shifting the goal from exact local maximization to efficient approximate selection, several distinct mechanisms have emerged to bypass the exhaustive scan.

Bandit and Stochastic Sampling

Instead of scanning the entire ground set, we can treat the selection process as a learning problem. Salehi et al. introduce a bandit framework that learns to sample the most impactful coordinates on the fly, combining the low per-iteration cost of random sampling with the rapid convergence of greedy methods. Similarly, Jawanpuria et al. reframe stochastic submodular maximization as a best-arm identification task, reducing computational complexity to linear or near-linear scales by avoiding exhaustive iterations over the ground set.

Geometric Mapping

Rather than evaluating coordinates one by one, we can restructure the search space geometrically. Karimireddy et al. demonstrate that the coordinate selection step can be mapped to a Maximum Inner Product Search (MIPS) problem. This allows optimization algorithms to leverage sub-linear nearest-neighbor data structures, effectively decoupling the per-iteration cost from the raw dimensionality of the dataset.

Randomized Sketching

For large linear systems, scanning every constraint to find the most violated one is highly inefficient. Rebrova addresses this by applying random sketching techniques, projecting the system onto a lower-dimensional space at each step. This drastically lowers the cost of identifying progress-enabling constraints while preserving an exponentially fast convergence rate.

The New Efficiency Frontier

By replacing exact linear scans with randomized, stochastic, or structured approximations, these methods fundamentally alter the trade-off space of greedy optimization. They prove that sacrificing a small amount of local precision can yield orders-of-magnitude speedups in wall-clock time, allowing greedy heuristics to finally scale to high-dimensional, real-time industrial applications.

Key Foundational Work

A General Greedy Approximation Algorithm with Applications (2001) — contributed 2 concept elements to this direction.
On the Difference Between Orthogonal Matching Pursuit and Orthogonal Least Squares (2007) — contributed 2 concept elements to this direction.
An improved training algorithm for kernel Fisher discriminants (2001) — 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_greedy_selection_overhead_b76bde3e,
  title = {greedy selection overhead},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/greedy-selection-overhead/rdr_b76bde3ead6d413cb2faa5af82282d02},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_greedy_selection_overhead_b76bde3e_v1,
  title = {greedy selection overhead},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/greedy-selection-overhead/rdr_b76bde3ead6d413cb2faa5af82282d02/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake