\section{Introduction}
\label{sec:intro}

Modern machine learning applications often involve high-dimensional datasets with large sample sizes, on which simple algorithms such as variants of online gradient descent are competitive with more complicated batch algorithms. 
In addition to often being more practical computationally as compared to batch methods, online methods apply to a wider range of scenarios such as online prediction against individual sequences. 
In the online non-stochastic (adversarial) setting, the regret of a learning algorithm is a more natural quantity to analyze than the cumulative loss (for the latter an adversary may as well emit a data sequence of pure noise). 
Although vanilla online gradient descent \citep{zinkevich2003online} obtains provably optimal regret in a minimax sense \citep{abernethy2008optimal}, if a method can simultaneously admit better guarantees against easy data sequences (such as low-dimensional data or i.i.d.~stochastic data) while maintaining the fallback guarantee of minimax optimality against the nastiest data sequences, such a method is even better. Such methods fall within the recently-sculpted space of ``learning faster from easy data'' \citep{grunwald2013learning}.

AdaGrad \citep{duchi2011adaptive} embodies an adaptive gradient family of algorithms, the two most prominent cases being full-matrix AdaGrad and diagonal AdaGrad. Whereas the former is computationally intractable in high-dimensions, the latter is tractable with only linear complexity in the dimension of the data. Both methods admit sequence-dependent regret bounds that can be much better than the regret bounds of online gradient descent. However, the computational levity of the diagonal version is matched with a price: if the components of the gradient are highly correlated, the diagonal version may fail to adapt well while the full-matrix version continues to be adaptive.

In addition to its theoretical strengths, even the diagonal version of AdaGrad has exhibited strong empirical performance on real-world problems \citep{duchi2011adaptive}. Moreover, diagonal AdaGrad also has been incorporated into deep learning algorithms that currently achieve state-of-the-art learning performance on a number of difficult image classification tasks \citep{dean2012large}.

Even though it is theoretically superior in terms of the regret, the full-matrix version has not seen similar large-scale applications due to its high per-round complexity of $O(n^3)$. This raises the question: is it possible to design a method lying between the full-matrix and diagonal versions of AdaGrad whose per-round complexity is $O(n)$? In this work, we answer this question in the affirmative, up to log factors, by presenting CompAdaGrad. 
This method replaces full-matrix AdaGrad's Bregman divergence regularization with the sum of a \emph{compressed} Bregman divergence operating in a low-dimensional subspace and a diagonal Bregman divergence operating in the orthogonal complement of that subspace. The precise form can be seen in \eqref{eqn:psi-rp-oc}. This method admits a theoretical guarantee that appears to be between full-matrix AdaGrad and diagonal AdaGrad, as shown in \cref{sec:regret}.

It is natural to ask why one would compress at the regularization level rather than simply compressing the data itself via a random projection from the very beginning. There are several reasons why compression at the regularization level makes more sense.
\begin{enumerate}
\item An initial compression of the data can reduce computational complexity but may lose information irretrievably, whereas by shifting the compression into the regularization component of the objective some part of the otherwise lost complementary information can still be exploited.
\item In an adversarial setting, if the learning algorithm commits to a fixed low-dimensional subspace, even an oblivious adversary can ensure that all the interesting action occurs in the complement of this subspace.
\item In some applications, one actually needs a predictor in the original space. This might be for interpretability, for instance.
\end{enumerate}

In the next section, we review AdaGrad and derive CompAdaGrad. In \cref{sec:regret} we present a regret bound for CompAdaGrad. We show how to compute updates for certain composite regularizers in \cref{sec:computations}. This section also contains a result that may be of independent interest: \cref{thm:1-sparse} establishes $O(n)$ complexity for computing the $n$-dimensional Walsh-Hadamard Transform of a 1-sparse vector. 
In \cref{sec:experiments}, we present experimental results on several datasets. Finally, we conclude the paper.


\section{AdaGrad: The Full, the Diagonal, and the Compressed}
\label{sec:adagrad}

\paragraph{Notation.}
Throughout this paper, we let $\mathcal{X} = \mathbb{R}^n$ and leave extensions to convex subsets for future work. 
For a strongly convex, differentiable function $\psi$, let $B_\psi$ be the Bregman divergence induced from $\psi$, defined as
\begin{align*}
B_\psi(x, y) = \psi(x) - \psi(y) - \langle \nabla \psi(y), x - y \rangle .
\end{align*}

