知识卡片：稳定移动用于非对偶 Lipschitz 凸优化：效率与近最优 Oracle 速率

一句话结论

本文研究 (G)-Lipschitz 凸函数在半径 (R) 的 (\ell_p) 球上、按 (\ell_q) 范数度量的一阶 oracle 优化；对 (p<q) 给出高效算法，达到 (\widetilde O_{p,q}(GR/T^{1/p-(1/q-1/2)_+})) 的误差率，并称解决了 COLT 2015 开放问题（Guz15b）的非光滑端。

事件概述或研究问题

• 研究对象：优化 (G)-Lipschitz 凸函数，约束在半径 (R) 的 (\ell_p)-ball 上，Lipschitz 性相对于 (\ell_q)-norm，其中 (1\le p,q\le\infty)。
• 核心问题：如何高效实现一阶 oracle 复杂度中的近最优率，特别是 (p<q) 的非光滑端。
• 论文称其目标之一是解决 COLT 2015 开放问题 (Guz15b) 的非光滑端，并高效实现 (MBG+26) 的近最优率。

方法/产品要点

• 将凸 Lipschitz 优化归约为 evolving bundle 的子水平集上的 chasing nested convex sets 问题 (LNN95; BBE+20)。
• 每次查询遵循二分逻辑：要么找到一个低函数值点，要么在当前 bundle 子水平集中产生一个 deep cut，然后追逐该割。
• 关键分析工具：选择器的稳定性与 deep cut 强制移动之间的二分法，用于把迭代次数限制在近最优范围。
• 对 (R B_p^d) 的嵌套子集，引入新的 stable center 概念；其移动在 (\ell_q)-norm 中 T 步后受 (\widetilde O_{p,q}(RT^{1-1/p+(1/q-1/2)_+})) 界约束，论文称该界在高维近最优。
• 所提选择器的 Monte Carlo average 以高概率达到近最优率，并可在 real-arithmetic model 中为优化算法多项式时间实现。

主要结果或产业意义

• 对 (p<q)，T 次 oracle 查询后误差为： [ \widetilde O_{p,q}\left(\frac{GR}{T^{1/p-(1/q-1/2)_+}}\right). ]
• 特例：(p=1,q=2)，即 (\ell_1)-ball 半径 R 上相对于欧氏范数的 Lipschitz 凸优化，误差率为 (\widetilde O(GR/T))。
• 论文声称高效实现了 (MBG+26) 的近最优率，并解决 COLT 2015 开放问题 (Guz15b) 的非光滑端。
• 产业意义：摘要未给出直接产业应用；更直接的影响是凸优化理论、一阶 oracle 复杂度和机器学习优化理论。具体产业落地场景待核实。

为什么重要

• 它为长期开放问题中的非光滑端提供了算法性解决，而不仅是下界或存在性陈述。
• 将“稳定选择器”与“深割强制移动”结合，提供了一种可复用的近最优算法分析框架。
• (p=1,q=2) 的特例给出 (\widetilde O(GR/T))，说明在特定几何组合下可达到快速率。
• 与已有卡片脉络：已有卡片涉及输入凸神经网络/Zonotope 上 Lp 范数最大化的参数化复杂性、去中心化在线黎曼优化等；本卡片增量在于非对偶 Lipschitz 凸优化的一阶 oracle 复杂度，以及 COLT 2015 开放问题非光滑端的近最优率，关注点和结果均不同。

局限与不确定性

• 摘要主要给出 (p<q) 的结果；(p\ge q) 或其他参数区域是否覆盖，待核实。
• (\widetilde O_{p,q}) 中对数因子、对 (p,q) 的依赖常数、上下界匹配的精确程度，待核实。
• “高概率”达到近最优率的具体概率界与假设，摘要未展开，待核实。
• 多项式时间实现是在 real-arithmetic model 下；有限精度、数值稳定性与实际实现成本，待核实。
• 论文是否经过同行评审、发表状态、实验或应用验证，材料未显示，待核实。
• 标题中的 “Nondual” 在摘要中没有展开定义；其精确含义与适用边界待核实。
• 论文声称解决 COLT 2015 开放问题的“非光滑端”，但该开放问题的完整表述与解决范围需查原文，待核实。

可用于图书/PPT/简报的角度

• 用“稳定中心 + 深割”二分法讲解近最优凸优化算法的设计直觉。
• 从一阶 oracle 复杂度看 (\ell_p) 约束与 (\ell_q) Lipschitz 几何的匹配。
• 作为 COLT 2015 开放问题非光滑端解决的案例，展示理论优化的长期进展。
• 重点展示特例：(\ell_1)-ball 上的欧氏 Lipschitz 凸优化达到 (\widetilde O(GR/T))。
• 讨论理论算法到多项式时间实现：Monte Carlo 平均选择器与 real-arithmetic model 的边界。
• 与既有凸优化/Lp 几何卡片串联，形成“凸优化与 Lp 几何中的复杂性/最优率”主题线。

原始材料

• 英文标题：Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates
• 英文关键词：G-Lipschitz convex optimization; first-order oracle complexity; (\ell_p)-ball; (\ell_q)-norm; chasing nested convex sets; stable center; deep cut; Monte Carlo selector; COLT 2015 open problem.
• arXiv ID：2609.20701v1
• 作者：David Martínez-Rubio, Cristóbal Guzmán
• 发布/更新：2026-09-17T17:02:55Z
• 类别：Primary math.OC；Categories: math.OC, cs.LG
• 原始来源：https://arxiv.org/abs/2609.20701v1
• PDF：https://arxiv.org/pdf/2609.20701v1
• 输入元数据：Track: academic；Topics: foundation-model