在线牛顿步 ONS：用二阶信息加速在线组合选择的遗憾收敛

一句话版本#

在线牛顿步（Online Newton Step, ONS）：因为对数财富损失 $-\log(b^\top x_t)$ 是 exp-concave 的，可以用梯度外积累积矩阵 $A_t = \sum_s g_s g_s^\top$ 做类牛顿更新 $b_{t+1} = \Pi^{A_t}_{\Delta}\left(b_t - \frac{1}{\eta} A_t^{-1} g_t\right)$，把在线组合选择的遗憾从一阶方法的 $O(\sqrt{T})$ 压到 $O(m \log T)$——指数级更快的收敛，多项式级的每步开销。

这是 Cover 通用组合故事的续集。Cover 的 UP 用贝叶斯混合拿到 $O(m \log T)$ 遗憾但每步要在单纯形上积分（维度爆炸）；ONS 用凸优化拿到同阶遗憾，每步只是一次线性代数运算。

从 Cover 的困境说起#

回顾一下问题设定。每天开盘前你选一个组合权重 $b_t \in \Delta_m$（单纯形：非负、和为一），当天市场揭晓价格相对 $x_t \in \mathbb{R}^m_+$（每个分量 = 今收/昨收），你的财富乘上 $b_t^\top x_t$。$T$ 天后：

$\log W_T = \sum_{t=1}^{T} \log(b_t^\top x_t)$

对手是事后最优常数再平衡组合（BCRP）：知道全部 $T$ 天数据后选出的最优固定权重 $b^*$。遗憾定义为：

$R_T = \max_{b \in \Delta_m} \sum_t \log(b^\top x_t) - \sum_t \log(b_t^\top x_t)$

Cover (1991) 证明 UP 的遗憾是 $O(m \log T)$，理论上无懈可击。但 UP 的每步计算是在 $(m-1)$ 维单纯形上对所有 CRP 做财富加权积分——离散化网格点数 $O(k^{m-1})$，超过 5 个资产就实际不可算。后续的 Kalai-Vempala 采样近似能救一部分，但工程上依然笨重。

一阶在线凸优化（OCO）方法轻得多：**在线梯度下降（OGD）**每步一次梯度投影，**指数梯度（EG）**每步一次乘法更新。但它们对一般凸损失只有 $O(\sqrt{T})$ 遗憾——对 $T=3000$ 个交易日，$\sqrt{T} \approx 55$ 对 $\log T \approx 8$，差距接近一个数量级。

问题：有没有每步开销多项式、遗憾又是 $O(\log T)$ 的算法？

Hazan, Agarwal, Kale (2007) 的回答是 ONS。钥匙是损失函数的一个中间性质。

Exp-concavity：比强凸弱，但足够好#

$O(\log T)$ 遗憾的经典充分条件是强凸：损失的 Hessian 处处有正下界。可惜 $f_t(b) = -\log(b^\top x_t)$ 不是强凸的——它的 Hessian 是

$\nabla^2 f_t(b) = \frac{x_t x_t^\top}{(b^\top x_t)^2}$

一个秩一矩阵，在与 $x_t$ 正交的方向上曲率为零。$m>1$ 时永远不可能强凸。

但它有一个更微妙的性质：$\alpha$-exp-concavity——$e^{-\alpha f_t(b)}$ 是凹函数。对对数损失，$e^{-1 \cdot f_t(b)} = b^\top x_t$ 是线性函数（自然凹），所以 $f_t$ 是 1-exp-concave。

exp-concavity 的力量在于这个不等式（Hazan et al. 引理 3）：对 $\alpha$-exp-concave 且梯度有界的 $f$，存在 $\beta > 0$ 使得

$f_t(b^*) \geq f_t(b_t) + \nabla f_t(b_t)^\top (b^* - b_t) + \frac{\beta}{2}\left[\nabla f_t(b_t)^\top (b^* - b_t)\right]^2$

翻译成人话：损失函数虽然不是各向同性地弯曲（强凸），但在梯度方向上有二次曲率。而遗憾分析恰恰只需要梯度方向的曲率——因为你的损失差本来就是沿着梯度累积的。

这就是 ONS 的几何直觉：用每一步的梯度外积 $g_t g_t^\top$ 累积出一个”经验曲率矩阵” $A_t$，在这个矩阵定义的椭球度量下做牛顿式更新。曲率大的方向步子小，曲率还没探明的方向步子大。

算法本体#

$\begin{aligned} A_t &= A_{t-1} + g_t g_t^\top, \qquad A_0 = \epsilon I \\ b_{t+1} &= \Pi^{A_t}_{\Delta_m}\left(b_t - \tfrac{1}{\eta}\, A_t^{-1} g_t \right) \end{aligned}$

