Logarithmic Adaptivity for Parallel Submodular Optimization

48 concepts31 papers1 proposal

Submodular functions are the discrete cousins of convex and concave functions, characterized by the property of "diminishing returns": adding an element to a small set increases the function value more than adding it to a larger set. This property makes them central to machine learning tasks like data summarization, sensor placement, and recommendation systems.

Traditionally, these problems are solved using the greedy algorithm, which builds a solution one element at a time. While effective, this sequential nature is a bottleneck for modern datasets. The research direction of logarithmic adaptivity seeks to break this bottleneck by reducing the number of sequential rounds—known as adaptivity—from linear to logarithmic scales, enabling massive parallelization without sacrificing solution quality.

The Sequential Bottleneck and the Power of Adaptivity

In submodular maximization, the goal is to select a subset that maximizes a function $f(S)$ under constraints. The classic greedy algorithm requires $k$ sequential steps to select $k$ elements. In a distributed computing environment, each step requires a synchronization round, which is prohibitively slow for large $k$.

Matthew Fahrbach et al. define adaptivity as the number of sequential rounds of queries an algorithm makes to the function, where in each round, many queries can be issued in parallel. The breakthrough in this field is the realization that we can achieve near-optimal approximation ratios (like the $1 - 1/e$ limit for monotone functions) in only $O(\log n)$ rounds. As Alan Kuhnle demonstrates, reducing adaptivity to logarithmic rounds allows thousands of function queries to be executed simultaneously, leading to speedups of nearly two orders of magnitude over sequential baselines.

From Greedy Steps to Parallel Batches

The core mechanism for achieving logarithmic adaptivity is threshold-based batching. Instead of searching for the single "best" element to add, these algorithms identify a threshold of "good enough" marginal gains.

  1. Thresholding: The algorithm sets a high threshold for the marginal contribution an element must provide.
  2. Batch Selection: All elements that exceed this threshold are added to the solution in a single parallel round.
  3. Adaptive Decay: If no more elements meet the threshold, the threshold is lowered, and the process repeats.

Canh V. Pham et al. apply this logic to knapsack constraints, showing that selecting batches of elements exceeding a specific marginal value threshold can maintain a $7 + \epsilon$ approximation ratio while keeping sequential iterations logarithmic. Similarly, Adam Breuer et al. introduce the FAST algorithm, which replaces "adaptive sampling" with "adaptive sequencing." By evaluating single random sequences rather than large random subsets, they reduce the constant overhead that often makes theoretical parallel algorithms slow in practice.

Balancing Speed and Query Complexity

A major challenge in parallel optimization is the trade-off between the number of rounds (adaptivity) and the total number of function evaluations (query complexity). An algorithm might run in very few rounds but require an astronomical number of queries to find the right elements.

Matthew Fahrbach et al. proved that it is possible to achieve nearly optimal parallel speed ($O(\log n)$ rounds) while maintaining nearly linear query complexity ($O(n \log k)$). This balance is crucial for large-scale applications where evaluating the objective function—such as running a complex simulation or a deep learning model—is expensive. Rohan Ghuge et al. further show that in stochastic settings, as few as 6–7 rounds of adaptivity are often sufficient to match the performance of fully sequential strategies.

Beyond Monotonicity and Simple Constraints

While monotone functions (where adding elements always increases value) are well-understood, many real-world problems are non-monotone (e.g., diverse summarization, where adding too many items reduces utility).

Recent work has pushed the boundaries of what is possible in the non-monotone regime:

  • Breaking Barriers: Yixin Chen et al. developed combinatorial algorithms that surpass the $1/e$ approximation barrier for non-monotone functions without relying on expensive continuous relaxations.
  • Complex Constraints: Francesco Quinzan and Vanja Doskoc introduced REP-SAMPLING, achieving poly-logarithmic adaptivity for non-monotone functions under general $p$-system constraints, providing an exponential speedup over previous linear-round methods.
  • Matroids: Chandra Chekuri and Kent Quanrud demonstrated that the $1 - 1/e$ ratio is achievable for monotone functions under matroid constraints within polylogarithmic rounds, proving that the inherent sequentiality of matroids is not a fundamental barrier to parallelization.

Parallel Submodular Minimization

While much of the focus is on maximization, submodular function minimization (SFM)—used in image segmentation and speech analysis—has also seen parallel breakthroughs. Robert Nishihara et al. provided the first proof that parallelizable alternating projection methods for decomposable SFM converge at a linear rate, meaning the number of iterations scales logarithmically with the desired precision.

Furthermore, Deeparnab Chakrabarty et al. showed that the sequential bottleneck in general SFM can be reduced to a depth of $n^{1/3}$, matching theoretical lower bounds and suggesting we are nearing the fundamental limits of parallel efficiency in discrete optimization.

Key Foundational Work

Parallel Pareto Optimization for Subset Selection (2016) — contributed 1 concept elements to this direction.
Algorithms and Adaptivity Gaps for Stochastic Probing (2016) — contributed 1 concept elements to this direction.
On the Convergence Rate of Decomposable Submodular Function Minimization (2014) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 32 papers
  2. Version 1 · 2026-10-04 · 75 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_logarithmic_adaptivity_b435126f,
  title = {logarithmic adaptivity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/logarithmic-adaptivity/rdr_b435126f2a034df0a3fb7e2ddac8a1ff},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_logarithmic_adaptivity_b435126f_v2,
  title = {logarithmic adaptivity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/logarithmic-adaptivity/rdr_b435126f2a034df0a3fb7e2ddac8a1ff/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake