Minimax Algorithm for Learning Rotations

Wojciech Kotłowski (KOTLOWSK@CWI.NL)

Centrum Wiskunde & Informatica

Manfred K. Warmuth (MANFRED@CSE.UCSC.EDU)

Department of Computer Science, UC Santa Cruz

Editor: Sham Kakade, Ulrike von Luxburg

Abstract

It is unknown what is the most suitable regularization for rotation matrices and how to maintain uncertainty over rotations in an online setting. We propose to address these questions by studying the minimax algorithm for rotations and begin by working out the 2-dimensional case.

The problem of online learning of rotations is defined as follows. In every iteration $t = 1, 2, \ldots, T$, the learner is given a unit vector $\boldsymbol{x}_t$ ($\|\boldsymbol{x}_t\| = 1$). The learner is then required to predict (deterministically or randomly), with a rotation matrix $\mathbf{R}_t \in \mathcal{SO}(n)$. The choice of $\mathbf{R}_t$ determines the predicted unit vector $\hat{\mathbf{y}}_t = \mathbf{R}_t\mathbf{x}_t$. Finally, the algorithm obtains the "true" rotated unit vector $\mathbf{y}_t$ and incurs loss

where $\cdot$ is the dot product, $\mathcal{R}_t$ is the distribution over $\mathcal{SO}(n)$ from which $\mathbf{R}_t$ is drawn, and $\mathbb{E}[.]$ is the expectation wrt $\mathcal{R}_T$. We seek on-line algorithms which have small bounded regret

for arbitrary sequences of examples $(\boldsymbol{x}_t, \boldsymbol{y}_t)$ of length $T$. Recently, a regret bound of $2\sqrt{nT}$ has been proven for a randomized¹ algorithm which does a gradient descent step in each iteration and then projects into a suitable chosen convex set (Hazan et al., 2010). Even though the regret of this algorithm was shown to be optimal within a constant factor (Hazan et al., 2010), many questions remain for this archetypical machine learning problem that has many applications in robotics, vision, matrix completion, subspace tracking, etc (See e.g. Arora (2009); Hazan et al. (2010)):

1. We don't know the proper way to regularize rotations. Is there some kind of entropy defined over $\mathcal{SO}(n)$? The algorithm of (Hazan et al., 2010) is based on regularizing wrt the squared Euclidean distance, which does not take the structure of the $\mathcal{SO}(n)$ into account.

2. The parameter space $\mathcal{SO}(n)$ is not convex and we don't know the "correct" way to maintain uncertainty over this space. The algorithm of (Hazan et al., 2010) projects using inequality constraints which means that it "forgets" information about the past examples.

3. A good on-line algorithm should intuitively exploit the elegant Lie group and Lie algebra connection (via the exponential map) between $\mathcal{SO}(n)$ and skew symmetric matrices, respectively (Arora, 2009).

We propose to resolve some of these issues by finding the minimax algorithm for learning rotations and we hope that this algorithm will give insights for learning other matrix classes:

where the $\mathcal{R}_q$ are distributions over $\mathcal{SO}(n)$ and the unit vectors $\boldsymbol{x}_q, \boldsymbol{y}_q$ are chosen deterministically.

