# Partial Matrix Completion

Elad Hazan
Princeton University
Google DeepMind
&Adam Tauman Kalai 11footnotemark: 1
Microsoft Research
Varun Kanade 11footnotemark: 1
University of Oxford
&Clara Mohri 11footnotemark: 1
Harvard University
&Y. Jennifer Sun 11footnotemark: 1
Princeton University
Google DeepMind
Authors ordered alphabetically

###### Abstract

The matrix completion problem aims to reconstruct a low-rank matrix based on a
revealed set of possibly noisy entries. Prior works consider completing the
entire matrix with generalization error guarantees. However, the completion
accuracy can be drastically different over different entries. This work
establishes a new framework of _partial matrix completion_ , where the goal is
to identify a large subset of the entries that can be completed with high
confidence. We propose an efficient algorithm with the following provable
guarantees. Given access to samples from an unknown and arbitrary
distribution, it guarantees: (a) high accuracy over completed entries, and (b)
high coverage of the underlying distribution. We also consider an online
learning variant of this problem, where we propose a low-regret algorithm
based on iterative gradient updates. Preliminary empirical evaluations are
included.

##  1 Introduction

In the classical matrix completion problem, a subset of entries of a matrix
are revealed and the goal is to reconstruct the full matrix. This is in
general impossible, but if the matrix is assumed to be low rank and the
distribution over revealed entries is uniformly random, then it can be shown
that reconstruction is possible. A common application of matrix completion is
in recommendation systems. For example, the rows of the matrix can correspond
to users, the columns to movies, and an entry of the matrix is the preference
score for the user over the corresponding movie. The completed entries can
then be used to predict user preferences over unseen movies. The low rank
assumption in this case is justified if the preference of users over movies is
mostly determined by a small number of latent factors such as the genre,
director, artistic style, and so forth.

However, in many cases, it is both infeasible and unnecessary to complete the
entire matrix. First consider the trivial example of movie recommendations
with users and movies coming from two countries $A$ and $B$, where each user
rates random movies only from their country. Without any cross ratings of
users from country $A$ on movies from country $B$ or vice versa, it is
impossible to accurately complete these entries. A solution here is
straightforward: partition the users and movies into their respective groups
and then complete only the part of the matrix corresponding to user ratings of
movies from their own country.

In reality, many users have categories of movies with few or no ratings based
on genre, language, or time period. For such users, it is difficult to
accurately complete unrated movie categories which they do not like to watch
from those which they have not even been exposed to. Thus it may be preferable
to abstain from making rating predictions for such users on these
unpredictable categories. This is further complicated by the fact that such
categories are not crisply defined and relevant categories may vary across
user demographics like country and age.

Figure 1: A simple example where some users rate only comedies and some rate
only horror movies. However, these two groups are unknown and the rows and
columns are permuted according to $\pi=\pi_{C}\circ\pi_{R}$. The partial
completions made by our algorithm, shown on simulated data, correspond to
completing the ratings for the half of the matrix as one would like. Note that
our algorithms can handle arbitrary revealed subsets, not only stochastic
block models. The experimental setup and more preliminary experiments are
described in Section 6.

This motivates a more general question: can we identify a subset of the matrix
that can be completed by the existing observations with high confidence? We
call this problem partial matrix completion. Let $M^{\star}$ be a target
matrix. A non-convex formulation would be to find a matrix $\hat{M}$ and a set
of entries $C\subseteq[m]\times[n]$ which maximizes:

$\max_{C\subseteq[m]\times[n]}|C|~{}\text{ s.t.
}~{}\frac{1}{|C|}\sum_{(i,j)\in
C}(M_{ij}^{\star}-\hat{M}_{ij})^{2}\leq\varepsilon.$ (1)

This is non-convex because the set $C$ is discrete and also because the choice
of $\hat{M}$ interacts $C$. Fortunately, there are already several matrix
completion algorithms which output $\hat{M}$ that guarantee low
“generalization error” with respect to future examples from the same
distribution of entries as those from the training distribution, though they
are not accurate over the entire matrix. We will fix any one of these
completions $\hat{M}$.

We thus relax the goal of partial matrix completion to identify a matrix $C$
which gives a confidence score for each entry between 0 and 1. A value of 0
indicates that this entry should not be completed, whereas 1 indicates we have
absolute confidence. We call this matrix the confidence matrix. Ideally, we
would like that the confidence matrix to have a value of 1 on all entries that
are well supported by the observation distribution.

We formalize this problem through the following definitions. The precise
definitions of some of the terms will be introduced in subsequent sections.
Let $M^{\star}$ be a target matrix and $\hat{M}$ be a completion given by a
matrix completion algorithm that guarantees low generalization error over
future examples from the same entry distribution (formal definition given in
Def. 8), and let $\varepsilon>0$. The coverage of $C$ is defined to be
$\|C\|_{1}\stackrel{{\scriptstyle\text{def}}}{{=}}\sum_{ij}|C_{ij}|$.

######  Definition 1 (Partial matrix completion problem).

Let $M^{\star}$ be a target matrix and $\hat{M}$ be a full completion (Def.
8), and $\varepsilon>0$ be an error tolerance. Find a confidence matrix
$C\in[0,1]^{m\times n}$ with maximal coverage, i.e.

$\displaystyle\operatorname*{arg\,max}_{C\in[0,1]^{m\times n}}\ \|C\|_{1}\
\mathrm{s.t.}\
\frac{1}{\|C\|_{1}}\sum_{i\in[m],j\in[n]}C_{ij}(M_{ij}^{\star}-\hat{M}_{ij})^{2}\leq\varepsilon.$

The matrix $C$ that solves the above optimization problem has the following
property: $C_{ij}$ indicates whether the $(i,j)$-th entry shall be completed,
and a fractional value can be interpreted as either a fractional completion or
a probability of completion. $C$ provides the largest coverage among all that
satisfy the property that the average error is at most $\varepsilon$ over the
completed entries.

##### Challenges of partial matrix completion.

The above formulation is intuitive and convex, but notice that we do not know
$M^{\star}$, and thus cannot apply convex optimization directly.

Key challenges are illustrated by two intuitive, but naïve approaches. First,
consider completing just those matrix entries $(i,j)$ where all rank-$k$
completions have nearly the same value $\hat{M}_{ij}$. Even in a simple case
where all revealed entries are 1, any single entry could be $\pm 1$ for some
rank 2 completion of the matrix. Based on this, one often will not be able to
complete any entries whatsoever.

Second, consider the generalization of our previous example where the sampling
distribution is uniform over an arbitrary subset $U$ of $m\times n$ possible
indices. For simplicity, think of $|U|=mn/2$ as covering half the matrix. It
follows from previous generalization bounds on matrix completion that one
could accurately complete all entries in $U$. However, in general $U$ is
unknown and arbitrarily complex. The second naïve approach would be to try to
learn $U$, but this requires $\approx|U|=mn/2\gg m+n$ observations.

###  1.1 Our contribution

We present an inefficient algorithm and its efficient relaxation to solve the
partial matrix completion problem with provable guarantees over arbitrary
sampling distributions. In particular, if $\mu$ is uniform over some arbitrary
subset $U\subseteq[m]\times[n]$ of a rank-$k$ matrix
$M^{\star}\in[-1,1]^{m\times n}$, the theoretical results obtained in this
work have the following implications. The first, is an inefficient algorithm
that solves the partial matrix completion problem for uniform distribution:

######  Corollary 2 (Inefficient algorithm, uniform sampling distribution).

For any $\varepsilon,\delta>0$, with probability $\geq 1-\delta$ over $N\geq
c_{0}\cdot\frac{k(m+n)+\log(1/\delta)}{\varepsilon^{2}}$ revealed entries from
$M^{\star}$ drawn from $\mu$, for some constant $c_{0}$, Algorithm 1 (Sec. 3)
outputs $\hat{M}$ and $C\in[0,1]^{m\times n}$, such that

$\displaystyle(1):$ $\displaystyle\ \ \ \|C\|_{1}\geq|U|,$ $\displaystyle(2):$
$\displaystyle\ \ \
\frac{1}{\|C\|_{1}}\sum_{i\in[m],j\in[n]}C_{ij}(M_{ij}^{\star}-\hat{M}_{ij})^{2}\leq\varepsilon.$

Next, we describe the guarantees of an efficient algorithm 4. It has a worse
sample complexity, up to polynomial factors in $k,\varepsilon$. The advantage
is that it runs in polynomial time. Otherwise, its guarantees are similar to
that of the first algorithm.

######  Corollary 3 (Efficient algorithm, uniform sampling distribution).

For any $\varepsilon,\delta>0$, with probability $\geq 1-\delta$ over $N\geq
c_{0}\cdot\frac{k^{2}}{\varepsilon^{4}}\cdot(k(m+n)+\log(1/\delta))$ revealed
entries from $M^{\star}$ drawn from $\mu$, for some constant $c_{0}$,
Algorithm 4 (Sec. 4) outputs $\hat{M}$ and $C\in[0,1]^{n\times m}$, such that

$\displaystyle(1):$ $\displaystyle\ \ \ \|C\|_{1}\geq|U|,$ $\displaystyle(2):$
$\displaystyle\ \ \
\frac{1}{\|C\|_{1}}\sum_{i\in[m],j\in[n]}C_{ij}(M_{ij}^{\star}-\hat{M}_{ij})^{2}\leq\varepsilon.$

Corollary 2 is a simplification of Theorem 10, and Corollary 3 is a
simplification of Theorem 11.

The results can be extended to the setting where the observed entries are
noisy with zero-mean bounded noise. A remarkable feature of our algorithms is
that once the full completion $\hat{M}$ is obtained using existing procedures,
they only rely on the _locations_ of observed entries and not the values.
Thus, the decisions regarding which entries to complete, i.e., to add to $C$
is completely agnostic to the actual values of the revealed entries. Our
framework is able to handle arbitrary sampling distributions, which captures
scenarios such as overlapping groups or idiosyncratic rating habits.

##### The online setting.

We formulate the partial matrix completion problem in the online learning
setting and propose an iterative gradient based online algorithm with provable
guarantees. Corollary 4 is a special case of Theorem 22. A simple simulation
of the online algorithm in this special case of uniform sampling over a subset
of entries is demonstrated in Fig. 1.

######  Corollary 4 (Online algorithm, uniform sampling distribution).

Suppose $M^{\star}\in[-1,1]^{n\times n}$ is a bounded matrix with max-norm
(Eq. 2) bounded by $K$. The sampling distribution $\mu$ is uniform over a
fraction $0<c\leq 1$ of the $n^{2}$ entries. For any $\delta>0$, after
$T=\tilde{O}(\delta^{-2}K^{2}n)$ iterations, the confidence matrix
$C\in[0,1]^{m\times n}$ output by the online algorithm ODD satisfies with
probability at least $1-c_{1}\exp(-c_{2}\delta^{2}T)$ for some universal
constants $c_{1},c_{2}>0$,

$\displaystyle(1):$ $\displaystyle\ \ \ \|C\|_{1}\geq(c-\delta^{1/6})n^{2},$
$\displaystyle(2):$ $\displaystyle\ \ \
\frac{1}{\|C\|_{1}}\sup_{M\in\mathcal{V}}\sum_{i\in[m],j\in[n]}C_{ij}(M_{ij}-M^{\star}_{ij})^{2}\leq\frac{\delta^{1/6}}{c-\delta^{1/6}},$

where $\mathcal{V}$ is the set of all matrices $M\in[-1,1]^{n\times n}$ with
max-norm bounded by $K$ satisfying that
$\mathbb{E}_{i,j\sim\mu}[(M_{ij}-M_{ij}^{\star})^{2}]\leq\delta$.

###  1.2 Related work

##### Matrix completion and recommendation systems.

The common approach to collaborative filtering is that of matrix completion
with trace norm minimization (Srebro, 2004). It was shown that the trace norm
regularization requires $\Omega((n+m)^{3/2})$ observations to complete the
matrix under arbitrary distributions, even when the rank of the underlying
matrix is constant, and this suffices even in the more challenging agnostic
online learning setting (Hazan et al., 2012a; Shamir and Shalev-Shwartz,
2014). Srebro and Shraibman (2005) study matrix completion with the max-norm,
which behaves better under arbitrary distributions, namely for low-rank
matrices, $\tilde{O}(n+m)$ observations suffice.

##### Matrix completion and incoherence assumptions.

A line of works in the matrix completion literature considered the goal of
finding a completion of the ground truth matrix with low Frobenius norm error
guarantee (Candès and Recht, 2009; Candès and Tao, 2010; Keshavan et al.,
2010; Gross, 2011; Recht, 2011; Negahban and Wainwright, 2012; Jain et al.,
2013; Chen et al., 2020; Abbe et al., 2020). Such guarantee is strong but
usually requires two restrictive assumptions on sampling distribution of
observations and the ground truth matrix structure: (1) the sampling of
observations is uniform across all entries, and (2) the ground truth matrix
$M^{\star}$ satisfies some incoherence conditions. The incoherence condition
is an assumption imposed on the singular vectors of $M^{\star}=U\Sigma
V^{\top}$, which ensures the vectors $u_{i},v_{j}$’s to be sufficiently spread
out on the unit sphere. The main reason the incoherence condition is necessary
in establishing meaningful guarantees in low-rank matrix completion is that
without such assumptions, there might exist multiple low-rank matrices that
could explain the observed entries equally well but differ substantially on
unobserved entries. When the incoherence condition is satisfied, it implies
that the observed entries capture enough information about the low-rank
structure, making it possible to recover the original matrix with sufficiently
well. However, uniform sampling and incoherence assumptions _do not_ hold in
many realistic scenarios.

Subsequently, to circumvent these restrictive assumptions, another line of
work evaluates the generalization error as an alternative metric for
completion performance (Srebro et al., 2004; Shamir and Shalev-Shwartz, 2014).
To formalize, consider the task of completing $M^{\star}$ with an arbitrary
observation sampling distribution $\mu$ over $[m]\times[n]$. This can be
conceptualized as predicting a hypothesis mapping from the domain
$[m]\times[n]$ to the codomain $[-1,1]$. The goal is to characterize the
guarantees on the expected prediction error, quantified for a given completion
$\hat{M}$ as $\mathbb{E}_{(i,j)\sim\mu}[(\hat{M}_{ij}-M^{\star}_{ij})^{2}]$.
When $\mu$ is the uniform distribution over $[m]\times[n]$, the generalization
error bound translates to a guarantee over the average error across all
entries. However, if $\mu$ is arbitrary (e.g. supported over a fraction of the
entries), then no guarantee could be established for entries that lie in the
complement of the support of $\mu$. This prohibits the use of $\hat{M}$ in
settings where abstention is imperative.

Our work takes an alternative approach to this fundamental limitation in
matrix completion. The focus of our work is to identify entries where we can
predict with high confidence to guarantee a low completion error weighted by
evaluated confidence. We provide formulation of the problem, its convex
relaxation, and an efficient gradient-based online algorithm due to a
formulation of the problem as an online two-player game.

##### Randomized rounding and semi-definite relaxations.

For the efficient algorithm, the main analysis technique we deploy is based on
randomized rounding solutions of semi-definite programming, due to the seminal
work of Goemans and Williamson (1995). These were originally developed in the
context of approximation algorithms for MAX-CUT and other combinatorial
problems. Here, we use this analysis technique for analyzing inner products of
high dimensional vectors, but in a different context and to argue about a
convex relaxation of a continuous optimization problem.

##### Abstention in classification and regression.

Abstaining from prediction has a long history in other learning problems such
as binary classification Chow (1957). There are several notable similarities.
First, many of the algorithms work as ours does, by first fitting a complete
classifier and then deciding afterwards where to abstain (e.g., Hellman, 1970;
Goldwasser et al., 2020). Second, numerous abstention models have been
considered, including a fixed cost for abstaining (e.g., Chow, 1957; Kalai and
Kanade, 2021), as well as fixing the error rate and maximizing the coverage
(e.g., Geifman and El-Yaniv, 2017), as in our work, and fixing the coverage
rate while minimizing the error (e.g., Geifman and El-Yaniv, 2019). Third,
there are algorithmic similarities, in particular the observation that worst-
case performance guarantees do not depend on knowing the underlying
distribution Kalai and Kanade (2021). Online models of abstention have also
been considered (e.g., Li et al., 2011). For detailed survey on selective
classification see (El-Yaniv and Wiener, 2010).

##  2 Problem Setup and Preliminaries

For a natural number $n$, let $[n]=\\{1,2,\ldots,n\\}$. Consider a fixed set
of indices ${\mathcal{X}}=[m]\times[n]$ throughout. Thus, in this paper
$x\in{\mathcal{X}}$ is $x=(i,j)$ where $i\in[m],j\in[n]$. The set of $m\times
n$ real-valued matrices is thus written as $\mathbb{R}^{\mathcal{X}}$. We will
thus view a matrix $M$ over index set ${\mathcal{X}}$ as a function from
${\mathcal{X}}\rightarrow\mathbb{R}$, and for $x\in{\mathcal{X}}$, by slight
abuse of notation denote by both $M_{x}$ and $M(x)$ the entry of $M$ at index
$x$.

We focus on the squared loss in this paper, though it may be interesting to
consider other loss functions in future work. Suppose $\nu$ is a distribution
over ${\mathcal{X}}$, for matrices, $M,M^{\prime}$, we denote by
$\ell(\nu,M,M^{\prime})\stackrel{{\scriptstyle\text{def}}}{{=}}\mathbb{E}_{x\sim\nu}[(M(x)-M^{\prime}(x))^{2}]$;
we will also use the shorthand
$\|M-M^{\prime}\|_{\nu}^{2}\stackrel{{\scriptstyle\text{def}}}{{=}}\ell(\nu,M,M^{\prime})$.

When $T\in{\mathcal{X}}^{N}$ is a sequence of elements of ${\mathcal{X}}$ of
length $N$, we denote by
$\ell(T,M,M^{\prime})\stackrel{{\scriptstyle\text{def}}}{{=}}\frac{1}{N}\sum_{x\in
T}(M(x)-M^{\prime}(x))^{2}$ and the shorthand
$\|M-M^{\prime}\|_{T}^{2}\stackrel{{\scriptstyle\text{def}}}{{=}}\ell(T,M,M^{\prime})$.

###  2.1 Matrix Classes, Version Space and Generalization

##### Matrix Norms.

Given a matrix $M$, we denote by $\|M\|_{2,\infty}$ the maximum row norm of
$M$. We denote by $\|M\|_{\max}$ the _max-norm_ of $M$ defined as,

$\displaystyle\|M\|_{\max}\stackrel{{\scriptstyle\text{def}}}{{=}}\min_{UV^{\top}=M}\|U\|_{2,\infty}\cdot\|V\|_{2,\infty}.$
(2)

