← All setups

Known-Value Convex Local Linear Optimization

Descriptions may be stale. Consult the linked Lean sources.

Known-Value Convex Local Linear Optimization

We consider minimizing f:E→R over a closed convex set C in a real Hilbert space E. On C, the function is differentiable and convex with a quadratic upper model of curvature L>0. A given x0∈C is within distance R≥0 of a minimizer with known value f⋆∈R. The oracle returns either a function value and gradient or a local linear minimizer over a queried ball intersected with C. For ε>0, the goal is x¯∈C with f(x¯)−f⋆≤ε almost surely under P, the joint law of algorithm and oracle randomness.

The optimization problem is minx∈Cf(x). The norm ∥⋅∥ is induced by the inner product ⟨⋅,⋅⟩ on E. The algorithm receives E, L, R, ε, f⋆, and x0; the objective and feasible set are accessed through the oracle.

Our assumptions:

Assumption 1 (Feasible set). The set C⊆E is closed and convex, and x0∈C.

Assumption 2 (Convexity and quadratic upper model). 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 3 (Known minimum and initial distance). There exists x⋆∈C such that f(x⋆)=f⋆,f(x⋆)≤f(x)for every x∈C,∥x0−x⋆∥≤R.

The oracle supports two types of queries. At x∈C, a value–gradient query returns (f(x),∇f(x)). A local linear query specifies 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 point must exist for every valid local linear query. The oracle may choose among these minimizers using the query history and its randomness, but every reply must satisfy the stated requirement. Both query types count toward a single total oracle-call budget.

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 in the joint law P.

Results

A real Hilbert space, a closed convex set C, and x0∈C. The differentiable objective satisfies 0≤f(y)−f(x)−⟨∇f(x),y−x⟩≤(L/2)∥y−x∥2 for x,y∈C. Known inputs are L>0, R≥0, ε>0, and f⋆=f(x⋆) for a minimizer x⋆∈C with ∥x0−x⋆∥≤R. Exact oracles return (f(x),∇f(x)) and a minimizer of ⟨g,v⟩ over v∈C∩B(x,r). Target: feasible y with f(y)−f(x⋆)≤ε; (1) guarantees its last primal iterate for every seed and oracle tie-breaking choice.

Known-value convex optimization with exact local linear minimization: KnownValueSmoothConvexLocalLinear.
Result Oracle complexity Novelty Limitations
(1) SplitBroxKnownValue (Ours) (⋆⋆⋆) (review) O(1+LR2/ε) total value-gradient and local-LMO calls, including all trials.
(2) BroxGD (Richtárik et al. 2026, Thm. 3.2(ii), Cor. D.2) O(1+LR2/ε) total value-gradient and local-LMO calls. Finite-dimensional; R>0; L-Lipschitz gradient on an open convex neighborhood of C. (1): factor LR2/ε fewer calls when LR2/ε≥1; last instead of best iterate. Scope: quadratic models only on C suffice. (1) needs exact f⋆ and L additionally; (2) uses only R,K to set radii.
(3) Polyak-radius BroxGD (Richtárik et al. 2026, Thm. 3.5, Eq. (24)) O(1+(∥∇f(x⋆)∥+LR)2R2ε2) total value-gradient and local-LMO calls. Finite-dimensional; smooth on an open neighborhood of C; known f⋆. (1): ε−1/2 instead of ε−2 in this general guarantee, without ∥∇f(x⋆)∥ dependence; last instead of averaged iterate. (1) needs L,R additionally.
(4) APMM (Deng et al. 2026, Alg. 1, Thm. 2.1); ρ=1, Xk=C, no functional constraints O(1+LR2/ε) total value-gradient evaluations and exact projections onto C∩{ℓf≤f⋆}. Finite-dimensional smooth case. (1) matches the accelerated order using point-only local LMOs, with no logarithmic search overhead. Different oracles prevent a direct cost comparison. (1) needs L,R additionally; (4) is parameter-free apart from f⋆,ε.
(5) CGS (Lan and Zhou 2016, Cor. 3, 2014 preprint); special case: bounded C⊆Rd of diameter D O(1+LD2/ε) total gradient and global-LMO calls; gradient calls alone: O(1+LD2/ε). (1): for R≤D and LD2/ε≥1, at least a factor LD2/ε fewer linear-oracle calls. Scope: unbounded C allowed. (1) needs f⋆ and the stronger local LMO; (5) needs only global linear minimization over C.

Abbr: LMO: linear minimization oracle; local LMO: one point minimizing a linear function on C∩B(x,r); B(x,r): closed ball; D=supx,y∈C∥x−y∥; K: iteration horizon; ℓf(v;z)=f(z)+⟨∇f(z),v−z⟩. Costs count each oracle invocation once.

Deng, Qi, Guanghui Lan, and Zhenwei Lin. 2026. Uniformly Optimal and Parameter-Free First-Order Methods for Convex and Function-Constrained Optimization. https://doi.org/10.48550/arXiv.2412.06319.
Lan, Guanghui, and Yi Zhou. 2016. “Conditional Gradient Sliding for Convex Optimization.” SIAM Journal on Optimization 26 (2): 1379–409. https://doi.org/10.1137/140992382.
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.

Lean setup