English static mirror for SEO/GEO · AI-assisted translation · Read Chinese original
智柴网 中文原文

Stable Movement for Nondual Lipschitz Convex Optimization: Efficient First-Order Algorithms Over Lp Balls

Forum topic · 小凯 · 2026-09-20

Summary

This post summarizes an arXiv paper (2609.20701) by David Martínez-Rubio and Cristóbal Guzmán on efficient first-order algorithms for optimizing G-Lipschitz convex functions over an l_p-ball of radius R with respect to the l_q norm. For p<q, the authors achieve error Õ_{p,q}(GR/T^{1/p-(1/q-1/2)_+}) after T oracle queries, efficiently realizing nearly optimal rates and resolving the nonsmooth end of a COLT 2015 open problem. Notably, the rate is Õ(GR/T) for Euclidean Lipschitz functions over an l_1-ball. The approach reduces convex Lipschitz optimization to chasing nested convex sets within sublevel sets of an evolving bundle: each query either finds a low-value point or produces a deep cut that is then chased. The paper introduces the concept of a stable centroid, whose l_q-norm movement over T steps is Õ_{p,q}(RT^{1-1/p+(1/q-1/2)_+}), shown to be nearly optimal in high dimensions. A Monte Carlo averaging of the proposed selection achieves near-optimal rates with high probability in polynomial time in the real arithmetic model.

Paper Overview

  • Field: Machine Learning / Optimization
  • Authors: David Martínez-Rubio, Cristóbal Guzmán
  • Posted: 2026-09-17
  • arXiv: 2609.20701

    • Summary

    The paper studies efficient algorithms for realizing the first-order oracle complexity of optimizing G-Lipschitz convex functions (with respect to the l_q norm) over an l_p-ball of radius R, where 1 ≤ p, q ≤ ∞.

    For p < q, the authors obtain error Õ_{p,q}(GR/T^{1/p-(1/q-1/2)_+}) after T oracle queries, efficiently realizing the nearly optimal rates of (MBG+26) and thereby resolving the nonsmooth end of the COLT 2015 open problem (Guz15b). In particular, the rate is Õ(GR/T) for Euclidean Lipschitzness over an l_1-ball of radius R (p = 1, q = 2).

    Method

    The solution reduces convex Lipschitz optimization to the chasing nested convex sets problem within sublevel sets of an evolving bundle (LNN95; BBE+20): at each query, the algorithm either finds a point with sufficiently low function value, or it produces a deep cut in the current sublevel set and chases it. A dichotomy between selector stability and deep-cut-enforced movement yields the nearly optimal iteration bounds.

    Key Contributions

  • For nested subsets of an l_p-ball of radius R, the authors introduce the new concept of a stable centroid: after T steps, its l_q-norm movement is at most Õ_{p,q}(RT^{1-1/p+(1/q-1/2)_+}), which is proven to be nearly optimal in high dimensions.
  • A Monte Carlo averaging of the proposed selector achieves the near-optimal rates with high probability.
  • The algorithm is implementable in polynomial time in the real arithmetic model.

Original Abstract (excerpt)

> We study efficient algorithms for realizing the first-order oracle complexity of optimization of G-Lipschitz convex functions with respect to the l_q-norm over an l_p-ball of radius R, where 1 ≤ p, q ≤ ∞. For p < q, we obtain error Õ_{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)...

---

*Auto-collected on 2026-09-20.*

Tags

#convex-optimization#first-order-methods#lipschitz-continuity#oracle-complexity#nested-convex-sets#stable-centroid#arxiv#machine-learning

This page is an English static mirror generated for search and AI citation. It may be a full translation or structured summary of the Chinese original. Canonical interactive discussion lives on the Chinese page: https://zhichai.net/topic/178635015