Online Learning: Sufficient Statistics and the Burkholder Method

Introduction

Two of the most appealing features of online learning methods are (a) robustness, due to the absence of assumptions on the data-generating process, and (b) the ability to efficiently incorporate data on the fly. According to this latter desideratum, online methods should not store all the data observed so far in memory, but instead maintain some “compressed” representation, sufficient for making online predictions. The focus of this work is the study of such sufficient statistics for online learning, and the design of computationally efficient methods that employ them.

It is natural to turn to Statistics for inspiration: a classical notion of sufficient statistics (Fisher, 1922) ensures that a statistician can search for methods that work on “compressed” representations of the data. Sufficient statistics have also been studied in sequential decision theory (Bahadur et al., 1954). However, the very notion of sufficiency is inherently tied to the posited probabilistic model, and the corresponding notion for arbitrary sequences—as postulated by the above desideratum (a)—is all but obvious.

The current theory of online learning offers little guidance as to what summaries of past data should be recorded by an online algorithm. For instance, the Exponential Weights algorithm (Vovk, 1990; Littlestone and Warmuth, 1994) keeps in memory the cumulative losses of the experts, while the general potential-based forecaster (Cesa-Bianchi and Lugosi, 2006) updates the cumulative regret of the algorithm with respect to each expert. The methods from the Follow-the-Regularized-Leader family (also known as Dual Averaging methods) work with the sum of gradients of convex functions, while the Online Newton Step (Hazan et al., 2007) method and the Vovk-Azoury-Warmuth forecaster (Cesa-Bianchi and Lugosi, 2006) also store the “covariance” matrix of outer products. The well-known adaptive gradient descent procedure (e.g. (Rakhlin and Sridharan, 2015)) tunes the step size of online gradient descent according to the cumulative squared norms of gradients, a statistic that appears to be necessary for achieving the adaptive bound, while the ZigZag method of Foster et al. (2017b) keeps track of a sign-transformed sequence of the gradients to achieve the empirical Rademacher complexity as a regret bound.

The question of sufficient statistics for online methods appears to be unexplored and poorly understood, and it will take significant effort to answer it. In this paper we propose an approach that appears to be general yet, inevitably, incomplete. We propose a definition that brings many existing methods under the same umbrella, and allows us to develop new efficient strategies that have been out of reach. The key workhorse for our development is the Burkholder method, studied in probability theory and harmonic analysis.

Beyond studying a notion of sufficient statistic for online methods, our work can be seen as providing a further understanding of emerging connections between online learning, martingale inequalities, and deterministic geometric quantities. At the risk of being imprecise, let us describe the bird’s-eye view of our overall approach:

Based on the definition of sufficient statistics for online methods, we first derive the corresponding martingale inequalities with the help of the minimax theorem. We then turn to the Burkholder method, and show equivalence of these martingale inequalities with sufficient statistics and existence of a special Burkholder (or Bellman) function, a purely geometric object. We then use this function for the problem of online prediction, thus completing the circle. Crucially, the sufficient statistics we start with are reflected in the Burkholder function, and, hence, the proposed algorithm is only required to update these compressed representations of the data. We exhibit the power of this approach by deriving several new efficient prediction methods.

We remark that (Foster et al., 2017b) studied a particular case of the Burkholder method related to the UMD property. The present work shows that the approach can be generalized significantly and used to address the question of sufficient statistics. For example, the explicit construction of the UMD-style Burkholder function for certain matrix prediction problems was noted to be challenging in (Foster et al., 2017b) and indeed does not appear to be known in the analysis community (Osękowski, 2017). In spite of this, the approach in the present paper uses different sufficient statistics to attain the same results with an explicit (and efficient) Burkholder function.

Problem Setup and Sufficient Statistics

for any sequence $(x_{1},y_{1}),\ldots,(x_{n},y_{n})$, where the expectation is with respect to forecaster’s randomization. The choice of $\phi$ models the problem at hand, and examples in this paper focus on

Since there is no probabilistic model for data in the online learning setting, the notion of “sufficiency” has to be tied to the particular choice of $\phi$. It is then tempting to define a sufficient statistic as a “compressed” representation which may be used by some strategy to ensure (1). While natural, such a definition does not provide any additional structure to narrow the search for an algorithm.

for any sequence $x_{1},{\widehat{y}}_{1},y_{1},\ldots,x_{n},{\widehat{y}}_{n},y_{n}$. We refer to $(\mathbf{T},V)$ as a sufficient statistic pair.

In Section 9, we consider a more general non-additive definition. All examples in this paper, however, are already covered by Definition 1, and we will drop the word “additive” for now. We will also make the mild assumption that there exists $(x^{0},y^{0})\in\mathcal{X}\times\mathcal{Y}$ such that $\mathbf{T}(x^{0},y^{0},0)=0\in\mathcal{T}$.

Consider $\phi$ as in Eq. (2) with $\mathcal{F}$ as the set of linear functions $f(x)=\left\langle f,x\right\rangle$ for $f\in\Delta_{d}$, with $\mathcal{X}=^{d}$, and with non-adaptive rate $\mathcal{A}\vcentcolon=c\sqrt{n\log d}$. Then the left-hand-side of (3) can be upper bounded via linearization of the convex loss by

Martingale Inequalities and the Burkholder Method

The notion of sufficient statistics introduced in the previous section will only be useful if we exhibit a prediction strategy employing this type of representation. Before doing so, we need to build the two bridges outlined in the diagram on the previous page. These correspond to Lemma 1 and Lemma 2 below.

First, we show that existence of a prediction strategy that guarantees the regret inequality (1) for all sequences can be ensured by checking a martingale inequality involving only the sufficient statistics. The key tool in proving the lemma is the minimax theorem.

