Metraipolis › archive › dc_09cdec4ee574

Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates — arXiv:2609.20701

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.20701
License (as archived): CC0-1.0
Archived: 2026-10-10T04:09:29.486Z
SHA-256 of the archived text: fa0fea6e4a13a263f43f50ae1af0916462d82a5cf9217e3ec3d5501c4e4f0359
Stable URL of this page: https://metraipolis.com/documento/dc_09cdec4ee574

How to cite

Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates — arXiv:2609.20701 — arXiv (en), https://arxiv.org/abs/2609.20701 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_09cdec4ee574 (Metraipolis archive dc_09cdec4ee574, sha256 fa0fea6e4a13a263f43f50ae1af0916462d82a5cf9217e3ec3d5501c4e4f0359)

BibTeX

@misc{dc09cdec4ee574,
  title = {Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates — arXiv:2609.20701},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.20701},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_09cdec4ee574; sha256 fa0fea6e4a13a263f43f50ae1af0916462d82a5cf9217e3ec3d5501c4e4f0359},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.20701. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study efficient algorithms for realizing the first-order oracle complexity of optimization of $G$-Lipschitz convex functions with respect to the $\ell_{q}$-norm over an $\ell_{p}$-ball of radius $R$, where $1\leq p,q\leq \infty$. For $p<q$, we obtain error $\widetilde{O}_{p,q}(GR/T^{1/p-(1/q-1/2)_{+}})$ after $T$ oracle queries, efficiently realizing the nearly optimal rates of (MBG+26), thereby resolving the nonsmooth end of the COLT 2015 open problem (Guz15b). In particular, the rate is $\widetilde{O}(GR/T)$ for Euclidean Lipschitzness over an $\ell_1$-ball of radius $R$ ($p=1,q=2$). Our solution consists of reducing convex Lipschitz optimization to the chasing nested convex sets problem in sublevel sets of an evolving bundle (LNN95; BBE+20): at each query we either find a point with low function value or we produce a deep cut in the current sublevel of the bundle, that we chase. The dichotomy between stability of selectors and forced movement by deep cuts bounds the number of iterations of the algorithm near optimally. For nested subsets of $R B_{p}^{d}$, we introduce a novel notion of stable center whose movement is bounded by $\widetilde{O}_{p,q}(RT^{1-1/p+(1/q-1/2)_{+}})$ in the $\ell_{q}$-norm after $T$ steps, which we show is nearly optimal in high dimensions. A Monte Carlo average of the proposed selector achieves near-optimal rates with high probability and can be implemented in polynomial time for our optimization algorithm in the real-arithmetic model.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-18 in cs.LG).
Categorie arXiv: Optimization and Control (math.OC) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.20701 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T03:48:18.474Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).