← All setups

Known Value Nondual Generalized Rate — Known-Value Generalized Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Known-Value Generalized Convex Minimization · Lean proof

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.

Proved result

⌈236⋅(1+(L0⋅R2ε)13+(L1⋅R)23)⋅(1+log⁡(2⋅d)+log⁡(2+L0⋅R2ε+L1⋅R))2⌉+

OracleTemplate.Convergence LongTails.Setups.KnownValueNondualGeneralizedConvex.spec
  LongTails.Theorems.KnownValueNondualGeneralizedRate.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.