Note that in a slight abuse of notation, we will concatenate the first two arguments of any sufficient statistic $\mathbf{T}$ and write them as $z_{t}\vcentcolon=(x_{t},{\widehat{y}}_{t})$ going forward.

holds for any $\boldsymbol{z}$ and any law of $\delta$. Moreover, when $\alpha\mapsto V(\tau+\mathbf{T}(z,\alpha))$ is convex for any $z\in\mathcal{X}\times\mathcal{Y},\tau\in\mathcal{T}$, it is enough to check (4) for $\delta_{t}=\epsilon_{t}\cdot L$, $t=1,\ldots,n$, where $\epsilon_{t}$s are independent Rademacher random variables.

Lemma 1 is in the spirit of results in (Rakhlin et al., 2010, 2014; Foster et al., 2015) whereby existence of a strategy (or, “learnability”) is certified non-constructively by proving a martingale inequality.

The next lemma provides a key insight into existence of certain deterministic functions with “geometric” properties (in particular, restricted concavity) and can be seen as a variation on the so-called Burkholder method (also sometimes called the Bellman function method; see (Osękowski, 2012) for the detailed treatment and examples).

Let $\delta=(\delta_{1},\ldots,\delta_{n})$ be a $[-L,L]$-valued martingale difference sequence with joint law $\boldsymbol{p}$ and let $\boldsymbol{z}=(\boldsymbol{z}_{1},\ldots,\boldsymbol{z}_{n})$ be a predictable process ($\boldsymbol{z}_{t}:[-L,L]^{t-1}\to\mathcal{X}\times\mathcal{Y}$) with respect to $\mathcal{G}_{t-1}=\sigma(\delta_{1},\ldots,\delta_{t-1})$. The probabilistic inequality

For any $\tau\in\mathcal{T}$, $\mathbf{U}(\tau)\geq V(\tau)$.

For any $\tau\in\mathcal{T}$, $z\in\mathcal{X}\times\mathcal{Y}$, and any mean-zero distribution $p$ on $[-L,L]$,

Furthermore, if for any $\tau\in\mathcal{T}$ and $z\in\mathcal{X}\times\mathcal{Y}$ the mapping $\alpha\mapsto V(\tau+\mathbf{T}(z,\alpha))$ is convex, then condition (5) can be relaxed with $\delta$ replaced by independent Rademacher random variables $(\epsilon_{1},\ldots,\epsilon_{n})$. In this case the following property holds for $\mathbf{U}$:

The mapping $\alpha\mapsto\mathbf{U}(\tau+\mathbf{T}(z,\alpha))$ is convex and (property $3^{o}$ is replaced by):

where $\epsilon$ is a Rademacher random variable.

We call any function $\mathbf{U}$ satsifying the properties $1^{o}$, $2^{o}$, and $3^{o}$/$3^{\prime}$ a Burkholder function for $(\mathbf{T},V)$.

In plain language, the lemma says that one can prove a certain probabilistic inequality if and only if there is a deterministic function with certain properties. The proof of the lemma, in fact, provides a construction for the “optimal” function $\mathbf{U}$, but it is not clear how to directly evaluate the optimal function efficiently (see Section 9 for a discussion of the computational prospects of automating this process).

We remark that the Burkholder functions guaranteed by the lemma are not unique, and some may be easier to find than others. We also note that any Burkholder function $\mathbf{U}$ for $(\mathbf{T},V)$ yields another sufficient statistic pair $(\mathbf{T},\mathbf{U})$ guaranteeing the same regret bound. The power of Lemma 2 is to guarantee the existence of a function $\mathbf{U}$ satisfying property $3^{o}$ when the function $V$ under consideration does not have these properties. This situation, where the choice of $V$ is “obvious” but the discovery of $\mathbf{U}$ requires nontrivial analysis, occurs frequently when one attempts to design adaptive algorithms for a new task.

for any $\mathcal{X}$-valued predictable process $(\boldsymbol{x}_{t})$ with respect to the dyadic filtration $\mathcal{F}_{t-1}=\sigma(\epsilon_{1},\ldots,\epsilon_{t-1})$. Lemma 2 guarantees existence of a Burkholder function $\mathbf{U}$, and property $3^{\prime}$ reads

and, thus, $x\mapsto\mathbf{U}(x,0)$ is smooth with respect to the norm and its dual is strongly convex with respect to $\left\|\cdot\right\|_{\star}$. In summary, the Burkholder method captures the geometry necessary for defining Gradient-Descent-style methods, as the dual of $\mathbf{U}(x,0)$ provides the universal construction for a strongly convex function with respect to a given norm. See Srebro et al. (2011) for an in-depth treatment of Mirror Descent and universal construction of strongly convex regularizers.

What should an algorithm designer take away from the developments thus far? Let us provide a brief summary. One first starts with a desired regret inequality for the online learning setting, such as (1). The next step is to find an upper bound on the regret inequality that can be expressed in terms of additive sufficient statistics. Lemma 1 and Lemma 2 then guarantee, respectively, that there is a certain martingale inequality that must hold if the upper bound in terms of sufficient statistics is achievable, and that there must exist a Burkholder function with certain geometric properties. In the next section we close the loop by showing that whenever such a Burkholder function can be evaluated efficiently, it yields an efficient algorithm that only keeps the sufficient statistics in memory.

Before proceeding, we briefly remark that the sufficient statistics expansion $V$ also serves as a lower bound on the regret inequality, then there is a formal sense in which the special Burkholder function exists if and only if there exists a strategy achieving the original regret inequality of interest; this is the focus of Section 8. In the reverse direction, one may start with a probabilistic inequality and determine the statistics that should be used to define the online prediction goal.This was precisely the approach used to develop a matrix prediction method we present in Section 6.

The Burkholder Algorithm

