知识卡片：非对偶设定下 Lipschitz 凸优化的一阶 Oracle 复杂度

一句话结论：该论文在非对偶 (\ell_p/\ell_q) 设定下正面回答 COLT 开放问题的非光滑版本，并把证明核心归结为一个由序列 fat-shattering 维度控制的在线学习博弈，同时导出 Wendel 型几何估计。

事件概述或研究问题：

• 研究一阶黑盒凸优化：可行域为 (\ell_p) 球，目标函数在 (\ell_q) 范数下 Lipschitz。
• 核心问题：较小可行域的几何是否能在 (p<q) 时改善凸优化收敛率？摘要称对 COLT 开放问题（Guz15b）的非光滑版本给出肯定回答，并与先前下界匹配到对数因子。
• 还推进 Sridharan [Sri12, Section 10.1.2, Q3] 提出的根本问题；结果适用于可行集 (X) 与可能次梯度集合 (H) 为凸、中心对称，并满足某类 minmax 定理的情形。

方法/产品要点：

• 关键技术装置是一个新的在线学习博弈：比较器的评估使用截至目前观察到的仿射损失的最大值。
• 用序列 fat-shattering dimension 给出该博弈值的上界与下界，并针对 (\ell_p/\ell_q) 情形进行刻画。
• 一般适用条件包括：(X) 与 (H) 凸、中心对称，且满足某类 minmax 定理。
• 几何推论：估计样本凸包到其均值的期望距离，覆盖多种 Banach 几何；这是 Wendel 定理的一个定量版本，面向有界一般分布，而非仅中心对称分布。

主要结果或产业意义：

• 速率包括：在 (\ell_1) 球上的凸、欧氏 Lipschitz 优化达到 (\widetilde O(1/T))，改进一般假设下的经典 (O(1/\sqrt{T})) 速率。
• 摘要称这些结果与先前下界匹配到对数因子。
• 产业直接意义待核实；从理论看，其意义在于连接一阶 oracle 复杂度、在线学习组合维度与 Banach 几何。

为什么重要：

• 与既有脉络的关系：已有相关卡片已概括该工作的非对偶 Lipschitz 凸优化效率、近最优 oracle 速率以及开放问题结论；本条增量在于技术机制（在线学习博弈、序列 fat-shattering 维度）、一般适用条件，以及 Wendel 型几何推论。具体速率公式如已有卡片所述，此处不重复。
• 对理论学习而言，它展示了“可行域几何”如何改变一阶方法的极限，并把优化下界与在线学习中的组合维度工具联系起来。
• 对几何概率而言，它给出 Wendel 定理的定量、较一般分布版本，具有独立兴趣。

局限与不确定性：

• 仅依据 arXiv 摘要与元数据，全文证明、常数、对数因子与算法实现细节未核验，待核实。
• 实验或数值验证在摘要中未出现，待核实。
• 同行评审或正式发表状态待核实。
• 产业应用与落地场景待核实。
• 来源材料未列官方关键词；本卡片关键词为据标题与摘要提取，官方关键词待核实。

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

• 用“可行域几何如何改变一阶优化极限”讲非对偶 Lipschitz 凸优化。
• 用“比较器取至今最大仿射损失”的在线学习博弈解释证明技术核心。
• 用序列 fat-shattering 维度串联在线学习、组合维度和优化下界。
• 用 Wendel 定理的定量与一般分布版本讲凸包—均值距离。
• 在已有卡片基础上做延伸：从“速率结论”转向“证明工具与外溢几何结论”。

原始材料：

• 英文标题：The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings
• 英文关键词（据标题/摘要提取；来源未列官方关键词）：first-order oracle complexity; Lipschitz convex optimization; nondual settings; sequential fat-shattering dimension; online learning game; Wendel's theorem
• 作者：David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán, Mathieu Molina
• arXiv ID：2609.20687v1
• Published/Updated：2026-09-17T16:55:54Z
• Primary category：math.OC；Categories：math.OC, cs.LG
• Abstract URL：https://arxiv.org/abs/2609.20687v1
• PDF URL：https://arxiv.org/pdf/2609.20687v1