← All setups

Convex Minimization with Local Linear Oracles

Descriptions may be stale. Consult the linked Lean sources.

Convex Minimization with Local Linear Oracles

We consider minimizing f:E→R over a closed convex set C in a real Hilbert space E. On C, f is differentiable and convex with a quadratic upper model of unknown curvature L≥0. A given point x0∈C is within distance R≥0 and objective gap Δ≥0 of a minimizer x⋆∈C; Δ is unknown. The oracle returns exact values and gradients, or a linear minimizer over a ball intersected with C. For ε>0, the goal is a feasible output x¯ with f(x¯)−f(x⋆)≤ε almost surely under P, the law of algorithm and oracle randomness.

The optimization problem is minx∈Cf(x). Write ⟨⋅,⋅⟩ for the inner product on E and ∥⋅∥ for its induced norm. The algorithm receives only E, R, ε, and x0, together with oracle access; L and Δ may enter the call budget but are not algorithm inputs. The optimal objective value is not supplied.

Our assumptions:

Assumption 1 (Feasible set and first-order models). The set C⊆E is closed and convex, and x0∈C. The function f is Fréchet differentiable at every point of C. For every x,y∈C, f(y)≥f(x)+⟨∇f(x),y−x⟩,f(y)≤f(x)+⟨∇f(x),y−x⟩+L2∥y−x∥2.

Assumption 2 (Initial distance and objective gap). There exists x⋆∈C such that f(x⋆)≤f(x)for every x∈C,∥x0−x⋆∥≤R,f(x0)−f(x⋆)≤Δ.

Assumption 3 (Exact value-gradient and local linear access). At any x∈C, a value-gradient query returns (f(x),∇f(x)). A local linear query takes a center x∈C, a radius r≥0, and a direction g∈E, and returns a point v∈argminz∈C∥z−x∥≤r⟨g,z⟩. Such a minimizer exists for every admissible query. Every reply must satisfy this requirement, even when the choice among minimizers depends on previous queries and replies or on oracle randomness.

Both query types count toward a single oracle-call budget, with one call charged for either type. After the allotted calls, the output must satisfy x¯∈C,f(x¯)−f(x⋆)≤εP-a.s. The algorithm’s randomness is independent of the oracle’s randomness, and the minimizer in this requirement is fixed independently of both.

Results

In a real Hilbert space, C is closed and convex, x0∈C, and f is differentiable on C with the convex lower model and quadratic upper model of curvature L≥0. A minimizer x⋆∈C satisfies ∥x0−x⋆∥≤R and f(x0)−f(x⋆)≤Δ, with R,Δ≥0. Access comprises exact value–gradient queries and exact point-only minimization of ⟨g,v⟩ over C∩B―(x,r), with arbitrary ties. Inputs are x0,R and ε>0; L,Δ appear only in the budget. The target is feasible y with f(y)−f(x⋆)≤ε; (1) returns a best-observed point for every seed. The gap bound Δ need not be bounded by LR2.

Unknown optimal value with an exact local linear oracle: UnknownValueSmoothConvexLocalLinear.
Result Oracle complexity Novelty Limitations
(1) CertifiedLevelBroxUnknownValue (Ours) (⋆⋆⋆) (review) O(1+LR2/ε+log(2+Δε+LR2/ε))
(2) Frank–Wolfe (Jaggi 2013, Thm. 1)
Derived bound on C∩B―(x0,R)
O(1+LR2ε); steps 2/(k+2), one value–gradient and one local-LMO call per iteration. (1): O(LR2/ε) versus O(LR2/ε) when LR2/ε≥max{1,log2⁡(2+Δ/ε)}; same oracle and no L,f⋆ input. (1) pays log⁡(2+Δ/ε): at L=0, (2) is exact in one iteration. Needs ε; best-observed rather than last iterate.
(3) BroxGD (Richtárik et al. 2026, Thm. 3.2(ii)) O(1+LR2ε); C⊆Rd, R>0, ∇f L-Lipschitz on an open convex neighborhood of C. (1): LR2/ε→LR2/ε when LR2/ε≥max{1,log2⁡(2+Δ/ε)}. Adaptivity: no L for certification. Scope: Hilbert spaces; upper model only on C. (1) adds log⁡(2+Δ/ε), which can dominate when LR2/ε is small.
(4) Polyak-radius Local LMO (Richtárik and Mahran 2026, Thm. 4, ϑ=1) O(1+LR2+G⋆Rε); C⊆Rd, globally convex differentiable f with L-Lipschitz gradient; exact f⋆ supplied. (1): ε−1/2 rather than ε−1 for fixed L,R>0,Δ,G⋆ as ε↓0. Adaptivity: no f⋆ required. (1) needs R as input; (4) does not.

Abbr: f⋆=f(x⋆); G⋆=∥∇f(x⋆)∥; B―(x,r) is the closed radius-r ball. LMO: linear minimization oracle. Costs count all value–gradient and local-LMO calls together.

Jaggi, Martin. 2013. “Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization.” In Proceedings of the 30th International Conference on Machine Learning, edited by Sanjoy Dasgupta and David McAllester, vol. 28. Proceedings of Machine Learning Research 1. PMLR. https://proceedings.mlr.press/v28/jaggi13.html.
Richtárik, Peter, Kaja Gruntkowska, and Hanmin Li. 2026. Broximal Gradient Descent: A Projection-Free Sister of Projected Gradient Descent. https://doi.org/10.48550/arXiv.2605.08850.
Richtárik, Peter, and Ammar Mahran. 2026. Local LMO Is Secretly a Projection Method! https://arxiv.org/abs/2609.33383v1.

Lean setup