Example 3 in the previous section already suggests that the Burkholder $\mathbf{U}$ functions may capture “geometry” needed for forming online predictions. The example is also suggesting that strong convexity and smoothness may not be sufficient for prediction problems where more complicated sufficient statistics (beyond the norm of the sum and the sum of the squared norms) are necessary. Thankfully, the function $\mathbf{U}$ reflects any sufficient statistics for the online prediction problem. We can now define a “universal” algorithm that has access to $\mathbf{U}$.

To define the algorithm, first let $\zeta_{t-1}=\sum_{j=1}^{t-1}\mathbf{T}(x_{j},{\widehat{y}}_{j},\delta_{j})$ be the cumulative value of the sufficient statistic computed after $t-1$ rounds. Since $\mathcal{T}$ is a vector space, $\zeta_{t}$s are elements of $\mathcal{T}$, and this is the only information the algorithm stores in memory.

The Burkholder algorithm is defined by the update:

For a sufficient statistic pair $(\mathbf{T},V)$, if there exists a Burkholder function $\mathbf{U}$ satisfying Properties $1^{o}$, $2^{o}$, and $3^{o}$ (or $3^{\prime}$) of Lemma 2, then the Burkholder algorithm (7) obtains the regret bound (1) in expectation for all sequences $(x_{1},y_{1}),\ldots,(x_{n},y_{n})$.

To check that the above strategy works, fix a value $x_{t}$ and observe that by the minimax theorem,The minimax theorem can be applied because $\Delta_{\mathcal{Y}}$ is compact; see discussion in the proof of Lemma 1.

Applying this argument from $t=n$ down to $t=0$ yields the value $\mathbf{U}(0)\leq 0$. ∎

Implementation When $\mathbf{U}$ is convex in ${\widehat{y}}$ and the set $\mathcal{Y}$ is convex, the minimum over $q$ is achieved at a deterministic strategy, and so the minimization problem simplifies to $\operatorname*{arg\,min}_{{\widehat{y}}\in\mathcal{Y}}$. All of the Burkholder functions we explore in this paper enjoy this or similar simplified and efficient representations for the algorithm. These simplifications are detailed in Appendix B. Even without convexity, the general form for the Burkholder algorithm in (7) can be implemented efficiently via convex programming assuming only Lipschitz continuity of $\mathbf{U}$.

Suppose $\mathbf{U}$ is Lipschitz and bounded and can be evaluated in constant time. Then (7) can be implemented approximately so as to achieve the regret inequality (1) up to additive constants in time $\textrm{poly}(n)$.

See Proposition 8 in the appendix for a precise version of this statement.

Example: Fast and Easy Parameter-Free Online Learning

To ease notational burden, we will assume the loss is $1$-Lipschitz in this section. We will efficiently obtain a regret bound of the form

for any such smooth norm. We begin by stating a sufficient statistic representation for the problem. This is based on a familiar potential which has appeared in previous works on parameter-free online learning (e.g. (McMahan and Orabona, 2014)) in Hilbert spaces; we extend it to any smooth norm, then use it in the Burkholder method to provide the first linear time/linear space algorithm for parameter-free learning with general smooth norms in online supervised learning.Since the original submission of this paper, the independent work of (Cutkosky and Orabona, 2018) has provided an algorithm with a similar regret guarantee and computational efficiency.

Suppose we are interested in an adaptive regret bound of

yield a sufficient statistic pair for the regret bound $\mathcal{A}$.

Because the regret bound we provide is not horizon independent unlike previous examples, it will be convenient to allow time-indexed Burkholder functions $(\mathbf{U}_{t})_{t\leq{}n}$. This indexing is of purely notational convenience, as time-dependent Burkholder functions fit squarely into the algorithmic framework of Lemma 3 by enlarging $\mathcal{X}$ to $\mathcal{X}\times{}\left[n\right]$. Nonetheless, we recap the analogous properties for time-dependent Burkholder functions in the proof of the following theorem.

Suppose $c=1$, $a=\beta$, and $\gamma=1/\sqrt{n}$ in (9). Then

is a family of time-varying Burkholder functions satisfying $1^{o}$, $2^{o}$, and $3^{\prime}$.

This Burkholder function immediately yields both a prediction strategy achieving (8) and a simple probabilistic martingale inequality. We will now state them both. Because $(\mathbf{U}_{t})_{t\leq{}n}$ satisfy additional convexity properties, the strategy is especially efficient (per Appendix B and Lemma 5).

Suppose that $\mathcal{Y}=\left[-B,B\right]$ for some $B>0$. Then the deterministic prediction strategy

Let $\boldsymbol{x}_{t}(\epsilon)\vcentcolon=\boldsymbol{x}_{t}(\epsilon_{1},\ldots,\epsilon_{t-1})$ be adapted to the filtration $\mathcal{F}_{t-1}=\sigma(\epsilon_{1},\ldots,\epsilon_{t-1})$ for Rademacher random variables $\epsilon_{1},\ldots,\epsilon_{n}$, and let $\left\|\boldsymbol{x}_{t}\right\|\leq{}1$ almost surely, where $\left\|\cdot\right\|$ is a $\beta$-smooth norm. Then it holds that

Example: Matrix Prediction

In a search for an adaptive bound on regret, we inspect the adaptive bound for the vector case. The direct analogue for matrices would be a bound proportional to $\left(\sum_{t=1}^{n}\left\|X_{t}\right\|^{2}_{\sigma}\right)^{1/2}$, and indeed such a bound is possible with Matrix Exponential Weights (Hazan et al., 2012, Theorem 13).With more work it is possible to obtain a bound of $\left(\max_{t}\left\|X_{t}\right\|_{\sigma}\cdot\left\|\sum_{t=1}^{n}X_{t}\right\|_{\sigma}\right)^{1/2}$; this is still weaker than our result, and seems to only be possible when the constraint set and $X_{t}$s are restricted to be positive-semidefinite. However, matrix version of Khintchine inequality, as well as matrix deviation inequalities, involve—for the case of random centered self-adjoint matrices—the tighter quantity $\left\|\sum_{t=1}^{n}X_{t}^{2}\right\|^{1/2}_{\sigma}$ (see (Tropp, 2012; Mackey et al., 2014)). Given the correspondence between online regret bounds and martingale inequalities, one may wonder if there is an algorithm that achieves this adaptive bound. We shall exhibit such a method using our approach, and the reader can already guess that $\sum_{t=1}^{n}X_{t}^{2}$ should be part of the sufficient statistic for the online algorithm. We present results for general non-square matrices.