For a sequence of subdifferentiable convex functions $f_1, \ldots, f_T$, let $g_1, \ldots, g_T$ be a corresponding sequence of subgradients, so that for each $t \in [T]$ we have $g_t \in \partial f_t$.

\paragraph{Online Convex Optimization game.}

We consider the following online learning protocol parameterized by a convex regularization function $\varphi: \mathcal{X} \rightarrow \mathbb{R}_+$.

Let Nature be an oblivious adversary; that is, before the game begins Nature selects its sequence of functions possibly with knowledge of Learner's (potentially randomized) strategy. The game then proceeds over a sequence of rounds:

\begin{quote}
For round $t = 1, 2, ...$
\begin{enumerate}[label=(\arabic*)]
\item Learner makes a prediction $x_t$ in action space $\mathcal{X}$.
\item Nature reveals a convex loss function $f_t : \mathcal{X} \rightarrow \mathbb{R}_+$ .
\item Learner suffers composite loss $f_t(x_t) + \varphi(x_t)$.
\end{enumerate}
\end{quote}

The goal is to find a strategy that minimizes the regret, defined as follows. 
Let $f_1, \ldots, f_T$ be a sequence of functions chosen by an oblivious adversary.
Then the regret on this sequence is
\begin{align} \label{eqn:regret}
\mathcal{R}(f_1, \ldots, f_T) 
= \sum_{t=1}^T \bigl( f_t(x_t) + \varphi(x_t) \bigr) 
    - \inf_{x^* \in \mathcal{X}} \sum_{t=1}^T \bigl( f_t(x^*) + \varphi(x^*) \bigr) .
\end{align}

AdaGrad with composite mirror descent embodies one family of learning strategies for obtaining low regret. Although previously AdaGrad also has been presented with regularized dual averaging, in this work we restrict to composite mirror descent for simplicity. AdaGrad for composite mirror descent is described by the updates
\begin{align} \label{eqn:update}
x_{t+1} = \argmin_{x \in \mathcal{X}} 
              \left\{
                  \eta \langle g_t, x \rangle + \eta \varphi(x) + B_{\psi_t}(x, x_t) 
               \right\} ,
\end{align}
for some constant learning rate $\eta > 0$ and some adaptive choice of convex function $\psi_t$. 

We define $G_t := \sum_{s=1}^t g_s g_s^T$ and use the notation $\|x\|_A^2 = x^T A x$. 
In its full-matrix incarnation, AdaGrad uses the choice \citep{duchi2011adaptive}
\begin{align*}
\psi_t(x) = \frac{1}{2} \| x \|_{G_t^{1/2}}^2 .
\end{align*}
As shown by \cite{duchi2011adaptive} and reproduced in \cref{sec:regret} for convenience, full-matrix AdaGrad admits a strongly adaptive regret bound. Unfortunately, the update \eqref{eqn:update} for full-matrix AdaGrad is not tractable for large $n$ because it involves a matrix square root and solving an $n$-dimensional linear system, each of which costs time $O(n^3)$. In response to this issue, there is a diagonal version of AdaGrad that admits updates in time $O(n)$. For a square matrix $A$, let $\mathrm{diag}(A)$ be the diagonal matrix satisfying $\mathrm{diag}(A)_{ii} = A_{ii}$ for all $i$ and $\mathrm{diag}(A)_{ij} = 0$ for all $(i,j)$ such that $i \neq j$. The diagonal version of AdaGrad uses the choice \citep{duchi2011adaptive}
\begin{align*}
\psi_t(x) = \frac{1}{2} \| x \|_{\mathrm{diag}(G_t)^{1/2}}^2 .
\end{align*}
This method also admits theoretical guarantees (cf.~\citep{duchi2011adaptive} or \cref{sec:regret}). However, by design the diagonal method ignores the correlations between the components of the gradients.

\paragraph{CompAdaGrad.}
In this work, we introduce \emph{CompAdaGrad}, a method which combines the full-matrix approach in a subspace plus the diagonal approach in the complementary subspace. 

