Near-Optimal Acceleration for Smooth $\ell_p$ / $\ell_q$ Nondual Convex First-Order Oracle Optimization
The paper claims a near-optimal first-order rate for a nondual $\ell_p/\ell_q$ convex optimization setting, resolving a COLT 2015 open problem up to logs.
Martínez-Rubio, Bullins, Guzmán, and Molina study convex objectives with Hölder-continuous gradients over an $\ell_p$ ball, with gradients measured in $\ell_q$. Their method combines selector movement bounds for nested convex-set chasing with Hölder descent. In the high-dimensional regime $T \le d$ and for $p<\min\{q,2\}$, it gives a polynomial-time feasible method with the stated accelerated error rate after $T$ oracle queries. At $(p,q)=(1,2)$, the abstract highlights cubic decay in the smooth case. ArXiv · AI/CL/LG's note
Martínez-Rubio, Bullins, Guzmán, and Molina study convex objectives with Hölder-continuous gradients over an $\ell_p$ ball, with gradients measured in $\ell_q$. Their method combines selector movement bounds for nested convex-set chasing with Hölder descent. In the high-dimensional regime $T \le d$ and for $p<\min\{q,2\}$, it gives a polynomial-time feasible method with the stated accelerated error rate after $T$ oracle queries. At $(p,q)=(1,2)$, the abstract highlights cubic decay in the smooth case. ArXiv · AI/CL/LG's note
score 6