Alternating Linear Minimization: Revisiting von Neumann's alternating projections

G\'abor Braun; Robert Weismantel; Sebastian Pokutta

arxiv: 2212.02933 · v4 · submitted 2022-12-06 · 🧮 math.OC

Alternating Linear Minimization: Revisiting von Neumann's alternating projections

G\'abor Braun , Sebastian Pokutta , Robert Weismantel This is my paper

Pith reviewed 2026-05-24 10:22 UTC · model grok-4.3

classification 🧮 math.OC

keywords alternating projectionsconvex setslinear minimization oraclefeasibility problemconvex optimizationvon Neumann theorem

0 comments

The pith

An algorithm finds a point in the intersection of two convex sets by alternating calls to linear minimization oracles.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Von Neumann proved that alternating projections onto two convex sets can approximate a point in their intersection. This paper replaces those projections with the weaker linear minimization oracles, which solve a linear optimization problem over each set in turn. It presents an alternating linear minimization procedure that generates a sequence of points converging to the intersection. A reader would care because many convex sets admit efficient linear minimization oracles even when projections are unavailable or expensive.

Core claim

The paper establishes that alternating linear minimization over two convex sets, using only their linear minimization oracles, produces a point in the intersection, thereby extending von Neumann's alternating projections result to this strictly weaker oracle model.

What carries the argument

The alternating linear minimization algorithm, which iteratively solves a linear minimization problem over one convex set and then the other.

If this is right

The method solves feasibility over the intersection whenever the oracles exist.
It applies directly in optimization settings where linear minimization is tractable but projection is not.
The same alternation works for any pair of convex sets admitting the oracles.
No stronger access to the sets, such as membership or separation oracles, is required.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The procedure may extend to cyclic alternation over more than two sets.
It could serve as a subroutine inside conditional-gradient methods that already rely on linear oracles.
Implementations on implicitly defined polytopes become feasible without explicit projection routines.

Load-bearing premise

Linear minimization oracles are available for both convex sets and convexity alone ensures the procedure reaches the intersection.

What would settle it

Two convex sets equipped with linear minimization oracles for which the alternating procedure fails to produce any point belonging to both sets.

read the original abstract

In 1933 von Neumann proved a beautiful result that one can approximate a point in the intersection of two convex sets by alternating projections, i.e., successively projecting on one set and then the other. This algorithm assumes that one has access to projection operators for both sets. In this note, we consider the much weaker setup where we have only access to linear minimization oracles over the convex sets and present an algorithm to find a point in the intersection of two convex sets.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The note gives an alternating algorithm using linear minimization oracles to hit the intersection of two convex sets, but the abstract leaves the conditions for those oracles to be defined unaddressed.

read the letter

The main takeaway is that this note replaces the projection oracles in von Neumann's 1933 alternating projections with linear minimization oracles and still claims to produce a point in the intersection of two convex sets. That is the concrete new piece: an algorithmic construction under strictly weaker access assumptions than the classical result. It frames the feasibility task in a way that could matter when projections are unavailable but linear optimization over each set is cheap. That part is useful for organizing oracle models in convex feasibility work. The authors are clear that the setup is weaker and they present the algorithm directly from the abstract claim. On the execution side, the stress-test note lands. The linear minimization oracle for a direction c returns an argmin only when the infimum is attained. For an unbounded convex set, any c in the recession cone makes the infimum -∞ and the argmin undefined. The abstract states only that the oracles are available and the sets are convex, with no mention of closedness, compactness, or recession-cone restrictions that would guarantee the oracles exist for the directions the algorithm generates. If those conditions are missing from the full paper as well, the central claim rests on an unstated technical assumption that makes the algorithm non-executable in general cases. No circularity appears in the claim itself. This is for people working on oracle-based convex optimization and feasibility algorithms. A reader already thinking about linear optimization oracles versus projections will get the most from it. The work shows clear engagement with the literature on the classical result and the weaker model, so it deserves a serious referee to check whether the proofs close the gap on oracle existence and convergence.

Referee Report

2 major / 2 minor

