技术摘要：针对结构化问题的约束变量投影

1. 问题陈述

现代数据科学经常涉及拟合具有两类不同变量的模型：一组进入损失函数的线性变量（$w$），以及一组控制特征、表示或物理参数的非线性变量（$\theta$）。虽然经典的**变量投影（VarPro）**方法能有效消除线性变量，从而降低可分离非线性最小二乘问题的维度，但这些方法主要针对无约束场景设计。

本文解决了处理约束场景时的空白，即剩余的非线性变量 $\theta$ 受限于凸约束（例如稀疏性、范数边界、单纯形约束）。这些约束在字典学习、盲解卷积和少样本学习等应用中至关重要，却使得标准的 VarPro 失效。核心挑战在于如何在不诉诸于会导致病态条件和更高维度的朴素联合优化的情况下，精确消除线性变量 $w$，并在凸可行集 $C$ 上优化 $\theta$。

2. 方法论

2.1 双层解释与简化

作者将约束 VarPro 问题重新解释为一个折叠的双层优化问题（collapsed bilevel optimization problem）：
$$\begin{aligned} \min_{\theta \in C} \quad & f_U(\hat{w}(\theta), \theta) \\ \text{s.t.} \quad & \hat{w}(\theta) \in \arg\min_{w} f_L(w, \theta) \end{aligned}$$
其中，下层问题 $f_L$ 是一个结构化的最小二乘问题。由于下层问题具有闭式解（通过 Moore-Penrose 伪逆），变量 $w$ 被消除，从而得到仅定义在约束集 $C$ 上的简化目标函数 $f(\theta) = f_U(\hat{w}(\theta), \theta)$。

2.2 简化梯度推导

一个关键贡献是推导了简化目标函数的精确简化梯度公式（exact reduced-gradient formulas）（即超梯度）。作者避免了对病态正规方程进行朴素微分。相反，他们利用了：

1. 闭式下层解： $\hat{w}(\theta) = M(\theta)^+ y(\theta)$。
2. 隐式微分： 通过对下层问题的阶一平稳条件进行微分，他们推导出了灵敏度 $\partial_\theta \hat{w}(\theta)$。
3. 向量-雅可比积（VJPs）： 最终梯度 $\nabla f(\theta)$ 通过结合上层目标的直接梯度与涉及下层问题 Hessian 矩阵的链式法则项来高效计算，该 Hessian 矩阵通过自动微分进行评估。

推导出的梯度公式为：
$$\nabla f(\theta) = \nabla_\theta f_U|_{(\hat{w}, \theta)} - \nabla^2_{w\theta} f_L|_{(\hat{w}, \theta)}^\top (M_L^\top M_L)^{-\top} \left[ M_U M_L^+ y_L - y_U \right]$$
在上下层算子相同的标准情况下，耦合项消失，梯度简化为对 $\theta$ 的偏导数。

2.3 算法：约束正则化变量投影（CR-VarPro）

为了求解简化后的约束问题，作者提出了一种无投影条件梯度法（projection-free conditional-gradient / Frank-Wolfe method）。

• 可行集结构： 假设集合 $C$ 可以分解为 $C = C_A \times C_B$，其中 $C_A$ 是紧致且凸的，而 $C_B$ 是无约束的（$\mathbb{R}^{p_B}$）。
• 块线性最小化算子（BLMO）： 标准的 Frank-Wolfe 方法在无界集合上会失效。所提出的 BLMO 通过以下方式处理此问题：
  • 在紧致集 $C_A$ 上求解线性最小化算子。
  • 针对无约束块 $C_B$ 进行归一化梯度下降步（在单位球内最小化）。
• 收敛性： 算法使用线搜索步长更新 $\theta$。理论分析证明，在标准光滑性和紧致性假设下，算法收敛至一阶平稳点，其收敛速率取决于 Frank-Wolfe 间隙（gap）。

2.4 结构化变量的扩展

该框架被扩展到被消除变量 $w$ 受限于低维集合 $\mathcal{W}$（例如仿射子空间或可微流形）的情况。作者证明，若要使下层解映射是全局可微的，约束集 $\mathcal{W}$ 必须是**仿射（affine）**的。这确保了该梯度方法对于卷积变换等结构化问题的有效性。

3. 核心贡献

1. 公式化： 本文将约束变量投影建模为折叠的双层优化问题，统一了 VarPro 与约束优化。
2. 梯度公式： 推导出了显式的、精确的简化梯度公式，这些公式利用了自动微分和闭式下层求解器，避免了与通过正规方程求导相关的数值不稳定问题。
3. 算法设计： 提出了定制的条件梯度算法（CR-VarPro），该算法结合了用于约束块的 Frank-Wolfe 步骤和用于无约束块的归一化梯度步骤，确保了该方法是无投影的，并且对于线性最小化比投影更廉价的集合非常高效。
4. 理论保证： 在标准假设下，确立了向一阶平稳点收敛的性质。
5. 可微性分析： 一个命题表征了下层解映射的可微性，表明全局可微性本质上要求被消除变量的约束集为仿射集合。

4. 实验结果

作者在四个数据科学应用中，将 CR-VarPro 与联合优化的基准方法（采用投影梯度下降）进行了对比评估：

• 稀疏自编码器： 在 MNIST 和 CIFAR10 上，尽管单次迭代成本较高，但 CR-VarPro 在固定的墙钟时间预算内实现了比联合优化更低的测试重建损失。
• 字典学习： 对于具有 $L_1$ 约束的字典问题，CR-VarPro 在重建损失相对于时间的表现上，显示出比投影梯度下降更优的收敛性。
• 盲解卷积： 应用于具有 Frobenius 范数约束的信号恢复，该方法在最小化目标函数的时间效率方面表现出改进。
• 少样本学习： 使用预训练的 ResNet-18 主干网络，该双层公式（优化线性头和特定的中间层）与标准的微调方法（Frozen Ridge, CE Linear Probe, LP-FT）相比，以更少的训练步数和更短的时间达到了具有竞争力的测试准确率。

在所有案例中，该方法均展示了在墙钟效率和数据效率方面的提升（即通过更少的优化步数或更短的时间实现更好的性能）。

5. 意义与主张

本文声称，通过将变量投影解释为双层优化的视角，可以将 VarPro 的降维优势扩展到现代机器学习中常见的约束场景。其意义在于：

• 效率： 消除线性变量降低了问题维度并改善了条件数，同时无投影算法避免了昂贵的欧几里得投影。
• 精确性： 利用精确简化梯度（通过隐式微分）避免了双层优化中常见的近似问题，从而实现了更稳定的收敛。
• 适用性： 该框架足够灵活，可以处理从稀疏表示到少样本学习的各种结构化问题，表明其对具有可分离线性/非线性结构的通用数据科学模型具有普适价值。

作者总结道，虽然该方法需要精确的下层求解，但它为结构化问题的联合优化提供了一个鲁棒的替代方案，未来计划开展针对非精确下层求解和随机变体的研究。