Near-Optimal Acceleration for Smooth ellp / ellq Nondual Convex First-Order Oracle Optimization

David Mart\'inez-Rubio; Brian Bullins; Crist\'obal Guzm\'an; Mathieu Molina

In the authors' words

We study the optimization of convex objectives with $(L, κ - 1)$ -H\"older-continuous gradients in $ℓ_{q}$ over $R B_{p}^{d}$ , $1 < κ \leq 2$ . (MG26) provides selectors with a movement bound for the problem of chasing high-dimensional convex nested sets for every $p < q$ and generally reduces Lipschitz convex optimization to bounds on the movement of selectors. We couple that movement with H\"older descent yielding a polynomial-runtime first-order method whose feasible output, in the high-dimensional regime $T \leq d$ and for $p < min {q, 2}$ , has error $O_{κ, p, q} (\frac{L R ^{κ}}{T ^{κ (1 + 1/ p - (1/ q - 1/2)_{+}) - 1}}),$ after $T$ queries to a first-order oracle, solving the COLT 2015 open problem of (Guz15), up to logarithmic factors. At $(p, q) = (1, 2)$ , the rate is $O (L R^{κ} / T^{2 κ - 1})$ , including $O (L R^{2} / T^{3})$ cubic decay in the smooth case.

Main resultLimitation the authors admit

Near-Optimal Acceleration for Smooth ℓp​ / ℓq​ Nondual Convex First-Order Oracle Optimization

In the authors' words

More on Optimization that day

Benign Nonconvex Landscape for Policy Optimization: Infinite-Horizon Discounted MDPs with General State and Action Spaces

Beyond Shadow Weights: Quantization-Aware Training as Quantized-Endpoint Descent

Energy minimization for eight points on the sphere

Interference-Driven Clustered Optimisation for FM Spectrum Coordination

Goal-Oriented Communication and Control Co-Design via Semantic Push-Pull in Industrial IoT

Near-Optimal Acceleration for Smooth $ℓ_{p}$ / $ℓ_{q}$ Nondual Convex First-Order Oracle Optimization