1 概述

1.1 题目

2021IJCAI：多示例学习优化间隔分布机 (Optimal margin distribution machine for multi-Instance learning)

1.2 摘要

最近的间隔理论研究表明，间隔分布 (Margin distribution) 对泛化能力的影响重于最小间隔 (Minimal margin)。受此启发，提出了多示例 (Multi-instance learning, MIL) 最优间隔分布机 (ODM)，其通过优化间隔分布来鉴别关键实例。进一步扩展随机加速镜像近似方法 (Stochastic accelerated mirror prox method) 来解决该公式化的极小极大问题。

1.3 Bib

@inproceedings{Zhang:2021:23832389,
author		=	{Teng Zhang and Hai Jin},
title		=	{Optimal margin distribution machine for multi-instance learning},
booktitle	=	{International Conference on International Joint Conferences on Artificial Intelligence},
pages		=	{2383--2389},
year		=	{2021}
url			=	{https://www.ijcai.org/proceedings/2020/0330.pdf}
}

2 基础知识

令$\mathcal{X}\subseteq {\mathbb{R}}^n$和 Y = { − 1 , 1 } \mathcal{Y}=\{-1,1\} Y={−1,1}分别表示输入和输出空间。对于任意的$m\le 1$，整数的集合 { 1 , … , m } \{1,\dots,m\} {1,…,m}表示为$[m]$。与某个正定核$\kappa$关联的特征映射表示为：$\varphi :\mathcal{X}\to \mathbb{H}$。

2.1 ODM

定义有标记实例$(\mathbf{x},y)$的间隔$\gamma (\mathbf{x},y)$为Sign决策值，即$\gamma (\mathbf{x},y)=y{\mathbf{w}}^T\varphi (\mathbf{x})$，其可以作为预测的置信度 (Confidence)。间隔越大，预测的标签也越可信。
众所周知，SVM使用最大边界理论来描绘决策边界，所获得的分割超平面包含少量实例，也称支持向量，余下的实例则是可以忽略的。当噪声实例存在时，学习者可能被误导，从而产生次优决策边界。
与此相应，优化间隔分布是一个更健壮性的策略，其通过探索整个数据集来防止噪声实例的干扰。描述间隔分布最简单的方法是通过第一和第二统计，即间隔均值和方差。此外，同时最大化均值和最小化方差可以产生更严格的泛化边界。优化间隔分布机 (Optimal margin distribution machine, ODM) 被初定义为😮‍：
$$\begin{array}{rl}{\min }_{\mathbf{w},\overline{\gamma },{\xi }_i,{ϵ}_i}& \frac{1}{2}\Vert \mathbf{w}{\Vert }^2-\eta \overline{\gamma }+\frac{\lambda }{m}{\sum }_{i\in [m]}({\xi }_i^2+{ϵ}_i^2),\\ \text{ s.t.}& \gamma ({\mathbf{x}}_i,y_i)\ge \overline{\gamma }-{\xi }_i,\\ & \gamma ({\mathbf{x}}_i,y_i)\le \overline{\gamma }+{ϵ}_i,\forall i\in [m],\end{array}\text{\hspace{1em}(1)}$$其中$\eta$喝$\lambda$是正则权衡参数，$\overline{\gamma }$是间隔均值，以及${\xi }_i$和${ϵ}_i$是$\gamma (\mathbf{x},y)$和间隔均值之间的偏差，因此公式1中的最后一项${\sum }_{i\in [m]}({\xi }_i^2+{ϵ}_i^2)/m$其实是间隔方差。
为了使得模型清晰有效，ODM被引入了三个改进：

1. 固定间隔均值；
2. 不同的偏差分配不同的权重；
3. 允许偏差小于给定阈值$\theta$以获取稀疏解。具体如下：

$$\begin{array}{rl}{\min }_{\mathbf{w},{\xi }_i,{ϵ}_i}& F(\mathbf{w})=\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+\frac{\lambda }{m}{\sum }_{i\in [m]}\frac{{\xi }_i^2+\nu {ϵ}_i^2}{(1-\theta {)}^2},\\ \text{ s.t. }& y_i{\mathbf{w}}^T\varphi \left({\mathbf{x}}_i\right)\ge 1-\theta -{\xi }_i,\\ & y_i{\mathbf{w}}^T\varphi \left({\mathbf{x}}_i\right)\le 1+\theta +{ϵ}_i,\forall i\in [m].\end{array}\text{\hspace{1em}(2)}$$其中$v$是不同偏差的权衡参数，以及$(1-\theta {)}^2$用于缩放第二项的替代损失。

3 方法

给定包含$m$个的训练集 S = { B i , y i } i ∈ [ m ] \mathcal{S}=\{\mathcal{B}_i,y_i\}_{i\in[m]} S={Bi​,yi​}i∈[m]​，其中 B i = { x i , 1 , … , x i , m i } \mathcal{B}_i=\{\boldsymbol{x}_{i,1},\dots,\boldsymbol{x}_{i,m_i}\} Bi​={xi,1​,…,xi,mi​​}是第$i$个包、 y i ∈ { ± 1 } y_i\in\{\pm1\} yi​∈{±1}是包标签，以及$m_i$是包中实例的数量。在不失一般性的前提下，假设前$p$个是正包，余下$m-p$是负包，即所有包可以被排序为：
$$y_i=\{\begin{array}{ll}1,& i\in [p],\\ -1,& i\in [m]\setminus [p].\end{array}$$包的标签预测由其实例的最大决策值决定，即$f({\mathcal{B}}_i)={\max }_{j\in [m_i]}{\mathbf{w}}^T\varphi ({\mathbf{x}}_{i,j})$。代入公式2有：
$$\begin{array}{ll}\underset{\mathbf{w},{\xi }_i,{ϵ}_i}{\min }& \frac{1}{2}\Vert \mathbf{w}{\Vert }^2+\frac{{\lambda }_1}{p}{\sum }_{i=1}^p\frac{{\xi }_i^2+\nu {ϵ}_i^2}{(1-\theta {)}^2}+\frac{{\lambda }_2}{q}{\sum }_{i=p+1}^m\frac{{\xi }_i^2+\nu {ϵ}_i^2}{(1-\theta {)}^2},\\ \text{ s.t. }& y_i{\max }_{j\in \left[m_i\right]}{\mathbf{w}}^T\varphi \left({\mathbf{x}}_{i,j}\right)\ge 1-\theta -{\xi }_i,\\ & y_i{\max }_{j\in \left[m_i\right]}{\mathbf{w}}^T\varphi \left({\mathbf{x}}_{i,j}\right)\le 1+\theta +{ϵ}_i,\forall i\in [m],\end{array}\text{\hspace{1em}(3)}$$其中${\lambda }_1$和${\lambda }_2$是权衡参数。
对于每一个正包${\mathcal{B}}_i$，引入二元向量：
a i = [ a i , 1 ; …   ; a i , m i ] ∈ { 0 , 1 } m i \boldsymbol{a}_i=[a_{i,1};\dots;a_{i,m_i}]\in\{0,1\}^{m_i} ai​=[ai,1​;…;ai,mi​​]∈{0,1}mi​来指示具有最大决策值的关键实例。依据标准多示例假设，每个正包中只有一个正实例，则有${\mathbf{e}}^T{\mathbf{a}}_i=1$，其中$\mathbf{e}$是一个全1向量。令$\mathbf{c}=[{\mathbf{a}}_1;\dots ,{\mathbf{a}}_p]$，以及$\mathcal{C}$表示其领域。然后公式3中的约束$y_i{\max }_{j\in \left[m_i\right]}{\mathbf{w}}^T\varphi \left({\mathbf{x}}_{i,j}\right)\ge 1-\theta -{\xi }_i$可以重写为${\max }_{{\mathbf{a}}_i}{\sum }_{j\in [m_i]}{a}_{i,j}{\mathbf{w}}^T\varphi ({\mathbf{x}}_{i,j})\ge 1-\theta -{\xi }_i$。
负包${\mathcal{B}}_i$中所有的实例都是负的，公式3与之相应的约束可以替换为：
$$\{\begin{array}{l}-{\mathbf{w}}^T\varphi ({\mathbf{x}}_{i,j})\ge 1-\theta -{\xi }_i,\\ -{\mathbf{w}}^T\varphi ({\mathbf{x}}_{i,j})\le 1+\theta +{ϵ}_i,{\forall }_j\in [m_i].\end{array}$$为了使得包更灵活，允许包有不同的松弛变量：
{ ξ s ( i , j ) } i ∈ [ m ] ∖ [ p ] , j ∈ [ m i ] , { ϵ s ( i , j ) } i ∈ [ m ] ∖ [ p ] , j ∈ [ m i ] , \{\xi_{s(i,j)}\}_{i\in[m]\setminus[p],j\in[m_i]},\qquad\{\epsilon_{s(i,j)}\}_{i\in[m]\setminus[p],j\in[m_i]}, {ξs(i,j)​}i∈[m]∖[p],j∈[mi​]​,{ϵs(i,j)​}i∈[m]∖[p],j∈[mi​]​,其中索引$s(i,j)=J_{i-1}-J_p+j+p$的范围为$p+1$到$J_m-J_p+p$，以及$J_i={\sum }_{t=1}^i{m}_t$ ($J_0=0$)。这个就是把所有的索$s(i,j)$重新索引至$p$到所有包的数量加$p$。结合以上，公式3转换为：
$$\begin{array}{ll}{\min }_{\mathbf{c}\in \mathcal{C}}& {\min }_{\mathbf{w},{\xi }_i,{ϵ}_i}\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+\frac{{\lambda }_1}{p}{\sum }_{i=1}^p\frac{{\xi }_i^2+\nu {ϵ}_i^2}{(1-\theta {)}^2}\\ & +\frac{{\lambda }_2}{q}{\sum }_{i=p+1}^m{\sum }_{j\in \left[m_i\right]}\frac{{\xi }_{s(i,j)}^2+\nu {ϵ}_{s(i,j)}^2}{(1-\theta {)}^2},\\ \text{ s.t. }& {\sum }_{j\in \left[m_i\right]}{a}_{i,j}{\mathbf{w}}^T\varphi \left({\mathbf{x}}_{i,j}\right)\ge 1-\theta -{\xi }_i,\\ & {\sum }_{j\in \left[m_i\right]}{a}_{i,j}{\mathbf{w}}^T\varphi \left({\mathbf{x}}_{i,j}\right)\le 1+\theta +{ϵ}_i,\forall i\in [p],\\ & -{\mathbf{w}}^T\varphi \left({\mathbf{x}}_{i,j}\right)\ge 1-\theta -{\xi }_{s(i,j)},\\ & -{\mathbf{w}}^T\varphi \left({\mathbf{x}}_{i,j}\right)\le 1+\theta +{ϵ}_{s(i,j)},\\ & \forall i\in [m]\backslash [p],\forall j\in \left[m_i\right].\end{array}\text{\hspace{1em}(4)}$$作为核方法，由于潜在的无限维特征映射，通常通过对偶形式处理公式4的内部最小化。引入对偶变量$\mathbf{u}=\left[u_1;\dots ;u_2\left(J_m-J_p+p\right)\right]⪰0$，公式4的拉格朗日形式为：
$$\begin{array}{rl}& \underset{\mathbf{c}\in \mathcal{C}}{\min }\underset{\mathbf{u}\in \mathcal{U}}{\max }-\frac{1}{2}{\mathbf{u}}^T\left[\begin{array}{cc}\mathbf{K}& -\mathbf{K}\\ -\mathbf{K}& \mathbf{K}\end{array}\right]\mathbf{u}\\ & -\frac{(1-\theta {)}^2}{4}{\mathbf{u}}^T\left[\begin{array}{cc}\frac{1}{{\lambda }_1}\mathbf{I}& 0\\ 0& \frac{1}{{\lambda }_2\nu }\mathbf{I}\end{array}\right]\mathbf{u}-{\left[\begin{array}{c}(\theta -1)\mathbf{e}\\ (\theta +1)\mathbf{e}\end{array}\right]}^T\mathbf{u}\end{array}\text{\hspace{1em}(5)}$$其中$\mathcal{U}$是非负象限，以及${\mathbf{K}}_{i,j}={\mathbf{\Psi }}_i^{\top }{\mathbf{\Psi }}_j\in {\mathbb{R}}^{q\times q}$是带有
$${\mathbf{\Psi }}_i=\{\begin{array}{ll}{\sum }_{j\in \left[m_i\right]}{a}_{i,j}\varphi \left({\mathbf{x}}_{i,j}\right)& i\in [p],j\in \left[m_i\right]\\ -\varphi \left({\mathbf{x}}_{i,j}\right)& i\in [m]\backslash [p],j\in \left[m_i\right]\end{array}$$的核矩阵。
为了克服混合整数规划的求解困难，一些凸松弛方法被使用，例如半正定规划松弛，以及最大松弛 (Minimax relaxation)。本文则使用后者。改变最大最小的顺序，有：
$$\underset{\mathbf{u}\in \mathcal{U}}{\max }\underset{\mathbf{c}\in \mathcal{C}}{\min }D(\mathbf{u},\mathbf{c}),$$其中$D(\mathbf{u},\mathbf{c})$是公式5中的优化目标。此外，通过重写内部优化，以上公式转换为：
$$\underset{\mathbf{u}\in \mathcal{U}}{\max }\underset{\mathbf{c}\in \mathcal{C}}{\min }d\text{s.t. }D(\mathbf{u},{\mathbf{c}}_k)\ge d,\forall {\mathbf{c}}_k\in \mathcal{C}.\text{\hspace{1em}(6)}$$进一步于内优化引入对偶变量$\mathbf{v}=\left[v_1;\dots ;v_{|\mathcal{C}|}\right]⪰0$，公式6的拉格朗日形式为：
$$\underset{\mathbf{v}⪰0}{\min }\underset{d}{\max }\left\{d+\sum _{k:{\mathbf{c}}_k\in \mathcal{C}}{v}_k\left(D\left(\mathbf{u},{\mathbf{c}}_k\right)-d\right)\right\}.$$设置$d$的derivative为$0$，有${\sum }_{k:c_k\in \mathcal{C}}{v}_k=1$，以及对偶问题转换为：
$$\underset{\mathbf{v}\in \mathcal{V}}{\min }\sum _{k:c_k\in \mathcal{C}}{v}_{k}D\left(\mathbf{u},{\mathbf{c}}_k\right),\text{\hspace{1em}(7)}$$其中$\mathcal{V}=\left\{\mathbf{v}\in {\mathbb{R}}_{+}^{|\mathcal{C}|}\mid e^{\top }\mathbf{v}=1\right\}$是${\mathbb{R}}^{|\mathcal{C}|}$上的单纯形 (Simplex)为了简洁，${\sum }_{k:{\mathbf{c}}_k\in \mathcal{C}}{v}_{k}D\left(\mathbf{u},{\mathbf{c}}_k\right)$表示为$G(\mathbf{u},\mathbf{v})$，代入公式7，有：
$$\underset{\mathbf{u}\in \mathcal{U}}{\max }\underset{\mathbf{v}\in \mathcal{V}}{\min }G(\mathbf{u},\mathbf{v}).$$$G(\mathbf{u},\mathbf{v})$是负正定象限函数的凸组合，因此$v$凸$u$凹，以及根据Siont最大理论，这里存在一个鞍点$\left({\mathbf{u}}^{\star },{\mathbf{v}}^{\star }\right)\in \mathcal{U}\times \mathcal{V}$使得：
$$\begin{array}{c}\underset{\mathbf{v}\in \mathcal{V}}{\min }\underset{\mathbf{u}\in \mathcal{U}}{\max }G(\mathbf{u},\mathbf{v})\le \underset{\mathbf{u}\in \mathcal{U}}{\max }G\left(\mathbf{u},{\mathbf{v}}^{\star }\right)=G\left({\mathbf{u}}^{\star },{\mathbf{v}}^{\star }\right)\\ =\underset{\mathbf{v}\in \mathcal{V}}{\min }G\left(\mathbf{u},{\mathbf{v}}^{\star }\right)\le \underset{\mathbf{u}\in \mathcal{U}}{\max }\underset{\mathbf{v}\in \mathcal{V}}{\min }G(\mathbf{u},\mathbf{v}).\end{array}\text{\hspace{1em}(8)}$$结合最大不等式：
$$\underset{\mathbf{v}\in \mathcal{V}}{\min }\underset{\mathbf{u}\in \mathcal{U}}{\max }G(\mathbf{u},\mathbf{v})\le \underset{\mathbf{u}\in \mathcal{U}}{\max }\underset{\mathbf{v}\in \mathcal{V}}{\min }G(\mathbf{u},\mathbf{v}),$$因此MI-ODM制定为：
$$\underset{\mathbf{v}\in \mathcal{V}}{\min }\underset{\mathbf{u}\in \mathcal{U}}{\max }G(\mathbf{u},\mathbf{v}).\text{\hspace{1em}(9)}$$最优质为鞍点$\left({\mathbf{u}}^{\star },{\mathbf{v}}^{\star }\right)$。

4 优化

简要地介绍最大问题，并详述用于快速最优值求解的随机加速镜像近似方法。

4.1 最大问题

根据一阶凸性不等式，$G(\mathbf{u},\cdot )$和$G(\cdot ,\mathbf{v})$均为凸函数，对于任意的对$(\hat{\mathbf{u}},\hat{\mathbf{v}})\in \mathcal{U}\times \mathcal{V}$，有：
$$\begin{array}{rl}& G(\mathbf{u},\hat{\mathbf{v}})-G(\hat{\mathbf{u}},\hat{\mathbf{v}})\le -{\partial }_{\mathbf{u}}G(\hat{\mathbf{u}},\hat{\mathbf{v}}{)}^{\top }(\hat{\mathbf{u}}-\mathbf{u}),\forall \mathbf{u}\in \mathcal{U},\\ & G(\hat{\mathbf{u}},\hat{\mathbf{v}})-G(\hat{\mathbf{u}},\mathbf{v})\le {\partial }_{\mathbf{v}}G(\hat{\mathbf{u}},\hat{\mathbf{v}}{)}^{\top }(\hat{\mathbf{v}}-\mathbf{v}),\forall \mathbf{v}\in \mathcal{V}.\end{array}$$叠加以上不等式，并增广$\mathbf{u}$和$\mathbf{v}$，有：
$$G(\mathbf{u},\hat{\mathbf{v}})-G(\hat{\mathbf{u}},\mathbf{v})\le g(\hat{\mathbf{w}}{)}^{\top }(\hat{\mathbf{w}}-\mathbf{w}),\forall \mathbf{u},\mathbf{v},\text{\hspace{1em}(10)}$$其中$\mathbf{w}=[\mathbf{u};\mathbf{v}]$，以及$g(\hat{\mathbf{w}})=\left[-{\partial }_{\mathbf{u}}G(\hat{\mathbf{w}});{\partial }_{\mathbf{v}}G(\hat{\mathbf{w}})\right]$。与一般的凸优化相比，$g(\hat{\mathbf{w}})$扮演着梯度的角色。因此对于任意的$\mathbf{u}$和$\mathbf{v}$，有：
$$\underset{\mathbf{u}\in \mathcal{U}}{\max }G(\mathbf{u},\hat{\mathbf{v}})-\underset{\mathbf{v}\in \mathcal{V}}{\min }G(\hat{\mathbf{u}},\mathbf{v})\le g(\hat{\mathbf{w}}{)}^{\top }(\hat{\mathbf{w}}-\mathbf{w}).\text{\hspace{1em}(11)}$$公式11的LHS可以进一步分解为当前点$G(\hat{\mathbf{u}},\hat{\mathbf{v}})$与鞍点$\left({\mathbf{u}}^{\star },{\mathbf{v}}^{\star }\right)$之间的间隔：
$$\begin{array}{rl}& \underset{\mathbf{u}\in \mathcal{U}}{\max }G(\mathbf{u},\hat{\mathbf{v}})-G\left({\mathbf{u}}^{\star },{\mathbf{v}}^{\star }\right)+G\left({\mathbf{u}}^{\star },{\mathbf{v}}^{\star }\right)-\underset{\mathbf{v}\in \mathcal{V}}{\min }G(\hat{\mathbf{u}},\mathbf{v})\\ & =\underset{\ge 0}{\underbrace{\underset{\mathbf{u}\in \mathcal{U}}{\max }G(\mathbf{u},\hat{\mathbf{v}})-\underset{\mathbf{v}\in \mathcal{V}\mathbf{u}\in \mathcal{U}}{\min }\underset{\mathbf{U}}{\max }G(\mathbf{u},\mathbf{v})}}+\underset{\ge 0}{\underbrace{\underset{\mathbf{u}\in \mathcal{U}}{\max }\underset{\mathbf{v}\in \mathcal{V}}{\min }G(\mathbf{u},\mathbf{v})-\underset{\mathbf{v}\in \mathcal{V}}{\min }G(\hat{\mathbf{u}},\mathbf{v})}}.\end{array}$$两个间隔均非负，其值越小越接近鞍点。公式11的LHS可以看作是一般凸优化中的“对偶间隔”，并作为算法设计的停止标准。

4.2 随机加速镜像近似

$\mathbf{u}$和$\mathbf{v}$的可行域分别对应框约束和单纯形。镜像下降方法用于探索其结构信息。对于变量$\mathbf{u}$，欧式距离镜像图${\psi }_{\mathcal{U}}=\Vert \mathbf{u}{\Vert }_2^2/2$可以工作的很好，对于变量$\mathbf{v}$，负熵镜像图${\psi }_{\mathcal{V}}(\mathbf{v})={\sum }_k\log v_k$很适用，因为它可以使得时间复杂度与维度的依赖程度是对数的。
镜像下降方法在镜像映射引起的对偶空间中执行梯度下降。为了使得最大结构得以像一般优化问题那样容易处理，引入联合镜像图$\psi (\mathbf{w})=a{\psi }_{\mathcal{U}}(\mathbf{u})+b{\psi }_{\mathcal{V}}(\mathbf{v})$，其中$a=\sqrt{2}/\tau \sqrt{J_m-J_p+p}$，以及$b=1/\sqrt{\log |\mathcal{C}|}$。这表明$\nabla \psi \mathcal{U}(\mathbf{u})=\mathbf{u}$，以及$\nabla {\psi }_{\mathcal{V}}(\mathbf{v})=\log \mathbf{v}+\mathbf{e}$。结合在一起有$\nabla \psi (\mathbf{w})=[a\mathbf{u};b\log \mathbf{v}+b\mathbf{e}]$。
如图1所示，在第$t$次迭代中，首先将当前点${\mathbf{w}}_t=\left[{\mathbf{u}}_t;{\mathbf{v}}_t\right]$映射到对偶空间$\nabla \psi \left({\mathbf{w}}_t\right)=$ $\left[a{\mathbf{u}}_t;b\log {\mathbf{v}}_t+b\mathbf{e}\right]$并执行一次梯度下降
$$\begin{array}{rl}& \nabla \left({\hat{\mathbf{w}}}_t\right)=\nabla \psi \left({\mathbf{w}}_t\right)-\eta g\left({\mathbf{w}}_t\right)\\ =& \left[a{\mathbf{u}}_t+\eta {\partial }_{\mathbf{u}}G\left({\mathbf{u}}_t,{\mathbf{v}}_t\right);b\log {\mathbf{v}}_t+b\mathbf{e}-\eta {\partial }_{\mathbf{v}}G\left({\mathbf{u}}_t,{\mathbf{v}}_t\right)\right],\end{array}$$其中$\eta$是步长大小，然后将$\nabla \psi \left({\hat{\mathbf{w}}}_t\right)$映射回最初的空间，即找到${\hat{\mathbf{w}}}_t=\left[{\hat{\mathbf{u}}}_t;{\hat{\mathbf{v}}}_t\right]$：
$$\left[\begin{array}{c}a{\hat{\mathbf{u}}}_t\\ b\log {\hat{\mathbf{v}}}_t+b\mathbf{e}\end{array}\right]=\left[\begin{array}{c}a{\mathbf{u}}_t+\eta {\partial }_{\mathbf{u}}G\left({\mathbf{u}}_t,{\mathbf{v}}_t\right)\\ b\log {\mathbf{v}}_t+b\mathbf{e}-\eta {\partial }_{\mathbf{v}}G\left({\mathbf{u}}_t,{\mathbf{v}}_t\right)\end{array}\right],$$其表明${\hat{\mathbf{u}}}_t={\mathbf{u}}_t+\eta {\partial }_{\mathbf{u}}G\left({\mathbf{u}}_t,{\mathbf{v}}_t\right)/a$且${\hat{\mathbf{v}}}_t=$ ${\mathbf{v}}_t\exp \left(-\eta {\partial }_{\mathbf{v}}G\left({\mathbf{u}}_t,{\mathbf{v}}_t\right)/b\right)$。最后，基于镜像图中的Bregman距离执行映射$\left[{\hat{\mathbf{u}}}_t;{\hat{\mathbf{v}}}_t\right]$到$\mathcal{U}\times \mathcal{V}$。特别地，欧式距离镜像图使用常用的欧氏距离，负熵镜像图使用Kullback-Leible散度。这可以制定为以下子优化问题：
$$\begin{array}{rl}{\mathbf{u}}_{t+1}=& \underset{\mathbf{u}\in \mathcal{U}}{\mathrm{argmin}}\Vert \mathbf{u}-{\hat{\mathbf{u}}}_t{\Vert }_2^2,\\ {\mathbf{v}}_{t+1}=& \underset{\mathbf{v}\in \mathcal{V}}{\mathrm{argmin}}{\mathbf{v}}^T\log \frac{\mathbf{v}}{{\hat{\mathbf{v}}}_t}.\end{array}$$

这两个子优化问题都有近似解，前者将${\hat{\mathbf{u}}}_t$映射到非负象限，因此 u t + 1 = max ⁡ { u ^ t , 0 } \boldsymbol{u}_{t+1}=\max\{\hat{u}_t,0\} ut+1​=max{u^t​,0}。后者中引入对偶变量$z$，则拉格朗日形式为：
$$\underset{z}{\max }\underset{\mathbf{v}}{\min }{\mathbf{v}}^T\log \left(\mathbf{v}/{\hat{v}}_t\right)+z\left({\mathbf{e}}^T\mathbf{v}-1\right).$$设置$v$的derivative为$0$，有$\log \left(\mathbf{v}/{\hat{\mathbf{v}}}_t\right)+\mathbf{e}+$ $z\mathbf{e}=0$，其表明${\mathbf{v}}_{t+1}={\hat{\mathbf{v}}}_t\exp (-1-z)$。注意${\mathbf{v}}_{t+1}$属于一个单纯形，因此$1={\mathbf{e}}^{\top }{\mathbf{v}}_{t+1}={\mathbf{e}}^{\top }{\hat{\mathbf{v}}}_t\exp (-1-z)={\Vert {\hat{\mathbf{v}}}_t\Vert }_1\exp (-1-z)$。代入到$\exp (-1-z)=1/{\Vert {\hat{v}}_t\Vert }_1$，得到近似解$v_{t+1}={\hat{v}}_t/{\Vert {\hat{v}}_t\Vert }_1$。

有了${\mathbf{y}}_{t+1}\triangleq \left[{\mathbf{u}}_{t+1};{\mathbf{v}}_{t+1}\right]$后，从${\mathbf{w}}_t$；当在对偶空间执行梯度下降时，使用${\mathbf{y}}_{t+1}$而非${\mathbf{w}}_t$。换言之，一个两步镜像下降方法在每次迭代中执行，其从同一点开始，但第二次使用的梯度在第一次的结束点进行评估。该过程已被证明有很好的收敛性。 图2展示了该方法的一次迭代。

镜像近似方法可以进一步通过Nesterov加速技术提速。方法是在 { w t } \left\{\boldsymbol{w}_t\right\} {wt​}和 { y t } \left\{\boldsymbol{y}_t\right\} {yt​}之外额外保留两个序列 { w ‾ t } \left\{\underline{\boldsymbol{w}}_t\right\} {w​t​}和 { w ‾ t } \left\{\overline{\boldsymbol{w}}_t\right\} {wt​}，其是 { w t } \left\{\boldsymbol{w}_t\right\} {wt​}和 { y t } \left\{\boldsymbol{y}_t\right\} {yt​}的结合。特别地，在第$t$次迭代中，首先更新${\underline{\mathbf{w}}}_t=\left(1-{\gamma }_t\right){\bar{\mathbf{w}}}_t+{\gamma }_t{\mathbf{y}}_t$，其中${\gamma }_t$是Nesterov加速系数，通常设置为$2/(t+1)$。随后，两部镜像近似基于${\underline{\mathbf{w}}}_t$来获得${\mathbf{y}}_{t+1}$和${\mathbf{w}}_{t+1}$。此外，为了使得数据集更好的适应大数据，该方法被扩展为一个随机版本，关键问题转换为找到无偏梯度${\partial }_{\mathbf{u}}\tilde{G}\left({\mathbf{u}}_t,{\mathbf{v}}_t\right)$和${\partial }_{\mathbf{v}}\tilde{G}\left({\mathbf{u}}_t,{\mathbf{v}}_t\right)$。注意$G(\mathbf{u},\mathbf{v})=$ ${\sum }_{k:c_k\in \mathcal{C}}{v}_{k}D\left(\mathbf{u},{\mathbf{c}}_k\right)$，则有
$$\begin{array}{rl}& {\partial }_{\mathbf{u}}G\left({\mathbf{u}}_t,{\mathbf{v}}_t\right)=\left[{\partial }_{\mathbf{u}}D\left({\mathbf{u}}_t,{\mathbf{c}}_1\right),\dots ,{\partial }_{\mathbf{u}}D\left({\mathbf{u}}_t,{\mathbf{c}}_{|\mathcal{C}|}\right)\right]{\mathbf{v}}_t\\ & {\partial }_{\mathbf{v}}G\left({\mathbf{u}}_t,{\mathbf{v}}_t\right)=\left[D\left({\mathbf{u}}_t,{\mathbf{c}}_1\right),\dots ,D\left({\mathbf{u}}_t,{\mathbf{c}}_{|\mathcal{C}|}\right)\right].\end{array}$$随机采样的索引$i_t$基于${\mathbf{v}}_t$在 { 1 , 2 , … , ∣ C ∣ } \{1,2, \ldots,|\mathcal{C}|\} {1,2,…,∣C∣}的分布获得，有${\partial }_{\mathbf{u}}\tilde{G}\left({\mathbf{u}}_t,{\mathbf{v}}_t,i_t\right)=$ ${\partial }_{\mathbf{u}}D\left({\mathbf{u}}_t,{\mathbf{c}}_{i_t}\right)$. 另一方面，均匀采样的索引$j_t$来自 { 1 , 2 , … , ∣ C ∣ } \{1,2, \ldots,|\mathcal{C}|\} {1,2,…,∣C∣}，有${\partial }_{\mathbf{v}}\tilde{G}\left({\mathbf{u}}_t,{\mathbf{v}}_t,j_t\right)=$ $\left[0,\dots ,|\mathcal{C}|D\left({\mathbf{u}}_t,{\mathbf{c}}_{j_t}\right)\dots ,0\right]$。这可以表示为：
$$\begin{array}{rl}\mathbb{E}\left[{\partial }_{\mathbf{u}}\tilde{G}\left({\mathbf{u}}_t,{\mathbf{v}}_t,i_t\right)\mid {\mathbf{u}}_t,{\mathbf{v}}_t\right]& ={\partial }_{\mathbf{u}}G\left({\mathbf{u}}_t,{\mathbf{v}}_t\right),\\ \mathbb{E}\left[{\partial }_{\mathbf{v}}\tilde{G}\left({\mathbf{u}}_t,{\mathbf{v}}_t,j_t\right)\mid {\mathbf{u}}_t,{\mathbf{v}}_t\right]& ={\partial }_{\mathbf{v}}G\left({\mathbf{u}}_t,{\mathbf{v}}_t\right),\end{array}$$以及$\tilde{g}\left({\mathbf{w}}_t\right)=\left[-{\partial }_u\tilde{G}\left({\mathbf{u}}_t,{\mathbf{v}}_t,i_t\right);{\partial }_{\mathbf{v}}\tilde{G}\left({\mathbf{u}}_t,{\mathbf{v}}_t,j_t\right)\right]$是$g\left({\mathbf{w}}_t\right)$的期望无偏估计。
综合以上步骤，将获得随机加速镜像近似方法MI-ODM，如算法1。