← All setups

Known-Value Generalized Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Known-Value Generalized Convex Minimization

We consider minimizing a continuously differentiable convex function f:Rd→R, where d≥1. The function f is (L0,L1)-smooth in the Euclidean norm, with L0,L1>0. Its minimum value f⋆∈R is known, and a given point x0∈Rd lies within coordinate ℓ1 distance R>0 of a global minimizer. The oracle returns (f(x),∇f(x)) at x. For ε>0, the goal is an output x¯∈Rd satisfying f(x¯)−f⋆≤ε almost surely under P, the law of the algorithm’s randomness.

The optimization problem is minx∈Rdf(x). We write ∥⋅∥2 for the Euclidean norm and ∥v∥1=∑i=1d|vi| for the coordinate ℓ1 norm. The algorithm receives d, L0, L1, R, ε, f⋆, and x0.

Our assumptions:

Assumption 1 (Convexity). For every x,y∈Rd and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y).

Assumption 2 (Generalized smoothness). The function f is differentiable everywhere, and ∇f is continuous. For every x,y∈Rd, ∥∇f(x)−∇f(y)∥2≤(L0+L1supz∈[x,y]∥∇f(z)∥2)∥x−y∥2,[x,y]={(1−t)x+ty:t∈[0,1]}.

Assumption 3 (Known minimum and initial distance). There exists x⋆∈Rd such that f(x⋆)≤f(x)for every x∈Rd,f(x⋆)=f⋆,∥x0−x⋆∥1≤R.

Queries may be made at any point of Rd, with each query returning both the exact function value and the exact gradient. After the allotted oracle calls, the output must satisfy f(x¯)−f(x⋆)≤εP-a.s.

Results

Convex f∈C1(Rd), d≥1, with L0,L1,R,ε>0 and ∥∇f(x)−∇f(y)∥2≤(L0+L1supz∈[x,y]∥∇f(z)∥2)∥x−y∥2. A global minimizer satisfies ∥x0−x⋆∥1≤R; f⋆=f(x⋆) is known. Exact value–gradient oracle. Target: f(x^)−f⋆≤ε deterministically.

Comparison for KnownValueNondualGeneralizedConvex.
Result Oracle complexity Novelty Limitations
(1) KnownValueNondualGeneralizedRate (Ours) (⋆⋆⋆) (review) O((1+A1/3+B2/3)ℓ2) paired value–gradient calls.
(2) (Rudomanov et al. 2026), Thm. 3.7 O(A+(1+B)log⁡(2+B)) gradient calls; applies with ∥x0−x⋆∥2≤R. (1): A1/2→A1/3, B→B2/3 up to logarithms. For A=B2, d≤B→∞: O(Blog⁡B)→O(B2/3log2⁡B). (1) needs f⋆, values, and an ℓ1 prior; converting an ℓ2 radius costs A↦dA, B↦dB. Worse dimension dependence, including A,B=O(1).
(3) (Martínez-Rubio et al. 2026), Thm. 1, (26), p=1,q=2,κ=2 O((1+C1/3)h8) value–gradient calls; uniform L-Lipschitz gradient near ∥x−x0∥1≤R. Probability 1−δ; stated high-dimensional regime T≤d. (1): polynomial B2/3 dependence where uniform L can grow exponentially in B. Smooth overlap L=L0, B≤1: matches A1/3, with logarithmic power 2 instead of 8. (1) needs f⋆; exact averaged-projection selector has no proved efficient implementation. (3) has polynomial runtime and also handles constrained minimizers.

Abbr: A=L0R2/ε, B=L1R, ℓ=1+log⁡(2d)+log⁡(2+A+B); C=LR2/ε, h=1+log⁡(2d)+log⁡(2+C)+log⁡(1/δ); δ∈(0,1) is failure probability, T is the query budget. L is a uniform Euclidean gradient Lipschitz constant.

Martínez-Rubio, David, Brian Bullins, Cristóbal Guzmán, and Mathieu Molina. 2026. Near-Optimal Acceleration for Smooth ℓp/ℓq Nondual Convex First-Order Oracle Optimization. https://arxiv.org/abs/2609.21880v1.
Rudomanov, Mikhail, Ivan Fomin, Alexander V. Gasnikov, and Fedor S. Stonyakin. 2026. Descending Everest with First-Order Oracles: Oracle Complexity of Convex Optimization Under (L0,L1)-Smoothness. https://arxiv.org/abs/2610.21461v1.

Lean setup