It is well-known that for any matrix $X$, $\lambda_{1}(\mathcal{H}(X))=\left\|X\right\|_{\sigma}.$

With these definitions in place, the desired adaptive regret bound takes the form

form a sufficient statistic pair for the adaptive regret bound $\mathcal{A}_{\eta}$.

Then $\mathbf{U}$ is a Burkholder function, for the pair $(\mathbf{T},V)$ in (12) when $c\geq{}r\log(d_{1}+d_{2})$.

This Burkholder function construction immediately implies both existence of a prediction strategy (via Lemma 3) and that a probabilistic inequality for matrix-values martingales holds. We will present both in detail. The matrix prediction strategy granted by the Burkholder algorithm is particularly simple due to extra convexity properties of $\mathbf{U}$; see Appendix B.

Suppose that $\mathcal{Y}=\left[-B,B\right]$ for some $B>0$. Then the deterministic strategy

Since this regret bound is monotonically increasing with time, it is easy to tune $\eta$ to obtain a fully adaptive strategy.

Let $R=\max_{t}\left\|X_{t}\right\|_{\sigma}$ be known. By tuning $\eta$ through the standard doubling trick, we arrive at a regret bound of

Let us briefly discuss the result. First, the computation in (13) involves an SVD, and does not scale with $t$ since the method only keeps in memory the cumulative statistics. The regret bound gives a sequence-optimal rate for the problem of Online Matrix Completion, where each $X_{t}$ is an indicator $e_{i_{t}}e_{j_{t}}^{\top}$ corresponding to—for example—a user-movie pair for which the learner must predict a score. Here the regret bound obtained by (13) interpolates between the worst-case configuration of the entries $(i_{t},j_{t})$ and “spread-out” (e.g. uniform) sampling of the entries. The result improves on (Foster et al., 2017b), which showed that this type of bound is possible by invoking the UMD inequality for Schatten norms but did not provide an efficient algorithm. See that paper for further discussion of the setting and problem.

For all Paley-Walsh martingale difference sequences $(\epsilon_{t}\boldsymbol{X}_{t}(\epsilon))_{t\leq{}n}$ it holds that

In the special case where $\boldsymbol{X}_{t}(\epsilon)=X_{t}$ is a fixed sequence, this square function inequality (14) recovers the Matrix Khintchine inequality (Mackey et al., 2014), including constants. A similar martingale inequality can be obtained from the Matrix Freedman/Bennett inequalities of Tropp et al. (2011), but this will depend on almost sure bounds on spectral norms of $(\boldsymbol{X}_{t}(\epsilon))_{t\leq{}n}$.

Further Examples

Pisier (1975) used martingale techniques to provide a characterization of super-reflexive Banach spaces as those admitting an equivalent uniformly convex norm. As already described in Example 3, the essential ingredient of this analysis is a construction of a function $\mathbf{U}$ with the desired restricted concavity property (which turns out to be equivalent to uniform smoothness) for the martingale inequality (6). The corresponding notion in the world of online learning is that of an adaptive gradient (or mirror) descent.

Burkholder (1981) provided a geometrical characterization of UMD spaces, and a key ingredient of the approach was to establish existence of (and sometimes to compute in closed form) the function $\mathbf{U}$ with corresponding geometric properties ($\zeta$-convexity, which is equivalent to “zigzag concavity” (Osękowski, 2012)). As shown in (Foster et al., 2017b), in the online learning world the corresponding adaptive regret bound is that of empirical Rademacher averages:

By linearizing the loss, it suffices to use the sufficient statistic $\mathbf{T}(x_{t},{\widehat{y}}_{t},\delta_{t})=(\delta_{t}{\widehat{y}}_{t},\delta_{t}x_{t},\epsilon_{t}x_{t})$ where $(\epsilon_{t})$ is taken to be a sequence drawn by the algorithm. The corresponding martingale inequality is

where the process in the subtracted term is decoupled and $p>1$ is arbitrary. We refer the reader to (Foster et al., 2017b) for more details.

We would like to emphasize that both smoothness/strong convexity (as in Pisier’s work) and the UMD property (as in Burkholder’s work) are two distinct notions with distinct sets of sufficient statistics. Since the fundamental works of Pisier and Burkholder, the so-called “Burkholder method” has been employed to prove a wide range of martingale inequalities and discover the corresponding geometric properties of the special function (Osękowski, 2012; Hytönen et al., 2016). The goal of this paper is to present a unifying approach for working with arbitrary sufficient statistics in online learning, and to show that the Burkholder approach is in fact algorithmic.

2 AdaGrad and Square Function Inequalities

The Burkholder method can be used to recover efficient algorithms that obtain regret bounds in the vein of diagonal AdaGrad and full-matrix AdaGrad (Duchi et al., 2011), with optimal constants. We thank Adam Osękowski for suggesting this example to us (Osękowski, 2017).