The idea of CompAdaGrad starts by restricting full-matrix AdaGrad's Bregman divergence to a low dimensional subspace by way of a mapping $\Pi: \mathbb{R}^n \rightarrow \mathbb{R}^k$ for some $k \leq n$ (and typically $k \ll n$). Since $\Pi G_t \Pi^T = \sum_{s=1}^T \Pi g_s (\Pi g_s)^T$, this leads to the modified Bregman divergence term
\begin{align} \label{eqn:radagrad}
\frac{1}{2} \| \Pi (x - x_t) \|_{(\Pi G_t \Pi^T)^{1/2}}^2 
= \frac{1}{2} \| x - x_t \|_{\Pi^T (\Pi G_t \Pi)^{1/2} \Pi}^2 ,
\end{align}
which was also used by \cite{krummenacher2014radagrad}.\footnote{Those authors select $\Pi$ to be an SRHT, described below, and we do this as well.} 
Our first remark is that if $k = n$ and $\Pi$ is in the orthogonal group, then it is easy to see that setting $\psi_t$ as in the RHS of \eqref{eqn:radagrad} recovers full-matrix AdaGrad. 

A deficiency of \eqref{eqn:radagrad} is that it ignores all of the action in the orthogonal complement of the image of $\Pi$; however, this action can be addressed naturally by directly considering the action in this complementary subspace. To this end, define $P$ to be the orthogonal projector corresponding to $\Pi$, defined as $P := \Pi^T (\Pi \Pi^T)^{-1} \Pi$. The corresponding complementary orthogonal projector is then $P^\perp := I - P$. Incorporating complementary regularization into the Bregman divergence with a diagonal approximation (since the dimension of the complementary subspace $n - k$ is presumably high) yields
\begin{align} \label{eqn:radagrad-complementary}
\frac{1}{2} \| \Pi (x - x_t) \|_{(\Pi G_t \Pi^T)^{1/2}}^2 
+ \frac{\tau}{2} \| P^\perp (x - x_t) \|_{\mathrm{diag}(G^\perp_t)^{1/2}}^2 ,
\end{align}
where $G^\perp_t := \sum_{s=1}^t (P^\perp g_s) (P^\perp g_s)^T = P^\perp G_T P^\perp$ and $\tau \geq 0$ is a parameter.

Note that when $k = n$ and $\Pi$ is in the orthogonal group, \eqref{eqn:radagrad-complementary} still recovers full-matrix AdaGrad (since the complementary subspace is empty). Additionally, when $k = 0$ and $\tau = 1$, \eqref{eqn:radagrad-complementary} recovers diagonal AdaGrad since $P^\perp = I$. Modulo a small modification to ensure strong convexity of $\psi_t$, we have just derived the method that we call CompAdaGrad, which is characterized by setting $\psi_t$ as
\begin{align} \label{eqn:psi-rp-oc}
\psi_t(x) = \frac{1}{2} \| x \|_{A^{(r)}_t + \tau A^{(c)}_t}^2 
\end{align}
\begin{flalign*}
\text{for} && 
A^{(r)}_t := \Pi^T \left( \Pi G_t \Pi^T  + \delta_r I \right)^{1/2} \Pi &&
\text{and} &&
A^{(c)}_t := 
P^\perp 
 \left( \mathrm{diag} \left( G^\perp_t \right)^{1/2} + \delta_c I \right) 
P^\perp . &&
\end{flalign*}


\paragraph{SRHT specialization.}
Throughout the rest of this paper, we take $\Pi$ to be a Subsampled Randomized Hadamard Transform (SRHT), defined as $\Pi: = \sqrt{\frac{n}{k}} R H \Sigma$ for a row selector $R \in \mathbb{R}^{k \times n}$, an $n$-dimensional (orthogonal) Walsh-Hadamard matrix $H$, and a diagonal Rademacher matrix $\Sigma \in \mathbb{R}^{n \times n}$ (whose diagonal entries are drawn i.i.d.~ as $+1$ and $-1$ with equal probability). The row selector $R$ is induced from the distribution of all cardinality-$k$ subsets of $n$ indices. 
The idea behind \eqref{eqn:psi-rp-oc} is that if there is interesting action in a low-dimensional subspace, the SRHT (i.e.~the $A^{(r)}$-part of the regularization) potentially can capture this action \citep{tropp2011improved}.
However, as the SRHT can only capture action in a low-dimensional subspace, it is critical to also include \emph{complementary} regularization by way of the $A^{(c)}$ part of the regularization. This is especially true in the adversarial regime, where an adversary can pick up on Learner's fixed SRHT and make all of the interesting action happen in the complement. In this sense, CompAdaGrad can have the benefit of full-matrix AdaGrad under an oblivious, easy adversary who restricts most of the action in a low-dimensional subspace, while also maintaining guarantees against a harder adversary who uses their knowledge of $\mathrm{Im}(P)$.