So far, we have obtained the following partial result sketched below: If the instances $\boldsymbol{x}_t$ are restricted to be a fixed unit, say $\boldsymbol{e}_1 = (1, 0, \ldots, 0)^\top$, then we can give the minimax algorithm. In the case of $n = 2$, the two problems coincide because any black box for solving the fixed instance problem can be used to solve the variable instance problem with the same regret. This holds because if $\mathbf{R}_{\boldsymbol{x}_t}$ rotates $\boldsymbol{x}_t$ onto $\boldsymbol{e}_1$ (i.e. $\boldsymbol{e}_1 = \mathbf{R}_{\boldsymbol{x}_t}\mathbf{x}_t$), then processing $(\boldsymbol{x}_t, \boldsymbol{y}_t)$ is the same as processing $(\boldsymbol{e}_1, \boldsymbol{y}_t')$, where $\boldsymbol{y}_t' := \mathbf{R}_{\boldsymbol{x}_t}\boldsymbol{y}_t$:

Note that in the 2nd equality we used $\mathbf{R}_t\mathbf{R}_{\boldsymbol{x}_t}^{-1} = \mathbf{R}_{\boldsymbol{x}_t}^{-1}\mathbf{R}_t$, which only holds for $n = 2$.

When $\boldsymbol{x}_t = \boldsymbol{e}_1$ for all $t$, then the loss $1 - (\mathbb{E}[\mathbf{R}_t]\boldsymbol{e}_1)\cdot\mathbf{y}_t$ can be rewritten as $1 - \boldsymbol{w}_t\cdot\mathbf{y}_t$, where $\boldsymbol{w}_t = \mathbb{E}[\mathbf{R}_t]\boldsymbol{e}_1$ is a new parameter vector which has norm at most 1. With this parameter vector, the regret simplifies to

where $\boldsymbol{s}_T = \sum_{t=1}^{T}\mathbf{y}_t$, and $\boldsymbol{w}^* = \arg\max_{\boldsymbol{w},\|\boldsymbol{w}\|\leq1}\boldsymbol{w}\cdot\boldsymbol{s}_T = \frac{\boldsymbol{s}_T}{\|\boldsymbol{s}_T\|}$. To find the optimal strategy of the forecaster, we proceed backwards. Fix $\boldsymbol{s}_{T-1}$ and $\boldsymbol{w}_1, \ldots, \boldsymbol{w}_{T-1}$. We want to solve the following minimax problem in the last iteration:

A more involved analysis reveals that the optimal solution $\boldsymbol{w}_T$ must be $\boldsymbol{s}_{T-1}$ times a shrinking factor:

while the optimal (worst-case) outcome $\mathbf{y}_T$ is orthogonal to $\boldsymbol{s}_{T-1}$. Plugging $\boldsymbol{w}_T$ and $\mathbf{y}_T$ into (1) and using $\mathbf{y}_T\cdot\boldsymbol{s}_{T-1} = \mathbf{y}_T\cdot\boldsymbol{w}_T = 0$ gives the optimal value of the regret increase in the last iteration: $\sqrt{\|\boldsymbol{s}_{T-1}\|^2 + 1}$. In the second to the last step

and $\mathbf{y}_{T-1}$ is orthogonal to $\boldsymbol{s}_{T-2}$. Plugging $\boldsymbol{w}_{T-1}$ and $\mathbf{y}_{T-1}$ into the optimized expression leads to the worst-case regret increase in the last two iterations which is $\sqrt{\|\boldsymbol{s}_{T-2}\|^2 + 2}$. Continuing the backward induction, in the $k$-th step from the end, we optimize

and the worst-case regret increase in the last $k$ iterations equals $\sqrt{\|\boldsymbol{s}_{T-k}\|^2 + k}$. The value of the minimax regret can be obtained for $k = T$ and is equal to $\sqrt{T}$.

Summarizing, we were able to prove that when the input $\boldsymbol{x}_t$ is restricted to be a fixed vector, then the minimax regret is $\sqrt{T}$ and does not depend on the dimension. The optimal strategy for this case is to choose $\boldsymbol{w}_t$ as the current "sufficient statistic" $\boldsymbol{s}_{t-1} = \sum_{q=1}^{t-1}\mathbf{y}_q$ times a shrinking factor that is related to the randomization. The worst-case data sequence for minimax algorithm is any sequence where the outcomes are always orthogonal to the current sufficient statistic (and the vector chosen by the optimal strategy).

For $n = 2$, the minimax regret for the fixed instance problem coincides with the minimax of the original rotation problem² and the open problem is to determine the minimax regret for dimension $n > 2$.

Acknowledgments

This research was supported by NSF grant IIS-0917397.

References

R. Arora. On learning rotations. In Y. Bengio, D. Schuurmans, J. Lafferty, C. K. I. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems 22, pages 55–63. MIT Press, 2009.

E. Hazan, S. Kale, and M. K. Warmuth. Learning rotations with little regret. In COLT ’10, June 2010. A corrigendum can be found at the conference website.