🔢 mathematics

Projected Subgradient Ascent for Convex Maximization

This paper demonstrates that projected subgradient ascent with arbitrarily large step sizes converges to a first-order stationary point for maximizing continuous convex functions over closed convex sets, with the infinite step-size limit yielding a deterministic variant of the conditional gradient algorithm.

Original authors: Pedro Felzenszwalb, Heon Lee

Published 2026-02-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Pedro Felzenszwalb, Heon Lee

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

Imagine you are standing in a vast, foggy field (this is your Hilbert Space, a mathematical playground). You are trying to find the highest point on a hill, but there's a catch: you are only allowed to walk on a specific, fenced-in area (this is your Convex Set).

Usually, finding the highest point on a hill is easy if the hill slopes down everywhere (convex minimization). But here, we are trying to find the highest point on a hill that slopes up everywhere (convex maximization). In the real world, this is like trying to find the absolute peak of a mountain that keeps getting steeper the higher you go. It's notoriously difficult because the "top" is usually at the very edge of your fenced-in area.

This paper by Pedro Felzenszwalb and Heon Lee proposes a surprisingly simple, almost magical way to solve this problem. Here is the breakdown using everyday analogies.

1. The "One Giant Leap" Trick (Linear Optimization)

Imagine you are trying to find the highest point in a fenced garden (the set $S$ ) based on a simple rule: "Go as far North as possible" (a linear function).

The Old Way:
Usually, algorithms take tiny steps. They look around, take a small step North, check if they are higher, take another small step, and repeat this thousands of times until they hit the fence.

The Paper's Discovery:
The authors say: "Why take tiny steps? Just take one giant leap!"

Imagine you are at a starting point $x_0$ . Instead of walking North, you imagine a super-strong wind blowing you North with infinite force. You let this wind blow you so far that you are essentially at "infinity" in the North direction. Then, you look at where you would land if you dropped a plumb line straight down to the nearest point inside your fenced garden.

The Magic:
The paper proves that if you blow hard enough (make the step size $\eta$ huge), that single drop-down point is guaranteed to be the absolute best spot in the garden for going North.

Analogy: It's like aiming a cannonball so far away that when it falls back down due to gravity, it lands exactly on the target you wanted, skipping all the intermediate steps.
The Catch: You don't need to know the exact size of the "giant leap." You just need to make it big enough. The bigger the leap, the closer you get to the perfect answer.

2. The "Rolling Ball" vs. The "Rocket" (General Convex Functions)

Now, imagine the hill isn't just a simple slope; it's a complex, curved shape. You want to maximize this shape.

The Standard Approach (Minimization):
If you were trying to find the lowest point (minimization), you would roll a ball down the hill. To make sure it stops exactly at the bottom and doesn't bounce past it, you have to make your steps smaller and smaller (vanishing step sizes) until it gently settles.

The Paper's Approach (Maximization):
The authors discovered that when you are trying to find the highest point, the rules flip.

The Rocket Analogy: Instead of rolling a ball, you are firing a rocket. To find the peak, you don't need to slow down. In fact, you need to go fast.
The Finding: If you take steps that are huge (or even infinitely huge), the algorithm doesn't crash; it actually converges to a "stationary point." This is a fancy way of saying it finds a spot where, no matter which way you look, you can't go higher without leaving the fence.
Why it works: In minimization, big steps make you overshoot the bottom. In maximization, big steps push you firmly against the "walls" of your constraints, helping you slide along the edge until you hit the peak.

3. The "Infinite Step" Limit (The Conditional Gradient)

What happens if you take a step so big it's effectively infinite?

The paper shows that this "Infinite Step" method turns into a well-known algorithm called the Conditional Gradient Method (or Frank-Wolfe algorithm).

The Analogy: Imagine you are blindfolded in the garden.
- Standard Method: You feel the ground, take a step, feel again, take another step.
- Infinite Step Method: You shout, "Which direction is the steepest slope?" The ground answers. You then instantly teleport to the very edge of the fence in that direction. Then you ask again, "What's the steepest slope from here?" and teleport to the new edge.
The Result: This "teleporting" method is actually a very efficient way to solve these problems. The paper shows that their "Projected Subgradient Ascent" with huge steps is just a more precise, deterministic version of this teleporting method.

Summary of the Big Ideas

For Simple Slopes (Linear): You don't need to walk to the top. Just aim a giant arrow at the sky, and the point where it lands on the ground (projected back to your set) is the solution. One shot is enough.
For Complex Hills (Non-linear): When maximizing, you don't need to slow down. You can take massive, even infinite, steps. The algorithm naturally settles into the best possible spot without needing to "taper off" like it does for finding the bottom of a valley.
The Connection: This "giant step" approach unifies several different mathematical techniques, showing that they are all just different ways of looking at the same "push against the wall" mechanic.

In a Nutshell:
Most math algorithms are like a cautious hiker taking small steps to avoid falling. This paper says, "If you are climbing a convex mountain, stop being cautious. Take a running leap. The bigger the leap, the better you'll find the peak."

1. Problem Statement

The paper addresses the problem of maximizing a convex function $f$ over a non-empty, closed, and convex set $S$ in a real Hilbert space $H$ .

Context: Unlike convex minimization (a well-understood field), convex maximization is generally NP-hard. The goal is not necessarily to find a global maximum (which is computationally intractable in the general case) but to find first-order stationary points.
Specific Focus: The authors investigate the behavior of Projected Subgradient Ascent (PGA) when using arbitrarily large step sizes. This contrasts with the standard convex minimization setting, where projected subgradient descent requires vanishing step sizes to converge.

2. Methodology

The paper employs two primary methodological approaches:

