一种用于Minty型广义变分不等式的块坐标与方差缩减方法

《ACM / IMS Journal of Data Science》：A Block Coordinate and Variance-Reduced Method for Generalized Variational Inequalities of Minty Type

该论文提出一种新型随机块坐标方法（REM），用于高效解决块可分解的广义变分不等式（GMVI）。方法结合算子外推与重要性采样，在块Lipschitz参数高度非均匀时，复杂度提升达线性因子m。同时，REM在有限和问题中实现方差减少，当组件Lipschitz参数非均匀时，复杂度比现有方法优√m倍。应用案例涵盖强化学习策略评估、矩阵博弈和L1回归，验证了其在多个数据科学场景的有效性。

　　在数据科学和优化问题中，块坐标方法是一种广泛应用的优化策略。这类方法通过每次仅更新变量的一个子集来减少计算成本，从而在特定条件下显著提高算法效率。然而，现有的方法在处理更广泛的变分不等式（Variational Inequalities, VIs）问题时，尤其是当问题具有非均匀块Lipschitz参数时，未能充分展示出块坐标方法的复杂度优势。本文提出了一种新的随机块坐标方法，该方法不仅在块分解结构的变分不等式问题中表现出显著的复杂度改进，还适用于具有有限和结构的更广泛问题，并展示了其在非均匀Lipschitz参数下的复杂度优势。

### 问题陈述

变分不等式问题广泛应用于建模各种均衡问题，特别是在涉及鲁棒性的数据科学场景中。在Minty类型的变分不等式问题中，目标是找到一个向量 $ \mathbf{x}^* \in \chi $，使得对于任意 $ \mathbf{x} \in \chi $，满足：
$$
\langle \mathbf{F}(\mathbf{x}), \mathbf{x} - \mathbf{x}^* \rangle + g(\mathbf{x}) - g(\mathbf{x}^*) \ge 0,
$$
其中 $ \mathbf{F} $ 是单调算子，$ g $ 是一个凸函数，且其近似梯度可以高效计算。与常见的最小化问题不同，变分不等式问题的算法在具有块分解结构和非均匀Lipschitz常数的情况下，通常不会表现出相同的复杂度优势。因此，问题的核心在于：在具有块分解结构和非均匀Lipschitz常数的情况下，是否可以显著提高变分不等式问题的复杂度？

### 方法

本文提出了一种新的随机块坐标方法，称为Randomized Extrapolated Method（REM）。该方法结合了算子外推策略和一种新的随机估计器，以减少计算复杂度。具体来说，REM采用类似于镜像下降的更新方式，但通过引入一个外推算子，以动量项的方式进行更新。这种方法不仅适用于块分解结构的问题，还适用于具有有限和结构的问题，其中可以视为一种方差减少方法。

在块分解结构中，REM的更新过程可以表示为：
$$
\mathbf{x}_k = \arg \min_{\mathbf{u} \in \mathbb{R}^d} \left\{ \sum_{i=1}^k a_i \big( \langle \widehat{\mathbf{F}}_i, \mathbf{u} \rangle + g(\mathbf{u}) \big) + D(\mathbf{u}, \mathbf{x}_0) \right\},
$$
其中 $ \widehat{\mathbf{F}}_i $ 是外推算子，$ a_i $ 是步长参数，$ D(\cdot, \cdot) $ 是一个Bregman散度，用于定义强凸性。此外，REM还维护一个表，记录每个块的估计值，并在每次迭代中更新特定的块。

在有限和结构中，REM可以视为一种方差减少方法。通过使用重要性采样的策略，REM能够更高效地估计算子的值，从而在非均匀Lipschitz参数下实现显著的复杂度提升。

### 结果

本文的算法在块分解结构和有限和结构的变分不等式问题中均表现出显著的复杂度优势。在块分解结构中，当块Lipschitz参数高度非均匀时，REM的复杂度可以比传统的全向量更新方法提高一个与块数 $ m $ 成线性关系的因子。在有限和结构中，当组件Lipschitz参数高度非均匀时，REM的复杂度可以比现有的方差减少方法提高一个与 $ \sqrt{m} $ 成比例的因子。

