🔢 mathematics

Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach

This paper proposes and analyzes a zeroth-order algorithm that combines Lovász extension subgradients and Gaussian smoothing to solve non-smooth min-max problems involving submodular-concave functions, proving convergence to an $\epsilon$ -saddle point in the offline setting and establishing an $O(\sqrt{N\bar{P}_N})$ online duality gap bound.

Original authors: Amir Ali Farzin, Yuen-Man Pun, Philipp Braun, Tyler Summers, Iman Shames

Published 2026-05-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Amir Ali Farzin, Yuen-Man Pun, Philipp Braun, Tyler Summers, Iman Shames

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: A Game of Cat and Mouse

Imagine a high-stakes game of chess, but instead of moving pieces on a board, two players are trying to solve a puzzle together.

Player A (The Minimizer): Wants to find the "best" solution to a problem (like cutting a cake perfectly or grouping people into teams).
Player B (The Maximizer): Is an adversary trying to mess things up. They want to make the solution as bad as possible (like adding noise to the data or tricking the system).

This is called a Min-Max problem. The goal is to find a "saddle point"—a sweet spot where Player A has done the best they can despite Player B trying their hardest to ruin it, and Player B can't make it any worse even if they try.

The Problem: A Rough, Bumpy Terrain

In this paper, the authors are dealing with a very specific, tricky type of puzzle:

The "Submodular" Part: Think of this like a "diminishing returns" rule. If you are picking items for a basket, the first apple you pick adds a lot of value. The second apple adds some value, but less than the first. The 100th apple adds almost nothing. This is common in real life (like picking the best sensors for a network or the most influential people in a social graph).
The "Non-Smooth" Part: Imagine the landscape of the problem isn't a smooth hill; it's a jagged, rocky mountain with sharp cliffs and no clear paths. You can't just roll a ball down the hill to find the bottom because the ball would get stuck or bounce off a sharp rock.
The "Concave" Part: Player B's moves are smooth and predictable in a mathematical sense, but Player A's moves are the jagged, rocky ones.

The Challenge: Blindfolded Exploration

Usually, to solve these problems, you need a map or a compass (mathematical gradients) to tell you which way is "down." But here, the paper says: "We don't have a map. We are blindfolded."

This is a Zeroth-Order approach. The algorithm can only ask, "What is the score if I stand here?" It cannot ask, "Which way is the slope?" It has to feel around in the dark.

The Solution: The "Gaussian Smoothing" Flashlight

Since the terrain is too rocky to navigate directly, the authors invented a clever trick:

The Lovász Extension: They take the jagged, discrete problem (picking specific items) and turn it into a continuous one (picking fractions of items). It's like turning a staircase into a ramp.
Gaussian Smoothing: To handle the remaining roughness, they use a "flashlight" that doesn't shine a single beam but a soft, fuzzy glow (Gaussian smoothing). Instead of feeling one specific rock, the algorithm feels the average texture of the ground around it. This smooths out the sharp cliffs just enough to find a path.

The Algorithm: The "Look-Ahead" Dancer

The authors propose an algorithm (Algorithm 1) that acts like a skilled dancer who doesn't just react to the music but anticipates the next beat.

Step 1: The algorithm takes a step based on its current feeling of the ground.
Step 2 (The Look-Ahead): Before committing to that step, it takes a "practice step" to see what the ground looks like there.
Step 3: It uses that new information to make a better, more stable move.

This "Extragradient" method helps the algorithm avoid getting stuck in local traps or oscillating back and forth.

The Results: Offline vs. Online

The paper tests this in two scenarios:

1. The Offline Scenario (The Static Puzzle)
Imagine solving a puzzle where the pieces never move.

Result: The algorithm successfully finds the "saddle point" (the best possible compromise). It proves that with enough tries, it will get close to the perfect answer, even without a map.

2. The Online Scenario (The Moving Puzzle)
Imagine solving a puzzle while the pieces are constantly sliding around, rotating, and changing shape (like a video game level that changes while you play).

Result: The algorithm doesn't just find one answer; it learns to chase the moving target. It tracks the "optimal" solution as it drifts. The paper proves that the algorithm's mistakes (the "duality gap") stay small and manageable, growing only as fast as the target moves.

Real-World Proof: The Adversarial Image Segmentation

To prove this works, the authors tested it on Image Segmentation (cutting an image into parts, like separating a person from a background).

The Setup: They created a scenario where an "adversary" tries to trick the segmentation by messing with the "seeds" (the starting points the computer uses to guess the shape).
The Comparison: They compared their new "Zeroth-Order" algorithm against standard U-Net models (a popular type of AI that usually needs massive amounts of training data and powerful computers).
The Surprise: Their new algorithm, which requires no pre-training and no massive datasets, actually performed better than the trained AI models in this specific adversarial setting. It was faster, used less memory, and was more robust against the "attacks."

Summary

The paper introduces a new way to solve tough, jagged optimization problems where one player tries to minimize a cost and another tries to maximize it. By using a "smoothed flashlight" to navigate the rough terrain and a "look-ahead" strategy to stay on track, the authors created an algorithm that works without needing a map (gradients) or a massive training dataset. It works well whether the problem is static or constantly changing, and it even outperformed heavy-duty AI models in a specific image-processing test.

