The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings
Smaller feasible-set geometry can improve nonsmooth convex optimization rates.
The paper proves this for first-order black-box optimization over an `ell_p` ball with objectives Lipschitz in `ell_q`, in the case `p < q`. It gives rates matching prior lower bounds up to logarithmic factors, including near-`O(1/T)` for Euclidean-Lipschitz convex optimization over the `ell_1` ball. The authors’ main tool is a new online learning game tied to sequential fat-shattering dimension. They also derive quantitative Banach-space estimates related to Wendel’s theorem. ArXiv · AI/CL/LG's note
The paper proves this for first-order black-box optimization over an `ell_p` ball with objectives Lipschitz in `ell_q`, in the case `p < q`. It gives rates matching prior lower bounds up to logarithmic factors, including near-`O(1/T)` for Euclidean-Lipschitz convex optimization over the `ell_1` ball. The authors’ main tool is a new online learning game tied to sequential fat-shattering dimension. They also derive quantitative Banach-space estimates related to Wendel’s theorem. ArXiv · AI/CL/LG's note
score 5