The trace norm of a matrix $M$, denoted by $\|M\|_{\mathrm{tr}}$, is the sum
of its singular values. The Frobenius norm of a matrix $M$, denoted by
$\|M\|_{\mathrm{fr}}$, is the square root of the sum of its squared entries.

We will restrict attention to matrices with entries in $[-1,1]$. The following
three classes of matrices with restrictions on respectively the _rank_ , _max-
norm_ and _trace-norm_ are of interest in this work. Formally, let
$\tilde{\mathcal{K}}=\\{M\in[-1,1]^{\mathcal{X}}\\}$, and define,

$\displaystyle{\mathcal{M}}^{\mathrm{rk}}_{k}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\\{\mathrm{rank}(M)\leq
k\\}\cap\tilde{\mathcal{K}},\ \ \ {\mathcal{M}}^{\mathrm{max}}_{K}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\\{\|M\|_{\max}\leq
K\\}\cap\tilde{\mathcal{K}},\ \ \ {\mathcal{M}}^{\mathrm{tr}}_{\tau}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\\{\|M\|_{\mathrm{tr}}\leq\tau\\}\cap\tilde{\mathcal{K}}.$

The standard assumption in matrix completion is that the target matrix is low-
rank; however, most completion algorithms exploit convex optimization methods
and optimize over max-norm or trace-norm bounded matrices. It is known that
$\|M\|_{\max}\leq\sqrt{\mathrm{rank}(M)}$ if $M\in[-1,1]^{\mathcal{X}}$ (cf.
Linial et al., 2007, Lemma 4.2) and it is easy to see that
$\|M\|_{\mathrm{tr}}\leq\mathrm{rank}(M)\sqrt{mn}$ for
$M\in[-1,1]^{\mathcal{X}}$. Thus,
${\mathcal{M}}^{\mathrm{rk}}_{k}\subseteq{\mathcal{M}}^{\max}_{\sqrt{k}}$ and
${\mathcal{M}}^{\mathrm{rk}}_{k}\subseteq{\mathcal{M}}^{\mathrm{tr}}_{k\sqrt{mn}}$.
Hence, we will work with the latter two classes which satisfy the following
lemma which is proved in Appendix A.

######  Lemma 5.

The classes, ${\mathcal{M}}^{\mathrm{max}}_{K}$ and
${\mathcal{M}}^{\mathrm{tr}}_{\tau}$, are closed under negations and are
convex.

##### Version Space.

We define the notion of version spaces that are used in our key results. For a
sequence $T\in{\mathcal{X}}^{N}$, for any class of matrices ${\mathcal{M}}$, a
matrix $M\in{\mathcal{M}}$ and $\beta>0$, we define the version space around
$M$ of radius $\beta$ based on $T$ w.r.t. ${\mathcal{M}}$ as

$\displaystyle{\mathcal{V}}(M,\beta,T;{\mathcal{M}})$
$\displaystyle=\\{M^{\prime}\in{\mathcal{M}}~{}|~{}\ell(T,M,M^{\prime})\leq\beta\\}.$
(3)

Intuitively, version space is the set of matrices in a particular matrix class
that are “close” to a given matrix with respect to $T$.

##### Generalization Bounds.

For a general class of matrices ${\mathcal{M}}$, we define a notion of sample
complexity that will guarantee the proximity of empirical and population
measures of interest for all matrices in the class; we denote this notion by
$\mathsf{sc}(\varepsilon,\delta,{\mathcal{M}})$.

######  Definition 6 (Sample Complexity).

For $\varepsilon,\delta>0$ and a class of matrices ${\mathcal{M}}$, denote by
$\mathsf{sc}(\varepsilon,\delta,{\mathcal{M}})$, the sample complexity, to be
the smallest natural number $N_{0}$, such that for any distribution $\mu$ over
${\mathcal{X}}$, for $S\sim\mu^{N_{0}}$, and for any fixed
$\hat{M}\in{\mathcal{M}}$ (possibly depending on $S$), with probability at
least $1-\delta$,

$\sup_{M\in{\mathcal{M}}}\left|\ell(S,M,\hat{M})-\ell(\mu,M,\hat{M})\right|\leq\varepsilon.$

If no such $N_{0}$ exists,
$\mathsf{sc}(\varepsilon,\delta,\mathcal{F})\stackrel{{\scriptstyle\text{def}}}{{=}}\infty$.

Bounds on the sample complexity for matrix completion can be derived in terms
of rank, max-norm and trace-norm using standard results in the literature, and
the fact that the squared loss is $2$-Lipschitz and bounded by $4$ when both
its arguments take values in $[-1,1]$. In the proposition below, the max-norm
result follows from Theorem 5 in (Srebro and Shraibman, 2005) and the trace-
norm result follows from Theorem 4 in (Shamir and Shalev-Shwartz, 2014).

######  Proposition 7.

For the classes, ${\mathcal{M}}^{\mathrm{max}}_{K}$,
${\mathcal{M}}^{\mathrm{tr}}_{\tau}$, the following hold,

  1. 1.

$\mathsf{sc}(\varepsilon,\delta,{\mathcal{M}}^{\mathrm{max}}_{K})=O\left(\frac{1}{\varepsilon^{2}}\left(K^{2}(m+n)+\log\frac{1}{\delta}\right)\right)$.

  2. 2.

$\mathsf{sc}(\varepsilon,\delta,{\mathcal{M}}^{\mathrm{tr}}_{\tau})=O\left(\frac{1}{\varepsilon^{2}}\left(\tau\sqrt{m+n}+\log\frac{1}{\delta}\right)\right)$.

It is worth comparing the two bounds in Proposition 7 above. Consider the
matrix $M^{\star}$ consisting of all $1$’s – from a matrix completion point of
view this is particularly easy as every “user” likes every “movie”. Note
however that $\|M^{\star}\|_{\max}=1$ and
$\|M^{\star}\|_{\mathrm{tr}}=\sqrt{mn}$. For this example, ignoring the
dependence on $\varepsilon,\delta$, the sample complexity bound obtained using
the trace-norm result would be $O((m+n)\sqrt{m+n})$, while that using max-norm
would be $O(m+n)$. In general, it is always the case that
$\|M\|_{\mathrm{tr}}/\sqrt{mn}\leq\|M\|_{\max}$, so it may seem that the
bounds in terms of trace-norm are weaker. However, there are matrices for
which this gap can be large and the sample complexity bound in terms of trace-
norm is shown to be tight in general (see (Srebro and Shraibman, 2005; Shamir
and Shalev-Shwartz, 2014) for further details).

###  2.2 Full Completion Problem (with Noise)

We now define the matrix completion problem with zero-mean noise, in fact a
matrix estimation problem in the noisy case. Let $\mathcal{D}$ be a
distribution supported on ${\mathcal{X}}\times[-1,1]$; the results in the
paper can all be easily extended when $\mathcal{D}$ is supported on
${\mathcal{X}}\times[-B,B]$, increasing squared error by a $B^{2}$ factor. Let
$\mu$ be the marginal distribution of $\mathcal{D}$ over ${\mathcal{X}}$. Let
$S_{XY}=\langle(x_{t},y_{t})\rangle_{t=1}^{N}$ be an iid sample drawn from
$\mathcal{D}^{N}$. Note here that $x_{t}=(i_{t},j_{t})$ denotes the index of
the matrix and $y_{t}$ the observed value. We let $S=(x_{1},\ldots,x_{N})$
denote the sequence of $x_{t}$’s from $S_{XY}$ (with repetitions allowed);
note that $S$ is distributed as $\mu^{N}$. Let
$M^{\star}\in[-1,1]^{\mathcal{X}}$ be the matrix where
$M^{\star}_{ij}=\mathbb{E}_{\mathcal{D}}[Y|X=(i,j)]$. We say that $\hat{M}$ is
an $\varepsilon$-accurate completion of $M^{\star}$, if
$\ell(\mu,M^{\star},\hat{M})\leq\varepsilon$.

######  Definition 8 (Full Completion Algorithm).

We say that $\mathsf{FullComp}(S_{XY},\varepsilon,\delta,{\mathcal{M}})$ is a
full completion algorithm with sample complexity
$\mathsf{sc}_{\mathsf{FC}}(\varepsilon,\delta,{\mathcal{M}})$ for
${\mathcal{M}}$, if provided $S_{XY}\sim\mathcal{D}^{N}$ for some
$\mathcal{D}$ over ${\mathcal{X}}\times[-1,1]$ with
$M^{\star}\in{\mathcal{M}}$,
$N\geq\mathsf{sc}_{\mathsf{FC}}(\varepsilon,\delta,{\mathcal{M}})$,
$\mathsf{FullComp}(S_{XY},\varepsilon,\delta,{\mathcal{M}})$ outputs
$\hat{M}\in{\mathcal{M}}$ that with probability at least $1-\delta$ satisfies,
$\ell(\mu,M^{\star},\hat{M})\leq\varepsilon$.

The following result follows from (Srebro and Shraibman, 2005; Shamir and
Shalev-Shwartz, 2014) (see also Prop. 7).

######  Proposition 9.

There exists polynomial time (in $mn/\varepsilon$) full completion algorithms
for ${\mathcal{M}}^{\mathrm{max}}_{K}$ and
${\mathcal{M}}^{\mathrm{tr}}_{\tau}$ (e.g. ERM methods) with the following
sample complexity bounds:

  1. 1.

$\mathsf{sc}_{\mathsf{FC}}(\varepsilon,\delta,{\mathcal{M}}^{\mathrm{max}}_{K})=O\left(\frac{1}{\varepsilon^{2}}\left(K^{2}(m+n)+\log\frac{1}{\delta}\right)\right)$.

  2. 2.

$\mathsf{sc}_{{\mathcal{M}}^{\mathrm{tr}}_{\tau}}(\varepsilon,\delta,{\mathcal{M}}^{\mathrm{tr}}_{\tau})=O\left(\frac{1}{\varepsilon^{2}}\left(\tau\sqrt{m+n}+\log\frac{1}{\delta}\right)\right)$.

###  2.3 The Partial Matrix Completion Problem

Recall the definition of the (fractional) partial matrix completion in Eq. 1
and Def. 1. In this work, we will assume that a full completion matrix
$\hat{M}$ is already obtained. The focus of the present work is finding a
completion matrix $C\in\\{0,1\\}^{\mathcal{X}}$ (or $C\in[0,1]^{\mathcal{X}}$
for fractional coverage) with large coverage. The coverage in both cases are
defined as:
$|C|\stackrel{{\scriptstyle\text{def}}}{{=}}\sum_{x\in{\mathcal{X}}}C_{x},$
and a low loss, defined as:

$\ell(C,M^{\star},\hat{M})\stackrel{{\scriptstyle\text{def}}}{{=}}\frac{1}{|C|}\sum_{x\in{\mathcal{X}}}C_{x}(M^{\star}_{x}-\hat{M}_{x})^{2}.$

Note that $C\in[0,1]^{\mathcal{X}}$ can be viewed as a “fractional” set and we
are overloading the notation $\ell$ to allow that. Such a fractional coverage
can be randomly rounded to a set whose size is within 1 of $|C|$. In an ideal
world, we would have at most $\varepsilon$ loss measured over the cells we
complete as defined above, and large or even full coverage $|C|=mn$.

Note that although the requirement in the optimization problems in Eq. (1) and
Def. 1 is to guarantee $\ell(C,M^{\star},M)\leq\varepsilon$, as we don’t know
$M^{\star}$, the only guarantee we have by using a full completion algorithm
(and generalization bounds) is that (with high probability) $M^{\star}$ is in
some version space, say ${\mathcal{V}}$, centered at $\hat{M}$. So we actually
show a stronger guarantee that,
$\sup_{M\in{\mathcal{V}}}\ell(C,M,\hat{M})\leq\varepsilon$.

A second observation is that if $M$ is a version space around $\hat{M}$, then
by convexity of the matrix classes, the matrix $(M-\hat{M})/2$, must be in
some version space, say ${\mathcal{V}}_{0}$, centered around the zero matrix,
$\mathbf{0}_{\mathcal{X}}$. Thus, we will actually find a $C$ that guarantees,
$\ell(C,M,\mathbf{0}_{\mathcal{X}})\leq\varepsilon$ for every
$M\in{\mathcal{V}}_{0}$. This means that for maximizing coverage our algorithm
has the remarkable property we only need to know the locations of the revealed
entries as indicated by $S$.

Section 3 presents a computationally inefficient but statistically superior
algorithm in terms of sample complexity for the _coverage problem_ and its
consequences for partial matrix completion. Section 4 presents a
computationally efficient algorithm at the cost of a slightly worse sample
complexity when using the class ${\mathcal{M}}^{\mathrm{max}}_{K}$.

##  3 An Inefficient Algorithm

The main novelty in the partial matrix completion problem is that of finding
an optimal coverage, defined as the matrix $C$ in the formulation in Def. 1.
In this section we give an (inefficient) algorithm for finding the optimal
coverage, and the generalization error bounds for Partial Matrix Completion
that arise from it. In the next section we give an efficient approximation
algorithm for doing the same, with slightly worse sample complexity bounds and
more complex analysis. This differs substantially from prior work on
abstention in classification and regression (Kalai and Kanade, 2021) where the
optimal solution can be found in polynomial time.

Let $C\in[0,1]^{\mathcal{X}}$ be a target confidence matrix. For such a $C$,
we will denote by $\nu_{C}$ the probability distribution where
$\nu_{C}(x)=C_{x}/\|C\|_{1}$ for $x\in{\mathcal{X}}$. Let $S\sim\mu^{N}$ be a
sample obtained from the target distribution $\mu$. We output a $C$ which is
an optimal solution to the following optimization problem, inspired by a
similar problem studied by Kalai and Kanade (2021) for classification with
abstention.

$\displaystyle\text{Parameters and inputs}:\gamma,\beta,S,{\mathcal{M}}$
$\displaystyle\text{maximize}\ \ \ \|C\|_{1}$ (4) $\displaystyle\text{subject
to }C\in[0,1]^{{\mathcal{X}}},\ \text{and}\quad\forall
M\in{\mathcal{V}}(\mathbf{0}_{\mathcal{X}},\beta,S;{\mathcal{M}}),\
\ell(\nu_{C},M,\mathbf{0}_{\mathcal{X}})\leq\gamma$

1: Inputs: $S_{XY}=\langle(x_{t},y_{t})\rangle_{t=1}^{N}\sim\mathcal{D}^{N}$,
$\varepsilon$, $\delta$, ${\mathcal{M}}$, $\mathsf{FullComp}$ (cf. Def. 8).

2: Obtain $\hat{M}\in{\mathcal{M}}$ using
$\mathsf{FullComp}(S_{XY},\varepsilon/4,\delta/3,{\mathcal{M}})$.

3: Obtain $C$ using MP 4 with
$\gamma\stackrel{{\scriptstyle\text{def}}}{{=}}\varepsilon/4$,
$\beta\stackrel{{\scriptstyle\text{def}}}{{=}}\varepsilon/8$,
$S=(x_{1},x_{2},\ldots,x_{N})$ from $S_{XY}$.

4: return $(\hat{M},C)$.

Algorithm 1

MP 4 defines a family of optimization problems; we will typically use
${\mathcal{M}}$ to be ${\mathcal{M}}^{\mathrm{max}}_{K}$ or
${\mathcal{M}}^{\mathrm{tr}}_{\tau}$. The above optimization problem is in
fact a linear program. The only unknowns are $C_{x}$ for $x\in{\mathcal{X}}$.
However, the set of constraints is infinite and it is unclear how a separation
oracle for the constraint set may be designed. Such an oracle could be
designed by solving the following optimization problem:

$\max_{M\in{\mathcal{V}}(\mathbf{0}_{\mathcal{X}},\beta,S;{\mathcal{M}})}\ell(\nu_{C},M,\mathbf{0}_{\mathcal{X}}).$
(5)

This optimization problem requires maximizing a quadratic function, and we
prove it to be $\mathsf{NP}$-hard with the additional PSD and symmetric
constraints in Appendix A.2.

The following result subsumes Corollary 2. We defer the proof of this theorem
to Appendix A, as the proof is similar to that of our efficient algorithm in
the next section.

######  Theorem 10.

Let ${\mathcal{M}}$ be either ${\mathcal{M}}^{\mathrm{max}}_{K}$ or
${\mathcal{M}}^{\mathrm{tr}}_{\tau}$. Let $\mathcal{D}$ be distribution over
${\mathcal{X}}\times[-1,1]$, $\mu$ the marginal of $\mathcal{D}$ over
${\mathcal{X}}$, $\mu_{\max}=\max_{i,j}\mathbb{P}_{\mu}((i,j)\text{ is
sampled})$. Suppose that $M^{\star}$, defined as
$M^{\star}_{ij}=\mathbb{E}_{(X,Y)\sim\mathcal{D}}[Y|X=(i,j)]$ satisfies that
$M^{\star}\in{\mathcal{M}}$. Furthermore, suppose that
$S_{XY}\sim\mathcal{D}^{N}$ and that $\mathsf{FullComp}$ is a full completion
algorithm as in Defn. 8. Then, provided
$N\geq\max\\{\mathsf{sc}_{\mathrm{FC}}(\varepsilon/4,\delta/3,{\mathcal{M}}),\mathsf{sc}(\varepsilon/8,\delta/3,{\mathcal{M}})\\}$,
for $(\hat{M},C)$ output by Alg. 1, it holds that:

  1. 1.

$\|C\|_{1}\geq 1/\mu_{\max}$,

  2. 2.

$\displaystyle\frac{1}{\|C\|_{1}}\sum_{x\in{\mathcal{X}}}C_{x}(\hat{M}_{x}-M^{\star}_{x})^{2}\leq\varepsilon.$

##  4 An Efficient Algorithm

In this section, we show how the result from Proposition 14 can be achieved
using an efficient algorithm at a modest cost in terms of sample complexity
when using the matrix class ${\mathcal{M}}^{\mathrm{max}}_{K}$. In particular,
we consider the optimization problem defined in MP 4, where the constraint
$\|M\|_{\nu_{C}}^{2}\leq\gamma$ for all
$M\in{\mathcal{V}}(\mathbf{0}_{\mathcal{X}},\beta,S;{\mathcal{M}}^{\mathrm{max}}_{K})$
from MP 4 is replaced by $\mathbb{E}_{x\sim\nu_{C}}[M_{x}]\leq\gamma$. The
efficiency comes from the fact that we can now implement a separation oracle
for the constraint set by solving, for a given $C$, the problem,

$\max_{M\in{\mathcal{V}}(\mathbf{0}_{\mathcal{X}},\beta,S,{\mathcal{M}}^{\mathrm{max}}_{K})}\mathbb{E}_{x\sim\nu_{C}}[M_{x}].$