此外，REM在有限和结构中可以视为一种方差减少方法，其性能与现有的SAGA型方法相比具有显著优势。通过合理选择采样概率分布，REM能够在保持高效计算的同时，实现更优的复杂度。

### 重要性

REM是首个在非均匀块Lipschitz参数下透明展示复杂度优势的块坐标方法，适用于广泛的变分不等式问题。其优势不仅体现在块分解结构上，还体现在有限和结构的方差减少应用中。这一方法的提出，填补了块坐标方法在变分不等式问题中的研究空白，为实际应用提供了更高效的优化工具。

### 与现有方法的比较

在块分解结构中，现有的方法如[38]在非均匀Lipschitz参数下复杂度较低，但本文的方法进一步优化了这一复杂度。通过合理选择采样概率分布，REM的复杂度可以达到 $ \mathcal{O} \left( \min \left\{ \frac{\Vert \mathbf{\lambda} \Vert_{1/2} \sup_{\mathbf{x} \in \mathrm{dom}(g)} D(\mathbf{x}, \mathbf{x}_0)}{\epsilon}, \left( m + \frac{\Vert \mathbf{\lambda} \Vert_{1/2}}{\gamma} \right) \log \left( \frac{\Vert \mathbf{\lambda} \Vert_{1/2} D(\mathbf{x}_*, \mathbf{x}_0)}{\epsilon} \right) \right\} \right) $，其中 $ \mathbf{\lambda} $ 是块Lipschitz参数向量，$ D(\cdot, \cdot) $ 是Bregman散度，$ \gamma $ 是强凸参数。

在有限和结构中，REM的复杂度可以达到 $ \mathcal{O} \left( \min \left\{ \frac{L_{\mathbf{p}, \mathbf{q}} \sup_{\mathbf{x} \in \mathrm{dom}(g)} D(\mathbf{x}, \mathbf{x}_0)}{\epsilon}, \left( \frac{1}{q_{j_*}} + \frac{L_{\mathbf{p}, \mathbf{q}}}{\gamma} \right) \log \left( \frac{L_{\mathbf{p}, \mathbf{q}} D(\mathbf{x}_*, \mathbf{x}_0)}{\epsilon} \right) \right\} \right) $，其中 $ L_{\mathbf{p}, \mathbf{q}} $ 是基于采样概率分布的参数。

### 实例应用

1. **强化学习中的策略评估**：在强化学习中，策略评估问题可以通过变分不等式框架进行建模。通过引入块分解结构，REM可以高效地解决这一问题，其复杂度与矩阵的非零元素数量和块数成比例。

2. **矩阵游戏**：标准的矩阵游戏可以通过变分不等式框架进行建模，其中包含一个双重变量。通过REM方法，可以在非均匀Lipschitz参数下实现显著的复杂度提升。

3. **盒约束的 $ \ell_1 $ 回归**：盒约束的 $ \ell_1 $ 回归问题可以通过变分不等式框架进行建模，其中包含一个目标向量和一个约束集。通过REM方法，可以在非均匀Lipschitz参数下实现高效的优化。

4. **最小绝对偏差问题**：最小绝对偏差问题可以通过变分不等式框架进行建模，其中包含一个目标向量和一个约束集。通过REM方法，可以在非均匀Lipschitz参数下实现高效的优化。

### 结论

本文提出了一种新的随机块坐标方法，该方法在块分解结构和有限和结构的变分不等式问题中均表现出显著的复杂度优势。通过合理选择采样概率分布，REM能够在非均匀Lipschitz参数下实现与块数 $ m $ 成线性关系的复杂度提升。这一方法不仅填补了块坐标方法在变分不等式问题中的研究空白，还为实际应用提供了更高效的优化工具。未来的研究可以进一步探索在非均匀和均匀Lipschitz参数下的复杂度平衡，以及如何在不同问题中优化采样策略以实现更优的性能。