Submodularity captures the intuitive concept of diminishing returns: adding an item to a small selection provides a greater marginal benefit than adding that same item to a larger selection. This mathematical structure appears everywhere in machine learning and data science, from selecting a diverse set of movies for a recommendation engine to choosing optimal sensor locations or picking a sparse subset of features.
Historically, the standard recipe for solving these discrete set problems has been to translate them into continuous ones. By using a fractional relaxation—most notably the multilinear extension—researchers could leverage the powerful machinery of continuous optimization, such as gradients and differential equations, before rounding the fractional solution back into a discrete set.
However, a growing body of research reveals that this continuous detour comes with a massive, often prohibitive computational cost. Instead, a new paradigm advocates for staying entirely within the discrete domain, using direct combinatorial optimization to achieve superior speed and scalability without sacrificing theoretical guarantees.
The Hidden Cost of Continuous Relaxations
To understand why continuous relaxations struggle at scale, we must look at how they evaluate fractional points. A continuous algorithm operates on a vector of probabilities (e.g., including item $A$ with $34\%$ probability and item $B$ with $12\%$ probability). But a submodular function is only defined on discrete sets.
To evaluate the function or estimate its gradient at a fractional point, an algorithm must randomly sample thousands of discrete sets and average their values. As Christopher Harshaw et al. demonstrate in Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity, estimating gradients in these relaxed spaces introduces immense computational overhead.
This "sampling tax" creates a severe bottleneck. As Georgios Amanatidis et al. point out in Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity, continuous methods require an excessive number of value queries just to approximate fractional values. For massive datasets containing millions of items, this overhead makes continuous relaxations practically unusable (Alan Kuhnle, Nearly Linear-Time, Parallelizable Algorithms for Non-Monotone Submodular Maximization). Niv Buchbinder notes in Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint that this reliance on continuous relaxations and randomized sampling creates a major barrier for real-world deployment where deterministic speed and simplicity are preferred.
The Power of Purely Discrete Selection
Direct combinatorial optimization eliminates this overhead by operating directly on discrete sets and items. By evaluating the objective function exactly where it is defined, combinatorial algorithms bypass multilinear extensions entirely (Vanja Doskoč et al., Non-Monotone Submodular Maximization with Multiple Knapsacks in Static and Dynamic Settings; Kai Han et al., Practical Parallel Algorithms for Submodular Maximization Subject to a Knapsack Constraint with Nearly Optimal Adaptivity).
Consider a discrete greedy algorithm. Instead of tracking a fractional trajectory through a continuous space, it evaluates the exact marginal gain of adding a single item to the current set. Vanja Doskoč et al. show that purely discrete greedy selection can reduce the number of required function evaluations by several orders of magnitude while maintaining or even improving the final objective value.
Continuous Relaxation Approach:
[Discrete Problem] ──► [Fractional Space] ──► [Heavy Sampling / Gradients] ──► [Rounding] ──► [Discrete Solution]
Direct Combinatorial Approach:
[Discrete Problem] ─────────────────────────► [Direct Greedy / Local Search] ────────────────► [Discrete Solution]
Can discrete algorithms match the theoretical guarantees of their continuous counterparts? Historically, continuous relaxations were thought necessary to break certain mathematical barriers, such as the $1/e$ approximation threshold for non-monotone functions. However, Yixin Chen et al. proved this assumption wrong in Discretely beyond $1/e$: Guided Combinatorial Algortihms for Submodular Maximization. By guiding a randomized greedy search with a fast local search, they broke the long-standing $1/e$ barrier using a purely combinatorial framework, unlocking massive practical speedups for video summarization and large-scale graph analysis.
Achieving Speed via Parallelism and Streaming
A common misconception is that discrete algorithms are inherently sequential—forcing a slow, item-by-item selection process—whereas continuous methods can take parallel steps along a gradient vector. Modern combinatorial designs overcome this by optimizing for low adaptivity, which minimizes the number of sequential rounds of queries an algorithm must make.
In Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity, Georgios Amanatidis et al. introduce a parallel combinatorial algorithm that achieves near-optimal adaptive complexity, completing high-dimensional maximization in just $O(\log n)$ parallel rounds. Because it avoids continuous multilinear extensions, it scales effortlessly to massive datasets where continuous methods stall (Alan Kuhnle).
This efficiency is vital for real-time applications. Kai Han et al. demonstrate that direct discrete operations make complex optimization tasks feasible on standard hardware. Furthermore, when data arrives as a massive, real-time stream, solving the differential equations required by continuous relaxations is out of the question. Alina Ene et al. address this in Streaming Algorithm for Monotone k-Submodular Maximization with Cardinality Constraints by building a fast, low-memory streaming framework that matches the approximation guarantees of continuous methods without their computational footprint.
Expanding Beyond Maximization
The philosophy of direct discrete optimization is also transforming submodular minimization, sparse feature selection, and noisy feedback environments:
- Submodular Function Minimization (SFM): Traditional methods rely on general convex relaxations. However, Yin Tat Lee et al. in Convex Minimization with Integer Minima in Õ(n4) Time and Sally Dong et al. in Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity show that adapting cutting-plane and interior-point methods directly to exploit discrete submodular structures yields dramatic reductions in evaluation oracle complexity, bypassing the limitations of poorly conditioned continuous spaces.
- Sparse Feature Selection: For sparse PCA, Baback Moghaddam et al. show in Spectral Bounds for Sparse PCA: Exact and Greedy Algorithms that direct discrete search algorithms achieve significantly higher computational efficiency and accuracy than traditional semidefinite programming relaxations.
- Alternative Feedback Models: This direct approach remains robust even under challenging conditions, such as risk-averse optimization (Tasuku Soma et al., Online Risk-Averse Submodular Maximization), optimization via simulation (Haixiang Zhang et al., Gradient-Based Algorithms for Convex Discrete Optimization via Simulation), or relative feedback from a dueling oracle (Kaien Sho et al., Submodular Function Minimization with Dueling Oracle), where continuous transformations only serve to introduce unnecessary overhead.
By treating discrete problems as inherently discrete rather than continuous approximations, this research direction trades expensive continuous oracle queries for fast, direct combinatorial operations, making large-scale submodular optimization practical on standard hardware.
Key Foundational Work
Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity (2018) — contributed 1 concept elements to this direction.
Spectral Bounds for Sparse PCA: Exact and Greedy Algorithms (2005) — contributed 1 concept elements to this direction.