The choices of $k$ and $\tau$ offer useful degrees of freedom for massive datasets. As $k$ increases toward $n$, the method more closely resembles full-matrix AdaGrad, and the regret bound generally becomes stronger as $k$ increases, while the computational complexity for various methods also becomes larger with larger $k$. The parameter $\tau$ on the other hand allows one to modulate how much emphasis to place on the complementary subspace, with this action increasingly ignored as $\tau$ decreases to 0. The next two sections help provide an understanding of the trade-off between regret and computation respectively.


\section{Regret Bounds}
\label{sec:regret}

Diagonal AdaGrad inherently is unable to adapt to correlations in a data sequence, as can be seen by Duchi et al.'s regret bound for this method (cf.~Theorem 5 of \cite{duchi2011adaptive}):
\begin{theorem} \label{thm:diagonal-regret}
\begin{align} \label{eqn:diagonal-regret}
\mathcal{R}(f_1, \ldots, f_T) 
\leq \frac{1}{2 \eta} \max_{t \in [T]} \|x^* - x_t\|_\infty^2 
                     \sum_{j=1}^n \left( \sum_{t=1}^T g_{t,j}^2 \right)^{1/2} 
                     + \eta \sum_{j=1}^n \left( \sum_{t=1}^T g_{t,j}^2 \right)^{1/2} 
\end{align}
\end{theorem}
Although diagonal AdaGrad can perform well on high-dimensional sparse data, the above summations over the $n$ dimensions are symptomatic of its inability to adapt to highly correlated dimensions.

In contrast, full-matrix AdaGrad admits the regret bound (cf.~Theorem 7 of \cite{duchi2011adaptive})
\begin{theorem} \label{thm:full-regret}
\begin{align} \label{eqn:full-regret}
\mathcal{R}(f_1, \ldots, f_T) 
\leq \frac{\delta}{\eta} \|x^*\|_2^2
                     + \frac{1}{2 \eta} \max_{t \in [T]} \|x^* - x_t\|_2^2 \tr(G_T^{1/2})
                     + \eta \tr(G_T^{1/2}) .
\end{align}
\end{theorem}
The above result, depending primarily on the trace of the covariance of the gradients, can exploit high correlations among the dimensions of points in a data sequence. We will show that, in certain situations of interest, CompAdaGrad can come close to the above regret guarantee at a small fraction of the computational complexity.

By design, it is quite straightforward to work out a regret bound for CompAdaGrad by leveraging the existing analysis of both full-matrix and diagonal AdaGrad from \cite{duchi2011adaptive}. Although in the context of concentration inequalities it is important to use the SRHT scaled as $\Pi = \sqrt{\frac{n}{k}} R H \Sigma$, in our analysis we instead analyze a variant of CompAdaGrad that is defined by replacing $\Pi$ with the unscaled $\tilde{\Pi} := R H \Sigma$ (which notably satisfies $\tilde{\Pi} \tilde{\Pi}^T = I$). The following regret bound is for this variant of CompAdaGrad. Also, we set $\delta_r = \delta_c = \delta$ because it simplifies the presentation. 
\begin{theorem} \label{thm:compressed-regret}
CompAdaGrad with learning rate $\eta > 0$ and $\delta > 0$ satisfies
\begin{align} \label{eqn:compressed-regret}
\mathcal{R}(f_1, \ldots, f_T) 
\leq 
&\frac{\delta}{2 \eta} \|x^* - x_1\|_2^2 \nonumber \\
&\frac{1}{2 \eta} 
        \left( 
            \max_{t \in [T]} \| P (x^* - x_t) \|_2^2 
            \tr \left( (\tilde{\Pi} G_T \tilde{\Pi}^T)^{1/2} \right) 
            + \max_{t \in [T]} \| P^\perp (x^* - x_t) \|_\infty^2 \| Z^\perp \|_{2,1} 
        \right) \nonumber \\
       &+ \eta \left( 
               \tr \left( (\tilde{\Pi} G_T \tilde{\Pi}^T)^{1/2} \right) 
               + \| Z^\perp \|_{2,1} 
           \right) ,
\end{align}
where $Z^\perp = (P^\perp g_1 \, \ldots \, P^\perp g_T)^T$ and $A \mapsto \| A \|_{2,1}$ is the sum of the $\ell_2$ norms of the columns of $A$.
\end{theorem}
The proof can be found in \cref*{appendix:regret}.