Mathematical program 4 is a convex optimization problem since the constraint
set is convex and the objective function is linear. However, it is not
immediately clear how this relaxed optimization problem relates to the
original, which is the main technical contribution of this section.

$\displaystyle\text{Parameters and
inputs}:\gamma,\beta,S,{\mathcal{M}}^{\mathrm{max}}_{K}$
$\displaystyle\text{maximize}\ \ \ \|C\|_{1}$ (6) $\displaystyle\text{subject
to }C\in[0,1]^{{\mathcal{X}}},\ \text{and }\forall
M\in{\mathcal{V}}(\mathbf{0}_{\mathcal{X}},\beta,S;{\mathcal{M}}^{\mathrm{max}}_{K}),\
\mathbb{E}_{x\sim\nu_{C}}[M_{x}]\leq\gamma$

Algorithm 2 (Efficient) Offline Algorithm for Partial Matrix Completion

1: Inputs: $S_{XY}=\langle(x_{t},y_{t})\rangle_{t=1}^{N}\sim\mathcal{D}^{N}$,
$\mathsf{FullComp}$ (cf. Def. 8), $\varepsilon$, $\delta$.

2: Obtain $\hat{M}\in{\mathcal{M}}^{\mathrm{max}}_{K}$ using
$\mathsf{FullComp}(S_{XY},\varepsilon^{2}/(4\pi^{2}K^{2}),\delta/3,{\mathcal{M}}^{\mathrm{max}}_{K})$.

3: Obtain $C$ using MP 4 with
$\gamma\stackrel{{\scriptstyle\text{def}}}{{=}}\varepsilon/(2\pi K)$,
$\beta\stackrel{{\scriptstyle\text{def}}}{{=}}\varepsilon^{2}/(8\pi^{2}K^{2})$,
$S=(x_{1},x_{2},\ldots,x_{N})$ from $S_{XY}$.

4: return $(\hat{M},C)$.

The following result subsumes Corollary 3.

######  Theorem 11.

Let $\mathcal{D}$ be a distribution over ${\mathcal{X}}\times[-1,1]$, $\mu$
the marginal of $\mathcal{D}$ over ${\mathcal{X}}$,
$\mu_{\max}=\max_{i,j}\mathbb{P}_{\mu}((i,j)\text{ is sampled})$. Suppose that
$M^{\star}$, defined as
$M^{\star}_{ij}=\mathbb{E}_{(X,Y)\sim\mathcal{D}}[Y|X=(i,j)]$ satisfies that
$M^{\star}\in{\mathcal{M}}^{\mathrm{max}}_{K}$. Furthermore, suppose that
$S_{XY}\sim\mathcal{D}^{N}$ and that $\mathsf{FullComp}$ is a full completion
algorithm as in Defn. 8. Then, provided
$N\geq\max\\{\mathsf{sc}_{\mathrm{FC}}(\varepsilon^{2}/(4\pi^{2}K^{2}),\delta/3,{\mathcal{M}}^{\mathrm{max}}_{K}),$
$\mathsf{sc}(\varepsilon^{2}/(8\pi^{2}K^{2}),\delta/3,{\mathcal{M}}^{\mathrm{max}}_{K})\\}$,
for $(\hat{M},C)$ output by Alg. 4, it holds that:

  1. 1.

$\|C\|_{1}\geq 1/\mu_{\max}$,

  2. 2.

$\displaystyle\frac{1}{\|C\|_{1}}\sum_{x\in{\mathcal{X}}}C_{x}(\hat{M}_{x}-M^{\star}_{x})^{2}\leq\varepsilon$.

##  5 Online Setting

The previous section introduces the offline setting for the partial matrix
completion problem. In Appendix B, we describe the online version of the
problem, which is motivated by two important considerations. First, in many
applications, the observation pattern is more general than a fixed
distribution. It can be a changing distribution or be comprised of adversarial
observations. Second, our online algorithm incrementally updates the solution
via iterative gradient methods, which is more efficient than the offline
methods. For space considerations, details are deferred to Appendix B which
contains the setting, definitions, algorithm specification, and main results,
and Appendix C, which details the proofs. In particular, the online algorithm,
called Online Dual Descent (ODD), is described in Algorithm 3, and its regret
guarantee in Theorem 18. The online regret guarantee implies the statistical
learning guarantees of the previous sections when the support size is a
constant fraction of the full matrix, and this implication is spelled out
precisely in Corollary 22.

##  6 Experiments and Implementation

The MovieLens dataset ((Harper and Konstan, 2015)) consists of, among other
data, a set of users with their rankings of a set of movies. It is a common
benchmark for matrix completion because some of the rankings are missing, and
one can make predictions on the rankings of user preferences.

We used the dataset differently, aiming to test our online algorithm on
generating a satisfying confidence matrix. The experimental procedure is
outlined as follows: we used training data from $250$ users and their ratings
on $250$ movies, giving us a total of $5189$ completed samples from the
incomplete matrix of size $250\times 250$. We ran our algorithm, ODD
(Algorithm 3), to get a confidence matrix $C$. In parallel, we used another
standard matrix completion tool, fancyimpute ((Rubinsteyn and Feldman, 2016)),
to fill in the missing entries of the matrix and obtain a completion
$\hat{M}_{f}$. After $C$ and $\hat{M}_{f}$ are obtained, we reveal the true
ratings at the missing entries using the validation set and computed the mean
squared error of the predicted rating and true rating at each entry. The
following plots show the distribution of the mean squared error with respect
to the confidence score $C$ assign at the particular entry.

Figure 2: (a) ODD heuristic on $250\times 250$ user-movie rating data from the
MovieLens Dataset. Squared error in entry-wise prediction and entry-wise
confidence level estimated by the ODD heuristic. (b) The average squared error
over various confidence levels suggests that a higher confidence level is
correlated with a lower squared error.

##  7 Conclusion

In this work we define the setting of partial matrix completion, with our
high-level contributions outlined as the following:

##### A new framework.

We propose a new framework called partial matrix completion. In this problem,
one is given possibly noisy observations from a low-rank matrix, and the goal
is to identify entries that can be predicted with high confidence. The partial
matrix completion problem answers two key questions:

  * •

Based on possibly noisy samples from an arbitrary unknown sampling
distribution $\mu$, how many entries can be completed with $\leq\varepsilon$
error?

  * •

How can we efficiently identify the entries that can be accurately completed?

When the underlying matrix has low rank $k$, we show that it is possible to
complete a large fraction of the matrix using only $\tilde{O}(k(m+n))$
observations while simultaneously guaranteeing high accuracy over the
completed set. We then study the complexity of identifying the optimal
completion matrix. We show that a naïve mathematical programming formulation
of the problem is hard. However, we propose a relaxation that gives rise to
efficient algorithms, which results in a slightly worse dependence on $k$ for
the sample complexity. These guarantees are outlined both in Corollary 2 and
Corollary 3, and Theorem 10 and Theorem 11 for their more general versions.

##### Online game formulation.

Furthermore, we consider the partial matrix completion problem in the online
setting, where the revealed observations are not required to follow any
particular fixed distribution. The goal henceforth is to minimize regret, the
gap between the algorithm’s performance and the single best decision in
hindsight. This is a more general setting, as when imposed with distribution
assumptions, regret guarantees in online learning algorithms naturally
translate to statistical guarantees.

Our proposed online partial matrix completion algorithm is derived from an
online repeated game. The version space is the set of all valid completions
with low generalization error. High confidence should be assigned to entries
where all completions in the version space are similar. Therefore, we
formulate the problem as a two-player online game. One player iteratively
updates a confidence matrix, and the other learns the version space. We gave
an iterative gradient-based method with provable regret guarantees and
concluded with preliminary experimental evidence of the validity of our
framework.

##  8 Acknowledgements

Elad Hazan acknowledges funding from the Office of Naval Research grant
N000142312156, the NSF award 2134040, and Open Philanthropy. This work was
done in part when Clara Mohri was visiting and supported by Princeton
University.

## References

  * Abbe et al. [2020] Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong.  Entrywise eigenvector analysis of random matrices with low expected rank.  _Annals of statistics_ , 48(3):1452, 2020.
  * Candès and Recht [2009] Emmanuel J Candès and Benjamin Recht.  Exact matrix completion via convex optimization.  _Foundations of Computational mathematics_ , 9(6):717–772, 2009.
  * Candès and Tao [2010] Emmanuel J Candès and Terence Tao.  The power of convex relaxation: Near-optimal matrix completion.  _IEEE Transactions on Information Theory_ , 56(5):2053–2080, 2010.
  * Chen et al. [2020] Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, and Yuling Yan.  Noisy matrix completion: Understanding statistical guarantees for convex relaxation via nonconvex optimization.  _SIAM journal on optimization_ , 30(4):3098–3121, 2020.
  * Chow [1957] Chi-Keung Chow.  An optimum character recognition system using decision functions.  _IRE Transactions on Electronic Computers_ , 4:247–254, 1957.
  * El-Yaniv and Wiener [2010] Ran El-Yaniv and Yair Wiener.  On the foundations of noise-free selective classification.  _Journal of Machine Learning Research_ , 11(53):1605–1641, 2010.  URL http://jmlr.org/papers/v11/el-yaniv10a.html.
  * Freund and Schapire [1999] Yoav Freund and Robert E Schapire.  Adaptive game playing using multiplicative weights.  _Games and Economic Behavior_ , 29(1-2):79–103, 1999.
  * Geifman and El-Yaniv [2017] Yonatan Geifman and Ran El-Yaniv.  Selective classification for deep neural networks.  _Advances in neural information processing systems_ , 30, 2017.
  * Geifman and El-Yaniv [2019] Yonatan Geifman and Ran El-Yaniv.  Selectivenet: A deep neural network with an integrated reject option.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 2151–2159. PMLR, 2019\.
  * Goemans and Williamson [1995] Michel X Goemans and David P Williamson.  Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.  _Journal of the ACM (JACM)_ , 42(6):1115–1145, 1995.
  * Goldwasser et al. [2020] Shafi Goldwasser, Adam Tauman Kalai, Yael Tauman Kalai, and Omar Montasser.  Selective classification algorithms provably robust to arbitrary adversarial examples.  In _Advances in Neural Information Processing Systems_ , 2020.
  * Gross [2011] David Gross.  Recovering low-rank matrices from few coefficients in any basis.  _IEEE Transactions on Information Theory_ , 57(3):1548–1566, 2011.
  * Grötschel et al. [1981] Martin Grötschel, László Lovász, and Alexander Schrijver.  The ellipsoid method and its consequences in combinatorial optimization.  _Combinatorica_ , 1(2):169–197, 1981.
  * Harper and Konstan [2015] F. Maxwell Harper and Joseph A. Konstan.  The movielens datasets: History and context.  _ACM Trans. Interact. Intell. Syst._ , 5(4), dec 2015.  ISSN 2160-6455.  doi: 10.1145/2827872.
  * Hastad [1996] Johan Hastad.  Clique is hard to approximate within n/sup 1-/spl epsiv.  In _Proceedings of 37th Conference on Foundations of Computer Science_ , pages 627–636. IEEE, 1996.
  * Hazan et al. [2012a] Elad Hazan, Satyen Kale, and Shai Shalev-Shwartz.  Near-optimal algorithms for online matrix prediction.  In _COLT_ , pages 38.1–38.13, 2012a.
  * Hazan et al. [2012b] Elad Hazan, Satyen Kale, and Shai Shalev-Shwartz.  Near-optimal algorithms for online matrix prediction.  In _Conference on Learning Theory_ , pages 38–1. JMLR Workshop and Conference Proceedings, 2012b.
  * Hazan et al. [2016] Elad Hazan et al.  Introduction to online convex optimization.  _Foundations and Trends® in Optimization_ , 2(3-4):157–325, 2016.
  * Hellman [1970] Martin E. Hellman.  The nearest neighbor classification rule with a reject option.  _IEEE Transactions on Systems Science and Cybernetics_ , 6(3):179–185, 1970.  doi: 10.1109/TSSC.1970.300339.
  * Jain et al. [2013] Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi.  Low-rank matrix completion using alternating minimization.  In _Proceedings of the forty-fifth annual ACM symposium on Theory of computing_ , pages 665–674, 2013.
  * Kalai and Kanade [2021] Adam Kalai and Varun Kanade.  Towards optimally abstaining from prediction with ood test examples.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , volume 34, pages 12774–12785. Curran Associates, Inc., 2021.  URL https://proceedings.neurips.cc/paper/2021/file/6a26c75d6a576c94654bfc4dda548c72-Paper.pdf.
  * Keshavan et al. [2010] Raghunandan H Keshavan, Andrea Montanari, and Sewoong Oh.  Matrix completion from a few entries.  _IEEE transactions on information theory_ , 56(6):2980–2998, 2010.
  * Li et al. [2011] Lihong Li, Michael L Littman, Thomas J Walsh, and Alexander L Strehl.  Knows what it knows: a framework for self-aware learning.  _Machine learning_ , 82(3):399–443, 2011.
  * Linial et al. [2007] Nati Linial, Shahar Mendelson, Gideon Schechtman, and Adi Shraibman.  Complexity measures of sign matrices.  _Combinatorica_ , 27(4):439–463, 2007.
  * Mahdavi et al. [2012] Mehrdad Mahdavi, Rong Jin, and Tianbao Yang.  Trading regret for efficiency: online convex optimization with long term constraints.  _The Journal of Machine Learning Research_ , 13(1):2503–2528, 2012.
  * Negahban and Wainwright [2012] Sahand Negahban and Martin J Wainwright.  Restricted strong convexity and weighted matrix completion: Optimal bounds with noise.  _The Journal of Machine Learning Research_ , 13(1):1665–1697, 2012.
  * Recht [2011] Benjamin Recht.  A simpler approach to matrix completion.  _Journal of Machine Learning Research_ , 12(12), 2011.
  * Rubinsteyn and Feldman [2016] Alex Rubinsteyn and Sergey Feldman.  fancyimpute: An imputation library for python, 2016.  URL https://github.com/iskandr/fancyimpute.
  * Shamir and Shalev-Shwartz [2014] Ohad Shamir and Shai Shalev-Shwartz.  Matrix completion with the trace norm: Learning, bounding, and transducing.  _Journal of Machine Learning Research_ , 15(1):3401–3423, 2014.
  * Srebro [2004] Nathan Srebro.  _Learning with Matrix Factorizations_.  PhD thesis, Massachusetts Institute of Technology, 2004.
  * Srebro and Shraibman [2005] Nathan Srebro and Adi Shraibman.  Rank, trace-norm and max-norm.  In _International Conference on Computational Learning Theory_ , pages 545–560. Springer, 2005.
  * Srebro et al. [2004] Nathan Srebro, Noga Alon, and Tommi Jaakkola.  Generalization error bounds for collaborative prediction with low-rank matrices.  _Advances In Neural Information Processing Systems_ , 17, 2004.
  * Warmuth [2010] Manfred K Warmuth.  The blessing and the curse of the multiplicative updates.  In _International Conference on Discovery Science_ , pages 382–382. Springer, 2010.

###### Contents

  1. 1 Introduction
    1. 1.1 Our contribution
    2. 1.2 Related work
  2. 2 Problem Setup and Preliminaries
    1. 2.1 Matrix Classes, Version Space and Generalization
    2. 2.2 Full Completion Problem (with Noise)
    3. 2.3 The Partial Matrix Completion Problem
  3. 3 An Inefficient Algorithm
  4. 4 An Efficient Algorithm
  5. 5 Online Setting
  6. 6 Experiments and Implementation
  7. 7 Conclusion
  8. 8 Acknowledgements
  9. A Supporting Proofs
    1. A.1 Proof of Lemma 5
    2. A.2 Computational Hardness of the Coverage Problem
    3. A.3 Proof of Theorem 10
    4. A.4 Proof of Theorem 11
  10. B Online Partial Matrix Completion
    1. B.1 Preliminaries
    2. B.2 Motivations
      1. B.2.1 Game theoretic nature of partial matrix completion
      2. B.2.2 Soft constraints
    3. B.3 Online PMC General Protocol
    4. B.4 Designing Convex-Concave Objectives
    5. B.5 Online Dual Descent (ODD): online gradient-based algorithm for partial matrix completion
    6. B.6 Offline implications
  11. C Supporting Proofs for Appendix B
    1. C.1 Linear Relaxation
    2. C.2 Proof of regret guarantees
      1. C.2.1 Proof of Theorem 19
      2. C.2.2 Proof of Theorem 20
    3. C.3 Proof of offline implications
      1. C.3.1 Proof of Lemma 21
      2. C.3.2 Proof of Theorem 22
  12. D Implementation Details
  13. E Definitions

##  Appendix A Supporting Proofs

###  A.1 Proof of Lemma 5

######  Lemma 5.

The classes, ${\mathcal{M}}^{\mathrm{max}}_{K}$ and
${\mathcal{M}}^{\mathrm{tr}}_{\tau}$, are closed under negations and are
convex.

###### Proof of Lemma 5.

Suppose $M$ is a matrix then we can write $M=UV^{\top}$ such that,

  * •

If $M\in{\mathcal{M}}^{\mathrm{max}}_{K}$,
$\|U\|_{2,\infty}\cdot\|V\|_{2,\infty}\leq K$.

  * •

If $M\in{\mathcal{M}}^{\mathrm{tr}}_{\tau}$,
$\|U\|_{\mathrm{fr}}\cdot\|V\|_{\mathrm{fr}}\leq\tau$.

Note that $-M=-UV^{\top}$, negating the sign of $U$ doesn’t affect its norm,
so clearly the classes are closed under negation.

The convexity of the class follows directly from that $\|\cdot\|_{\max}$ and
$\|\cdot\|_{\mathrm{tr}}$ are well-defined norms.

∎

###  A.2 Computational Hardness of the Coverage Problem

In this section we show that the optimization problem MP 4 is NP-hard in full
generality. The first fact we use is the polynomial time equivalence between
linear optimization and separation that was established in the work of
Grötschel et al. [1981]. It thus remains to prove NP-hardness of the
separation problem, which is given in equation 5, and can be restated as the
following mathematical program when our version space is restricted with a
trace norm constraint:

$\displaystyle\max_{X}\sum_{ij}C_{ij}X_{ij}^{2}$ (7)
$\displaystyle|X_{ij}|\leq 1,\|X\|_{\mathrm{tr}}\leq k.$

We give evidence of NP-hardness for this program by considering the same
mathematical program added a symmetric positive-definite constraint, as
follows.

######  Lemma 12.

Mathematical program (8) is NP-hard to compute, or approximate with factor
$k^{1-\varepsilon}$ for any $\varepsilon>0$.

$\displaystyle\max_{X}\sum_{ij}C_{ij}X_{ij}^{2}$ (8) $\displaystyle
0~{}\leq~{}X_{ij}\leq 1,X\succeq 0\ ,X\in\mathrm{Sym}(n),\ \mathrm{tr}(X)\leq
k.$