$\mathbf{U}_{\textrm{square}}$ satisfies three properties in the vein of Lemma 2: 1. $\mathbf{U}_{\textrm{square}}(x,y)\geq{}\left\|x\right\|_{2}-2y$, 2. $\mathbf{U}_{\textrm{square}}(x,\left\|x\right\|_{2})\leq{}0$, and 3. $\mathbf{U}_{\textrm{square}}(x+d,\sqrt{y^{2}+\left\|d\right\|_{2}^{2}})\leq{}\mathbf{U}_{\textrm{square}}(x,y)+\left\langle\partial_{x}\mathbf{U}_{\textrm{square}}(x,y),d\right\rangle$. This function consequently leads to two algorithms in the style of AdaGrad (Duchi et al., 2011) but with optimal constants, and which we now sketch.

3 Strongly Convex Losses

for some $c>0$. Here we the classical Vovk-Azoury-Warmuth-type bound for strongly convex losses (Vovk, 1998; Azoury and Warmuth, 2001). This example is important because it shows that the Burkholder method in full generality can both obtain fast rates for curved losses and obtain bounds that jointly depend on the comparator and data; the UMD-type Burkholder functions used in Foster et al. (2017b) do not obtain such results. The right sufficient statistic for this problem should be familiar: In addition to storing a sum of gradients, we also store the empirical covariance $\sum_{t=1}^{n}z_{t}z_{t}^{\top}$. We introduce one last piece of notation: For $A\succeq{}0$, $\Psi_{A}(w)=\frac{1}{2}\left\langle w,Aw\right\rangle$.

forms a sufficient statistic pair for the adaptive regret bound $\mathcal{A}_{\lambda}$.

For the sufficient statistic pair $(\mathbf{T},V)$ in Proposition 5, $\mathbf{U}=V$ is a Burkholder function whenever $c\geq{}L^{2}/\rho$.

Note that for this setting the natural choice for $V$ turned out to be a Burkholder function itself.

Necessary Conditions

We now state a simple, yet powerful result that characterizes when existence of a Burkholder function for a sufficient statistic representation pair $(\mathbf{T},V)$ is not only sufficient, but necessary to obtain a particular regret bound.

Let $\delta=(\delta_{1},\ldots,\delta_{n})$ be a $[-L,L]$-valued martingale difference sequence over filtration $\mathcal{F}_{t-1}=\sigma(\delta_{1},\ldots,\delta_{t-1})$ and let $\boldsymbol{z}=(\boldsymbol{z}_{1},\ldots,\boldsymbol{z}_{n})$ be a sequence of functions $\boldsymbol{z}_{t}:[-L,L]^{t-1}\to\mathcal{X}\times\mathcal{Y}$, each viewed as a predictable process with respect to $\mathcal{F}_{t-1}$. Suppose for every such $(\delta,\boldsymbol{z})$ pair there exists a randomized adversary strategy $(x_{t},y_{t})$ that guarantees, for every learner strategy $({\widehat{y}}_{t})_{t\leq{}n}$,

Then, if there exists a strategy $({\widehat{y}}_{t})_{t\leq{}n}$ that achieves the regret bound $\mathcal{A}(f;x_{1:n})$, this implies that

When $\alpha\mapsto V(\tau+\mathbf{T}(z,\alpha))$ is convex for any $z\in\mathcal{X}\times\mathcal{Y},\tau\in\mathcal{T}$, we only require the preceeding inequalities to hold for $\delta_{t}=\epsilon_{t}\cdot L$, $\forall{}t=1,\ldots,n$, where $\epsilon_{t}$s are independent Rademacher random variables. In this case achievability of the regret bound $\mathcal{A}(f;x_{1:n})$ only implies existence of a Burkholder function $\mathbf{U}$ satisfying property $3^{\prime}$, not $3^{o}$.

Let us first consider a natural choice of $V$ for the upper bound in this setting. Linearizing and using symmetry of $\mathcal{W}$, we have

Noting that $\alpha\mapsto{}V(\tau+\mathbf{T}(x,{\widehat{y}},\alpha))$ is convex, Lemma 1 implies that a sufficient condition to achieve the regret bound for any convex $1$-Lipschitz loss is that

where $\boldsymbol{z}$ is any $\mathcal{X}\times{}\mathcal{Y}$-valued predictable process with respect to the Rademacher sequence $\epsilon_{1},\ldots,\epsilon_{n}$.

There exists a Burkholder function $\mathbf{U}$ for the pair $(\mathbf{T},V)$ if and only if the regret bound (18) is achievable.

There exists a Burkholder function for the sufficient statistic pair $(\mathbf{T},V)$ in (19).

Discussion

The core techniques developed in this paper suggest a number of promising future directions and natural extensions.

For the examples in this paper, we exclusively considered benchmark classes $\mathcal{F}$ that were linear, which appears to have made the search for sufficient statistics easier. However, even when one considers a class $\mathcal{F}$ of non-linear functions, the approach of trying to expand the desired regret inequality (which now involves nonlinear $f\in\mathcal{F}$) around a given instance $x$ in terms of some basis may still help to obtain an adequate sufficient statistics. Furthermore, one may enlarge the class $\mathcal{F}$ to make the sufficient statistic search easier. For instance, if we want to learn the class of boolean decision trees of depth $d$, we can exploit that the class can be represented by polynomials of degree $d$ by using the discrete Fourier coefficients of the input instances up to degree $d$ as a sufficient statistic. In summary, for non-linear classes one may still search for sufficient statistics and Burkholder functions by expressing nonlinearities (approximately) via linear combinations of higher-order terms.

This approach is sound in that it will never incorrectly return a function $\mathbf{U}$ that does not satisfy the three properties, but may not be complete a-priori. An interesting direction is therefore to explore whether there are conditions under which this system can indeed be made complete.

Generalized/non-additive sufficient statistics The restriction in Definition 1 that sufficient statistics combine additively can be relaxed. A more general form is as follows. First, define a representation space $\mathcal{T}$. The function $\mathbf{T}$ now takes the form:

The restricted concavity condition for $\mathbf{U}$ under this definition becomes

