|
L-Lipschitz Convex
||f(x) - f(y)|| ≤ L||x - y||
|
First-Order Subgradient Oracle (f(x), g ∈ ∂f(x)) |
Ω( (L R / ε)² ) |
O( (L R / ε)² ) |
Subgradient Method (η_t = R / (L√t)) |
|
β-Smooth Convex
||∇f(x) - ∇f(y)|| ≤ β||x - y||
|
First-Order Gradient Oracle (f(x), ∇f(x)) |
Ω( √(β R² / ε) ) |
O( √(β R² / ε) ) |
Nesterov Accelerated Gradient (NAG) |
|
α-Strongly Convex & β-Smooth
Condition number κ = β / α
|
First-Order Gradient Oracle (f(x), ∇f(x)) |
Ω( √κ · log(1/ε) ) |
O( √κ · log(1/ε) ) |
Nesterov AGD with Restart / Heavy-Ball |
|
Constrained on Polytope X
β-smooth over bounded domain diam(X)=D
|
Linear Optimization Oracle (arg min_{s∈X} ⟨∇f(x), s⟩) |
Ω( (β D² / ε) ) |
O( (β D² / ε) ) |
Frank-Wolfe (Conditional Gradient) |
|
Simplex Δ_n Domain (Non-Euclidean)
Dimension-free log(n) geometry
|
First-Order Oracle with Entropic Divergence |
Ω( (L_∞² log n) / ε² ) |
O( (L_∞² log n) / ε² ) |
Mirror Descent (Bregman KL Regularizer) |
|
General Convex (Dimension-dependent)
X ⊂ Rⁿ bounded convex body
|
Zeroth / Subgradient Separation Oracle |
Ω( n · log(1/ε) ) |
O( n² · log(1/ε) ) |
Ellipsoid Method / Center of Gravity |