Technical Summary: Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions

Problem Formulation
This work addresses mixed-integer min-max and max-min optimization problems of the form:
$\max_{y \in Y} \min_{S \subset Q} f(S, y) \quad \text{and} \quad \min_{S \subset Q} \max_{y \in Y} f(S, y)$
where $Q = [n]$ is a ground set of $n$ elements, $2^Q$ denotes the power set, and $Y \subset \mathbb{R}^m$ is a compact convex set. The objective function $f: 2^Q \times \mathbb{R}^m \to \mathbb{R}$ is assumed to be submodular with respect to the set variable $S$ and concave with respect to the continuous variable $y$ . Crucially, the function is allowed to be non-smooth (non-differentiable) with respect to both variables. The authors aim to compute an $\epsilon$ -saddle point, defined as a pair $(\bar{S}, \bar{y})$ such that the duality gap is bounded by $\epsilon$ .

Methodology
The proposed approach utilizes a Zeroth-Order (ZO) framework based on the extragradient method. The methodology relies on two primary techniques to handle the non-smoothness and mixed-variable structure:

Lovász Extension for Submodularity: To handle the discrete submodular component, the authors utilize the Lovász extension $f^L$ , which maps the submodular set function to a continuous, convex function over the hypercube $[0, 1]^n$ . The subgradient of $f^L$ with respect to the set variable can be computed using only function evaluations (via a maximal chain of subsets), avoiding the need for higher-order information.
Gaussian Smoothing for Concavity: For the continuous concave variable $y$ , where the function may be non-smooth, the authors employ Gaussian smoothing. They define a random oracle using a two-point estimator to approximate the gradient of the smoothed function. This allows for gradient-based updates without explicit access to derivatives.

The resulting algorithm (Algorithm 1, ZO-EG) operates in an iterative loop:

Forward Step: Estimate the operator at the current iterate $z_k = (x_k, y_k)$ by sampling Gaussian directions to compute the random oracle for $y$ and calculating the subgradient for $x$ .
Extrapolation Step: Perform a descent step to a lookahead point $\hat{z}_k$ .
Update Step: Re-estimate the operator at $\hat{z}_k$ and perform a second descent step to update $z_{k+1}$ .

The method requires only function value queries (zeroth-order information) and does not assume access to gradients or subgradients directly.

Key Contributions and Theoretical Results
The paper provides convergence guarantees for both offline and online settings:

Offline Convergence: The authors prove that the algorithm converges, in expectation, to an $\epsilon$ -saddle point. The total sample complexity is shown to be $O(nm^2\epsilon^{-2})$ , where $n$ is the size of the ground set and $m$ is the dimension of the continuous variable. The dependence on $n$ arises from the per-iteration cost of computing Lovász extension subgradients, while the iteration count depends on $m$ .
Online Convergence: In the online setting, where the cost function $f_k$ changes over time, the algorithm achieves an expected online duality gap of $O(\sqrt{N \bar{P}_N})$ . Here, $N$ is the number of iterations and $\bar{P}_N$ is the path length of the sequence of optimal decisions. This result aligns with established dynamic regret bounds in online optimization.
Existence of Solutions: The paper discusses conditions under which saddle points exist for the original discrete problem by relating them to the solutions of the continuous Lovász extension problem, specifically when the minimizer of the extension lies on a vertex of the hypercube.

Numerical Results and Applications
The theoretical findings are illustrated through numerical examples, specifically focusing on adversarial image segmentation and semi-supervised clustering:

Offline Adversarial Segmentation: The method is applied to a min-max problem where an adversary perturbs the trust weights of seed pixels. The algorithm successfully recovers segmentation matching the ground truth, demonstrating robustness against adversarial perturbations.
Online Adversarial Segmentation: The algorithm is tested on a video stream where shapes and clusters move and rotate, causing the cost function to change at every frame. The method performs real-time segmentation (approx. 80 fps on CPU) without pre-training.
Comparison with Deep Learning: In the online adversarial setting, the proposed ZO method outperforms both supervised and semi-supervised trained U-Net models in terms of Intersection over Union (IoU), precision, and recall. Notably, the ZO method requires no pre-training, has a significantly smaller memory footprint (~0.05 MB vs. ~8 MB for U-Net), and operates effectively in unseen environments without access to large datasets.

Significance and Claims
The authors claim this is the first study dedicated to solving min-max optimization problems with non-smooth submodular-concave cost functions. The significance of the work lies in:

Bridging a Gap: It addresses a class of combinatorial min-max problems that were previously difficult to solve due to the lack of smoothness and the mixed discrete-continuous nature.
Zeroth-Order Efficiency: It demonstrates that zeroth-order methods, traditionally used for continuous non-smooth problems, can be effectively adapted to submodular optimization via the Lovász extension.
Robustness and Efficiency: The numerical results suggest that this approach offers a viable alternative to deep learning for real-time, resource-constrained, and adversarial environments, particularly where pre-training is infeasible or the environment is non-stationary.

The paper concludes by noting that future work could explore the relationship between these solutions and mixed-strategy Nash equilibria, extend the results to submodular-submodular cost functions, and investigate unbounded constraint sets.