Note that in the case where the data occupies a low-dimensional subspace and the SRHT preserves the action within this subspace, the above bound is similar to the regret bound for full-matrix AdaGrad \eqref{eqn:full-regret}. However, even when the data sequence is not so easy, \cref{thm:compressed-regret} still offers a fall-back guarantee based on the action in the orthogonal complement. In the event that the dimensions of the gradients are uncorrelated and the gradients do not occupy a low-dimensional subspace, the guarantee for diagonal AdaGrad provided by \cref{thm:diagonal-regret} could be better than the guarantee for CompAdaGrad provided by \cref{thm:compressed-regret}. 





\section{Computations}
\label{sec:computations}

In this section, we show two important composite regularizers for which it is possible to compute the updates steps for CompAdaGrad: the squared $\ell_2$ regularizer and the $\ell_1$ regularizer. 
Some of the results below rely upon the following conjecture which we hope to affirm in the long version.
\begin{conjecture} \label{conjecture:k-sparse}
The $n$-dimensional Walsh-Hadamard Transform of an $r$-sparse vector can be computed in time $O(n \log r)$.
\end{conjecture}
For any results that rely on the conjecture for some variable (e.g.~$r$) indicating the sparsity level, we present the results instead with a \emph{primed} version of the variable (e.g.~$r'$) with the understanding that $r' = r$ if the conjecture is true and $r' = n$ otherwise.

Regardless of the veracity of \cref{conjecture:k-sparse}, we do however prove the following weaker result.
\begin{theorem} \label{thm:1-sparse}
The $n$-dimensional Walsh-Hadamard Transform of a $1$-sparse vector can be computed in time $O(n)$.
\end{theorem}
The proof is constructive, and the algorithm and its analysis can be found in \cref*{appendix:1-sparse-proof}.

\subsection{CompAdaGrad with the squared $\ell_2$ composite regularizer}

An update for squared $\ell_2$ composite mirror descent with the compressed Bregman divergence can be written in the form
\begin{align*}
\min_x \eta \langle g_t, x \rangle 
            + \frac{1}{2} \left\| \Pi (x- x_t) \right\|_{K_t}^2 
            + \frac{\tau}{2} \left\| P^\perp (x - x_t) \right\|_{D_t}^2 
            + \frac{\eta \lambda}{2} \|x\|_2^2 ,
\end{align*}
where $K_t = (\Pi G_t \Pi^T + \delta_r I)^{1/2}$ and $D_t = \mathrm{diag}(G^\perp_t)^{1/2} + \delta_c I$.

To simplify, we define $g := \eta g_t$, $K := K_t$, and $D = \tau D_t$, and we replace $\eta \lambda$; the above is then
\begin{align} \label{eqn:squared-ell2-simplified}
\min_x \langle g, x \rangle 
            + \frac{1}{2} \left\| \Pi (x- x_t) \right\|_K^2 
            + \frac{1}{2} \left\| P^\perp (x - x_t) \right\|_D^2 
            + \frac{\lambda}{2} \|x\|_2^2 .
\end{align}
Since $P$ is the orthogonal projector corresponding to the low-dimensional mapping $\Pi$, the above can be written equivalently as
\begin{align*}
\min_x \left\{
  \textcolor{dark-blue}{
    \langle P g, x \rangle 
    + \frac{1}{2} \left\| P (x- x_t) \right\|_{\Pi^T K \Pi}^2 
    + \frac{\lambda}{2} \|P x\|_2^2
  } 
  + \textcolor{dark-red}{
    \langle P^\perp g, x \rangle 
    + \frac{1}{2} \left\| P^\perp (x - x_t) \right\|_D^2
    + \frac{\lambda}{2} \|P^\perp x\|_2^2
  }
\right\} .
\end{align*}


From the above final rewriting, it is clear that the optimization decouples over the two subspaces, with the minimizer of the above problem $x^*$ being equal to the sum of
\begin{align} \label{eqn:problem-parallel}
&&& x^*_\parallel := 
  \argmin_{x \in \mathrm{Im}(P)} \left\{ 
    \textcolor{dark-blue}{
       \langle P g, x \rangle 
      + \frac{1}{2} \left\| x - P x_t \right\|_{\Pi^T K \Pi}^2 
      + \frac{\lambda}{2} \|x\|_2^2
    }
\right\} && \\
\text{and} &&& x^*_\perp :=
\argmin_{x \in \mathrm{Im}(P^\perp)} \left\{ 
  \textcolor{dark-red}{
    \langle P^\perp g, x \rangle 
    + \frac{1}{2} \left\| x - P^\perp x_t \right\|_D^2
    + \frac{\lambda}{2} \|x\|_2^2 
   }
    \right\} . && \label{eqn:problem-perp}
\end{align}


As shown in \cref*{appendix:computational}, the solution to \eqref{eqn:problem-parallel} is
\begin{align}
x^*_\parallel = (\Pi^T K \Pi + \lambda I)^{-1} (\Pi^T K \Pi x_t - P g) . \label{eqn:unconstrained-constrained}
\end{align}
This can be computed efficiently as follows; the proof can be found in \cref*{appendix:computational}.
\begin{lemma} \label{lemma:computation-squared-ell2-parallel}
$x^*_\parallel $ can be computed as
\begin{align} \label{eqn:computation-squared-ell2-parallel}
x^*_\parallel 
&= \Pi^T \left( \frac{n}{k} K + \lambda I \right)^{-1} \left( K \Pi x_t - \frac{k}{n} \Pi g \right)
\end{align}
in time $O(n \log k' + k^3)$.
\end{lemma}


To solve \eqref{eqn:problem-perp}, we take the dual. First, observe that \eqref{eqn:problem-perp} can be rewritten as
\begin{align*}
\begin{aligned}
&\min_x 
& & \langle P^\perp g, x \rangle 
       + \frac{1}{2} \left\| x - P^\perp x_t \right\|_D^2
       + \frac{\lambda}{2} \|x\|_2^2 \\
&\,\,\text{s.t.} 
& & \Pi x = \mathbf{0} .
\end{aligned}
\end{align*}

The Lagrangian is
\begin{align*}
\mathcal{L}(x, \nu) = 
  \langle P^\perp g, x \rangle 
  + \frac{1}{2} \left\| x - P^\perp x_t \right\|_D^2
  + \frac{\lambda}{2} \|x\|_2^2 
  + \langle \nu, \Pi x \rangle .
\end{align*}

\begin{lemma} \label{lemma:computation-squared-ell2-perp}
Problem \eqref{eqn:problem-perp} can be solved as
\begin{align} \label{eqn:x-in-terms-of-nu}
x^*_\perp = (D + \lambda I)^{-1} (-P^\perp g + D P^\perp x_t - \Pi^T \nu^*) 
\end{align}
with
\begin{align} \label{eqn:computation-for-nu}
\nu^* = 
\left( \Pi B \Pi^T \right)^{-1} 
\Pi B (-P^\perp g + D P^\perp x_t - D B y - \lambda B y + y) ,
\end{align}
for $B = (D + \lambda I)^{-1}$ and $y = -P^\perp g + D P^\perp x_t$. 
These computations can be completed in time $O(n k \log k)$.
\end{lemma}
The proof can be found in \cref*{appendix:computational}.



\subsection{CompAdaGrad with the $\ell_1$ composite regularizer}

We first sketch the LARS algorithm \citep{efron2004least}. We then show how the computations can be done efficiently for CompAdaGrad.

\paragraph{Re-expression as a LASSO problem.}

Using the same simplifications as in \eqref{eqn:squared-ell2-simplified}, the update step is
\begin{align*}
\argmin_x \langle g, x \rangle 
            + \frac{1}{2} \left\| x- x_t \right\|_A^2 
            + \lambda \|x\|_1 .
\end{align*}
for the symmetric matrix $A = \Pi^T K \Pi + P^\perp D P^\perp$. The above can be re-expressed as
\begin{align} \label{eqn:l1-update}
  x_{t+1} = \argmin_x \left\{ 
                                      \langle u, x \rangle 
                                      + \frac{1}{2} \langle x, A x \rangle 
                                      + \lambda \|x\|_1 
                                  \right\} ,
\end{align}
for $u = g - A x_t$. Note that $A$ is positive definite whenever $\delta_r, \delta_c > 0$.

The problem \eqref{eqn:l1-update} can be expressed as a LASSO problem, as the optimal objective value is equal to
\begin{align*}
\min_x \frac{1}{2} \|x\|_A^2 - \langle -A^{-1} u, x \rangle_A + \frac{1}{2} \left\| -A^{-1} u \right\|_A^2 + \lambda \|x\|_1 
&\equiv 
\min_x \frac{1}{2} \left\| x - (-A^{-1} u) \right\|_A^2 + \lambda \|x\|_1 \\
&\equiv 
\min_x \frac{1}{2} \left\| A^{1/2} x - (-A^{-1/2} u) \right\|^2 + \lambda \|x\|_1 .
\end{align*}




\paragraph{Efficient computations}

The standard LARS algorithm takes as input a matrix of covariates $X$ and targets $y$. In our case, $X = A^{1/2}$ is too expensive to compute since $A \in \mathbb{R}^{n \times n}$, while $y = A^{-1/2} u$ is similarly too expensive to compute. Therefore, we cannot just run the usual LARS algorithm but instead have to find efficient ways to perform some of the algorithm's internal computations.

The two computations for LARS that need to be handled differently are the computation of 
(a) the correlation of the covariates with the current residual; 
and 
(b) the entries of the Gram matrix for doing Cholesky Insert operations.

For both of the above, a certain $k$-by-$k$ matrix $Q$ arises in the computations which can be pre-computed and re-used for the entire run of LARS. $Q$ is defined as 
$\frac{n}{k} K + R H \Sigma D \Sigma H R^T$, or equivalently as $\frac{n}{k} K + R H D H R^T$. The second term can computed in time $O(n k \log k)$, in parallel over columns, precisely like $\Pi B \Pi^T$ from \eqref{eqn:computation-for-nu}, as explained in the proof of \cref{lemma:computation-squared-ell2-perp}.

Given a current hypothesis $\beta$, the correlation of the covariates with the residual can be computed as $X^T(y - X \beta) = A^{1/2} A^{-1/2} u - A^{1/2} A^{1/2} \beta = u - A \beta$. Thus, a matrix vector multiplication is the main work. This operation can be completed in time $O(n \log k' + k^2)$, as shown in \cref*{appendix:matrix-vector}.

When performing a Cholesky Insert (increasing the active set $\Lambda$ by one), we need to compute part of a column of the Gram matrix. If the new dimension is $i$, we need to compute $G_{ii}$ and $G_{ij}$ for each $j \in \Lambda$. Since the Gram matrix $G = A$, we just need to compute $e_i^T A e_j$ for each $j \in \Lambda$. 

To compute $G_{ii}$, observe that
\begin{align} \label{eqn:Gram-ii}
G_{ii} = A_{ii} = d_i \langle R H e_i, Q R H e_i \rangle - 2 d_i \frac{k}{n} ,
\end{align}
To compute \eqref{eqn:Gram-ii}, we first compute $R H e_i$ in $O(k \log n)$ and store this for use in future rounds. The additional cost for computing $Q R H e_i$ is then $O(k^2)$, and we re-use this result in \eqref{eqn:Gram-column}. So the cost is $O(k \log n + k^2)$. 
To compute $G_{i,\Lambda}$, we compute for each $j \in \Lambda$
\begin{align} \label{eqn:Gram-column}
G_{ij} = \sigma_i \sigma_j \left( \langle R H e_j, Q R H e_i \rangle - (d_i + d_j) \langle R H e_j, R H e_i \rangle \right) .
\end{align}
Computing \eqref{eqn:Gram-column} can be done in $O(|\Lambda| k)$ since we have already stored $R H e_j$ for all $j \in \Lambda$ and already computed $Q R H e_i$.





\section{Experiments}
\label{sec:experiments}

For all the experiments we used the squared $\ell_2$ regularizer. For CompAdaGrad, we always set $\delta_r$ and $\delta_c$ to be equal and hereafter refer to them both as $\delta$. 
When reporting test error for MNIST and Reuters RCV1, we select the values of $\delta$, $\eta$, $\lambda$, and $\tau$ that attained the lowest online zero-one loss.


\paragraph{MNIST 4 vs 9.}
This dataset was constructed by selecting 400 random prototypes (200 from each class) from the training set and using as features a Gaussian kernel computation of each data point with each of the 400 prototypes. We train on the entire training set for MNIST 4 and 9 and test on the test set for MNIST 4 and 9. 
The results in \cref{fig:mnist} indicate that CompAdaGrad well-outperforms the diagonal method, and as the SRHT dimension increases from 25 to 256, the gains over the diagonal method are all the larger. It is worth mentioning that the CompAdaGrad improves over diagonal AdaGrad even for $k = 25$. We suspect that that CompAdaGrad surpasses diagonal AdaGrad on this task because the features are dense and highly correlated. 




\paragraph{Reuters RCV1.}
We used Reuters RCV1-v2 \citep{lewis2004rcv1}. After stopping, stemming, and retaining only those unigrams and bigrams that occurred at least twice in the corpus, the data consisted of 800,000 documents in 1,889,478 dimensions. We computed gradients in mini-batches of 160 points and performed a hypothesis update from each resulting averaged gradient. We generated 4 random permutations of the data. For each permutation, we train on the first 75\% and test on the last 25\%. Each of the 4 runs is an experiment. 
We report the average test error over the 4 experiments. This test error need not correspond to a single $(\eta, \lambda,\delta,(\tau))$ configuration. 
As shown in \cref{table:reuters}, CompAdaGrad with $k=512$ does not improve upon the diagonal version. We suspect the lack of improvement is because the data is very sparse and does not admit a low-dimensional linear subspace capturing a large amount of the action in the data. Therefore, it does not help much to pick up on correlations.




\paragraph{Foxes and Wolves.}
We grabbed a visual-bag-of-words representation for 829 images of kit foxes (\emph{Vulpes macrotis}) and 1,156 images of red wolves (\emph{Canis rufus}) from ImageNet \citep{russakovsky2015imagenet} (originally from Flickr). The original features are 1000 visual words which represent 1000 clusters of a random subset of 10 million SIFT features. 
We computed visual word bigrams by selecting\footnote{We selected 0.002 based on the quantiles of the distance distribution of all pairs of visual words in images.} a radius of 0.002 for visual words to be considered collocated (based on $(x,y)$ coordinates for the visual words); this led to 238,822 bigrams which occurred at least once in the 1,985 images. The final dataset for learning consisted of the unigram counts and bigram counts, constituting 239,822 features.

We trained on the first 75\% of a random permutation of the data and tested on the remainder. 
Because the number of instances in this dataset is small relative to the dimension, the online zero-one loss is not a sensible rule for parameter tuning as a relatively large number hypotheses contributing to the online loss are from early rounds where not much learning has taken place. We therefore tuned the parameters based on the online training zero-one loss of the final hypothesis of the online learning algorithm. The results presented in \cref{table:foxes-wolves} are inconclusive. Both diagonal AdaGrad and CompAdaGrad with $k=256$ obtain the same zero-one test risk. This either could be due to the hardness of the task, the small sample size, or the fact that the features are still quite sparse due to the visual bag-of-words bigram representation.


\begin{figure}
\begin{floatrow}
\capbtabbox{
\begin{tabular}{c c}
\toprule
Method                   & Zero-one test risk \\
\midrule
Diagonal            &  0.056084 \\
CompAdaGrad-512  & 0.056155 \\ 
\bottomrule
\end{tabular}
}{
  \caption{\label{table:reuters} Reuters RCV1 test error.}
}
\capbtabbox{
\begin{tabular}{c c}
\toprule
Method      & Zero-one test risk \\
\midrule
Diagonal   &  0.2696 \\
CompAdaGrad-256 & 0.2696 \\ 
\bottomrule
\end{tabular}
}{
  \caption{\label{table:foxes-wolves}  Foxes and Wolves test error}
}
\end{floatrow}
\end{figure}


\begin{figure}
\begin{floatrow}
\ffigbox{
\includegraphics[width=75mm]{mnist_k_vs_test_error.pdf}
}{
  \caption{\label{fig:mnist} MNIST 4 vs 9 test error.}
}
\ffigbox{
\includegraphics[width=40mm]{kit_fox.jpg}
\includegraphics[width=40mm]{red_wolf.jpg}
}{
  \caption{A kit fox and a red wolf}
}
\end{floatrow}
\end{figure}




\section{Conclusion}
\label{sec:discussion}

We have introduced a new adaptive gradient method, CompAdaGrad, which can obtain regret bounds competitive with full-matrix AdaGrad under easier adversaries that put most of the interesting action in a low-dimensional subspace, while maintaining a fallback regret bound in the case that the adversary is not easy. CompAdaGrad also admits efficient updates for certain choices of the composite regularizer. In preliminary experiments, we demonstrate that CompAdaGrad can sometimes obtain lower risk as compared to diagonal AdaGrad, but this outcome appears to be tied to the density and more importantly the correlation of the features. In the future, we intend to apply CompAdaGrad to massive datasets with dense, highly correlated features. Along these lines, one promising application for future work is to incorporate CompAdaGrad into the training of deep learning methods.


\subsubsection*{Acknowledgments}

This work is supported in part by the Australian Research Council Discovery Project DP0987773 and NICTA, which is funded by the Australian Government through the Department of Communications and the Australian Research Council through the ICT Centre of Excellence Program.


\newpage

\renewcommand{\refname}{{\normalsize References}}

