Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates
The paper claims an efficient method that nearly matches optimal oracle rates for nonsmooth Lipschitz convex optimization in the nondual norm setting.
Martínez-Rubio and Guzmán study first-order optimization of \(G\)-Lipschitz convex functions over \(\ell_p\)-balls under \(\ell_q\)-norms. For \(p<q\), they give an algorithm with error \(\widetilde{O}_{p,q}(GR/T^{1/p-(1/q-1/2)_+})\) after \(T\) oracle queries. The abstract says this resolves the nonsmooth end of a COLT 2015 open problem. Their construction reduces the optimization task to chasing nested convex sets, using stable centers whose movement can be bounded nearly optimally in high dimensions. ArXiv · AI/CL/LG's note
Martínez-Rubio and Guzmán study first-order optimization of \(G\)-Lipschitz convex functions over \(\ell_p\)-balls under \(\ell_q\)-norms. For \(p<q\), they give an algorithm with error \(\widetilde{O}_{p,q}(GR/T^{1/p-(1/q-1/2)_+})\) after \(T\) oracle queries. The abstract says this resolves the nonsmooth end of a COLT 2015 open problem. Their construction reduces the optimization task to chasing nested convex sets, using stable centers whose movement can be bounded nearly optimally in high dimensions. ArXiv · AI/CL/LG's note
score 5