Properties $1^{o}$ and $2^{o}$ of Lemma 2 remain the same. This generalized notion of a sufficient statistic allows us to move beyond additive updates — $\mathbf{T}$ can multiply $z$ with elements of $\mathcal{T}$, for example — but still restricts storage to the space $\mathcal{T}$ and is fully compatible with the Burkholder method and general algorithm framework. The generalizations of the equivalence theorem (Lemma 2) and the Burkholder algorithm (Lemma 3) for this notion of sufficient statistic hold as well.

Acknowledgements

We thank Adam Osękowski for helpful discussions and for suggesting the example in Section 7.2.

References

Appendix A Proofs

We will use the notation \left\llangle\ldots\right\rrangle_{t=1}^{n} to denote the repeated application of operators, with the outer application corresponding to $t=1$. Existence of a randomized strategy for (1) is equivalent to the following quantity being non-positive:

The last expression can be written in the functional form as

We first establish existence of $\mathbf{U}$ under the premise of the lemma. The construction is given by

Then under the probabilistic inequality that is the premise of the lemma, it holds that

Next, by our assumption, $\exists z^{0}$ s.t. $\mathbf{T}(z^{0},0)=0$, we can lower bound the supremum in (20) by considering a particular $\boldsymbol{z}$ that is constant $\boldsymbol{z}_{t}\vcentcolon=z^{0}$ for all $t$, and a distribution for $\delta_{t}$ that only places mass on the singleton . This yields a lower bound

To verify the third condition, observe that for any zero-mean random variable $\alpha$ with distribution $p$ supported on $[-L,L]$,

For the converse, assume we have a function $\mathbf{U}$ satisfying the three properties. Fix any $\boldsymbol{z}$ and $\boldsymbol{p}$ of length $n$. In this case, by property $2^{o}$, the following inequality holds deterministically:

By property $3^{o}$, we have that for any time $s$,

Continuing this argument all the way to $t=0$ and using property $1^{o}$,

A.2 Proofs from Section 5

We define a potential function that will eventually be used in the construction of the Burkholder function $\mathbf{U}$ we provide for $V$. As discussed in the main body, a variant of this potential was first introduced by McMahan and Orabona (2014) for the special case of Hilbert spaces. Let $\Psi(x)=\frac{1}{2}\left\|x\right\|^{2}$ (not necessarily a Hilbert space norm) and define

From (McMahan and Orabona, 2014, Lemma 14), along with the additional fact that $(f(\left\|\cdot\right\|))^{\star}=f^{\star}(\left\|\cdot\right\|_{\star})$ for general dual norm pairs, it holds that

This is all we need to establish the result. We proceed as follows

Since $\mathbf{U}$ depends on time, we generalize the properties of Lemma 2 to

For any $\tau\in\mathcal{T}$, $\mathbf{U}_{n}(\tau)\geq V(\tau)$

For any $\tau\in\mathcal{T}$, $z\in\mathcal{X}\times\mathcal{Y}$, and any mean-zero distribution $p$ on $[-L,L]$, and any $t\geq{}1$

For any $\tau\in\mathcal{T}$, $z\in\mathcal{X}\times\mathcal{Y}$, and any $t\geq{}1$,

where $\epsilon$ is a Rademacher random variable.

Recall that for simplicity we assume $L=1$ and $\mathcal{X}$ is a unit ball: $\left\|x\right\|\leq{}1$. Let $\Psi(x)=\frac{1}{2}\left\|x\right\|^{2}$, where we have assumed that $\beta$-smoothness of $\Psi$:

and $F_{0}=\gamma\exp\left(\frac{1}{2}\sum_{t=1}^{n}\frac{1}{t}\right)$. Note that $F_{n}$ here is the same as in the proof of Proposition 2.

where $F_{t}^{\star}$ is as defined as in the proof of Proposition 2. We proceed to establish the three properties of $\mathbf{U}$ from Lemma 2. Property $2^{o}$ holds since $V=\mathbf{U}_{n}$. We will show property $3^{\prime}$ first, then conclude with property $1^{o}$. Note that $\alpha\mapsto{}\mathbf{U}_{t}(\tau+\mathbf{T}(z,\alpha))$ is convex with respect to $\alpha$, and so it indeed suffices to show property $3^{\prime}$.

To handle $F_{n}$, begin by using smoothness of $\Psi$:

Using the assumption $\left\|x\right\|\leq{}1$, we obtain an upper bound of

We now use a basic fact from convex analysis, namely that any $\beta$-smooth function $f$, $\frac{1}{2\beta}\left\|\nabla{}f(x)-\nabla{}f(y)\right\|_{\star}^{2}\leq{}f(x)-f(y)-\left\langle\nabla{}f(y),x-y\right\rangle$ . This yields an upper bound

As a last step, observe that $\frac{1}{n}+\frac{1}{n^{2}}\leq{}\frac{1}{n-1}$. Indeed,

The argument also yields (by removing unnecessary steps):

We will set $\gamma=\frac{1}{\sqrt{n}}$ and $c=1$, which yields $\mathbf{U}_{0}(0)\leq{}0$.

A.3 Proofs from Section 6

Recall that $\mathcal{A}_{\eta}(X_{1},\ldots,X_{n})=\frac{\eta{}rL^{2}}{2}\left\|\sum_{t=1}^{n}\mathcal{M}(X_{t})\right\|_{\sigma}+\frac{c}{\eta}$. Linearizing the loss with the adaptive bound as in (2),

Using the fact that $\lambda_{1}(\mathcal{H}(X))=\left\|X\right\|_{\sigma}$, linearity of $\mathcal{H}$, and that $\mathcal{M}(X_{t})$ is positive semidefinite, we write this as

Sub-additivity of $\lambda_{1}$ gives a further upper bound of

