Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory

Blake Woodworth; Nathan Srebro

arxiv: 1907.00762 · v1 · pith:Q7MT6WGRnew · submitted 2019-07-01 · 💻 cs.LG · math.OC· stat.ML

Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory

Blake Woodworth , Nathan Srebro This is my paper

Pith reviewed 2026-05-25 12:18 UTC · model grok-4.3

classification 💻 cs.LG math.OCstat.ML

keywords convex optimizationoracle complexitymemory constraintsfirst-order methodsminimax complexity

0 comments

The pith

Known optimal first-order convex optimization methods require quadratic memory, but whether this is necessary remains open.

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

The paper observes that all known algorithms achieving the lowest possible number of first-order oracle queries for minimizing convex Lipschitz functions use memory quadratic in the dimension. It asks whether this quadratic memory requirement is unavoidable or whether algorithms exist that match the optimal query count with strictly less memory. The broader goal is to characterize how a hard limit on memory changes the minimum number of queries needed.

Core claim

All currently known first-order methods that attain optimal oracle complexity for convex Lipschitz minimization require quadratic memory, and it is open whether the minimax number of queries must increase when memory is restricted below quadratic.

What carries the argument

Minimax number of first-order queries for convex Lipschitz minimization subject to a memory bound.

If this is right

A positive answer would show that memory limits force a strict increase in the number of oracle calls needed for optimal convex optimization.
A negative answer would imply that the known quadratic-memory constructions are not information-theoretically necessary.
Either resolution would give the precise memory-query trade-off curve for first-order convex optimization.

Where Pith is reading between the lines

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

The question is connected to whether lower-bound techniques from streaming or limited-space models can be applied to optimization oracles.
A resolution could guide whether entirely new algorithmic ideas beyond existing optimal-query methods are required for memory-constrained settings.
It suggests examining whether the same trade-off appears in related problems such as stochastic or online convex optimization.

Load-bearing premise

That the quadratic memory used by known optimal-query algorithms is representative of any method achieving that query count rather than an artifact of those particular constructions.

What would settle it

Either an explicit algorithm that achieves the unconstrained optimal query count while using only linear memory, or a proof that any algorithm using sub-quadratic memory must make asymptotically more queries.

read the original abstract

We note that known methods achieving the optimal oracle complexity for first order convex optimization require quadratic memory, and ask whether this is necessary, and more broadly seek to characterize the minimax number of first order queries required to optimize a convex Lipschitz function subject to a memory constraint.

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

This short note flags that known optimal first-order convex optimization methods use quadratic memory and asks whether that is required, but supplies no analysis or partial results.

read the letter

The paper notes that methods achieving the known optimal oracle complexity for first-order convex optimization require quadratic memory, and poses the question of whether this is necessary when memory is limited. It seeks to characterize the minimax number of queries under a memory constraint. What stands out is the framing: it connects the standard optimal rates to an explicit memory limit, which isn't directly addressed in the usual literature on oracle complexity. That seems like a reasonable observation worth raising, especially since practical implementations often face memory constraints in large-scale problems. The limitation is that there's no further work here—no lower bounds, no upper bounds with reduced memory, no examples showing the trade-off. It's entirely a statement of the open problem based on known constructions. The premise that quadratic memory is representative rests on those constructions being the only ones, but the note treats it as motivation for the question rather than a proven fact. No derivations are provided, so the soundness depends on accepting the existing literature at face value. This is aimed at optimization theorists who care about fine-grained complexity and trade-offs. Someone looking for solved results or new algorithms won't get much from it, but it could organize thinking for future papers on memory-efficient methods. I'd recommend sending it to peer review. The question is substantive enough that referees could provide useful input on whether the gap is real and how to approach it, even though the paper itself is brief and contains no new technical content. It might not change practice immediately, but highlighting the issue is useful.

Referee Report

0 major / 1 minor

Summary. The manuscript notes that known methods achieving the optimal oracle complexity for first-order convex optimization require quadratic memory. It poses the open question of whether this is necessary and more broadly seeks to characterize the minimax number of first-order queries required to optimize a convex Lipschitz function subject to a memory constraint.

Significance. Resolving the posed open problem would clarify fundamental trade-offs between memory and oracle complexity in convex optimization. Either a memory lower bound matching the quadratic requirement or the discovery of memory-efficient optimal methods would be of substantial interest to the optimization community, with implications for high-dimensional and resource-limited settings. The note provides a concise and well-formulated statement of the question.

minor comments (1)

[Abstract] Abstract: the premise that known optimal methods require quadratic memory would be strengthened by including at least one specific citation or brief example of such a method.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the note and for recommending minor revision. The manuscript is a concise open-problem statement, and we are pleased that its potential interest to the optimization community is recognized.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The manuscript is a short open-problem note whose sole content is the observation that existing algorithms attaining the known optimal first-order oracle complexity for convex Lipschitz minimization use quadratic memory, followed by the question of whether this is necessary. No theorem, bound, or derivation is asserted; the text therefore contains no internal logical step whose failure would falsify a claim. The premise that the listed constructions are representative is explicitly framed as the motivation for an open question rather than a settled fact.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

This is an open-problem statement with no central derivation. No free parameters, axioms, or invented entities are introduced.

pith-pipeline@v0.9.0 · 5557 in / 987 out tokens · 24926 ms · 2026-05-25T12:18:03.713308+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/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

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

We note that known methods achieving the optimal oracle complexity for first order convex optimization require quadratic memory, and ask whether this is necessary...
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

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

TL,B(d,M,ϵ) = inf {T : inf A∈AM,T sup F∈FdL,B F(A(F))−min∥x∥≤B F(x)≤ϵ}

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.