Iterative Modular Approximations for Discrete Optimization

27 concepts20 papers

In continuous optimization, when a function is too complex to minimize directly, we often rely on its derivatives. A first-order Taylor expansion gives us a local linear approximation—a tangent plane—that allows us to take a small step forward.

But what do we do when the domain is discrete? When optimizing over sets, there are no traditional gradients, and the landscape is a combinatorial maze. If we want to find a subset of data that maximizes diversity, minimizes cost, or satisfies complex constraints, exact solutions are often NP-hard.

To bridge this gap, researchers have developed a powerful paradigm: discrete majorization-minimization (MM) and minorize-maximize frameworks. Instead of relaxing discrete variables into continuous ones—which introduces rounding errors and "integrality gaps"—this approach constructs simple, discrete surrogate functions that bound the complex objective. By iteratively optimizing these surrogates, we can navigate complex discrete landscapes efficiently and with strong theoretical guarantees.

The Discrete Analogue of a Tangent Plane

In the discrete world, the closest equivalent to a linear function is a modular function. A set function $h$ is modular if the weight of a set is simply the sum of the weights of its individual elements: $h(A) = \sum_{e \in A} w(e)$. Modular functions are incredibly easy to optimize; to minimize one, you simply select all elements with negative weights.

For more complex set functions—such as submodular functions, which exhibit a "diminishing returns" property—we can construct modular bounds that mimic tangent planes. As established by Rishabh K Iyer et al., we can define discrete semidifferentials (sub-gradients and super-gradients). Just as a continuous sub-gradient defines a linear lower bound for a convex function, a discrete sub-gradient defines a modular lower bound for a submodular function. Conversely, a super-gradient defines a modular upper bound.

Continuous Optimization:
Function f(x)  --->  Gradient ∇f(x)  --->  Linear Bound (Tangent Plane)

Discrete Optimization:
Set Function f(A) ---> Semidifferential ---> Modular Bound (Element Weights)

These bounds allow us to turn an intractable combinatorial problem into a sequence of trivial linear selections.

The Majorization-Minimization Loop

The core algorithmic engine is an iterative loop. Suppose we want to minimize a complex, non-linear discrete function $f(A)$. The process works as follows:

  1. Start at a current solution set $A_t$.
  2. Construct a surrogate function $M(A)$ (a majorant) that upper-bounds the true objective function everywhere ($M(A) \ge f(A)$ for all sets) but matches it exactly at the current solution ($M(A_t) = f(A_t)$).
  3. Minimize the surrogate to find the next candidate set: $A_{t+1} = \arg\min M(A)$.
  4. Repeat until convergence.

Why does this guarantee progress? Because the surrogate is an upper bound, the true objective value at the new point is guaranteed to be less than or equal to the surrogate value. And because we minimized the surrogate, its value at $A_{t+1}$ is less than or equal to its value at $A_t$.

$$f(A_{t+1}) \le M(A_{t+1}) \le M(A_t) = f(A_t)$$

This "sandwiching" effect ensures that the objective function decreases monotonically at every single iteration.

  Objective Value
        ^
        |       \       /   <-- True Objective f(A)
        |        \_   _/
        |          \_/
        |         .---.     <-- Surrogate M(A) (Upper Bound)
        |        /  .  \
        |       /   .   \
        |      /    .    \
        +-----------+---------> Sets (A)
                  A_t  A_{t+1}

This strategy has proven remarkably versatile across different optimization landscapes:

  • Submodular Minimization: For large-scale datasets, exact submodular minimization is too slow. Stefanie Jegelka et al. demonstrated that iteratively constructing tight submodular upper bounds and solving them via fast graph-cut techniques allows submodular minimization to scale to massive machine learning problems.
  • Robust Minimization: When dealing with uncertainty or adversarial noise, Rishabh K Iyer showed that replacing complex submodular objectives with modular super-gradients transforms difficult min-max tasks into highly scalable, practical sub-problems.
  • Non-Submodular Energies: The framework is not limited to submodular functions. In computer vision, binary pairwise energy functions are often non-submodular and notoriously difficult to optimize. Lena Gorelick introduced Local Submodular Approximations (LSA), which iteratively approximate these complex energies with submodular surrogates. By staying entirely within the discrete domain, this method completely avoids the rounding errors and integrality gaps associated with continuous linear programming relaxations.

