技术摘要：凸优化中更强的记忆-查询权衡

问题陈述

本文研究了在优化算法受限于有限内存时，最小化 $d$ 维 1-Lipschitz 凸函数（在单位球上）的基本限制。作者分析了具有 $m$ 比特内存的算法的查询复杂度（即一阶预言机查询次数）。目标是找到一个点 $\hat{w}$，使得 $F(\hat{w}) - \min_{w \in B(1)} F(w) \leq \alpha$。

虽然在没有内存限制的情况下，查询复杂度是已知的（$\Theta(\min\{1/\alpha^2, d \log(1/\alpha)\})$），但在高精度机制下（即 $\alpha < 1/\sqrt{d}$ 时），内存与查询复杂度之间的相互作用仍然是一个极具挑战性的开放问题。前人的工作建立了下界，但在内存机制的临界点以及实现近乎最优查询复杂度所需的二次方级内存必要性方面，仍存在差距。

方法论

作者引入了一个新的理论原语——带提示的标记子空间博弈 (Marked Subspace Game with Hint, MSGH)，用于分析受限内存策略的局限性。

带提示的标记子空间博弈 (MSGH)

MSGH 是一个由玩家（Player）和对手（Adversary）针对随机矩阵 $A \in \mathbb{R}^{d' \times d}$ 进行的游戏：

1. 消息阶段： 玩家选择一个函数 $h_1$，用于编码关于 $A$ 的大小为 $m_1$ 比特的消息。
2. 标记阶段： 对手在已知 $A$ 和消息的情况下，选择（“标记”）一个 $k$ 维线性子空间 $L$。
3. 提示阶段： 玩家收到一个微小的“提示” $q$（大小为 $m_2$ 比特），该提示可以依赖于被标记的子空间 $L$ 和 $A$。
4. 查询阶段： 玩家对 $A$ 进行 $T$ 次行查询。
5. 获胜条件： 如果玩家找到一个查询向量 $u$，使其接近 $A$ 的正交方向（即 $\|Au\|_\infty$ 很小），但远离被标记的子空间 $L$，则玩家获胜。

核心洞察： 作者证明，对于任何具有有限内存（较小的 $m_1$）的策略，对手都可以选择一个子空间 $L$，使得任何与 $A$ 近似正交的查询向量都必须位于 $L$ 的一个微小邻域内。这模拟了算法存储特定子空间以规避损失函数中“障碍”项的行为。

硬实例构造

为了将 MSGH 应用于凸优化，作者构造了一个由三部分组成的硬损失函数 $F(w)$：

1. Nemirovski 函数： 线性项 $\langle w, x_j \rangle - j\gamma$ 的最大值，旨在迫使算法发现特定的向量 $x_j$。
2. 障碍函数 (Barrier Function)： 一个涉及 $\|Aw\|_\infty$ 的项，惩罚非正交于随机矩阵 $A$ 的查询。
3. 墙函数 (Wall Function，针对随机化情况)： 对前人工作中术语的修改，迫使查询在发现的向量张成的空间之外具有较小的范数，从而收紧相关性要求。

该构造对于确定性算法是自适应的（使用“抵抗型预言机”），而对于随机化算法则是非自适应的。核心证明技术在于表明，为了在 Nemirovski 函数上取得进展，优化器必须有效地进行 MSGH（或相关的正交相关向量博弈，OCVG），以寻找与 $A$ 正交的向量。

核心贡献

1. 针对随机化算法的新下界

作者证明，任何具有 $m$ 比特内存的随机化算法，在寻找具有多项式级 $d$ 子优性（即 $\alpha = 1/\text{poly}(d)$）的解时，需要：
$$\tilde{\Omega}\left( \frac{d^2}{\sqrt{m}} \right)$$
次查询。

• 意义： 这改进了之前最优的 $\tilde{\Omega}(d^{8/3}/m^{4/3})$ 边界。至关重要的是，它证明了要达到最优的 $\tilde{O}(d)$ 查询复杂度，$\tilde{\Omega}(d^2)$ 级别的内存是必要的（在无内存限制时可达到此复杂度）。此前，仅在准多项式级子优性（$\alpha \leq 2^{-\log^5 d}$）的情况下才确立了这种必要性。

2. 针对确定性算法的新下界

对于确定性算法，作者确立了一个下界：
$$\tilde{\Omega}\left( \min\left\{ d^{1.6}, \frac{d^{8/3}}{m^{2/3}} \right\} \right)$$
这改进了之前最优的 $\tilde{\Omega}(d^{5/3}/m^{1/3})$ 边界。

• 意义： 该边界揭示了在 $m \approx d^2$ 附近存在一个剧烈的相变。
  • 当 $m = O(d^2 \log(1/\alpha))$ 时，像 Vaidya 方法这样的算法可以实现 $O(d \log(1/\alpha))$ 的查询复杂度。
  • 当 $m = \Omega(d^2 / \log(d))$ 时，所需的查询复杂度会跃升一个多项式因子，达到 $\tilde{\Omega}(d^{4/3})$。
  • 这意味着，任何试图改进 Vaidya 方法内存复杂度（即使只是通过对数级改进）的确定性算法，都必须承受多项式级的查询复杂度损失。之前的边界并未表现出如此剧烈的转换。

3. 改进对正交相关向量博弈 (OCVG) 的分析

作者利用 MSGH 对 [CP23] 中引入的 OCVG 进行了更紧凑的分析。他们表明，赢得博弈所需的关联阈值可以从 $(k/d)^{1/4}$ 降低到 $\sqrt{k/d}$。这一更紧的界对于推导随机化和确定性设置下的改进下界起到了关键作用。

结果汇总

算法类型	内存机制	之前的最优下界	新的下界
随机化 (Randomized)	通用 $m$	$\tilde{\Omega}(d^{8/3}/m^{4/3})$	$\tilde{\Omega}(d^2/\sqrt{m})$
确定性 (Deterministic)	通用 $m$	$\tilde{\Omega}(d^{5/3}/m^{1/3})$	$\tilde{\Omega}(\min\{d^{1.6}, d^{8/3}/m^{2/3}\})$

注：这些边界适用于子优性 $\alpha = 1/\text{poly}(d)$。

意义与主张

本文声称解决了 COLT 2019 关于凸优化中记忆-查询权衡的开放问题，因为它提供了首个满足以下条件的下界：

1. 确立了剧烈的相变： 对于确定性算法，这项工作识别出了一个精确的内存阈值（$m \approx d^2$），在该阈值处，查询复杂度会发生多项式跳跃。这阐明了降低切割平面法所需的二次方级内存以下的根本代价。
2. 扩展了二次方内存的必要性： 对于随机化算法，该结果将实现近乎最优查询复杂度的 $\tilde{\Omega}(d^2)$ 内存的必要性，从准多项式机制扩展到了多项式机制。这表明，在高精度凸优化中，内存限制比此前理解的更为严重。
3. 引入了一个鲁棒的原型： 带提示的标记子空间博弈 (MSGH) 被呈现为一个强大的新工具，用于分析优化中的信息论限制，能够处理自适应向量采样以及关于障碍矩阵的信息泄露。

作者强调，这些结果是通过使用 Yao 最小化原理进行的严格下界证明得出的，并不提出新的算法或实验验证。研究结果表明，梯度下降（$O(d)$ 内存）与切割平面法（$\tilde{\Omega}(d^2)$ 内存）之间的差距，在高精度机制下是该问题结构的内在属性。