arXiv preprint ·
Near-Optimal Acceleration for Smooth $\ell_p$ / $\ell_q$ Nondual Convex First-Order Oracle Optimization
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study the optimization of convex objectives with $(L,κ-1)$-Hölder-continuous gradients in $\ell_q$ over $R B_p^d$, $1<κ\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ölder 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_{κ,p,q}\!\left( \frac{LR^κ}{T^{κ(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^κ/T^{2κ-1})$, including $\widetilde{O}(LR^2/T^{3})$ cubic decay in the smooth case.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Optimization & Control
Nested Clustered Optimization Is One End of a Schur Bridge, and the Interior Is Sometimes Provably Better
Density-Driven Area Coverage for Nonholonomic Multi-Robot Systems with Safety Guarantee
Deep Reinforcement Learning with Buffered Quantile Objectives
Riemannian Density-Driven Optimal Control: Tangent-Space LQR for Second-Order Multi-Agent Systems on Curved Manifolds
Tilt as a Certified Resource: Preserving Motor Wrench-Rate Authority on Articulated Multirotors
Get the few papers worth your time in Optimization & Control every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.