Taming Competing Objectives: Differences and Ratios

In many real-world applications, we must balance competing forces. For example, in viral marketing, we want to maximize revenue (a submodular benefit) while minimizing data traffic costs (a submodular cost). This creates optimization problems based on the difference or ratio of submodular functions, which lose the nice mathematical properties of pure submodularity.

Iterative modular approximations provide an elegant escape hatch. To minimize the difference between two submodular functions, $f(A) - g(A)$, Mukund Narasimhan et al. proposed a variational procedure: iteratively approximate the supermodular component ($-g(A)$) with a modular upper bound. Because a submodular function plus a modular function is still submodular, each step of the loop reduces to a standard submodular minimization problem that can be solved efficiently.

This difference-of-submodular (DS) framework has unlocked solutions in several domains:

  • Social Networks: Jing Tang et al. utilized modular upper and lower bounds to maximize net profit for online network providers, slashing the search space by up to 98%.
  • Biochemical Engineering: In protein design, Kevin K Yang et al. applied alternating modular approximations to navigate massive combinatorial spaces, successfully identifying rare, high-performing biological variants.
  • Submodular+Supermodular Maximization: When maximizing functions that exhibit both diminishing and increasing returns, Jeff Bilmes et al. used discrete semi-gradients to bound the supermodular component, reducing the problem to iterative submodular maximization.

When the competing objectives are structured as a fraction rather than a difference, Wenruo Bai et al. showed that constructing simultaneous modular upper and lower bounds for the numerator and denominator allows the ratio of submodular functions to be optimized as a sequence of simple modular ratio tasks.

Managing Constraints and Structure

The utility of modular surrogates extends beyond the objective function itself; it can also simplify complex constraints.

When minimizing a submodular cost subject to a submodular coverage constraint, Rishabh K Iyer et al. demonstrated that replacing both the objective and the constraint functions with modular surrogates yields the first bounded approximation guarantees for these problems. Similarly, Kai Wei et al. leveraged linear surrogates to handle non-linear objectives in mixed robust submodular partitioning.

This philosophy of iterative reduction appears across a wide taxonomy of discrete problems:

  • Data Summarization: Jeff Bilmes et al. used modular approximations to compute the "submodular span," identifying redundant data points to generate concise text and video summaries.
  • Clustering: To optimize non-submodular objectives derived from higher-order element interactions, Jennifer Gillenwater et al. designed an MM framework using modular upper bounds to optimize submodular Hamming metrics.
  • Fairness: In minimum-cost set selection tasks with demographic constraints, Wenjing Chen et al. showed that iteratively adjusting estimated solution sizes allows fairness bounds designed for maximization tasks to be adapted seamlessly.
  • Graph Theory: Even in pure structural graph problems like finding nearly complete subgraphs, Yi Zhou 0016 et al. demonstrated that isolating a core sub-problem to serve as a highly optimized black-box subroutine mirrors this philosophy, drastically accelerating execution on massive biological and social networks.

By treating complex combinatorial landscapes as a sequence of simple, linear, or highly optimized sub-problems, iterative modular approximation provides a unified, scalable, and mathematically rigorous toolkit for modern discrete optimization.

Key Foundational Work

A submodular-supermodular procedure with applications to discriminative structure learning (2005) — contributed 5 concept elements to this direction.
On fast approximate submodular minimization (2011) — contributed 2 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_iterative_modular_approximation_61dca9f1,
  title = {iterative modular approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/iterative-modular-approximation/rdr_61dca9f1b80f47a6bab8ae3dff95a580},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_iterative_modular_approximation_61dca9f1_v1,
  title = {iterative modular approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/iterative-modular-approximation/rdr_61dca9f1b80f47a6bab8ae3dff95a580/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}

See something wrong? Report a mistake