其中 $g_t = -x_t / (b_t^\top x_t)$ 是对数损失的梯度，$\Pi^{A}_{\Delta}$ 是广义投影——在 $A$ 诱导的范数 $\|v\|_A = \sqrt{v^\top A v}$ 下投影回单纯形：

$\Pi^{A}_{\Delta}(y) = \arg\min_{b \in \Delta_m} (b - y)^\top A (b - y)$

三个与普通牛顿法的区别值得强调：

1. $A_t$ 不是 Hessian，是梯度外积的累积和（类似统计里的 Fisher 信息经验估计、或 Adagrad 的满矩阵版本）；
2. 投影在 $A_t$-范数下做，不是欧氏投影——这是遗憾证明成立的关键，用错范数界会断掉；
3. $A_t^{-1}$ 可用 Sherman-Morrison 秩一更新维护，每步 $O(m^2)$ 而非 $O(m^3)$。

遗憾保证（Hazan et al. 2007 定理 2）：

$R_T \leq 5\left(\frac{1}{\alpha} + GD\right) m \log T = O(m \log T)$

其中 $G$ 是梯度上界、$D$ 是可行域直径。与 Cover UP 同阶，但每步是线性代数而不是高维积分。

import numpy as np

def run_ons(X, eta=8.0, eps=1.0):
    """X: (T, m) 价格相对矩阵。返回对数财富路径与权重轨迹。"""
    T, m = X.shape
    b = np.ones(m) / m
    A = eps * np.eye(m)
    logw, W, Bs = 0.0, [], []
    for t in range(T):
        x = X[t]
        ret = b @ x
        logw += np.log(ret)
        W.append(logw); Bs.append(b.copy())
        g = -x / ret                      # 对数损失梯度
        A += np.outer(g, g)               # 秩一累积经验曲率
        y = b - np.linalg.solve(A, g) / eta
        b = gen_simplex_proj(y, A)        # A-范数下投影回单纯形
    return np.array(W), np.array(Bs)

广义投影是一个小 QP。$m=2$ 时单纯形是一条线段，直接一维网格搜索即可；$m$ 大时用任何 QP 求解器（cvxpy/OSQP）。

实验一：Cover 市场上的教科书式 log T#

先在遗憾理论的”标准考场”上验货：Cover 经典对抗市场——资产 A 是现金（价格相对恒为 1），资产 B 每天在翻倍（×2）和减半（×0.5）之间交替。这个市场的妙处：买入持有任何单资产都不赚钱（B 两天一循环回到原点），但 $b^*=0.5$ 的 CRP 每两天稳赚 $\frac{1.5}{2} \times \frac{0.75}{0.5} = 1.125$ 倍——纯粹的再平衡收益，且每轮损失是标准的 exp-concave 函数。

3000 天，三个算法同场竞技，对 BCRP 的累积遗憾：

三条曲线讲了三个故事：

• ONS 贴着 $c \cdot \log T$ 参考线走。右图把横轴换成对数刻度，ONS 遗憾近似一条直线——这就是 $O(\log T)$ 的图形签名。从 T=1000 到 T=3000，遗憾只从 0.360 涨到 0.396；
• OGD 贴着 $c\sqrt{T}$，遗憾持续累积不封顶；
• EG 在这个市场上出了大问题（8.37）：固定学习率的 EG 遗憾界是 $O(G_\infty \sqrt{T \log m})$，而这个市场的梯度界 $G$ 很大（减半日 $x/b^\top x$ 分量可达 2/0.75），固定 η=0.05 太小追不上、调大又震荡——EG 的遗憾界依赖梯度上界的平方，重尾市场是它的天敌。

有趣的是 T=30 时 EG 反而最好——log T 是渐近优势，短窗口内常数项主导。这句话在后文冷水部分还会回来。

实验二：带 regime 切换的市场——二阶敏锐度的 alpha 与成本#

换一个更像真实市场的考场：3000 日双资产，资产 A 年化波动 ~40% 的高波动资产（在第 800-1200 日注入下跌趋势、2000-2400 日注入上涨趋势），资产 B 是年化波动 ~1.6% 的类现金资产。事后最优 CRP 是 $b^* = 0.71$。

终值财富（初始 1）：

ONS 的遗憾是负的——它跑赢了事后最优的固定权重组合。这不是 bug，是重要的概念区分：遗憾界保证你不输 BCRP 太多，但没说你不能赢。BCRP 是被”权重恒定”束缚的基准，而 ONS 是自适应算法——当市场有 regime 切换时，它可以在下跌段减仓、上涨段加仓，做到固定权重做不到的事。