We will show that $\mathbf{U}$ satisfies the three properties of Lemma 2. For property $1^{o}$, we have

Thus, $\mathbf{U}(0)\leq{}0$ as soon as $c\geq{}r\log(d_{1}+d_{2})$.

For property $2^{o}$, it suffices to show that $\lambda_{1}(H-\frac{\eta{}L^{2}}{2}M)\leq{}\frac{1}{\eta}\log\,\mathsf{tr}\,\exp\left(\eta{}H-\frac{\eta^{2}L^{2}}{2}M\right)$. To this end, we have

where the equality is well-defined because the matrix under consideration is symmetric and the inequality follows because $e^{A}$ is positive semidefinite for any symmetric matrix $A$.

For the third property, observe that the mapping $\alpha\mapsto{}V(\tau+\mathbf{T}(z,\alpha))$ is convex (e.g. (Lewis, 1996)). Consequently, by Lemma 2, it suffices only to prove property $3^{\prime}$, i.e. that the restricted concavity condition holds only for Rademacher random variables.

Fix $\tau\in\mathcal{T}$ and $z=(X,{\widehat{y}})\in\mathcal{X}\times{}\mathcal{Y}$, and let $\epsilon$ be a Rademacher random variable. Writing

Focusing on the log-trace-exponential term, observe that

Since $\exp\left(\eta\epsilon{}L\mathcal{H}(X)\right)$ is positive definite and $\eta{}\tau_{2}-\frac{\eta^{2}L^{2}}{2}\tau_{3}-\frac{\eta^{2}L^{2}}{2}\mathcal{M}(X)$ is symmetric (by assumption), we can apply Lieb’s Concavity Theorem to upper bound this by

The Rademacher matrix mgf bound (Tropp, 2012) now yields

Since $A\preceq{}B$ implies $\mathsf{tr}{}e^{A}\leq{}\mathsf{tr}{}e^{B}$, this implies that

Combining everything we proved so far, this implies

The Burkholder function $\mathbf{U}$ satisfies the conditions of Lemma 5. Direct calculation shows that the strategy in Lemma 5 matches the strategy in the statement of the corollary. ∎

We invoke the Burkholder function $\mathbf{U}$ from Theorem 2 for the special case $r=1$ and $c=\log(d_{1}+d_{2})$, and $L=1$. In particular, its existence per Lemma 2 implies (for the corresponding $V$, here denoted $V_{\eta}$ to refer to the $V$ given for a fixed value of $\eta$)

We use this inequality only for the special case where $\delta_{t}=\epsilon_{t}$ and $\boldsymbol{z}_{t}=(\boldsymbol{X}_{t}(\epsilon),0)$. For this special case, the inequality above implies

For any fixed martingale $(\boldsymbol{X}_{t}(\epsilon))_{t\leq{}n}$, this implies

To conclude, observe that for any sequence $(X_{t})$ we have

Indeed, \sum_{t=1}^{n}\mathcal{M}(X_{t})=\left(\begin{array}[]{ll}\sum_{t=1}^{n}X_{t}X_{t}^{\top}&0\\ 0&\sum_{t=1}^{n}X_{t}^{\top}X_{t}\end{array}\right) and the spectral norm of a block-diagonal matrix is always obtained by the spectral norm of one of its blocks.

A.4 Proofs from Section 7

The path from here to a Burkholder function in the sense of Lemma 2 is clear given the three properties of $\mathbf{U}_{\textrm{square}}$ stated in the main body.

where $x_{t}[i]$ refers to the $i$th coordinate of $x_{t}$. Once again, the three properties of $\mathbf{U}_{\textrm{square}}$ directly lead to a valid Burkholder function $\mathbf{U}$. ∎

Let $A_{n}=\rho\sum_{t=1}^{n}z_{t}z_{t}^{\top}+\lambda{}I$ and $A_{0}=\lambda{}I$. Recall that $\Psi_{A}(w)=\frac{1}{2}\left\langle w,Aw\right\rangle$. We begin by rewriting the desired regret bound as

for a constant $c>0$ to be determined. With this definition, we have

Recall that we have defined $\mathbf{U}(x,A)=V(x,A)=\Psi^{\star}_{A}\left(x\right)-c\log\left(\det(A)/\det(A_{0})\right)$. We verify the properties from Lemma 2. Property $2^{o}$ is immediate, and for property $1^{o}$ we have

Let $A=\rho(\tau_{2}+zz^{\top})+\lambda{}I$ and $B=\rho\tau_{2}+\lambda{}I$. Then since $\Psi^{\star}$ is a squared Euclidean norm and $\alpha$ is mean-zero:

Also note that since $B\preceq{}A$, $\Psi^{\star}_{A}(\tau_{1})\leq{}\Psi^{\star}_{B}(\tau_{1})$.

To conclude, we first note that we just established

A.5 Proofs from Section 8

Recall that the regret inequality of interest is

As sketched in the Section 8, Lemma 1 shows that this is implied by

For the final step, let $\widetilde{\mathbf{y}}$ be an arbitrary $\mathcal{Y}$-valued tree $\widetilde{\mathbf{y}}_{t}(\epsilon)=\widetilde{\mathbf{y}}_{t}(\epsilon_{1},\ldots,\epsilon_{t-1})$. Using the explicit form for $V$, we have

Since the argument above holds for any trees $\mathbf{x}$ and $\widetilde{\mathbf{y}}$, we conclude that the regret inequality implies that

for all $\mathcal{X}\times{}\mathcal{Y}$-valued trees.

Appendix B Burkholder Algorithm Implementation

In this section we assume that $\mathcal{Y}=\left[-B,B\right]$ for $B>0$ for simplicity. The only assumption we make on the form of $\mathbf{U}$ is Lipschitzness and boundedness.

The are constants $K_{t}$ and $H_{t}$ such that the mapping

