Explaining the Empirical Success of Greedy Submodular Maximization

36 concepts34 papers1 proposal

In combinatorial optimization, submodularity acts as a discrete analog to convexity or concavity. A function is submodular if it exhibits the law of diminishing returns: adding an element to a smaller set yields a larger marginal gain than adding the same element to a larger set. Because finding the absolute optimal subset of elements is often NP-hard, practitioners almost universally rely on the Greedy algorithm, which iteratively selects the single next item offering the highest immediate marginal gain.

For decades, the theoretical foundation of greedy submodular maximization has been anchored to a famous worst-case lower bound: $1 - 1/e \approx 63.2\%$. As noted by Yoshinobu Kawahara et al. in Submodularity Cuts and Applications, a potential 37% gap between a greedy solution and the true optimum can be deeply concerning for high-stakes or critical systems.

Yet, a profound paradox lies at the heart of practical optimization: in real-world applications, the greedy algorithm rarely performs this poorly. Instead, it routinely captures 90% to 95%+ of the optimal value. Even in problems structurally classified as theoretically "highly inapproximable" in the worst case—such as maximizing submodular functions under submodular constraints or coordinating resource pooling—empirical results on real-world datasets show that simple greedy heuristics consistently yield near-optimal solutions (see Madhavan R. Padmanabhan and Haris Aziz et al.).

This persistent discrepancy is known as the empirical-theoretical performance gap. A major research direction focuses on dismantling these pessimistic worst-case bounds to explain exactly why greedy algorithms excel in practice, developing refined mathematical tools that capture the hidden tractability of real-world data.

Why Worst-Case Bounds Lie

Traditional worst-case analysis is inherently adversarial. It evaluates an algorithm against pathological, highly engineered instances designed specifically to trick the heuristic into making poor choices early on.

Real-world data structures, however, are rarely adversarial. Whether analyzing social network influence patterns or natural data distributions, the underlying structures possess inherent regularities that prevent the greedy algorithm from falling into worst-case traps (as observed by Nguyễn Kim Thắng et al. in Online Non-Monotone DR-Submodular Maximization and Siddharth Gollapudi et al. in Composable Coresets for Determinant Maximization: Greedy is Almost Optimal).

A key insight into this phenomenon comes from feature selection and sparse approximation. As Abhimanyu Das et al. demonstrate in Approximate Submodularity and its Applications: Subset Selection, Sparse Approximation and Dictionary Selection, real-world target variables are typically not aligned with the most problematic or noisy dimensions of a feature space. Because the data avoids these pathological zones, the "effective" submodularity encountered by the algorithm during its execution is significantly higher than the global minimum across the entire dataset.

Curvature: Measuring Closeness to Linearity

To formalize this real-world mildness, researchers look to the concept of curvature.

If a submodular function has zero curvature, it means the marginal contribution of an element never decreases, regardless of the size of the set it is added to. Such a function is purely linear (or modular), a state where the greedy algorithm is guaranteed to find the 100% exact optimum. Curvature mathematically quantifies how far a function "bends" away from this ideal, linear state.

In Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions, Rishabh K Iyer et al. proved that bounding this deviation yields much tighter theoretical guarantees, explaining why seemingly complex problems behave elegantly in practice.

Consider a concrete example: maximizing entropy using Gaussian Radial Basis Function (RBF) kernels. While general entropy maximization is bound by the pessimistic 63% limit, Dravyansh Sharma et al. proved in On Greedy Maximization of Entropy that the specific geometry of Gaussian RBF kernels forces the objective function to maintain a very low curvature. It behaves almost linearly, structurally guaranteeing that the greedy approach will achieve near-perfection (>95%).

By integrating various refined measures of curvature—such as forward, backward, or extended greedy curvature—the authors of recent work have successfully bypassed the conservative 63% baseline to prove near-optimal guarantees for network graph cuts, sequence optimization, and multi-agent coverage tasks (see Tobias Friedrich et al., Zhenliang Zhang et al., and Shirantha Welikala et al.).

The Submodularity Ratio: Beyond Strict Diminishing Returns

In many practical machine learning tasks, such as feature selection via Orthogonal Matching Pursuit (OMP) or sensor network controllability, the objective function is not actually submodular. The strict law of diminishing returns is occasionally violated. Yet, remarkably, greedy algorithms still deliver outstanding empirical results.

To explain this success, Abhimanyu Das et al. introduced the submodularity ratio in Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection. The submodularity ratio measures how close a non-submodular function is to satisfying the submodular property. If the ratio is close to 1, the function behaves almost entirely like a submodular function.

This metric provided the first strong multiplicative approximation guarantees for non-submodular greedy heuristics, explaining their stability even when data is highly correlated. To handle more intricate constraints, Theophile Thiery et al. expanded this framework in Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression by introducing an upper submodularity ratio to bound deviations when elements are both added and removed.

Ultimately, by unifying both the submodularity ratio and curvature into a single framework, Yatao Bian et al. in Guarantees for Greedy Maximization of Non-submodular Functions with Applications established tight, principled bounds that explain why greedy selection remains highly effective across a vast landscape of non-submodular objectives.

Continuous Geometry and Smoothed Budgets

Other approaches explain greedy success by translating the problem into continuous spaces or altering the nature of the constraints.

In robust optimization settings, Bryan Wilder demonstrated in Equilibrium Computation and Robust Optimization in Zero Sum Games With Submodular Structure that combining continuous relaxations with greedy heuristics allows algorithms to scale to massive problems while coming within 8% of the global optimum, far outperforming their conservative mathematical baselines.

Instance-Specific Verification: Knowing How Well You Did

Even with global metrics like curvature or sharpness, a practitioner running a greedy algorithm on a specific dataset faces a fundamental limitation: global bounds are a priori. They tell you how well the algorithm performs on a class of functions, but they cannot tell you if your specific run on your specific dataset is near-optimal or if there is still room for improvement.

To bridge this final gap, Eric Balkanski et al. introduced an analytical framework called DUAL in Instance Specific Approximations for Submodular Maximization.

Instead of trying to predict performance ahead of time, DUAL computes an instance-specific upper bound on the true optimum dynamically during or after the algorithm's execution.

$$\text{Worst-Case Bound } (63\%) \quad \ll \quad \text{DUAL Instance Bound } (>95\%) \quad \le \quad \text{True Optimum}$$

By evaluating the specific mathematical properties of the items chosen along the greedy path, DUAL provides a data-dependent guarantee. This allows practitioners to rigorously verify, post hoc, that their simple greedy heuristic successfully captured over 95% of the available value, completely bypassing theoretical pessimism on a case-by-case basis.

Key Foundational Work

Submodularity Cuts and Applications (2009) — contributed 1 concept elements to this direction.
Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection (2011) — 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_empirical_theoretical_performance_gap_6c6a97bc,
  title = {empirical-theoretical performance gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/empirical-theoretical-performance-gap/rdr_6c6a97bcc6ff480f9e8e300e0d9b3b16},
  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_empirical_theoretical_performance_gap_6c6a97bc_v1,
  title = {empirical-theoretical performance gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/empirical-theoretical-performance-gap/rdr_6c6a97bcc6ff480f9e8e300e0d9b3b16/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