Summary. The manuscript presents an algorithm, Alternating Linear Minimization, that finds a point in the intersection of two convex sets C and D by successively calling linear minimization oracles over each set, thereby generalizing von Neumann's 1933 alternating projections result which requires projection oracles.

Significance. If the convergence analysis holds under the stated assumptions, the result is significant: LMOs are weaker than projections and are available in closed form for many structured convex sets (e.g., polytopes, spectrahedra) where projections are expensive or unavailable. The work therefore widens the scope of alternating-type methods in convex optimization.

major comments (2)

[Abstract, §1] Abstract and §1: the central claim that the algorithm 'finds a point in the intersection' presupposes that both LMOs always return a finite minimizer. No recession-cone, closedness, or compactness conditions are stated to guarantee that argmin_{x∈C} ⟨c,x⟩ exists and is attained whenever the infimum is finite. This assumption is load-bearing; without it the algorithm is not executable on unbounded sets.
[§3] §3 (convergence theorem): the proof sketch does not address the case in which a linear functional lies in the recession cone of one set, leaving open whether the iterates remain well-defined or whether the claimed convergence to a point in C∩D still holds.

minor comments (2)

[Throughout] Notation: the paper uses C and D for the sets but occasionally switches to script letters; standardize throughout.
[§4] Add a short remark comparing the obtained rate (if any) with the classical von Neumann rate under the stronger projection-oracle model.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the importance of well-definedness assumptions for the linear minimization oracles. We address the two major comments below.

read point-by-point responses

Referee: [Abstract, §1] Abstract and §1: the central claim that the algorithm 'finds a point in the intersection' presupposes that both LMOs always return a finite minimizer. No recession-cone, closedness, or compactness conditions are stated to guarantee that argmin_{x∈C} ⟨c,x⟩ exists and is attained whenever the infimum is finite. This assumption is load-bearing; without it the algorithm is not executable on unbounded sets.

Authors: We agree that the existence of finite minimizers returned by the LMOs is a load-bearing assumption that should be stated explicitly. In the revised manuscript we will add a standing assumption (new Assumption 2.1) that all linear minimization oracles encountered during execution return finite points. We will also include a brief discussion of sufficient conditions (compactness of one set, or the queried direction not belonging to the recession cone of either set) under which this holds, and we will qualify the abstract and §1 accordingly. revision: yes
Referee: [§3] §3 (convergence theorem): the proof sketch does not address the case in which a linear functional lies in the recession cone of one set, leaving open whether the iterates remain well-defined or whether the claimed convergence to a point in C∩D still holds.

Authors: The current proof sketch implicitly assumes that every LMO call returns a finite point. We will revise §3 to treat the recession-cone case explicitly: if a direction lies in the recession cone of one set but the corresponding functional is bounded below on the other set, the algorithm can detect that C ∩ D is empty; otherwise, under the new standing assumption, the iterates remain well-defined and the convergence argument proceeds unchanged. The revised proof will contain a short case analysis covering this situation. revision: yes

Circularity Check

0 steps flagged

No circularity: direct algorithmic construction from LMOs

full rationale

The paper presents a constructive algorithm that alternates linear minimization steps to approximate a point in the intersection of two convex sets, given access to LMOs. This is a self-contained algorithmic derivation with no fitted parameters, no self-definitional quantities, and no load-bearing self-citations. The central result does not reduce to its inputs by construction; it is an explicit procedure whose correctness is argued from convexity and oracle access. External assumptions (e.g., attainment of minima) are stated as prerequisites rather than derived internally. This matches the common case of an honest algorithmic paper with score 0-2.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on standard domain assumptions of convex optimization; no free parameters, invented entities, or ad-hoc axioms are visible in the abstract.

axioms (1)

domain assumption The two sets are convex
Invoked implicitly as the setting for the intersection problem and linear minimization oracles.

pith-pipeline@v0.9.0 · 5601 in / 1030 out tokens · 18975 ms · 2026-05-24T10:22:57.170734+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

we consider the much weaker setup where we have only access to linear minimization oracles over the convex sets and present an algorithm to find a point in the intersection of two convex sets
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 3.1 (Convergence of Cyclic Block-Coordinate Conditional Gradient algorithm)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.