Near-Optimal Acceleration for Smooth $\ell_p$ / $\ell_q$ Nondual Convex First-Order Oracle Optimization (arxiv.org)
arXiv:2609.21880v1 Announce Type: cross
Abstract: We study the optimization of convex objectives with $(L,\kappa-1)$-H\"older-continuous gradients in $\ell_q$ over $R B_p^d$, $1<\kappa\le 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\le d$ and for $p<\min\{q,2\}$, has error $$
\widetilde O_{\kappa,p,q}\!\left(
\frac{LR^\kappa}{T^{\kappa(1+1/p-(1/q-1/2)_+)-1}}
\right), $$ 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 $\widetilde{O}(LR^\kappa/T^{2\kappa-1})$, including $\widetilde{O}(LR^2/T^{3})$ cubic decay in the smooth case.
Abstract: We study the optimization of convex objectives with $(L,\kappa-1)$-H\"older-continuous gradients in $\ell_q$ over $R B_p^d$, $1<\kappa\le 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\le d$ and for $p<\min\{q,2\}$, has error $$
\widetilde O_{\kappa,p,q}\!\left(
\frac{LR^\kappa}{T^{\kappa(1+1/p-(1/q-1/2)_+)-1}}
\right), $$ 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 $\widetilde{O}(LR^\kappa/T^{2\kappa-1})$, including $\widetilde{O}(LR^2/T^{3})$ cubic decay in the smooth case.
Comments