###### Proof.

The proof relies on strong hardness of approximation results for the MAX-
CLIQUE problem that were proven in Hastad [1996] and subsequent work.

We prove by reduction from $k$-CLIQUE. Let $G(V,E)$ be an instance of the
$k$-CLIQUE problem.

The reduction. Given a graph $G$, let

$\mathbb{R}^{V\times V}\ni
C_{ij}={\left\\{\begin{array}[]{ll}{1}&{\;\text{$(i,j)\in E$ \text{ or }
$i=j$}}\\\\[4.30554pt] {0}&{\;\text{otherwise}}\end{array}\right.}.$

∎

We now claim the following:

######  Lemma 13.

The value of mathematical program (7) is at least ${k^{2}}$ if $G$ contains
clique of size $k$. Conversely, if the value of (7) is at least $k^{2}$, then
$G$ contains a clique of size at least $k$.

###### Proof.

Completeness If $G$ has a $k$ clique, then consider the following solution
$X$. Let

$v_{i}={\left\\{\begin{array}[]{ll}{1}&{\;\text{$i\in$ clique}}\\\\[4.30554pt]
{0}&{\;\text{o/w}}\end{array}\right.}$

and let $X=vv^{\top}$. Then we have that $\mathrm{tr}{X}=k$,
$X_{ij}\in\\{0,1\\}$. In addition, by definition of $X$, we have that

$\sum_{ij}C_{ij}X_{ij}^{2}=\sum_{ij}C_{ij}v_{i}^{2}v_{j}^{2}=k^{2}.$

Soundness Suppose program (8) has a solution $X$ with value $k^{2}$ and trace
exactly $k$. The trace equality is w.l.o.g since we can always increase the
diagonal entries while preserving constraints and only increasing the
objective. Therefore, without loss of generality, we may assume that
$\mathrm{tr}(X)=k$.

Next, we claim that w.l.o.g. we have that $\mathrm{rank}(X)=1$. To see this,
notice that we can define a vector $u_{i}=\sqrt{X_{ii}}$, and
$\tilde{X}=uu^{\top}$. Now, we have that $\mathrm{tr}(\tilde{X})=k$, and it
satisfies the bounded-ness constraints by definition. In addition, we have
that the objective is only increased, since

$\sum_{ij}C_{ij}(v_{i}v_{j})^{2}=\sum_{ij}C_{ij}{X_{ii}}{X_{jj}}~{}\geq~{}\sum_{ij}C_{ij}X_{ij}^{2},$

where the last inequality is by positive semi-definiteness.

Thus, we can restrict our attention to the set of solutions given by
$\mathcal{K}_{k}=\\{uu^{\top}\ ,\ 0~{}\leq~{}u_{i}~{}\leq~{}1\ ,\
\|u\|_{1}=k\\}$. We claim that $\mathcal{K}_{k}$ can be alternatively
characterized as the convex hull of all rank-one matrices of the following
form:

$\mathcal{K}_{k}=\operatorname*{conv}\left\\{vv^{\top}|v\in\\{0,1\\}^{V}\ ,\
\|v\|_{1}=k\right\\}.$

This fact is shown in page 279 of Warmuth [2010].

We can now continue with the soundness proof. Since the objective
$\sum_{ij}C_{ij}X_{ij}^{2}$ is a convex function, given a distribution over
points in $\mathcal{K}_{k}$, the maximum is obtained in a vertex. Thus, there
exists a binary vector $v$ such that its trace is $k$, and for which
$\sum_{ij}C_{ij}v_{i}v_{j}=k^{2}$.

Define a subgraph according to $v$ in the natural way: $i\in S$ if and only if
$v_{i}=1$. Notice that the subset of vertices $S$ is of size $k$ due to the
trace.

In terms of number of edges in this subgraph, notice that

$\displaystyle|E(S)|$ $\displaystyle=\frac{1}{2}\sum_{ij\in
S}\mathbf{1}_{(i,j)\in
E}=\frac{1}{2}\sum_{ij}C_{ij}v_{i}v_{j}=\frac{k^{2}}{2}.$

Thus, we have found a clique of size $k$. ∎

We note that, although we have shown NP-hardness for the trace-norm with
symmetric PSD constraints, it is possible that the optimization problem is
efficiently solvable for the max-norm or rank.

###  A.3 Proof of Theorem 10

Recall our main theorem for the inefficient algorithm, which we prove in this
appendix.

######  Theorem 10.

Let ${\mathcal{M}}$ be either ${\mathcal{M}}^{\mathrm{max}}_{K}$ or
${\mathcal{M}}^{\mathrm{tr}}_{\tau}$. Let $\mathcal{D}$ be distribution over
${\mathcal{X}}\times[-1,1]$, $\mu$ the marginal of $\mathcal{D}$ over
${\mathcal{X}}$. Suppose that $M^{\star}$, defined as
$M^{\star}_{ij}=\mathbb{E}_{D}[Y|X=(i,j)]$ satisfies that
$M^{\star}\in{\mathcal{M}}$. Furthermore, suppose that $S\sim\mathcal{D}^{N}$
and that $\mathsf{FullComp}$ is a full completion algorithm as in Defn. 8.
Then, provided
$N\geq\max\\{\mathsf{sc}_{\mathrm{FC}}(\varepsilon/4,\delta/3,{\mathcal{M}}),\mathsf{sc}(\varepsilon/8,\delta/3,{\mathcal{M}})\\}$,
for $(\hat{M},C)$ output by Alg. 1, with probability at least $1-\delta$, it
holds that:

  1. 1.

$\|C\|_{1}\geq 1/\mu_{\max}$ and

  2. 2.

$\displaystyle\frac{1}{\|C\|_{1}}\sum_{x\in{\mathcal{X}}}C_{x}(\hat{M}_{x}-M^{\star}_{x})^{2}\leq\varepsilon.$

The proof relies on the following proposition.

######  Proposition 14.

Suppose $S\sim\mu^{N}$ for some distribution $\mu$ over ${\mathcal{X}}$; let
$\mu_{\max}\stackrel{{\scriptstyle\text{def}}}{{=}}\max_{x\in{\mathcal{X}}}\mu_{x}$.
Suppose ${\mathcal{M}}$ is one of ${\mathcal{M}}^{\mathrm{max}}_{K}$ or
${\mathcal{M}}^{\mathrm{tr}}_{\tau}$, let
$N\geq\mathsf{sc}(\gamma/2,\delta,{\mathcal{M}})$ (cf. Defn. 6) and suppose
$C$ is the maximizer of MP 4 with $\beta=\gamma/2$, then with probability at
least $1-\delta$, we have $\|C\|_{1}\geq 1/\mu_{\max}$.

###### Proof.

Based on the condition on $N$ and using $\hat{M}=\mathbf{0}_{\mathcal{X}}$ in
Defn. 6, with probability at least $1-\delta$, the following holds for all
$M\in{\mathcal{M}}$:

$\displaystyle\left|\|M\|_{\mu}^{2}-\|M\|_{S}^{2}\right|$
$\displaystyle\leq\gamma/2$ (9)

We need to show that some $C^{\mu}$, with $\|C^{\mu}\|_{1}\geq 1/\mu_{\max}$
is feasible. Let $C^{\mu}_{x}=\mu(x)/\mu_{\max}$. Then, clearly
$C_{x}\in[0,1]$, $\|C^{\mu}\|_{1}=1/\mu_{\max}$ and $\nu_{C^{\mu}}=\mu$. Using
Eq. (9), we have that, $\|M\|_{\mu}^{2}\leq\|M\|_{S}^{2}+\gamma/2$, and as a
result for every
$M\in{\mathcal{V}}(\mathbf{0}_{\mathcal{X}},\beta,S;{\mathcal{M}})$, it holds
that $\|M\|_{\mu}^{2}\leq\beta+\gamma/2=\gamma$. Thus, $C_{\mu}$ is a feasible
solution to the optimization problem with objective value at least
$1/\mu_{\max}$. ∎

###### Proof of Theorem 10.

There are three bad events, for each of which we bound their probability by at
most $\delta/3$. First, $\mathsf{FullComp}$ succeeds with probability at least
$1-\delta/3$.

Second, provided $N\geq\mathsf{sc}(\varepsilon/8,\delta/3,{\mathcal{M}})$, for
$\hat{M}$ output by $\mathsf{FullComp}$, using Defn. 6 it must hold for each
$M\in{\mathcal{M}}$ that with probability at least $1-\delta/3$,

$\displaystyle\left|\|M-\hat{M}\|_{\mu}^{2}-\|M-\hat{M}\|_{S}^{2}\right|$
$\displaystyle\leq\varepsilon/8$ (10)

In particular, when $\beta=\varepsilon/8$, this means that (assuming
$\mathsf{FullComp}$ has not failed),

$\displaystyle\|(M^{\star}-\hat{M})/{2}\|^{2}_{S}$
$\displaystyle\leq\frac{1}{4}\|M^{\star}-M\|_{\mu}^{2}+\frac{\epsilon}{32}\leq\frac{\varepsilon}{16}+\frac{\varepsilon}{32}\leq\beta.$

As a result, and also using the convexity of ${\mathcal{M}}$ (cf. Lemma 5),
$(M^{\star}-\hat{M})/2\in{\mathcal{V}}(\mathbf{0}_{\mathcal{X}},\beta,S;{\mathcal{M}})$.

Finally, for
$N\geq\mathsf{sc}(\varepsilon/8=\gamma/2,\delta/3,{\mathcal{M}})$, Proposition
14 guarantees with probability at least $1-\delta/3$, that the output of MP 4
satisfies $\|C\|_{1}\geq 1/\mu_{\max}$.

The constraint of MP 4 together with the fact that
$(M^{\star}-\hat{M})/2\in{\mathcal{V}}(\mathbf{0}_{\mathcal{X}},\beta,S;{\mathcal{M}})$
guarantees that, $\|M^{\star}-\hat{M}\|_{\nu_{C}}^{2}\leq 4\gamma$ which
completes the required proof. ∎

###  A.4 Proof of Theorem 11

######  Proposition 15.

Suppose $S\sim\mu^{N}$ for some distribution $\mu$ over ${\mathcal{X}}$; let
$\mu_{\max}\stackrel{{\scriptstyle\text{def}}}{{=}}\max_{x\in{\mathcal{X}}}\mu_{x}$.
Let $N\geq\mathsf{sc}(\gamma^{2}/2,\delta,{\mathcal{M}}^{\mathrm{max}}_{K})$
(cf. Defn. 6) and suppose $C$ is the maximizer of MP 4 with
$\beta=\gamma^{2}/2$, then with probability at least $1-\delta$, we have
$\|C\|_{1}\geq 1/\mu_{\max}$.

###### Proof of Proposition 15.

Based on the condition on $N$ and using $\hat{M}=\mathbf{0}_{\mathcal{X}}$ in
Defn. 6 with probability at least $1-\delta$ it holds for every
$M\in{\mathcal{M}}^{\mathrm{max}}_{K}$:

$\displaystyle\left|\|M\|_{\mu}^{2}-\|M\|_{S}^{2}\right|\leq\gamma^{2}/2.$
(11)

As in the proof of Proposition 14, let $C^{\mu}_{x}=\mu_{x}/\mu_{\max}$ and
notice that $C^{\mu}_{x}\in[0,1]$, $\|C^{\mu}\|_{1}=1/\mu_{\max}$ and
$\nu_{C^{\mu}}=\mu$. Using Eq. (11), for any
$M\in{\mathcal{V}}(\mathbf{0}_{\mathcal{X}},\beta,S;{\mathcal{M}}^{\mathrm{max}}_{K})$,
we have that $\|M\|_{\mu}^{2}\leq\beta+\gamma^{2}/2\leq\gamma^{2}$. Finally,
using the fact that $\mathbb{E}_{x\sim\mu}[M_{x}]\leq\sqrt{\|M\|_{\mu}^{2}}$,
we get that $C^{\mu}$ is feasible and the result follows. ∎

The key to proving Theorem 11 is the following proposition, whose proof
contains the main technical innovation. The derivation of the main theorem
given the proposition is in the Appendix.

######  Proposition 16.

For the class ${\mathcal{M}}^{\mathrm{max}}_{K}$, for any distribution $\nu$
over ${\mathcal{X}}$, $\beta>0$ and $S\in{\mathcal{X}}^{N}$, the following
holds: for
${\mathcal{V}}={\mathcal{V}}(\mathbf{0}_{\mathcal{X}},\beta,S;{\mathcal{M}}^{\mathrm{max}}_{K})$,

$\sup_{M\in{\mathcal{V}}}\ell(\nu,M,\mathbf{0}_{\mathcal{X}})\leq\frac{\pi
K}{2}\sup_{M\in{\mathcal{V}}}\mathbb{E}_{x\sim\nu}[M_{x}].$

###### Proof of Proposition 16.

For succinctness let
${\mathcal{V}}_{0}={\mathcal{V}}(\mathbf{0}_{\mathcal{X}},\beta;S,{\mathcal{M}}^{\mathrm{max}}_{K})$.
Let $\nu$ be a an arbitrary distribution over ${\mathcal{X}}$ and since we
know that ${\mathcal{V}}_{0}$ is closed and bounded, we know that a matrix
$M\in{\mathcal{V}}_{0}$ exists which achieves the value of
$\sup_{M\in{\mathcal{V}}_{0}}\ell(\nu,M,\mathbf{0}_{\mathcal{X}})$. We will
use the probabilistic method to show that there exists
$\tilde{M}\in{\mathcal{V}}_{0}$ such that
$\mathbb{E}_{x\sim\nu}[\tilde{M}_{x}]\geq\frac{2}{\pi
K}\ell(\nu,M,\mathbf{0}_{\mathcal{X}})$.

Since $M\in{\mathcal{M}}^{\mathrm{max}}_{K}$, there exist $U,V$ such that
$M=UV^{\top}$ and that $\|U\|_{2,\infty}\cdot\|V\|_{2,\infty}\leq K$. Denote
by $u_{i},v_{j}$ respectively the $i$-th and $j$-th rows of $U$ and $V$.
Suppose $u_{i},v_{j}\in\mathbb{R}^{D}$ for some finite $D$, we know that we
can always choose $D\leq\min\\{m,n\\}$. Let $w$ be a random vector drawn
uniformly from the unit sphere in $\mathbb{R}^{D}$. For any vector
$v\in\mathbb{R}^{D}$, let
$\tilde{v}\stackrel{{\scriptstyle\text{def}}}{{=}}\text{
}\mathrm{sign}(v^{\top}w)v$ and obtain the matrices $\tilde{U},\tilde{V}$ from
$U$ and $V$ by applying this transformation to all the rows of $U$ and $V$.

We define $\tilde{M}=\tilde{U}\tilde{V}^{\top}$. Note that as the only
difference between $U$ and $\tilde{U}$ (resp. $V$ and $\tilde{V}$) is sign
changes for some subset of the rows, we have
$\|\tilde{U}\|_{2,\infty}=\|U\|_{2,\infty}$ (resp.
$\|\tilde{V}\|_{2,\infty}=\|V\|_{2,\infty}$). Also for any $i,j$,
$|u_{i}^{\top}v_{j}|=|\tilde{u}_{i}^{\top}\tilde{v}_{j}|$, thus the entries of
$M$ and $\tilde{M}$ may only differ in sign. Thus,
$\tilde{M}\in{\mathcal{M}}^{\mathrm{max}}_{K}$ irrespective of the random
choice of the vector $w$. In order to complete the proof by the probabilistic
method, it suffices to show that,

$\displaystyle\mathbb{E}_{w}\left[\mathbb{E}_{x\sim\nu}[\tilde{M_{x}}]\right]$
$\displaystyle\geq\frac{2}{\pi K}\ell(\nu,M,\mathbf{0}_{\mathcal{X}}).$ (12)

Let $\theta(u,v)$ denote the angle between any two vectors
$u,v\in\mathbb{R}^{D}$. For a vector $w$ drawn at random from the unit sphere
it can be verified that $\operatorname{\mathbb{P}}[\text{
}\mathrm{sign}(\tilde{u}^{\top}\tilde{v})\neq\text{
}\mathrm{sign}(u^{\top}v)]=\frac{\theta(u,v)}{\pi}$. We will show:

$\displaystyle\mathbb{E}_{w}[\tilde{u}^{\top}\tilde{v}]$
$\displaystyle\geq\frac{2(u^{\top}v)^{2}}{\pi\|u\|\|v\|}.$ (13)

It suffices to show the above for the case when $u^{\top}v\geq 0$ as flipping
the sign of $v$ affects neither $\tilde{v}$ nor $(u^{\top}v)^{2}$. Note that
in this case $\theta(u,v)\in[-\pi/2,\pi/2]$. To prove Eq. (13), we use:

######  Lemma 17.

For any $\theta\in[-\pi/2,\pi/2]$, we have that, $1-2\theta/\pi\geq
2\cos(\theta)/\pi$.

###### Proof of Lemma 17.

Let $f:[-\pi/2,\pi/2]\rightarrow\mathbb{R}$, where
$f(\theta)=1-2\theta/\pi-2\cos\theta/\pi$. Note that since $|\sin\theta|\leq
1$ for all $\theta$, $f^{\prime}(\theta)\leq 0$, so $f$ is decreasing and
$f(\pi/2)=0$. ∎

Now, using the fact that $\cos(\theta(u,v))=u^{\top}v/(\|u\|\|v\|)$, we get,

$\displaystyle\mathbb{E}_{w}[\tilde{u}^{\top}\tilde{v}]$
$\displaystyle=u^{\top}v\cdot\left(1-2\operatorname{\mathbb{P}}[\text{
}\mathrm{sign}(\tilde{u}^{\top}\tilde{v})\neq\text{
}\mathrm{sign}(u^{\top}v)]\right)$
$\displaystyle=u^{\top}v\cdot\left(1-\frac{2\theta(u,v)}{\pi}\right)\geq
u^{\top}v\cdot\frac{2\cos(\theta(u,v))}{\pi}=\frac{2(u^{\top}v)^{2}}{\pi\|u\|\|v\|}.$

In the last step, we used Lemma 17. For any fixed $x=(i,j)\in{\mathcal{X}}$,
we have that,

$\mathbb{E}_{w}[\tilde{M}_{x}]=\mathbb{E}_{w}[\tilde{u_{i}}^{\top}\tilde{v_{i}}]\geq\frac{2(u_{i}^{\top}v)^{2}}{\pi\|u_{i}\|\|v_{j}\|}\geq\frac{2M_{x}^{2}}{\pi
K}.$

The last inequality follows from the fact that
$\|M\|_{\max}=\|U\|_{2,\infty}\cdot\|V\|_{2,\infty}\leq K$ and that
$M_{x}=u_{i}^{\top}v_{j}$. Taking expectation with respect to $\nu$ and
applying Fubini’s theorem establishes (12). ∎

###### Proof of Theorem 11.

Apart from the use of Proposition 16, the proof is essentially the same as
that of Theorem 10. We bound the probability of the three undesirable events
by $\delta/3$ each. First, $\mathsf{FullComp}$ succeeds with probability at
least $1-\delta/3$.

Second, provided
$N\geq\mathsf{sc}(\varepsilon^{2}/(8\pi^{2}K^{2}),\delta/3,{\mathcal{M}}^{\mathrm{max}}_{K})$,
for $\hat{M}$ output by $\mathsf{FullComp}$, using Defn. 6 it must hold for
each $M\in{\mathcal{M}}^{\mathrm{max}}_{K}$ that with probability at least
$1-\delta/3$,

$\displaystyle\left|\ell(\mu,M,\hat{M})-\ell(S,M,\hat{M})\right|$
$\displaystyle\leq\frac{\varepsilon^{2}}{8\pi^{2}K^{2}}$ (14)

In particular, when $\beta=\varepsilon^{2}/(8\pi^{2}K^{2})$, this means that
(assuming $\mathsf{FullComp}$ has not failed),

$\displaystyle\|(M^{\star}-\hat{M})/{2}\|^{2}_{S}\leq\frac{1}{4}\|M^{\star}-M\|_{\mu}^{2}+\frac{\epsilon^{2}}{32\pi^{2}K^{2}}\leq\frac{\varepsilon^{2}}{16\pi^{2}K^{2}}+\frac{\varepsilon^{2}}{32\pi^{2}K^{2}}\leq\beta.$

As a result, and using the convexity of ${\mathcal{M}}^{\mathrm{max}}_{K}$
(cf. Lemma 5),
$(M^{\star}-\hat{M})/2\in{\mathcal{V}}(\mathbf{0}_{\mathcal{X}},\beta,S;{\mathcal{M}}^{\mathrm{max}}_{K})$.

For
$N\geq\mathsf{sc}(\varepsilon^{2}/(8\pi^{2}K^{2})=\gamma^{2}/2,\delta/3,{\mathcal{M}}^{\mathrm{max}}_{K})$,
Proposition 15 guarantees with probability at least $1-\delta/3$, that the
output of MP 4 satisfies $\|C\|_{1}\geq 1/\mu_{\max}$.

Finally, since
$(M^{\star}-\hat{M})/2\in{\mathcal{V}}(\mathbf{0}_{\mathcal{X}},\beta,S;{\mathcal{M}}^{\mathrm{max}}_{K})$,
we have:

$\displaystyle\ell(\nu_{C},M^{\star},\hat{M})$
$\displaystyle\leq\sup_{M\in{\mathcal{V}}(\mathbf{0}_{\mathcal{X}},\beta,S;{\mathcal{M}}^{\mathrm{max}}_{K})}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\ell(\nu_{C},M,\mathbf{0}_{\mathcal{X}})\leq\frac{\pi
K}{2}\cdot\\!\\!\\!\\!\\!\sup_{M\in{\mathcal{V}}(\mathbf{0}_{\mathcal{X}},\beta,S;{\mathcal{M}}^{\mathrm{max}}_{K})}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\mathbb{E}_{x\sim\nu_{C}}[M_{x}]\leq\frac{\pi
K}{2}\cdot\gamma.$

In the penultimate step we used Proposition 16 and in the last step we used
the fact that $C$ is feasible for MP 4. Substituting the value of $\gamma$
completes the proof. ∎

##  Appendix B Online Partial Matrix Completion

This section uses tools from online convex optimization, in particular its
application to games, to design an efficient gradient-based online algorithm
with provable regret guarantee to find a near optimal confidence matrix to the
partial matrix completion problem.

##### Organization.

The organization of this section is as follows: we begin with a short
background description on online convex optimization, its application to
matrix completion problems and games in Section B.1, explain the main
motivations and intuitions of our online algorithm in Section B.2, introduce
the general protocol of online partial matrix completion in Section B.3 and
the design of objective functions in Section B.4. We formally give the
algorithm specification and the regret guarantee in Section B.5. Finally, we
show the implication on statistical guarantee in Section B.6.

###  B.1 Preliminaries

##### Online convex optimization.

In online convex optimization, a player iteratively chooses a point
$x_{t}\in\mathcal{K}\subseteq\mathbb{R}^{d}$ at time step $t$, and receives a
convex loss function $h_{t}$, to which the player incurs loss $h_{t}(x_{t})$.
The performance of the player is measured by _regret_ , the total excess loss
incurred by the player’s decisions than the best single decision
$x^{*}\in\mathcal{K}$. Formally, regret is given by the following definition

$\displaystyle\mbox{{Regret}}_{T}\stackrel{{\scriptstyle\text{def}}}{{=}}\sum_{t=1}^{T}h_{t}(x_{t})-\min_{x\in\mathcal{K}}\sum_{t=1}^{T}h_{t}(x).$

The goal is to design algorithms that achieve sublinear regret, which means
that with time the algorithm’s decisions converge in performance to the best
single decision in hindsight. For a survey of methods and techniques, see
[Hazan et al., 2016].

##### Online matrix prediction.

Online convex optimization has been proved useful in solving matrix prediction
problems. In particular, Hazan et al. [2012b] give an efficient first-order
online algorithm that iteratively produces matrices $M_{t}$ of low complexity
that for any sequence of adversarially chosen convex, Lipschitz loss functions
and indices $(i_{t},j_{t})$’s, the online matrix prediction algorithm gives a
regret bound of $\tilde{\mathcal{O}}(\sqrt{(m+n)T})$. The linear dependence on
the matrix dimension $m,n$ translates to the convergence in performance to the
best complexity-constrained matrix in hindsight after seeing only square root
of the total number of entries.

##### Games and regret.

One important branch of theory developed in online convex optimization is its
connection to finding the equilibrium point in two-player games, first
discovered by Freund and Schapire [1999]. In this framework, two players
iteratively pick decisions $x_{t}\in{\mathcal{X}},y_{t}\in{\mathcal{Y}}$ at
time step $t$, after which a (possibly adversarially) chosen loss function
$h_{t}(x,y)$ is revealed, where $h_{t}$ is convex in $x$ and concave in $y$.
Player 1 incurs loss $h_{t}(x_{t},y_{t})$ and player 2 gains reward
$h_{t}(x_{t},y_{t})$. The objective for the players is to produce a sequence
of decisions $\\{x_{t}\\}_{t=1}^{T},\\{y_{t}\\}_{t=1}^{T}$ that converges in
performance to the best single $x^{*},y^{*}\in\mathcal{K}$ in hindsight. The
regret for the two players are given by

$\displaystyle\mbox{{Regret}}_{T}(\texttt{player1})$
$\displaystyle=\sum_{t=1}^{T}h_{t}(x_{t},y_{t})-\min_{x\in{\mathcal{X}}}\sum_{t=1}^{T}h_{t}(x,y_{t}),$
$\displaystyle\mbox{{Regret}}_{T}(\texttt{player2})$
$\displaystyle=\max_{y\in{\mathcal{Y}}}\sum_{t=1}^{T}h_{t}(x_{t},y)-\sum_{t=1}^{T}h_{t}(x_{t},y_{t}).$

Under distributional assumption of the function $h_{t}$’s, namely if $h_{t}$’s
are bilinear, i.i.d. stochastically chosen according to some distribution,
then the following holds:

$\displaystyle\ \ \ \ \
\left|\mathbb{E}\left[\sum_{t=1}^{T}h_{t}(x_{t},y_{t})\right]-\min_{x\in{\mathcal{X}}}\max_{y\in{\mathcal{Y}}}\mathbb{E}\left[\sum_{t=1}^{T}h_{t}(x,y)\right]\right|$
$\displaystyle\leq\max\\{\mbox{{Regret}}_{T}(\texttt{player1}),\mbox{{Regret}}_{T}(\texttt{player2})\\}.$

For such reasons, we define a notion of game regret, denoted $\mbox{{Game-
Regret}}_{T}$, to be the maximum of the regret incurred by the two players.
Sublinear game regret can be used to compute the game equilibrium [Freund and
Schapire, 1999].

###  B.2 Motivations

Two important aspects lie at heart of the general motivation for considering
partial matrix completion in an online setting. First, in many applications,
the observation pattern is more general than a fixed distribution. It can be a
changing distribution or be comprised of adversarial observations. Second, our
online algorithm incrementally updates the solution via iterative gradient
methods, which is more efficient than the offline methods.

####  B.2.1 Game theoretic nature of partial matrix completion

With the preliminary introduction on saddle-point problems, we will describe
their connection to our problem of interest - finding the optimal confidence
matrix $C$ in partial matrix completion problems. Recall that we want to find
$C$ that (1) has maximal coverage under the constraint that (2) the deviation
between any two possible completions $M^{1}$ and $M^{2}$ with respect to $C$
is small.

With this objective in mind, we can think of the following two-player game.
Player 1 plays a confidence matrix $C$, player 2 plays a pair of possible
matrix completions $(M^{1},M^{2})$. The goal of player 1 is to (a) maximize
the coverage of $C$ and (b) minimize the deviation between $M^{1}$ and $M^{2}$
with respect to $C$. The goal of player 2 is to maximize the deviation between
$M^{1}$ and $M^{2}$ with respect to $C$. The equilibrium point in this problem
is exactly given by a confidence matrix that simultaneously has high coverage
and with respect to which the deviation between any two possible completions
$M^{1}$ and $M^{2}$ is small. The game theoretic nature of the partial matrix
completion problem leads us to consider designing a provably low-game-regret
online two-player algorithm.

####  B.2.2 Soft constraints

It is worth noting that this formulation differs from the MP4 and MP4 in the
absence of hard constraints. In particular, instead of imposing an
$\varepsilon$-margin on the deviation between any two possible completions
with respect to the confidence matrix, we formulate this objective in the
objective functions for player 1 and 2. This allows us to perform fast
gradient-based algorithm, which will be detailed soon in the Algorithm 3. The
set of possible matrix completions is formally given by the version space,
i.e. the set of matrices of low complexity, with bounded norms, and deviate
little from the observed data. To avoid computationally expensive projections,
Algorithm 3 further removed the constraint on deviation from observations and
replaced with a soft constraint that penalizes the completion’s deviation from
observations. Similar techniques have been seen in [Mahdavi et al., 2012].

###  B.3 Online PMC General Protocol

With the motivations explained, we are ready to introduce the general protocol
of online matrix completion and then give the details of our objective
functions. In the online partial matrix completion problem, the algorithm acts
for two players and follows the following protocol. At time step $t$,

  1. 1.

Player 1 picks a confidence matrix from a constraint set
$C_{t}\in{\mathcal{C}}$, where ${\mathcal{C}}$ is defined below. Player 2
picks two matrices $M_{t}^{1},M_{t}^{2}\in{\mathcal{M}}^{\mathrm{max}}_{K}$.

  2. 2.

An adversary reveals a tuple $(x_{t},o_{t})\in{\mathcal{X}}\times[-1,1]$.
Based on this tuple, a function is constructed, denoted
$h_{t}(C,M^{1},M^{2})$, which is concave in $C$ and convex in $M^{1},M^{2}$.

  3. 3.

Player 1 receives reward $h_{t}(C_{t},M_{t}^{1},M_{t}^{2})$. Player 2 incurs
loss $h_{t}(C_{t},M_{t}^{1},M_{t}^{2})$.

The convex-concave function $h_{t}$, detailed in Section B.4, measures the
coverage of $C$, the deviation between $M^{1}$ and $M^{2}$ with respect to
$C$, and the deviation of $M^{1},M^{2}$ from the observations.

Note that in previous sections, we took ${\mathcal{C}}=[0,1]^{{\mathcal{X}}}$.
In this section we consider a more general case, and consider two choices for
${\mathcal{C}}$. The first choice is the unit simplex
$\Delta_{{\mathcal{X}}}\subset\mathbb{R}^{{\mathcal{X}}}$. This is natural as
it induces a probability distribution of completion confidence over the
entries. The second choice is the scaled hypercube
${\mathcal{C}}=\left[0,\frac{1}{(m+n)^{3/2}}\right]^{{\mathcal{X}}}$. The
scaling is for the mere purpose for analysis and representation of theorems.
In B.6, we will show a reduction from the online result to the offline
guarantee.

###  B.4 Designing Convex-Concave Objectives

The previous sections motivate the design of the convex-concave function
$h_{t}$, where $\alpha,\theta>0$ are positive parameters:

$\displaystyle h_{t}(C,M^{1},M^{2})$ $\displaystyle=H(C)-\alpha
G(C,M^{1},M^{2})+\alpha\theta f_{t}(M^{1},M^{2}),$

where the three components of $h_{t}$ are:

  1. 1.

$H(\cdot)$ is a measure of the effective support size of $C$, which can be
taken to be either:

    1. (a)

entropy, i.e. $H(C)=-\sum_{x\in{\mathcal{X}}}C_{x}\log(C_{x})$ defined over
the simplex ${\mathcal{C}}=\Delta_{{\mathcal{X}}}$, or

    2. (b)

$H(C)=\|C\|_{1}$, defined over the scaled hypercube
${\mathcal{C}}=\left[0,\frac{1}{(m+n)^{3/2}}\right]^{{\mathcal{X}}}$.

  2. 2.

$G(C,M^{1},M^{2})\stackrel{{\scriptstyle\text{def}}}{{=}}\sum_{x\in{\mathcal{X}}}C_{x}(M_{x}^{1}-M_{x}^{2})$,
a linear relaxation of
$\sum_{x\in{\mathcal{X}}}C_{x}(M_{x}^{1}-M_{x}^{2})^{2}$ (see Theorem 24 and
Corollary 25 in Appendix C), which measures the deviation of two completions
$M^{1},M^{2}$ with respect to $C$.

  3. 3.

$f_{t}(M^{1},M^{2})\stackrel{{\scriptstyle\text{def}}}{{=}}\left[(M^{1}_{x_{t}}-o_{t})^{2}+(M^{2}_{x_{t}}-o_{t})^{2}\right]$,
which measures the deviation of the two completions from observation made at
time $t$. This serves as a soft constraint where $M^{1},M^{2}$ minimizing
$h_{t}$ will have values close to $o_{t}$ at entry $x_{t}$.

With slight abuse of notation, we denote
$M_{t}\stackrel{{\scriptstyle\text{def}}}{{=}}(M_{t}^{1},M_{t}^{2})$ in the
following sections for convenience and presentation clarity. Note that $h_{t}$
is concave in $C$ and convex in $M^{1},M^{2}$. Similar to the previous
section, remark that we can, albeit suffering a constant in all performance
metrics, consider that all observations $o_{t}$ are zero and maintain a single
matrix in place of $M_{t}^{1},M_{t}^{2}$ that measures the radius of the
version space.

###  B.5 Online Dual Descent (ODD): online gradient-based algorithm for
partial matrix completion

Formally, we propose Online Dual Descent (ODD, Algorithm 3):

Algorithm 3 Online Dual Descent for Partial Matrix Completion (ODD)

1: Input: Gradient-based online coverage and matrix update functions
${\mathcal{A}}_{C},{\mathcal{A}}_{M}$, parameters $\eta>0$, $\alpha,\theta>0$.

2: Initialize
$C_{1},M_{1}\leftarrow{\mathcal{A}}_{C}(\emptyset),{\mathcal{A}}_{M}(\emptyset)$.

3: for $t=1,2,...,T$ do

4: Player 1 plays $C_{t}$; player 2 plays $M_{t}$.

5: Adversary draws tuple $(x_{t},o_{t})$ and constructs function $h_{t}$ with
parameters $\alpha,\theta$.

6: Player 1 receives reward $h_{t}(C_{t},M_{t})$, player 2 incurs loss
$h_{t}(C_{t},M_{t})$.

7: Player 1 updates $C_{t+1}\leftarrow{\mathcal{A}}_{C}(C_{t},M_{t})$. Player
2 updates $M_{t+1}\leftarrow{\mathcal{A}}_{M}(C_{t},M_{t},(x_{t},o_{t}))$.

8: end for

9: output:s $\bar{C}=\frac{1}{T}\sum_{t=1}^{T}C_{t}$.

Here,
${\mathcal{A}}_{C}:{\mathcal{C}}\times({\mathcal{M}}^{\mathrm{max}}_{K})^{2}\rightarrow{\mathcal{C}}$
and
${\mathcal{A}}_{M}:{\mathcal{C}}\times({\mathcal{M}}^{\mathrm{max}}_{K})^{2}\times({\mathcal{X}},[-1,1])\rightarrow({\mathcal{M}}^{\mathrm{max}}_{K})^{2}.$
The detailed analysis of the algorithm will be deferred to the following
section and Appendix C, but we will first state its regret guarantee:

######  Corollary 18.

For any sequence of $\\{(x_{t},o_{t})\\}_{t=1}^{T}$, Algorithm 3 gives the
following regret guarantee on the obtained set
$\\{(C_{t},M_{t})\\}_{t=1}^{T}$, such that for settings 1a, 1b,

$\displaystyle\mbox{{Game-Regret}}_{T}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\max\left\\{\mbox{{Regret}}_{T}^{{\mathcal{A}}_{C}},\alpha\cdot\mbox{{Regret}}_{T}^{{\mathcal{A}}_{M}}\right\\}\leq\tilde{O}(K\alpha\theta\sqrt{(m+n)T}).$

We henceforth denote the upper bound on the regret by

$\mbox{{Game-Regret}}_{T}\leq B_{T}.$

The main theorem regarding the game regret of Algorithm 3 is implied by the
existence of low regret guarantee for gradient-based subroutines
${\mathcal{A}}_{C},{\mathcal{A}}_{M}$, outlined in the following theorems. The
details of the subroutines and analysis are deferred to Appendix C.

######  Theorem 19.

Denote at every time step $t$, consider the concave reward function
$r_{t}(C)\stackrel{{\scriptstyle\text{def}}}{{=}}H(C)-\alpha G(C,M_{t})$.
There exists a sub-routine gradient-based update ${\mathcal{A}}_{C}$ (see Alg.
4 for an example) with the following regret guarantee w.r.t. $r_{t}$:

  1. 1.

For setting 1a,

$\displaystyle\mbox{{Regret}}_{T}^{{\mathcal{A}}_{C}}\stackrel{{\scriptstyle\text{def}}}{{=}}\max_{C\in{\mathcal{C}}}\sum_{t=1}^{T}r_{t}(C)-\sum_{t=1}^{T}r_{t}(C_{t})\leq
O(\alpha\sqrt{\log(mn)T})=\tilde{O}(\alpha\sqrt{T}).$

  2. 2.

For setting 1b,

$\displaystyle\mbox{{Regret}}_{T}^{{\mathcal{A}}_{C}}\stackrel{{\scriptstyle\text{def}}}{{=}}\max_{C\in{\mathcal{C}}}\sum_{t=1}^{T}r_{t}(C)-\sum_{t=1}^{T}r_{t}(C_{t})\leq
O(\alpha\sqrt{(m+n)T}).$

######  Theorem 20 (adapted from Hazan et al. [2012b]).

Denote at every time step $t$, consider the concave reward function
$\gamma_{t}(M)\stackrel{{\scriptstyle\text{def}}}{{=}}G(C_{t},M)-\theta
f_{t}(M)$. There exists a sub-routine gradient-based update
${\mathcal{A}}_{M}$ (see Alg. 5 for an example) such that, under either
setting 1a or 1b, the following regret guarantee w.r.t. $\gamma_{t}$ holds:

$\displaystyle\mbox{{Regret}}_{T}^{{\mathcal{A}}_{M}}\stackrel{{\scriptstyle\text{def}}}{{=}}\max_{M\in{\mathcal{M}}^{\mathrm{max}}_{K}\times{\mathcal{M}}^{\mathrm{max}}_{K}}\sum_{t=1}^{T}\gamma_{t}(M)-\sum_{t=1}^{T}\gamma_{t}(M_{t})\leq
O(K\theta\sqrt{(m+n)T}).$

###  B.6 Offline implications

In this section we show that how the regret guarantee we obtained in the
online setting translates to an offline performance guarantee on $C$. The
offline implications hold under the following assumptions of the revealed
entries:

######  Assumption 1.

At each time step $t$, the index $x_{t}=(i_{t},j_{t})$ is sampled according to
some unknown sampling distribution $\mu$, and the observation
$o_{t}=M^{\star}(i_{t},j_{t})$, where
$M^{\star}\in{\mathcal{M}}^{\mathrm{max}}_{K}$ is the ground truth matrix.

Consider the following empirical and general version spaces:

$\displaystyle{\mathcal{V}}_{T,\delta}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\left\\{M\in{\mathcal{M}}^{\mathrm{max}}_{K}\mid\frac{1}{T}\sum_{t=1}^{T}(M_{x_{t}}-o_{t})^{2}\leq\delta\right\\},$
$\displaystyle{\mathcal{V}}_{\delta}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\left\\{M\in{\mathcal{M}}^{\mathrm{max}}_{K}\mid\underset{(x,o)\sim\mathcal{D}}{\mathbb{E}}[(M_{x}-o)^{2}]\leq\delta\right\\}.$

######  Lemma 21.

After $T$ iterations, and assume that for some $\delta>0$,

$\frac{1}{\theta}\left(2D+\frac{\mbox{{Regret}}_{T}^{{\mathcal{A}}_{M}}}{T}\right)\leq\frac{\delta^{2/3}}{2},$

with $D=1$ in setting 1a, and $D=\sqrt{m+n}$ in setting 1b. The following
properties hold on the obtained
$\bar{C}\stackrel{{\scriptstyle\text{def}}}{{=}}\frac{1}{T}\sum_{t=1}^{T}C_{t}$
returned by Algorithm 3: with probability $\geq
1-\exp\left(-\frac{\delta^{4/3}T}{512}\right)$,

$\displaystyle H(\bar{C})-\max_{M\in{\mathcal{V}}_{T,\delta}^{2}}\alpha\cdot
G(\bar{C},M)\geq\max_{C\in{\mathcal{C}}}\min_{M\in{\mathcal{V}}_{\delta^{2/3}}^{2}}\left\\{H(C)-\alpha\cdot
G(C,M)\right\\}-2\alpha\theta\delta-\frac{B_{T}}{T}.$

Lemma 21 implies the following guarantee.

######  Theorem 22.

Suppose the underlying sampling distribution is $\mu$. Let
$C_{\mu}\in{\mathcal{C}}$ be its corresponding confidence matrix. In
particular, for setting 1a, $C_{\mu}=\mu$, i.e.
$(C_{\mu})_{ij}=\mathbb{P}_{\mu}((i,j)\text{ is sampled})$; for setting 1b,
$C_{\mu}$ satisfies that $C_{\mu}/\|C_{\mu}\|_{1}=\mu$. Then, for any
$\delta>0$, Algorithm 3 run with $\alpha=O(\delta^{-1/6})$ returns a $\bar{C}$
that guarantees the following bounds: with probability at least
$1-c_{1}\exp(-c_{2}\delta^{2}T)$ for some universal constants $c_{1},c_{2}>0$,

  1. 1.

For setting 1a, take $\theta=O(\delta^{-2/3})$, after
$T=\tilde{O}(\delta^{-2}K^{2}(m+n))$ iterations,

    1. (a)

$H(\bar{C})\geq H(C_{\mu})-O(\delta^{1/6})$.

    2. (b)

$\underset{M^{1},M^{2}\in{\mathcal{V}}_{\delta}}{\max}\
G(\bar{C},M^{1},M^{2})\leq O(\delta^{1/6}\log(mn))$.

  2. 2.

For setting 1b, take $\theta=O(\delta^{-2/3}\sqrt{m+n})$, after
$T=\tilde{O}(\delta^{-2}K^{2}(m+n))$ iterations,

    1. (a)

$\|\bar{C}\|_{1}\geq\|C_{\mu}\|_{1}-O(\delta^{1/6}\sqrt{m+n})$.

    2. (b)

$\underset{M^{1},M^{2}\in{\mathcal{V}}_{\delta}}{\max}G(\bar{C},M^{1},M^{2})\leq
O(\delta^{1/4}\sqrt{m+n})$.

######  Remark 23.

We explain the implication of the above theorem. Suppose the sampling
distribution is supported uniformly across a constant fraction $0<c\leq 1$ of
the entire matrix. This implies that (1) the obtained confidence matrix
$\bar{C}$ has a coverage lower bounded by $1-\delta^{1/6}$ fraction of the
true distribution, and (2) $\bar{C}$ induces a weighted maximal distance on
the version space ${\mathcal{V}}_{\delta}$:

$\displaystyle\max_{M^{1},M^{2}\in{\mathcal{V}}_{\delta}}\left\\{\frac{1}{\|\bar{C}\|_{1}}\sum_{i\in[m],j\in[n]}\bar{C}_{ij}(M_{ij}^{1}-M_{ij}^{2})^{2}\right\\}\leq
O(\delta^{1/6}).$

Also see Corollary 4 for this example.

##  Appendix C Supporting Proofs for Appendix B

###  C.1 Linear Relaxation

This section follows similarly to that of Proposition 16.

######  Theorem 24.

Consider the following two functions defined on ${\mathcal{C}}$:

$\displaystyle\tilde{g}(C)\stackrel{{\scriptstyle\text{def}}}{{=}}\sup_{M\in{\mathcal{V}}_{0}}\sum_{x\in{\mathcal{X}}}C_{x}M_{x}^{2},\
\
g(C)\stackrel{{\scriptstyle\text{def}}}{{=}}\sup_{M\in{\mathcal{V}}_{0}}\sum_{x\in{\mathcal{X}}}C_{x}M_{x}.$

Assume that ${\mathcal{V}}_{0}=\mathcal{M}_{K}^{\max}\cap S$, where $S$ is a
constraint set that contains $0$ that is closed under the operation of
negating any subset of entries. Then $g(\cdot)$ is non-negative and $\forall
C\in{\mathcal{C}}$, there holds

$\displaystyle\tilde{g}(C)\leq\frac{\pi K}{2}g(C).$

###### Proof.

That $g(\cdot)$ is non-negative follows from the assumption that
$0\in{\mathcal{V}}_{0}$. It suffices to show the inequality for
${\mathcal{C}}=\Delta_{{\mathcal{X}}}$, since $\forall
C\in\left[0,\frac{1}{(m+n)^{3/2}}\right]^{{\mathcal{X}}}$, we can consider
$C^{\prime}=\frac{C}{\|C\|_{1}}\in\Delta_{{\mathcal{X}}}$, and
$\tilde{g}(C^{\prime})\leq\frac{\pi K}{2}g(C^{\prime})$ implies
$\tilde{g}(C)\leq\frac{\pi K}{2}g(C)$.

By compactness of ${\mathcal{V}}_{0}$, $\exists M\in{\mathcal{V}}_{0}$ such
that the value of $\tilde{g}(C)$ is achieved. Moreover, since
${\mathcal{C}}=\Delta_{{\mathcal{X}}}$, $C$ defines a probability distribution
on ${\mathcal{X}}$. Then, it suffices to show that
$\exists\tilde{M}\in{\mathcal{V}}_{0}$ such that

$\displaystyle\sum_{x\in{\mathcal{X}}}C_{x}M_{x}^{2}=\mathbb{E}_{C}[M_{x}^{2}]\leq\frac{\pi
K}{2}\mathbb{E}_{C}[\tilde{M}_{x}]\leq\frac{\pi
K}{2}\sum_{x\in{\mathcal{X}}}C_{x}\tilde{M}_{x}.$

We start the construction of $\tilde{M}$. By assumption that
${\mathcal{V}}\subseteq{\mathcal{M}}^{\mathrm{max}}_{K}$, $\exists
U\in\mathbb{R}^{m\times d},V\in\mathbb{R}^{n\times d}$, $d=\text{rank}(M)$
such that $M=UV^{T}$ and $\|U\|_{2,\infty}\|V\|_{2,\infty}\leq K$. Denote as
$u_{i},v_{j}$ the $i$-th and $j$-th row of $U,V$, respectively. Let $S^{d}$
denote the unit sphere in $\mathbb{R}^{d}$. Draw a random vector $w\sim S^{d}$
uniformly at random and consider its inner product with each of the
$u_{i},v_{j}$’s. Define $\tilde{U}\in\mathbb{R}^{m\times
d},\tilde{V}\in\mathbb{R}^{n\times d}$ in the following way: with
$\tilde{u}_{i},\tilde{v}_{j}$ being the $i$-th and $j$-th row of
$\tilde{U},\tilde{V}$,

$\tilde{u}_{i}\stackrel{{\scriptstyle\text{def}}}{{=}}\text{sign}(w^{T}u_{i})u_{i},\
\
\tilde{v}_{j}\stackrel{{\scriptstyle\text{def}}}{{=}}\text{sign}(w^{T}v_{j})v_{j}.$

Note that $\|\tilde{U}\|_{2,\infty}=\|U\|_{2,\infty}$,
$\|\tilde{V}\|_{2,\infty}=\|V\|_{2,\infty}$. Therefore, together with the
assumption that $S$ is closed under negation over any subset of entries,
$\tilde{M}\stackrel{{\scriptstyle\text{def}}}{{=}}\tilde{U}\tilde{V}^{T}\in{\mathcal{V}}_{0}$.

Consider the hyperplane parametrized by $w$,
$P_{w}\stackrel{{\scriptstyle\text{def}}}{{=}}\\{x\in\mathbb{R}^{d}\mid
w^{T}x=0\\}$, then

$\displaystyle\mathbb{P}(\text{sign}(u_{i}^{T}v_{j})\neq\text{sign}(\tilde{u}_{i}^{T}\tilde{v}_{j}))$
$\displaystyle=\mathbb{P}(\text{sign}(w^{T}u_{i})\neq\text{sign}(w^{T}v_{j}))$
$\displaystyle=\mathbb{P}(u_{i},v_{j}\text{ are separated by
}P_{w})=\frac{\arccos\left(\frac{u_{i}^{T}v_{j}}{\|u_{i}\|_{2}\|v_{j}\|_{2}}\right)}{\pi}.$

Taking expectation over the distribution of the random vector $w$,

$\displaystyle\mathbb{E}_{w}[\tilde{u_{i}}^{T}\tilde{v_{j}}]=u_{i}^{T}v_{j}\left(1-\frac{2\arccos\left(\frac{u_{i}^{T}v_{j}}{\|u_{i}\|_{2}\|v_{j}\|_{2}}\right)}{\pi}\right)\geq\frac{2(u_{i}^{T}v_{j})^{2}}{\pi\|u_{i}\|_{2}\|v_{j}\|_{2}}\geq\frac{2(u_{i}^{T}v_{j})^{2}}{\pi
k}\Longleftrightarrow\mathbb{E}_{w}[\tilde{M}_{ij}]\geq\frac{2M_{ij}^{2}}{\pi
k}.$

Taking expectation over distribution $C$ and applying Fubini’s Theorem,

$\displaystyle\mathbb{E}_{C}[M_{x}^{2}]\leq\frac{\pi
K}{2}\mathbb{E}_{w}\mathbb{E}_{C}[\tilde{M}_{x}],$

which implies that there exists an instance of $\tilde{M}\in{\mathcal{V}}_{0}$
such that

$\displaystyle\sum_{x\in{\mathcal{X}}}C_{x}M_{x}^{2}\leq\frac{\pi
K}{2}\sum_{x\in{\mathcal{X}}}C_{x}\tilde{M}_{x}.$

∎

######  Corollary 25.

The following inequality holds:

$\displaystyle\sup_{M^{1},M^{2}\in{\mathcal{V}}}\sum_{x\in{\mathcal{X}}}C_{x}(M^{1}_{x}-M^{2}_{x})^{2}\leq\pi
K\sup_{M^{1},M^{2}\in{\mathcal{V}}}\sum_{x\in{\mathcal{X}}}C_{x}(M^{1}_{x}-M^{2}_{x}),$

for max-norm constrained, symmetric version space ${\mathcal{V}}$ around a
given matrix.

###### Proof.

By transformation to a version space ${\mathcal{V}}_{0}$ centered around the
zero matrix, if $M^{1},M^{2}\in{\mathcal{V}}$, then
$M\stackrel{{\scriptstyle\text{def}}}{{=}}\frac{M^{1}-M^{2}}{2}\in{\mathcal{V}}_{0}$,
where ${\mathcal{V}}_{0}={\mathcal{M}}^{\mathrm{max}}_{K}\cap S$ and $S$ is a
constraint set that is closed under negation under any subset of entries. The
result is subsumed by Theorem 24. ∎

###  C.2 Proof of regret guarantees

####  C.2.1 Proof of Theorem 19

######  Theorem 19.

Denote at every time step $t$, consider the concave reward function
$r_{t}(C)\stackrel{{\scriptstyle\text{def}}}{{=}}H(C)-\alpha G(C,M_{t})$.
There exists sub-routine gradient-based update ${\mathcal{A}}_{C}$ (see Alg. 4
for an example) with the following regret guarantee w.r.t. $r_{t}$:

  1. 1.

For setting 1a,

$\displaystyle\mbox{{Regret}}_{T}^{{\mathcal{A}}_{C}}\stackrel{{\scriptstyle\text{def}}}{{=}}\max_{C\in{\mathcal{C}}}\sum_{t=1}^{T}r_{t}(C)-\sum_{t=1}^{T}r_{t}(C_{t})\leq
O(\alpha\sqrt{\log(mn)T})=\tilde{O}(\alpha\sqrt{T}).$

  2. 2.

For setting 1b,

$\displaystyle\mbox{{Regret}}_{T}^{{\mathcal{A}}_{C}}\stackrel{{\scriptstyle\text{def}}}{{=}}\max_{C\in{\mathcal{C}}}\sum_{t=1}^{T}r_{t}(C)-\sum_{t=1}^{T}r_{t}(C_{t})\leq
O(\alpha\sqrt{(m+n)T}).$

###### Proof of Theorem 19.

We divide the proof into two parts, corresponding to two different choices of
$H(\cdot)$ and the corresponding ${\mathcal{C}}$. Both use online mirror
descent (OMD) step as updates. The analysis for the entropy case is slightly
more involved due to the gradient behavior at the boundary. We will begin with
outlining the algorithm:

######  Definition 26 (Bregman divergence).

Let $R:\Omega\rightarrow\mathbb{R}$ be a continuously-differentiable, strictly
convex function defined on a convex set $\Omega$. The _Bregman divergence_
associated with $R$ for $p,q\in\Omega$ is defined by

$\displaystyle B_{R}(p,q)=R(p)-R(q)-\langle\nabla\mkern-2.5muR(q),p-q\rangle.$

In particular, Bregman divergence measures the difference between $R(p)$ and
the first-order Taylor expansion of $R(p)$ around $q$.

Algorithm 4 ${\mathcal{A}}_{C}$

1: Input: previous $C_{t}$, completions $M_{t}=(M_{t}^{1},M_{t}^{2})$.

2: Require: step-size $\eta$, regularization function $R$.

3: if input is empty then

4: Set $(\hat{C}_{t+1})_{x}=e^{-1}$, $\forall x\in{\mathcal{X}}$ in setting
1a; set $\hat{C}_{t+1}=\mathbf{0}_{{\mathcal{X}}}$ in setting 1b.

5: else

6: Update $\hat{C}_{t+1}$ via
$\nabla\mkern-2.5muR(\mathbf{vec}(\hat{C}_{t+1}))=\nabla\mkern-2.5muR(\mathbf{vec}(C_{t}))+\eta\nabla\mkern-2.5mur_{t}(\mathbf{vec}(C_{t}))$.

7: end if

8: Obtain $C_{t+1}$ via Bregman projection:
$C_{t+1}=\underset{C\in{\mathcal{C}}^{\prime}}{\operatorname*{arg\,min}}\
B_{R}(\mathbf{vec}(C),\mathbf{vec}(\hat{C}_{t+1}))$.

9: Output $C_{t+1}$.

${\mathcal{C}}^{\prime}$ is taken to be

  1. 1.

For setting 1a,
${\mathcal{C}}^{\prime}=\Delta_{{\mathcal{X}}}^{\beta}\stackrel{{\scriptstyle\text{def}}}{{=}}\\{C\in\Delta_{{\mathcal{X}}}:\min_{x\in{\mathcal{X}}}\
C_{x}\geq e^{1-\beta}\\}$.

  2. 2.

For setting 1b,
${\mathcal{C}}^{\prime}={\mathcal{C}}=\left[0,\frac{1}{(m+n)^{3/2}}\right]^{{\mathcal{X}}}$,
and

The square root diameter $D_{R}$ of $R(\cdot)$ over
$\mathbf{vec}({\mathcal{C}}^{\prime})$ is given by

$\displaystyle
D_{R}\stackrel{{\scriptstyle\text{def}}}{{=}}\sqrt{\underset{{X,Y\in{\mathcal{C}}^{\prime}}}{\max}\\{R(\mathbf{vec}(X))-R(\mathbf{vec}(Y))\\}}.$

#####  $\ell_{1}$-norm and cube.

In setting 1b, take
$R:\mathbf{vec}({\mathcal{C}}^{\prime})\subset\mathbb{R}^{mn}\rightarrow\mathbb{R}$
given by $R(x)=\frac{1}{2}\|x\|_{2}^{2}$. Then
$D_{R}\leq\frac{1}{2\sqrt{m+n}}$. The regret guarantee for online mirror
descent also depends on the bound on local norms of the gradients. In
particular, the local norm at time $t$ is a function mapping from
$\mathbb{R}^{mn}$ to $\mathbb{R}_{++}$ given by

$\displaystyle\|x\|_{t}^{*}=\sqrt{x^{\top}\nabla\mkern-2.5mu^{2}R(\tilde{C})x},$

where $\tilde{C}$ is some convex combination of $C_{t}$ and $C_{t+1}$
satisfying

$\displaystyle R(\mathbf{vec}(C_{t}))$
$\displaystyle=R(\mathbf{vec}(C_{t+1}))+\nabla\mkern-2.5muR(\mathbf{vec}(C_{t+1}))^{\top}\mathbf{vec}(C_{t}-C_{t+1})$
$\displaystyle\ \ \ \ \
+\frac{1}{2}\mathbf{vec}(C_{t}-C_{t+1})^{\top}\nabla\mkern-2.5mu^{2}R(\mathbf{vec}(\tilde{C}))\mathbf{vec}(C_{t}-C_{t+1}).$

Note that $\forall x\in\mathbf{vec}({\mathcal{C}}^{\prime})$,
$\nabla\mkern-2.5mu^{2}R(x)=I_{mn}$, and thus

$\displaystyle
G_{R}^{2}\stackrel{{\scriptstyle\text{def}}}{{=}}{\|\mathbf{vec}(\nabla\mkern-2.5mur_{t}(C_{t}))\|_{t}^{*}}^{2}=\|\mathbf{vec}(\nabla\mkern-2.5mur_{t}(C_{t}))\|_{2}^{2}\leq(1+2\alpha)^{2}mn,$

where inequality follows from that
$(\nabla\mkern-2.5mur_{t}(C))_{x}=1-\alpha(M_{x}^{1}-M_{x}^{2})\leq
1+2\alpha$.

By standard Online Mirror Descent (OMD) analysis using the diameter and
gradient bounds, by taking $\eta=\frac{D_{R}}{G_{R}\sqrt{T}}$, we have the
regret bound of $r_{t}$’s over the cube:

$\displaystyle\max_{C\in{\mathcal{C}}^{\prime}}\sum_{t=1}^{T}r_{t}(C)-\sum_{t=1}^{T}r_{t}(C_{t})\leq
D_{R}G_{R}\sqrt{T}=O(\alpha\sqrt{(m+n)T}).$

##### Entropy and simplex.

In this setting, take $R(\mathbf{vec}(X))=-H(X)$, the negative entropy
function, $D_{R}^{2}=\log(mn)$. The proof will be divided into two parts: (1)
we first show low regret of ${\mathcal{A}}_{C}$ w.r.t.
$\Delta_{{\mathcal{X}}}^{\beta}$, then (2) we show that the best $C$ in
$\Delta_{{\mathcal{X}}}^{\beta}$ exhibits approximately the same performance
as the best $C$ in $\Delta_{{\mathcal{X}}}$.

Let $\gamma\stackrel{{\scriptstyle\text{def}}}{{=}}\beta+2\alpha$. For any
$C\in\Delta_{{\mathcal{X}}}^{\beta}$, the gradient of the reward function is
bounded by:

$\displaystyle\|\mathbf{vec}(\nabla\mkern-2.5mur_{t}(C))\|_{\infty}$
$\displaystyle\leq\|\nabla\mkern-2.5muH(C)\|_{\infty}+\alpha\|\nabla\mkern-2.5mu_{C}G(C,M_{t})\|_{\infty}$
$\Delta$-inequality $\displaystyle=\max_{x\in{\mathcal{X}}}|-1-\log
C_{x}|+\alpha\cdot\max_{x\in{\mathcal{X}}}|(M_{t}^{1}-M_{t}^{2})_{x}|$
definition of $\|\cdot\|_{\infty}$, $H$, $G$ $\displaystyle\leq
1+\log(e^{\beta-1})+2\alpha$ $C\in\Delta_{{\mathcal{X}}}^{\beta}$,
$M_{t}^{1},M_{t}^{2}\in{\mathcal{M}}^{\mathrm{max}}_{K}$
$\displaystyle\leq\gamma.$

Thus, for some convex combination $\tilde{C}$ of $C_{t}$ and $C_{t+1}$,

$\displaystyle
G_{R}^{2}={\|\mathbf{vec}(\nabla\mkern-2.5mur_{t}(C_{t}))\|_{t}^{*}}^{2}=\sum_{x\in{\mathcal{X}}}\tilde{C}_{x}(\nabla\mkern-2.5mur_{t}(C_{t}))_{x}^{2}\leq\|\mathbf{vec}(\nabla\mkern-2.5mur_{t}(C_{t}))\|_{\infty}^{2}\|\tilde{C}\|_{1}\leq\gamma^{2},$

where the last last inequality follows from
$\|\mathbf{vec}(\nabla\mkern-2.5mur_{t}(C))\|_{\infty}\leq\gamma$ and
$\|\tilde{C}\|_{1}=1$.

By standard Online Mirror Descent (OMD) analysis using the diameter and
gradient bounds, we have the regret bound of $r_{t}$’s over the constrained
unit simplex $\Delta_{{\mathcal{X}}}^{\beta}$ as the following:

$\displaystyle\max_{C\in\Delta_{\mathcal{X}}^{\beta}}\sum_{t=1}^{T}r_{t}(C)-\sum_{t=1}^{T}r_{t}(C_{t})\leq
D_{R}G_{R}\sqrt{T}=O(\alpha\sqrt{\log(mn)T})=\tilde{O}(\alpha\sqrt{T}),$

when taking $\eta=\frac{D_{R}}{G_{R}\sqrt{T}}$.

With the regret bound established w.r.t. $\Delta_{{\mathcal{X}}}^{\beta}$, it
is left to show the following inequality, which justifies constraining the
feasible set to $\Delta_{{\mathcal{X}}}^{\beta}$:

######  Lemma 27.

The following inequality holds for $\beta=2\log(mn)$ assuming
$T=\tilde{O}(m+n)$:

$\displaystyle\max_{C\in\Delta_{{\mathcal{X}}}}\sum_{t=1}^{T}r_{t}(C)-\max_{C\in\Delta_{{\mathcal{X}}}^{\beta}}\sum_{t=1}^{T}r_{t}(C)\leq\tilde{O}\left(\frac{\alpha}{\min\\{m,n\\}}\right).$

###### Proof of Lemma 27.

Recall $\beta$ fixes an upper-bound on the gradient of the entropy of $C$.
This is equivalent to fixing a lower-bound $\delta$ on the entries of $C$,
where $\delta\stackrel{{\scriptstyle\text{def}}}{{=}}e^{1-\beta}=e(mn)^{-2}$.
We define $C^{*}$ as follows:

$\displaystyle
C^{*}\stackrel{{\scriptstyle\text{def}}}{{=}}\operatorname*{arg\,max}_{C\in\Delta_{{\mathcal{X}}}}\
\sum_{t=1}^{T}r_{t}(C).$

Denote the set of indices where $C^{*}$ is less than $\delta$ as follows:
$S_{\delta}\stackrel{{\scriptstyle\text{def}}}{{=}}\\{x\in{\mathcal{X}}\mid
C^{*}_{x}<\delta\\}$. Enumerate $S_{\delta}$ as
$\\{(i_{k},j_{k})\\}_{k=1}^{|S_{\delta}|}$.

Note that $\forall(i_{k},j_{k})\in S_{\delta}$,
$\exists(i_{k}^{\prime},j_{k}^{\prime})\in{\mathcal{X}}$ such that
$C^{*}_{i_{k}^{\prime},j_{k}^{\prime}}-\delta\geq\delta-C^{*}_{i_{k},j_{k}}$.
Otherwise, we have by choice of $\delta$,

$\displaystyle\|C^{*}\|_{1}<mn(2\delta-C^{*}_{i_{k},j_{k}})\leq 2\delta mn<1.$

We construct the matrix $C$ initialized as $C=C^{*}$. Next, for each
$k\in[1,|S_{\delta}|]$ we iteratively change two entries in $C$ as follows for
all $k$:

  1. 1.

$C_{i_{k},j_{k}}=\delta$,

  2. 2.

$C_{i_{k}^{\prime},j_{k}^{\prime}}=C^{*}_{i_{k}^{\prime},j_{k}^{\prime}}-(\delta-C^{*}_{i_{k},j_{k}})$.

For each such operation,

$\displaystyle H(C)-H(C^{*})$
$\displaystyle=\left(C_{i_{k},j_{k}}\log\left(\frac{1}{C_{i_{k},j_{k}}}\right)+C_{i_{k}^{\prime},j_{k}^{\prime}}\log\left(\frac{1}{C_{i_{k}^{\prime},j_{k}^{\prime}}}\right)\right)$
$\displaystyle\ \ \ \ \
-\left(C^{*}_{i_{k},j_{k}}\log\left(\frac{1}{C^{*}_{i_{k},j_{k}}}\right)+C^{*}_{i_{k}^{\prime},j_{k}^{\prime}}\log\left(\frac{1}{C^{*}_{i_{k}^{\prime},j_{k}^{\prime}}}\right)\right).$

Note that
$C_{i_{k},j_{k}}+C_{i_{k}^{\prime},j_{k}^{\prime}}=C^{*}_{i_{k},j_{k}}+C^{*}_{i_{k}^{\prime},j_{k}^{\prime}}\geq
2\delta$, and $C^{*}_{i_{k},j_{k}}<\delta$. Thus, $H(C)-H(C^{*})\geq 0$ holds
for each operation. $C$ constructed by this enumeration satisfies $H(C)\geq
H(C^{*})$. On the other hand, $G$ is Lipschitz. In particular, let
$\bar{M}^{1}=\frac{1}{T}\sum_{t=1}^{T}M_{t}^{1}$,
$\bar{M}^{2}=\frac{1}{T}\sum_{t=1}^{T}M_{t}^{2}$, then

$\displaystyle\sum_{t=1}^{T}G(C,M_{t}^{1},M_{t}^{2})-\sum_{t=1}^{T}G(C^{*},M_{t}^{1},M_{t}^{2})$
$\displaystyle=\alpha
T\sum_{i,j}(C_{ij}-C^{*}_{ij})(\bar{M}^{1}_{ij}-\bar{M}^{2}_{ij})$ linearity
of $G$ $\displaystyle\leq 2\alpha T\|C-C^{*}\|_{1}$
$\displaystyle\bar{M}^{1},\bar{M}^{2}\in[-1,1]^{{\mathcal{X}}}$
$\displaystyle\leq 4mn\delta\alpha T$
$\displaystyle\|C-C^{*}\|_{\infty}\leq\delta$ $\displaystyle=\frac{4e\alpha
T}{mn}.$ $\displaystyle\delta=\frac{e}{(mn)^{2}}$

Under the assumption that $T\geq\tilde{O}(m+n)$, we conclude that

$\max_{C\in\Delta_{{\mathcal{X}}}}\sum_{t=1}^{T}r_{t}(C)-\max_{C\in\Delta_{{\mathcal{X}}}^{\beta}}\sum_{t=1}^{T}r_{t}(C)\leq\tilde{O}\left(\frac{\alpha}{\min\\{m,n\\}}\right).$

∎

By taking $\beta=O(\log(mn))$ and assuming $T=\tilde{O}(m+n)$, we can conclude
that

$\displaystyle\mbox{{Regret}}_{T}^{{\mathcal{A}}_{C}}\stackrel{{\scriptstyle\text{def}}}{{=}}\max_{C\in\Delta_{{\mathcal{X}}}}\sum_{t=1}^{T}r_{t}(C)-\sum_{t=1}^{T}r_{t}(C_{t})\leq
O(\alpha\sqrt{\log(mn)T})=\tilde{O}(\alpha\sqrt{T}).$

∎

####  C.2.2 Proof of Theorem 20

######  Theorem 20.

Denote at every time step $t$, consider the concave reward function
$\gamma_{t}(M)\stackrel{{\scriptstyle\text{def}}}{{=}}G(C_{t},M)-\theta
f_{t}(M)$. There exists sub-routine gradient-based update ${\mathcal{A}}_{M}$
(see Alg. 5 for an example) such that, under either setting 1a or 1b, the
following regret guarantee w.r.t. $\gamma_{t}$ holds:

$\displaystyle\mbox{{Regret}}_{T}^{{\mathcal{A}}_{M}}\stackrel{{\scriptstyle\text{def}}}{{=}}\max_{M\in{\mathcal{M}}^{\mathrm{max}}_{K}\times{\mathcal{M}}^{\mathrm{max}}_{K}}\sum_{t=1}^{T}\gamma_{t}(M)-\sum_{t=1}^{T}\gamma_{t}(M_{t})\leq
O(K\theta\sqrt{(m+n)T}).$

###### Proof of Theorem 20.

We will begin by outlining the update algorithm ${\mathcal{A}}_{M}$, then
introduce the key definitions used in ${\mathcal{A}}_{M}$, and proceed to
prove Theorem 20. We note that this algorithm is modified from the matrix
multiplicative weights for online matrix prediction (Algorithm 2) in Hazan et
al. [2012b].

Algorithm 5 ${\mathcal{A}}_{M}$

1: Input:
$C_{t},M_{t}=(M_{t}^{1},M_{t}^{2})\in{\mathcal{M}}^{\mathrm{max}}_{K}$,
$(i_{t},j_{t},o_{t})$.

2: if input is empty then

3: Output: $\phi^{-1}\left(\frac{K}{2}I\right)$.

4: end if

5: Compute $X_{t}=\phi(M_{t}^{1},M_{t}^{2})$ with
$\phi(\emptyset)=\frac{K}{2}I$.

6: Create matrix $L_{t}(\gamma_{t})$ according to Definition 29.

7: Update: with step size
$\eta=\frac{1}{2(1+8\theta)}\sqrt{\frac{(m+n)\log(2p)}{T}}$, project w.r.t.
matrix relative entropy:  $\displaystyle
X_{t+1}=\underset{X\in\mathcal{K}_{X}}{\operatorname*{arg\,min}}\
\Delta(X,\exp(\log(X_{t})+\eta L_{t}(\gamma_{t}))).$

8: Output: $M_{t+1}=(M_{t+1}^{1},M_{t+1}^{2})=\phi^{-1}(X_{t+1})$.

$\mathcal{K}_{X}$ is given by

$\displaystyle\mathcal{K}_{X}\stackrel{{\scriptstyle\text{def}}}{{=}}\\{X\in{\text{S}ym}(2p):\
$ $\displaystyle X\succeq 0,\ {\text{Tr}}(X)\leq 2K(m+n),\ X_{ii}\leq K,\
X[:p,:p]-X[p:,p:]\in[-1,1]^{p\times p}\\}.$

The operator $\phi$ is given as the following:

######  Lemma 28.

$\forall M^{1},M^{2}\in{\mathcal{M}}^{\mathrm{max}}_{K}$,
$M=\begin{bmatrix}M^{1}&\mathbf{0}\\\ \mathbf{0}&M^{2}\end{bmatrix}$ is
$(K,2K(m+n))$-decomposable.

Denote $p\stackrel{{\scriptstyle\text{def}}}{{=}}2(m+n)$.
$(\beta,\tau)$-decomposability allows for two matrices in
${\mathcal{M}}^{\mathrm{max}}_{K}$ to be embedded in ${\text{S}ym}(2p)$:

$\phi(\cdot,\cdot):{\mathcal{M}}^{\mathrm{max}}_{K}\times{\mathcal{M}}^{\mathrm{max}}_{K}\rightarrow{\text{S}ym}(2p)$
is the embedding operator given by

$\phi(M)\stackrel{{\scriptstyle\text{def}}}{{=}}\phi(M^{1},M^{2})\stackrel{{\scriptstyle\text{def}}}{{=}}\begin{bmatrix}P&\mathbf{0}\\\
\mathbf{0}&N\end{bmatrix},$

where $P,N$ are the PSD matrices given by the $(\beta,\tau)$-decomposition.

The descent matrix $L_{t}(\gamma_{t})$, which we shorthand denote as $L_{t}$,
is constructed as the following:

######  Definition 29 (Descent matrix).

At time $t$, we define the matrix $L_{t}\in{\text{S}ym}(2p)$ as
$L_{t}\stackrel{{\scriptstyle\text{def}}}{{=}}L_{t}^{G}+L_{t}^{F}$, where
$L_{t}^{G}$ is symmetric and

$\begin{cases}L_{t}^{G}[1:m,2m+1:2m+n]=C_{t}\\\
L_{t}^{G}[p+m+1:p+2m,p+2m+n+1:2p]=C_{t}\\\
L_{t}^{G}[m+1:2m,2m+n+1:p]=-C_{t}\\\
L_{t}^{G}[p+1:p+m,p+2m+1:p+2m+n]=-C_{t}\\\ L_{t}^{G}[i,j]=0\hskip
2.84544pt\text{if otherwise and $j\geq i$}\end{cases}$

$L_{t}^{F}$ is symmetric and

$\begin{cases}L_{t}^{F}[i_{t},2m+j_{t}]=-2\theta((M_{t}^{1})_{i_{t},j_{t}}-o_{t}),L_{t}^{F}[m+i_{t},2m+n+j_{t}]=-2\theta((M_{t}^{2})_{i_{t},j_{t}}-o_{t})\\\
L_{t}^{F}[p+i_{t},p+2m+j_{t}]=2\theta((M_{t}^{1})_{i_{t},j_{t}}-o_{t}),L_{t}^{F}[p+m+i_{t},p+2m+n+j_{t}]=2\theta((M_{t}^{2})_{i_{t},j_{t}}-o_{t})\\\
L_{t}^{F}[i,j]=0\hskip 2.84544pt\text{if otherwise and $j\geq i$}\end{cases}$

Note that by construction $(L_{t}^{G})^{2}$, $(L_{t}^{F})^{2}$ are diagonal
matrices, and ${\text{Tr}}(L_{t}^{2})\leq O(\theta^{2})$.

The rest of the proof follows from Section 3.2 in [Hazan et al., 2012b].

∎

###  C.3 Proof of offline implications

####  C.3.1 Proof of Lemma 21

######  Lemma 21.

After $T$ iterations, and assume that for some $\delta>0$,

$\frac{1}{\theta}\left(2D+\frac{\mbox{{Regret}}_{T}^{{\mathcal{A}}_{M}}}{T}\right)\leq\frac{\delta^{2/3}}{2},$

with $D=1$ in setting 1a, and $D=\sqrt{m+n}$ in setting 1b. The following
properties hold on the obtained
$\bar{C}\stackrel{{\scriptstyle\text{def}}}{{=}}\frac{1}{T}\sum_{t=1}^{T}C_{t}$
returned by Algorithm 3: with probability $\geq
1-\exp\left(-\frac{\delta^{4/3}T}{512}\right)$,

$\displaystyle H(\bar{C})-\max_{M\in{\mathcal{V}}_{T,\delta}^{2}}\alpha\cdot
G(\bar{C},M)\geq\max_{C\in{\mathcal{C}}}\min_{M\in{\mathcal{V}}_{\delta^{2/3}}^{2}}\left\\{H(C)-\alpha\cdot
G(C,M)\right\\}-2\alpha\theta\delta-\frac{B_{T}}{T}.$

###### Proof of Lemma 21.

For notation convenience, denote

$\displaystyle
C^{\star},M^{1}_{\star},M^{2}_{\star}=\underset{C\in{\mathcal{C}}}{\operatorname*{arg\,max}}\
\underset{(M^{1},M^{2})\in{\mathcal{V}}_{\delta^{2/3}}^{2}}{\operatorname*{arg\,min}}\
H(C)-\alpha G(C,M^{1},M^{2}).$

Consider the subroutine ${\mathcal{A}}_{M}$. Under the assumption,
${\mathcal{A}}_{M}$ is a low-regret OCO algorithm for $\gamma_{t}$’s. In
particular, under the realizable assumption, since there exist
$M=(M^{1},M^{2})$ such that $f_{t}(M)=\gamma_{t}(M)=0$, $\forall t$, we have
that for the sequence of $M_{t}$’s output by the algorithm,

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}f_{t}(M_{t})$
$\displaystyle=\frac{1}{T\theta}\sum_{t=1}^{T}\left(G(C_{t},M_{t})-\gamma_{t}(M_{t})\right)\leq\frac{1}{\theta}\left(2D+\frac{\mbox{{Regret}}_{T}^{{\mathcal{A}}_{M}}}{T}\right)\leq\frac{\delta^{2/3}}{2}.$

Note that $\forall M\in{\mathcal{M}}^{\mathrm{max}}_{K}$, $M$ can be seen as a
function mapping from ${\mathcal{X}}$ to $[-1,1]$. Denote
$f(M)\stackrel{{\scriptstyle\text{def}}}{{=}}\mathbb{E}_{(x,o)\sim\mathcal{D}}[(M_{x}^{1}-o)^{2}+(M_{x}^{2}-o)^{2}]$.
Define $Z_{t}=f(M_{t})-f_{t}(M_{t})$, $X_{t}=\sum_{i=1}^{t}Z_{i}$, then we
have with ${\mathcal{F}}_{t}$ denoting the filtration generated by the
algorithm’s randomness up to iteration $t$, and since
$M_{t}\in{\mathcal{F}}_{t-1}$,

$\displaystyle\mathbb{E}[Z_{t}\mid{\mathcal{F}}_{t-1}]=0,\ \
\mathbb{E}[X_{t}\mid{\mathcal{F}}_{t-1}]=X_{t-1},$

and $|X_{t}-X_{t-1}|=|Z_{t}|\leq 8$. By Azuma’s inequality, we have
$\forall\varepsilon>0$,

$\displaystyle\mathbb{P}\left(\frac{1}{T}\sum_{t=1}^{T}f(M_{t})-f_{t}(M_{t})>\sqrt{\frac{128\log\left(\frac{1}{\varepsilon}\right)}{T}}\right)=\mathbb{P}\left(\frac{1}{T}\sum_{t=1}^{T}X_{t}>\sqrt{\frac{128\log\left(\frac{1}{\varepsilon}\right)}{T}}\right)\leq\varepsilon.$

We can conclude that with probability at least
$1-\exp\left(-\frac{\delta^{4/3}T}{512}\right)$,

$\displaystyle
f(\bar{M})\leq\frac{1}{T}\sum_{t=1}^{T}f(M_{t})\leq\frac{1}{T}\sum_{t=1}^{T}f_{t}(M_{t})+\frac{\delta^{2/3}}{2}\leq\frac{\delta^{2/3}}{2}+\frac{\delta^{2/3}}{2}=\delta^{\frac{2}{3}},$

in which case $\bar{M}^{1},\bar{M}^{2}\in{\mathcal{V}}_{\delta^{2/3}}$. We
have thus with probability at least
$1-\exp\left(-\frac{\delta^{4/3}T}{512}\right)$,

$\displaystyle H(C^{\star})-\alpha G(C^{\star},M^{1}_{\star},M^{2}_{\star})$
$\displaystyle\leq H(C^{\star})-\alpha G(C^{\star},\bar{M}^{1},\bar{M}^{2})$
($M^{1}_{\star},M^{2}_{\star}$) are optimal w.r.t. $C^{\star}$ in
${\mathcal{V}}_{\delta}$
$\displaystyle=\frac{1}{T}\sum_{t=1}^{T}r_{t}(C^{\star})$ linearity of $G$,
definition of $r_{t}$
$\displaystyle\leq\frac{1}{T}\sum_{t=1}^{T}r_{t}(C_{t})+\frac{\mbox{{Regret}}_{T}^{{\mathcal{A}}_{C}}}{T}$
${\mathcal{A}}_{C}$ regret guarantee $\displaystyle\leq
H(\bar{C})-\frac{\alpha}{T}\sum_{t=1}^{T}G(C_{t},M_{t}^{1},M_{t}^{2})+\frac{\mbox{{Regret}}_{T}^{{\mathcal{A}}_{C}}}{T}$
concavity of $H(\cdot)$ on ${\mathcal{C}}$ $\displaystyle\leq
H(\bar{C})-\frac{\alpha}{T}\sum_{t=1}^{T}\gamma_{t}(M_{t}^{1},M_{t}^{2})+\frac{\mbox{{Regret}}_{T}^{{\mathcal{A}}_{C}}}{T}$
$f_{t}\geq 0$ $\displaystyle\leq
H(\bar{C})-\frac{\alpha}{T}\sum_{t=1}^{T}\gamma_{t}(\hat{M}^{1},\hat{M}^{2})+\frac{B_{T}}{T}$
$\forall(\hat{M}^{1},\hat{M}^{2})\in{{\mathcal{M}}^{\mathrm{max}}_{K}}^{2}$ by
${\mathcal{A}}_{M}$ regret guarantee
$\displaystyle~{}\leq~{}H(\bar{C})-\max_{(M^{1},M^{2})\in{\mathcal{V}}_{T,\delta}^{2}}\alpha\cdot
G(\bar{C},M^{1},M^{2})+2\alpha\theta\delta+\frac{B_{T}}{T}$ definition of
${\mathcal{V}}_{T,\delta}$

∎

####  C.3.2 Proof of Theorem 22

######  Theorem 22.

Suppose the underlying sampling distribution is $\mu$. Let
$C_{\mu}\in{\mathcal{C}}$ be its corresponding confidence matrix. In
particular, for setting 1a, $C_{\mu}=\mu$, i.e.
$(C_{\mu})_{ij}=\mathbb{P}_{\mu}((i,j)\text{ is sampled})$; for setting 1b,
$C_{\mu}$ satisfies that $C_{\mu}/\|C_{\mu}\|_{1}=\mu$. Then, for any
$\delta>0$, Algorithm 3 run with $\alpha=\delta^{-1/6}$ returns a $\bar{C}$
that guarantees the following bounds: with probability $\geq
1-\exp\left(-\frac{\delta^{2}T}{128}\right)-\exp\left(-\frac{\delta^{4/3}T}{512}\right)$,

  1. 1.

For setting 1a, take $\theta=4\delta^{-2/3}$, after
$T=\tilde{O}(\delta^{-2}K^{2}(m+n))$ iterations,

    1. (a)

$H(\bar{C})\geq H(C_{\mu})-O(\delta^{1/6})$.

    2. (b)

$\underset{M^{1},M^{2}\in{\mathcal{V}}_{\frac{\delta}{2}}}{\max}\
G(\bar{C},M^{1},M^{2})\leq O(\delta^{1/6}\log(mn))$.

  2. 2.

For setting 1b, take $\theta=4\delta^{-2/3}\sqrt{m+n}$, after
$T=\tilde{O}(\delta^{-2}K^{2}(m+n))$ iterations,

    1. (a)

$\|\bar{C}\|_{1}\geq\|C_{\mu}\|_{1}-O(\delta^{1/6}\sqrt{m+n})$.

    2. (b)

$\underset{M^{1},M^{2}\in{\mathcal{V}}_{\frac{\delta}{2}}}{\max}G(\bar{C},M^{1},M^{2})\leq
O(\delta^{1/6}\sqrt{m+n})$.

###### Proof of Theorem 22.

First, note that $\forall i,j,o$, we have by assumption
$(M_{ij}-o)^{2}\in[0,4]$, $\forall M\in{\mathcal{M}}^{\mathrm{max}}_{K}$.
Therefore, by subgaussian concentration, $\forall c\geq 1$,

$\displaystyle\mathbb{P}\left(\frac{1}{T}\sum_{t=1}^{T}(M_{i_{t},j_{t}}-o_{t})^{2}-\mathbb{E}_{i,j}[(M_{ij}-o)^{2}]\geq\frac{\delta}{2}\right)\leq\exp\left(-\frac{\delta^{2}T}{128}\right).$

Therefore, with probability at least
$1-\exp\left(-\frac{\delta^{2}T}{128}\right)$, we have

$\displaystyle{\mathcal{V}}_{\frac{\delta}{2}}\subseteq{\mathcal{V}}_{T,\delta}.$

Therefore, it suffices to show the inequality in (b) for the maximum over
${\mathcal{V}}_{T,\delta}$. Let

$\displaystyle C^{\star},M^{1}_{\star},M^{2}_{\star}$
$\displaystyle=\underset{C\in{\mathcal{C}}}{\operatorname*{arg\,max}}\
\underset{(M^{1},M^{2})\in{\mathcal{V}}_{\delta^{2/3}}^{2}}{\operatorname*{arg\,min}}\
H(C)-\alpha G(C,M^{1},M^{2})$
$\displaystyle=\underset{C\in{\mathcal{C}}}{\operatorname*{arg\,max}}\
\underset{(M^{1},M^{2})\in{\mathcal{V}}_{\delta^{2/3}}^{2}}{\operatorname*{arg\,min}}\
H(C)-\delta^{-1/6}G(C,M^{1},M^{2}).$

Choose $T$ such that $\frac{B_{T}}{T}\leq\alpha\theta\delta$. Note that in
both settings, the choice of $\theta$ and $T$ satisfies the assumption in
Theorem 21.

##### Simplex and entropy.

We can bound $G(C_{\mu},M_{\star}^{1},M_{\star}^{2})$ by

$\displaystyle G(C_{\mu},M^{1}_{\star},M^{2}_{\star})$
$\displaystyle=\mathbb{E}_{x\sim\mu}[(M_{\star}^{1})_{x}-(M_{\star}^{2})_{x}]$
$\displaystyle=\sqrt{(\mathbb{E}_{(x,o)\sim\mathcal{D}}[(M_{\star}^{1})_{x}-o_{x}]-\mathbb{E}_{(x,o)\sim\mathcal{D}}[(M_{\star}^{2})_{x}-o_{x}])^{2}}$
$\displaystyle\leq\sqrt{2(\mathbb{E}_{(x,o)\sim\mathcal{D}}[(M_{\star}^{1})_{x}-o_{x}]^{2}+\mathbb{E}_{(x,o)\sim\mathcal{D}}[(M_{\star}^{2})_{x}-o_{x}]^{2})}$
$\displaystyle(a-b)^{2}\leq 2(a^{2}+b^{2})$
$\displaystyle\leq\sqrt{2(\mathbb{E}_{(x,o)\sim\mathcal{D}}[((M_{\star}^{1})_{x}-o_{x})^{2}]+\mathbb{E}_{(x,o)\sim\mathcal{D}}[((M_{\star}^{2})_{x}-o_{x})^{2}])}$
Jensen’s $\displaystyle\leq 2\delta^{1/3}$ $\displaystyle
M_{\star}^{1},M_{\star}^{2}\in{\mathcal{V}}_{\delta^{2/3}}$

Theorem 21 implies that with probability $\geq
1-\exp\left(-\frac{\delta^{4/3}T}{512}\right)$,

$\displaystyle
H(\bar{C})-\underset{M^{1},M^{2}\in{\mathcal{V}}_{T,\delta}}{\max}\
\delta^{-1/6}G(\bar{C},M^{1},M^{2})$ $\displaystyle\geq H(C_{\mu})-\alpha
G(C_{\mu},M_{\star}^{1},M_{\star}^{2})-2\alpha\theta\delta-\frac{B_{T}}{T}$
$\displaystyle\geq H(C_{\mu})-12\delta^{1/6},$

Note that by definition
$\underset{M^{1},M^{2}\in{\mathcal{V}}_{T,\delta}}{\max}\
G(\bar{C},M^{1},M^{2})\geq 0$, and thus

$\displaystyle H(\bar{C})\geq H(C_{\mu})-12\delta^{1/6}.$

Since $H(\cdot)$ is bounded by $\left[0,\log(mn)\right]$ over ${\mathcal{C}}$,
then

$\displaystyle\underset{M^{1},M^{2}\in{\mathcal{V}}_{T,\delta}}{\max}G(\bar{C},M^{1},M^{2})$
$\displaystyle\leq\delta^{1/6}\left(H(\bar{C})-H(C_{\mu})\right)+12\delta^{1/3}$
$\displaystyle\leq\delta^{1/6}\log(mn)+12\delta^{1/3}$ $\displaystyle\leq
O(\delta^{1/6}\log(mn)).$

##### Cube and $\ell_{1}$ norm.

We can bound $G(C_{\mu},M_{\star}^{1},M_{\star}^{2})$ by

$\displaystyle
G(C_{\mu},M_{\star}^{1},M_{\star}^{2})\leq\sqrt{m+n}\mathbb{E}_{x\sim\mu}\left[(M_{\star}^{1})_{x}-(M_{\star}^{2})_{x}\right]\leq
2\delta^{1/3}\sqrt{m+n}.$

Theorem 21 implies that

$\displaystyle
H(\bar{C})-\underset{M^{1},M^{2}\in{\mathcal{V}}_{T,\delta}}{\max}\
\delta^{-1/6}G(\bar{C},M^{1},M^{2})\geq H(C_{\mu})-12\delta^{1/6}\sqrt{m+n}.$

Thus, similar as before, we get

$\displaystyle H(\bar{C})$ $\displaystyle\geq
H(C_{\mu})-12\delta^{1/6}\sqrt{m+n},$

and

$\displaystyle\underset{M^{1},M^{2}\in{\mathcal{V}}_{T,\delta}}{\max}G(\bar{C},M^{1},M^{2})$
$\displaystyle\leq\delta^{1/6}\left(H(\bar{C})-H(C_{\mu})\right)+12\delta^{1/3}\sqrt{m+n}$
$\displaystyle\leq O(\delta^{1/6}\sqrt{m+n}).$

∎

##  Appendix D Implementation Details

With the theoretical guarantee established above, we implemented a simple
version of ODD in Section 6 and experimented with both simulated toy datasets
and real-world datasets including the well-known MovieLens dataset. In
particular, the simplification of ODD we implemented is given by the following
algorithm:

Algorithm 6 Simplified ODD

1: Input: initial (uniform) distribution $C_{1}$, matrix $M\in\mathcal{K}$,
parameters $\eta>0$, $\alpha>0$, matrix prediction update function matrix-
predict($\cdot$). $R(\cdot)=-H(\cdot)$.

2: for $t=1,2,...,T$ do

3: Adversary draws tuple $x_{t}=(i_{t},j_{t})$, reveals $M_{x_{t}}$.

4: Update $M_{t+1}=\texttt{matrix-predict}(C_{t},M_{t})$.

5: Consider reward
$\tilde{r}_{t}(C)\stackrel{{\scriptstyle\text{def}}}{{=}}\alpha H(C)-\langle
C,M_{t}\rangle.$

6: Update
$\nabla\mkern-2.5muR(\hat{C}_{t+1})\leftarrow\nabla\mkern-2.5muR(C_{t})+\eta\nabla\mkern-2.5mu\tilde{r}_{t}(C_{t}).$

7: Project
$C_{t+1}=\underset{C\in\Delta_{{\mathcal{X}}}}{\operatorname*{arg\,min}}\
\|C-\hat{C}_{t+1}\|_{\mathrm{fr}}$.

8: end for

9: return:
$\bar{C}\stackrel{{\scriptstyle\text{def}}}{{=}}\frac{1}{T}\sum_{t=1}^{T}C_{t}$.

This algorithm is an instantiation of our online algorithm ODD (Algorithm 3),
using mirror descent for updating the confidence matrix, and an arbitrary
matrix completion method called matrix-predict.

##  Appendix E Definitions

##### Matrix logarithm.

Given the matrix $X\in{\text{S}ym}(n)$, $X\succeq 0$, $X$ admits a
diagonalization $X=V\Sigma V^{T}$, where $\Sigma$ can be written as follows:

$\Sigma\stackrel{{\scriptstyle\text{def}}}{{=}}\begin{bmatrix}\Sigma_{11}&0&...&0\\\
0&\Sigma_{22}&...&0\\\ ...&...&...&...\\\ 0&0&...&\Sigma_{nn}\end{bmatrix}.$

The logarithm of $X$ is given by:

$\log(X)\stackrel{{\scriptstyle\text{def}}}{{=}}V\begin{bmatrix}\log(\Sigma_{11})&0&...&0\\\
0&\log(\Sigma_{22})&...&0\\\ ...&...&...&...\\\
0&0&...&\log(\Sigma_{nn})\end{bmatrix}V^{T}.$

Matrix logarithm satisfies the following properties for
$X,Y\in{\text{S}ym}(n),X,Y\succ 0$:

  1. 1.

${\text{Tr}}(\log(XY))={\text{Tr}}(\log(X))+{\text{Tr}}(\log(Y))$.

  2. 2.

If $XY=YX$, then $\log(XY)=\log(X)+\log(Y)$.

  3. 3.

$\log(cI)=(\log c)I$, $\forall c>0$.

##### Matrix relative entropy.

Given matrices $X,Y\in{\text{S}ym}(n),X,Y\succeq 0$, their relative entropy is
given by

$\Delta(X,Y)\stackrel{{\scriptstyle\text{def}}}{{=}}\text{Tr}(X\log(X)-X\log(Y)-X+Y).$

##### ($\beta,\tau$)-decomposability.

$M\in\mathbb{R}^{m\times n}$ is $(\beta,\tau)$-decomposable if $\exists
P,N\in{\text{S}ym}(m+n)$, $P,N\succeq 0$:

$\displaystyle P-N=\begin{bmatrix}\mathbf{0}&M\\\
M^{T}&\mathbf{0}\end{bmatrix},\ \ \ {\text{Tr}}(P)+{\text{Tr}}(N)\leq\tau,\ \
\ \max_{i}\ P_{ii},\max_{i}\ N_{ii}\leq\beta.$