Single Projection Analysis (Linear Case): For linear objectives, the authors analyze the behavior of a single orthogonal projection of a scaled cost vector. They define the update rule as $x_\eta = P_S(x_0 + \eta c)$ , where $P_S$ is the orthogonal projection onto $S$ , $x_0$ is an initial point, $c$ is the linear objective vector, and $\eta$ is a scaling factor (step size).
Iterative Ascent Analysis (General Convex Case): For general continuous convex functions, they analyze the sequence generated by $x_{k+1} = P_S(x_k + \eta_k g_k)$ , where $g_k$ is a subgradient of $f$ at $x_k$ . They specifically study the regime where step sizes $\eta_k$ are large (bounded away from zero and potentially approaching infinity).

The analysis relies heavily on:

Hilbert Projection Theorem: Properties of the unique closest point in a convex set.
Normal Cone Theory: Using the condition $x - P_S(x) \in N_S(P_S(x))$ .
Monotone Operator Theory: Utilizing maximal monotone operators and resolvents to prove convergence in infinite-dimensional spaces without requiring differentiability or Lipschitz gradients.

3. Key Contributions and Results

A. Linear Optimization via Single Projection

The authors demonstrate that for linear optimization ( $\max \langle c, x \rangle$ ), a single orthogonal projection suffices to obtain an approximate solution.

Convergence: As the scaling factor $\eta \to \infty$ , the point $x_\eta = P_S(x_0 + \eta c)$ converges strongly to $x^*$ , the unique optimal solution closest to the initial point $x_0$ .
Error Bounds: They provide tight bounds on the objective value gap:
$0 \leq \langle c, x^* \rangle - \langle c, x_\eta \rangle \leq \frac{\|x^* - x_0\|^2 - \|x_\eta - x_0\|^2}{2\eta}$
If $S$ is bounded with diameter $D$ , the error is bounded by $D^2 / (2\eta)$ .
Significance: This reduces linear optimization to orthogonal projection. While previous work focused on polytopes, this result holds for general closed convex sets (including those with smooth boundaries) in infinite-dimensional Hilbert spaces.

B. Projected Subgradient Ascent (PGA) for General Convex Functions

The paper establishes convergence guarantees for PGA with large step sizes, a regime previously unexplored for convex maximization.

Monotonicity: The sequence of objective values $\{f(x_k)\}$ is non-decreasing. If $S$ is bounded, the sequence converges.
Connectedness of Accumulation Points: If step sizes are bounded from above, the set of accumulation points of the sequence $\{x_k\}$ is connected.
Stationarity with Large Steps: The most significant result (Theorem 3.14) states that if step sizes are bounded from below (i.e., $\liminf \eta_k > 0$ $lim inf η_{k} > 0$ ) and bounded from above, every accumulation point of the sequence is a first-order stationary point.
- Definition: A point $\bar{x}$ is stationary if there exists a subgradient $g \in \partial f(\bar{x})$ such that $g \in N_S(\bar{x})$ (equivalently, $\langle g, z - \bar{x} \rangle \leq 0$ for all $z \in S$ ).
Relaxed Assumptions: Unlike prior work on non-convex maximization or convex maximization in finite dimensions, this result does not require:
- Differentiability of $f$ .
- Lipschitz continuity of the gradient.
- The Kurdyka-Lojasiewicz (KL) inequality.
- Finite dimensionality (it holds in infinite-dimensional Hilbert spaces).

C. Connection to Conditional Gradient and Iterated Linear Optimization

The authors analyze the limit of PGA as step sizes $\eta_k \to \infty$ .

Limit Behavior: In this limit, the update rule becomes:
$x_{k+1} = \text{argmax}_{z \in M(\nabla f(x_k))} \|z - x_k\|$
where $M(\nabla f(x_k))$ is the set of maximizers of the linearized objective.
Relation to Frank-Wolfe: This limit is a deterministic variant of the Conditional Gradient (Frank-Wolfe) algorithm with unit step size (CGU). Standard CGU selects any maximizer of the linear subproblem; PGA with infinite steps selects the specific maximizer closest to the current iterate.
Relation to Iterated Linear Optimization: When $f(x) = \frac{1}{2}\|x\|^2$ , the PGA limit recovers the "iterated linear optimization" paradigm, showing that this method is a generalization of that approach.

4. Significance and Implications

Theoretical Insight: The paper fundamentally shifts the understanding of convex maximization. It proves that unlike minimization (which needs small steps), maximization benefits from large steps to reach stationary points. This provides a theoretical justification for "aggressive" ascent methods.
Algorithmic Efficiency:
- For linear problems, it suggests that if an efficient projection algorithm exists, linear optimization can be solved via a single projection, potentially bypassing complex simplex or interior-point methods.
- For general convex maximization, it offers a robust algorithm (PGA) that converges to stationary points without needing smoothness assumptions or diminishing step sizes, which are often difficult to tune.
Broad Applicability: The results apply to infinite-dimensional spaces (e.g., semidefinite programming, function spaces) and non-smooth functions, making them highly relevant for modern machine learning and optimization problems involving non-differentiable regularizers or complex constraints.
Complexity Perspective: The reduction of linear optimization to projection challenges the view that projection-based methods are inherently slower. It suggests that efficient projection algorithms can directly translate to efficient linear optimization solvers.

Summary Conclusion

Felzenszwalb and Lee provide a rigorous theoretical framework showing that projected subgradient ascent with large step sizes is a powerful tool for convex maximization. They prove that this method converges to first-order stationary points under minimal assumptions (continuity and convexity only) and demonstrate that in the limit of infinite steps, it unifies with the Conditional Gradient method and Iterated Linear Optimization. Furthermore, they show that for linear objectives, a single projection is sufficient to approximate the solution, linking the complexity of linear optimization directly to that of orthogonal projection.