is $K_{t}$-Lipschitz and bounded in magnitude by $H_{t}$ for any $y_{t}\in\mathcal{Y}$, $x_{t}\in\mathcal{X}$, and $\zeta_{t-1}$ of the form $\zeta_{t}=\sum_{s=1}^{t}\mathbf{T}(x_{s},{\widehat{y}}_{s},\partial({\widehat{y}}_{s},y_{s}))$.

Fix precision $\varepsilon_{1}>0$ and set $N=\left\lceil 2B/\varepsilon_{1}\right\rceil$.

Define control points $z_{i}=-B+\varepsilon_{1}\cdot{}i$ for $0\leq{}i\leq{}N$.

Let $\widehat{\mu}_{t}$ be a solution to the convex program

up to additive precision $\varepsilon_{2}$.

Sample ${\widehat{y}}_{t}\sim{}\widehat{\mu}_{t}$.

Given a Burkholder function $\mathbf{U}$, the strategy above guarantees

That is, the regret inequality (1) is obtained up to additive slack controlled by $\varepsilon_{1}$ and $\varepsilon_{2}$.

Before proving the theorem, let us discuss the computational prospects of implementing this strategy. First, suppose $K_{t}=K$ and $H_{t}=H\;\forall{}t\leq{}n$. To obtain the regret inequality up to constant error it suffices to take $\varepsilon_{1}=1/Kn$ and $\varepsilon_{2}=1/n$. In this case, we have $N=O(BKn)$.

Lastly, we remark that if we replace Mirror Descent with Mirror Prox for saddle points (Nemirovski, 2004), the dependence on $n$ in running time for the two cases above can be improved to $O(n^{2})$ and $O(n^{3})$ respectively.

The runtime can improved further if a regret bound of order $O(\sqrt{n})$ is sufficient, as this requires less precision.

To begin, observe that since $\widehat{\mu}_{t}$ is an approximate solution to (23), it holds that

The remainder of the proof will show that the right-hand-side above can be bounded as

where the second inequality follows from property $3^{o}$ of $\mathbf{U}$ and was shown in the proof of Lemma 3.

Define $\mathcal{I}_{1}=\left[z_{0},z_{1}\right]$ and $\mathcal{I}_{i}=(z_{i-1},z_{i}]$ for $2\leq{}N$. Then $\left\{\mathcal{I}_{i}\right\}$ form a partition of $\left[-B,B\right]$ and the integral can be approximated as

Since this holds for any $q\in\Delta_{\mathcal{Y}}$ and $y\in\mathcal{Y}$, we have

B.2 Faster Implementation under Specific Structure

In the remainder of this section of the appendix we show how to implement the Burkholder algorithm for certain special cases that enable admit especially simple strategies.

achieves the value of the game in Lemma 3.

This follows by reduction to the general case:

The strategy in (24) is the minimax strategy for second expression above. The final expression is precisely the value of the Burkholder algorithm, which is controlled when $\mathbf{U}$ is a Burkholder function via Lemma 3. ∎

Suppose that $\mathcal{Y}=\left[-B,B\right]$ for some $B>0$. Further suppose that we can write

where $\delta\mapsto{}F(\tau,x,\delta)$ is convex for all $\tau,x$. Then the prediction strategy

achieves the value of the game in Lemma 3.

Let $\widetilde{y}_{t}$ denote the unprojected version of ${\widehat{y}}_{t}$:

We prove the lemma by inducting backwards. Let $t\in\left[n\right]$ be fixed. We first claim that

Now, by the convexity assumption of the lemma, it holds that

The choice of $\widetilde{y}_{t}$ guarantees that $\widetilde{y}_{t}\cdot{}L\cdot(1)+F(\zeta_{t-1},x_{t},L\cdot(1))=\widetilde{y}_{t}\cdot{}L\cdot{}(-1)+F(\zeta_{t-1},x_{t},L\cdot(-1))$; this can be seen by rearranging this equality and solving for $\widetilde{y}_{t}$. This means that we can take $\sigma=1$ to obtain the maximum in the expression above. Substituting in the value of $\widetilde{y}_{t}$ then yields

Finally, we use property $3^{\prime}$ of $\mathbf{U}$ and the explicit form for $\mathbf{U}$ assumed in the lemma statement to proceed back to time $t-1$:

Appendix C Algebra of Burkholder Functions

This appendix contains some additional structural results about Burkholder functions which may be useful for algorithm designers.

Any convex combination of Burkholder functions is a Burkholder function.

The minimum of a family of Burkholder functions is a Burkholder function.

The first statement follows from property $3^{o}$ of the Burkholder function $\mathbf{U}$, which immediately implies that it is a supermartingale. The second statement is trivial. To prove the third statement it suffices to verify property $3^{o}$, which holds due to concavity of the minimum.

whose sufficient statistics are the original sufficient statistic of the family of $V_{a}$s along with an additional $|A|$-dimensional real vector, for which one coordinate per $a\in A$ will be used to represent $C[a]=\sup_{\tau,z,\alpha}(\mathbf{U}_{a}(\tau+\mathbf{T}(z,\alpha))-\mathbf{U}_{a}(\tau))^{2}$ (note that this is a vacuous statistic as it is constant for each instance). Property $3^{o}$ for $\mathbf{U}$ holds as follows:

For property $1^{o}$ it can be seen immediately that $\mathbf{U}(0)\leq 0$. Property $2^{o}$ holds via

We remark that one uses non-additive sufficient statistics as discussed in Section 9, then one can make the bound implied by the Burkholder function $\mathbf{U}$ above more data-dependent by replacing $C[a]$ with $\sup_{\delta}\left(\mathbf{U}_{a}(\tau+\mathbf{T}(z,\delta))-\mathbf{U}_{a}(\tau)\right)^{2}$ for each $a$.