权重轨迹把机制看得很清楚：

红色的 ONS 权重在 A 下跌段（红色底纹）迅速压到接近 0，在上涨段（绿色底纹）拉回 0.5 以上；蓝色 EG 和绿色 OGD 的一阶更新则慢吞吞地微调，3000 天里基本没离开过 0.5 附近。二阶方法用曲率信息重新缩放了每个方向的步长，收敛快、转向也快。

但敏锐是有价格的。换手统计：

• ONS：日均换手 207bp，3000 日累计单边换手 62 倍本金
• EG：日均 95bp，累计 29 倍

按单边成本扣减后的终值：

单边 10bp 时 ONS 的成本拖累约 $62 \times 0.001 = 6.2\%$ 对数财富，20bp 时拖累 12.4%——在低费率市场（美股 ETF、期货）可以接受，在 A 股股票双边千分之一以上的环境里，日频 ONS 的敏锐会被成本吃掉大半。降频到周度再平衡、或加换手惩罚项，是实操的必要修正。

冷水三盆#

第一盆：η 和 ε 在非对抗市场里是真实的超参数。 理论给的 $\eta = \frac{1}{2}\min\{\frac{1}{4GD}, \alpha\}$ 是为最坏情况准备的保守值。实验里 η 从 0.5 到 16 扫描，regime 市场终值从 2.23 变到 1.75——方向性没变（都盈利），但幅度差 27%。η 小 = 信任曲率矩阵、步子大转向快；η 大 = 保守贴近均匀权重。$A_0 = \epsilon I$ 的 ε 同理：太小则前期矩阵病态、权重乱跳，太大则前期等于不更新。没有免费的自适应。

第二盆：log T 优势需要 T 足够大，且对手要”够坏”。 Cover 市场 T=30 时 EG 还领先 ONS；regime 市场里 OGD/EG 对 BCRP 的遗憾其实只有 0.04-0.05——温和的随机市场里一阶方法根本不差（随机市场的期望遗憾和最坏情况遗憾是两回事）。ONS 的价值主张在对抗性/重尾/结构突变场景：那正是梯度外积矩阵累积信息最快的地方。如果你确信市场温和平稳，EG 的每步 $O(m)$ 更香。

第三盆：广义投影是 m 大时的工程瓶颈。 每步一个 $A$-范数 QP，m=500 的股票池就是每天解一个 500 维二次规划——可行但不再轻盈，且 $A_t^{-1}$ 的 Sherman-Morrison 更新在病态时有数值稳定性问题（实践中要定期做 Cholesky 重分解）。对比之下 EG 的更新永远是一行乘法加归一化。ONS 的甜蜜点是 m ≤ 50 的资产配置层，不是全市场选股层。

与家族其他成员的关系图#

ONS 在这张表里的位置一目了然：拿 Cover 的遗憾阶，付 OCO 的计算价。它也是后来一大票工作的起点——Adagrad 的满矩阵版本形式上就是把 ONS 的思想用于一般在线学习，FTL 正则化视角（Follow-The-Approximate-Leader）给了它第二种推导，而近年的 projection-free 变体（用 Frank-Wolfe 替换 QP 投影）在攻它最后一个工程短板。

A 股使用注记#

• T+1 与做空约束天然兼容：ONS 输出的就是单纯形上的多头权重，无需修改；
• 成本是第一敌人：如上文，日频 ONS 换手是 EG 的 2 倍多。建议周频调仓 + 5% 权重死区（偏离小于阈值不动）；
• 资产层面用它，个股层面别用它：沪深 300ETF/国债 ETF/黄金 ETF/货币基金这类 5-10 个资产的配置问题是 ONS 的主场；
• 若你想复现：全部实验代码只依赖 numpy，价格相对矩阵换成真实 ETF 复权净值比即可。

结语#

ONS 是那种”理论优雅落到工程刚好能用”的稀有算法：exp-concavity 这个恰到好处的中间性质，把对数财富问题从一阶方法的 $\sqrt{T}$ 世界拽进了 $\log T$ 世界，而且不需要 Cover 积分的指数开销。实验里它在标准考场复现了教科书曲线，在 regime 市场里甚至打出了负遗憾——但请记住负遗憾的另一面是 207bp 的日换手，以及 η、ε、投影 QP 这些真实的工程摩擦。

遗憾界是保险单，不是收益承诺。 ONS 卖给你的是”最坏情况下不输事后最优 CRP 超过 $O(m\log T)$“这份保单，保费是二阶方法的计算与换手。想清楚你的市场里最坏情况值多少钱，再决定买不买。