Online learning with kernel losses
Aldo Pacchiano Niladri S. Chatterji Peter L. Bartlett

Metallic nanolayers – a sub-visible  wonderland of optical properties
    A. E. Kaplan
    December 30, 2023
=====================================================================


We present a generalization of the adversarial linear bandits framework, where the underlying losses are kernel functions (with an associated reproducing kernel Hilbert space) rather than linear functions. We study a version of the exponential weights algorithm and bound its regret in this setting. Under conditions on the eigendecay of the kernel we provide a sharp characterization of the regret for this algorithm. When we have polynomial eigendecay μ_j ≤𝒪(j^-β), we find that the regret is bounded by ℛ_n ≤𝒪(n^β/(2(β-1))); while under the assumption of exponential eigendecay μ_j ≤𝒪(e^-β j ), we get an even tighter bound on the regret ℛ_n ≤𝒪(n^1/2log(n)^1/2). We also study the full information setting when the underlying losses are kernel functions and present an adapted exponential weights algorithm and a conditional gradient descent algorithm.



§ INTRODUCTION

In adversarial online learning <cit.>, a player interacts with an unknown and arbitrary adversary in a sequence of rounds. At each round, the player chooses an action from an action space and incurs a loss associated with that chosen action. The loss functions are determined by the adversary and are fixed at the beginning of each round. After choosing an action the player observes some feedback, which can help guide the choice of actions in subsequent rounds. The most common feedback model is the full information model, where the player has access to the entire loss function at the end of each round. Another, more challenging feedback model is the partial information or bandit feedback model where the player at the end of the round just observes the loss associated with the action chosen in that particular round. There are also other feedback models in between and beyond the full and bandit information models, many of which have also been studied in detail. A figure of merit that is often used to judge online learning algorithms is the notion of regret, which compares the players actions to the best single action in hindsight (defined formally in Section <ref>). 

When the underlying action space is a continuous and compact (possibly
convex) set and the losses are linear or convex functions over this
set; there are many algorithms known that attain sub-linear and
sometimes optimal regret in both these feedback settings. In this work
we present a generalization of the well studied adversarial online
linear learning framework. In our paper, at each round the player
selects an action a ∈𝒜⊂ℝ^d. This
action is mapped to an element in a reproducing kernel Hilbert space
(RKHS) generated by a mapping (·,·). The function
(·,·) is a kernel map, that is, it can be thought of as the inner product of an appropriate Hilbert space ℋ. The kernel map can be expressed as (x,y) = ⟨Φ(x),Φ(y) ⟩_ℋ, where Φ(·) ∈ℝ^D is the associated feature map.

At each round the loss is ⟨Φ(a), w ⟩_ℋ, where w ∈ℋ is the adversary's action. In the full information setting, as feedback, the player has access to the entire adversarial loss function ⟨· , w⟩_ℋ. In the bandit setting the player is only presented with the value of the loss, ⟨Φ(a), w ⟩_ℋ. 

Notice that this class of losses is much more general than ordinary linear losses and includes potentially non-linear and non-convex losses like:

    
  * Linear Losses: ⟨ a,w ⟩_ℋ= a^⊤w. This loss is well studied in both the bandit and full information settings. We shall see that our regret bounds will match the bounds established in the literature for these losses.
    
  * Quadratic Losses: ⟨Φ(a), Wb⟩_ℋ = a^⊤ W a   + b^⊤ a, where W is a symmetric (not necessarily positive semi-definite) matrix and b is a vector. Convex quadratic losses have been well studied under full information feedback as the online eigenvector decomposition problem. Our work establishes regret bounds in the full information setting and also in the previously unexplored bandit feedback setting.
    
  * Gaussian Losses: ⟨Φ(a), Φ(y) ⟩_ℋ = exp(-‖ a - y ‖_2^2/2σ^2 ). We provide regret bounds for kernel losses not commonly studied before like Gaussian losses that provide a different loss profile than a linear or convex loss. 
    
  * Polynomial Losses: ⟨Φ(a), Φ(y) ⟩_ℋ = (1+ x^⊤y)^2 for example. We also provide regret bounds for polynomial kernel losses which are potentially (non-convex) under both partial and full information settings. Specifically in the full information setting we study posynomial losses (discussion in Appendix <ref>).




 §.§ Related Work

Adversarial online convex bandits were introduced and first studied by <cit.>. The problem most closely related to our work is the case when the losses are linear and was introduced earlier by <cit.>. To improve the dimension dependence in the regret, <cit.> proposed the  (Expanded Exp) algorithm under different choices of exploration distributions. <cit.> worked with the uniform distribution over the barycentric spanner of the set, <cit.> used the uniform distribution over the set and <cit.> set the exploration distribution to be the one given by John's theorem which leads to a regret bound of 𝒪((dnlog(|𝒜|))^1/2). Here |𝒜| is the number of actions, n is the number of rounds and d is the dimension of the losses. In the case of linear bandits when the set 𝒜 is convex and compact, <cit.> analyzed mirror descent to get a regret bound of 𝒪(d√(θ nlog(n))) for some θ>0. For the case with general convex losses with bandit feedback recently <cit.> proposed a poly-time algorithm that has a regret guarantee of 𝒪̃(d^9.5√(n)), which is optimal in its dependence on the number of rounds n. Previous work on this problem includes, <cit.> in the adversarial setting under different assumptions on the structure of the convex losses and by <cit.> who studied this problem in the stochastic setting[For an extended bibliography of the work on online convex bandits see <cit.>.]. <cit.> study stochastic kernelized contextual bandits with a modified Upper Confidence Bound (UCB) algorithm to obtain a regret bound similar to ours, ℛ_n ≤d̃√(n) where d̃ is the effective dimension dependent on the eigendecay of the kernel. This problem was also studied previously for loss functions drawn from Gaussian processes by <cit.>. Online learning under bandit feedback has also been studied when the losses are non-parametric, for example when the losses are Lipschitz <cit.>. 

In the full information case, the online optimization framework with convex losses was first introduced by <cit.>. The conditional gradient descent algorithm (a modification of which we study in this work) for convex losses in this setting was introduced and analyzed by <cit.> and then improved subsequently by <cit.>. The exponential weights algorithm which we modify and use multiple times in this paper has a rich history and has been applied to various online as well as offline settings. 
The case of convex quadratic losses has been well studied in the full information setting. This problem is called online eigenvector decomposition or online Principal Component Analysis (PCA). Recently <cit.> established a regret bound of 𝒪̃(√(n)) for this problem by presenting an efficient algorithm that achieves this rate – a modified exponential weights strategy termed “follow the compressed leader”. Previous results for this problem were established in both adversarial and stochastic settings by modifications of exponential weights, gradient descent and follow the perturbed leader algorithms <cit.>. 

In the full information setting there has also been work on analyzing
gradient descent and mirror descent in an RKHS
<cit.>. However, in
these papers, the player is allowed to play any action in a bounded set in a Hilbert space, while in our paper the player is constrained to only play rank one actions, that is the player chooses an action in 𝒜 which gets mapped to an action in the RKHS.





  §.§.§ Contributions

Our primary contribution is to extend the linear bandits framework to more general classes of kernel losses. We present an exponential weights algorithm in this setting and establish a regret bound on its performance. We provide a more detailed analysis of the regret under assumptions on the eigendecay of the kernel. When we assume polynomial eigendecay of the kernel (μ_j ≤𝒪(j^-β)) we can guarantee the regret is bounded as ℛ_n≤𝒪(n^β/2(β-1)). Under exponential eigendecay we can guarantee an even sharper bound on the regret of ℛ_n ≤𝒪(n^1/2log(n)^1/2). We also provide an exponential weights algorithm and a conditional gradient algorithm for the full information case where we don't need to assume any conditions on the eigendecay. Finally we provide a couple of applications of our framework – (i) general quadratic losses (not necessarily convex) with linear terms which we can solve efficiently both in the full information setting and the bandit setting, (ii) we provide a computationally efficient algorithm when the underlying losses are posynomials (special class of polynomials).


  §.§.§ Organization of the Paper

In the next section we introduce the notation and definitions. In Section <ref> we present our algorithm under bandit feedback along with regret bounds for it. In Section <ref> we study the problem in the full information setting. In Section <ref> we apply our framework to general quadratic losses prove that our algorithms are computationally efficient in this setting. All the proofs and technical details are relegated to the appendix. Also in the appendix is the example of our framework applied to posynomial losses and experimental evidence verifying our claims.



 §.§ Notation, main definitions and setting


Here we introduce definitions and notational conventions used throughout the paper.

In each round t= {1,…,n}, the player chooses an action vector {a_t}_t=1^n∈𝒜⊂ℝ^d. The underlying kernel function at each round is  (·,·) which is a map from ℝ^d ×ℝ^d →ℝ such that it is a kernel map and has an associated separable reproducing kernel Hilbert space (RKHS) ℋ with an inner product ⟨·, ·⟩_ℋ <cit.>. Let Φ(·): ℝ^d ↦ℝ^D denote a feature map of (·,·) such that for every x,y we have (x,y) = ⟨Φ(x),Φ(y) ⟩_ℋ. Note that the dimension of the RKHS, D could be infinite (for example in the Gaussian kernel over [0,1]^d). 

We let the adversary choose a vector in ℋ, w_t ∈𝒲⊂ℝ^D and at each round the loss incurred by the player is ⟨ a_t,w_t⟩_ℋ. We assume that the adversary is oblivious, that is, it is a function of the previous actions of the player (a_1,…,a_t-1) but unaware of the randomness used to generate a_t. 



We let the size of the sets 𝒜,𝒲 be bounded[We set the bound on the size of both sets to be the same for ease of exposition, but they could be different and would only change the constants in our results.] in kernel norm, that is, 

    sup_a ∈𝒜(a,a) ≤𝒢^2      and, sup_w ∈𝒲⟨ w,w⟩_ℋ≤𝒢^2.

Throughout this paper we assume a rank-one learner, that is, in each round the player can pick a vector v ∈ℋ, such that v = Φ(a) for some a ∈ℝ^d. We now formally define the notion of expected regret.
 
The expected regret of an algorithm ℳ after n rounds is defined as

    ℛ_n     = 𝔼_ℳ[∑_t=1^n⟨Φ(a_t),w_t ⟩_ℋ -∑_t=1^n⟨Φ(a^*),w_t ⟩_ℋ],

where a^* = inf_a∈𝒜{∑_t=1^n⟨Φ(a),w_t⟩_ℋ} and the expectation is over the randomness in the algorithm. 

Essentially this amounts to comparing against the best single action a^* in hindsight. Our hope will be to find a randomized strategy such that the regret grows sub-linearly with the number of rounds n. In what follows we will omit the subscript ℋ from the subscript of the inner product whenever it is clear from the context that it refers to the RKHS inner product.
















To establish regret guarantees we will find that it is essential to work with finite dimensional kernels when working under bandit feedback (more details regarding this are in the proof of the regret bound of Algorithm <ref>). General kernel maps can have infinite dimensional feature maps thus we will require the construction of a finite dimensional kernel that uniformly approximates the original kernel (·,·). This motivates the definition of ϵ-approximate kernels.
 
Let _1 and _2 be two kernels over 𝒜×𝒜 and let ϵ >0. We say _2 is an ϵ-approximation of _1 if for all x, y ∈𝒜, |_1(x,y) - _2(x,y)|≤ϵ.
















§ BANDIT FEEDBACK SETTING


In this section we present our results on kernel bandits. In
the bandit setting we assume the player knows the underlying kernel
function (·,·), however, at each round after the player
plays a vector a_t only the value of the loss associated with that
action is revealed to the player – ⟨Φ(a_t),w_t⟩_ℋ – and not the action of the
adversary w_t. We also assume that the player's action set
𝒜 has finite cardinality[This assumption can be
relaxed to let 𝒜 be a compact set when  is Lipschitz
continuous. In this setting we can instead work with an appropriately
fine approximating cover of the set 𝒜.].This is a
generalization of the well studied adversarial linear bandits problem.
As we will see in subsequent sections, to guarantee a bound on the regret in the bandit setting our algorithm will build an estimate of adversary's action w_t. This becomes impossible if w_t is infinite dimensional (D →∞). To circumvent this, we will construct a finite dimensional proxy kernel that is an ϵ-approximation of .

Whenever no approximate kernel is needed, for example when D < ∞ we allow the adversary to be able to choose an action w_t ∈𝒲⊂ℝ^D without imposing extra requirements on the set 𝒲 other than it being bounded in ℋ norm. When D is infinite we impose an additional constraint on the adversary to also select rank-one actions at each round, that is, w_t = Φ(y_t) for some y_t ∈ℝ^d. Next we present a procedure to construct a finite kernel that approximates the original kernel well.



 §.§ Construction of the finite dimensional kernel

 
To construct the finite dimensional kernel we will rely crucially on Mercer's theorem. We first recall a couple of useful definitions.

Let 𝒜⊂ℝ^d and ℙ be a probability measure supported over 𝒜. Let L_2(𝒜;ℙ) denote square integrable functions over 𝒜 and measure ℙ, L_2(𝒜;ℙ) := {f:𝒜→ℝ|∫_𝒜 f^2(x) dℙ(x) < ∞}.



A kernel : 𝒜×𝒜→ℝ is square integrable with respect to measure ℙ over 𝒜, if ∫_𝒜×𝒜^2(x,y) dℙ(x) dℙ(y) < ∞.

Now we present Mercer's theorem <cit.> <cit.>.

Let 𝒜⊂ℝ^d be compact and ℙ be a finite Borel measure with support 𝒜. Suppose  is a continuous square integrable positive definite kernel on 𝒜, and define a positive definite operator 𝒯_ : L_2(𝒜;ℙ) ↦ L_2(𝒜;ℙ) by

    ( 𝒯_ f    ) ( ·) := ∫_𝒜(·, x) f(x) ℙ.

Then there exists a sequence of eigenfunctions {ϕ_i}_i=1^∞ that form an orthonormal basis of L_2(𝒜;ℙ) consisting of eigenfunctions of 𝒯_, and an associated sequence of non-negative eigenvalues {μ_j}_j=1^∞ such that 𝒯_𝒦(ϕ_j) = μ_j ϕ_j for j = 1,2,…. Moreover the kernel function can be represented as

    (u,v) = ∑_i=1^∞μ_i ϕ_i(u)ϕ_i(v),

where the convergence of the series holds uniformly.

Mercer's theorem suggests a natural way to construct a feature map Φ(x) for  by defining the i^th component of the feature map to be Φ(x)_i := √(μ_i)ϕ_i(x). Under this choice of the feature map the eigenfunctions {ϕ_i}_i=1^∞ are orthogonal with respect to the inner product ⟨· ,·⟩_ℋ[To see this observe that the function ϕ_i can be expressed as a vector in the RKHS as a vector v_i with ϕ_i in the i^th coordinate and zeros everywhere else. So for any two v_i and v_j with i≠ j we have ⟨ v_i,v_j ⟩_ℋ = 0.]. Armed with Mercer's theorem we first present a simple deterministic procedure to obtain a finite dimensional ϵ-approximate kernel of . When the eigenfunctions of the kernel are uniformly bounded, sup_x ∈𝒜|ϕ_j(x) |≤ℬ for all j, and if the eigenvalues decay at a suitable rate we can truncate the series in Equation (<ref>) to get a finite dimensional approximation.
lemmadetelemma
 Given ϵ >0, let {μ_j }_j=1^∞ be the Mercer operator eigenvalues of  under a finite Borel measure ℙ with support 𝒜 and eigenfunctions {ϕ_j }_j=1^∞ with μ_1 ≥μ_2 ≥⋯. Further assume that sup_j ∈ℕsup_x ∈𝒜|ϕ_j(x) |≤ℬ for some ℬ < ∞. Let m(ϵ) be such that ∑_j=m+1^∞μ_j ≤ϵ/4ℬ^2. Then the truncated feature map,

    Φ^o_m(x) := √(μ_i)ϕ_i(x)    if  i ≤ m 
     0    o.w.

induces a kernel ^o(x,y) := ⟨Φ^o_m(x),Φ^o_m(y) ⟩_ℋ = ∑_j=1^m μ_j ϕ_j(x)ϕ_j(y), for all  (x,y) ∈𝒜×𝒜 that is an ϵ/4-approximation of .

The Hilbert space induced by ^o is a subspace of the original Hilbert space ℋ. The proof of this lemma is a simple application of Mercer's theorem and is relegated to Appendix <ref>. If we have access to the eigenfunctions of  we can construct and work with ^o because as Lemma <ref> shows ^o is an ϵ/4-approximation to . Additionally, ^o also has the same first m Mercer eigenvalues and eigenfunctions under ℙ as . Unfortunately, in most applications of interest the analytical computation of the eigenfunctions {ϕ_i }_i=1^∞ is not possible. We can get around this by building an estimate of the eigenfunctions using samples from ℙ by leveraging results from kernel principal component analysis (PCA). 
Let S_m be the subspace of ℋ spanned by the first m eigenvectors of the covariance matrix 𝔼_x ∼ℙ[ Φ(x) Φ(x)^⊤].

This corresponds[This holds as the i^th eigenvector of the covariance matrix has ϕ_i as the i^th coordinate and zero everywhere else combined with the fact that {ϕ_i }_i=1^∞ are orthonormal under the L_2(𝒜;ℙ) inner product.]
to the span of the eigenfunctions ϕ_1,…,ϕ_m in ℋ. Define the linear projection operator P_S_m: ℋ↦ℋ that projects onto the subspace S_m; where P(S_m)(v+ v^⊥) = v, if v ∈ S_m and v^⊥∈ S_m^⊥. 

The feature map Φ^o_m(x) is a projection of the complete feature map to this subspace, Φ^o_m(x) = P_S_m(Φ(x)).


Let x_1,x_2,…,x_p ∼ℙ be p i.i.d. samples and construct the sample (kernel) covariance matrix, Σ̂ := 1/p∑_i=1^p Φ(x_i) Φ(x_i)^⊤. Let Ŝ_m be the subspace spanned by the m top eigenvectors of Σ̂. Define the stochastic feature map, Φ_m(x) := P_Ŝ_m(Φ(x)), the feature map defined by projecting Φ(x) to the random subspace Ŝ_m. Intuitively we would expect that if the number of samples p is large enough, then the  kernel defined by the feature map Φ_m(x), (x,y) = ⟨Φ_m(x), Φ_m(y) ⟩_ℋ will also be an ϵ-approximation for the original kernel . Formalizing this claim is the following theorem.


Let ϵ, m, ℙ be defined as in Lemma <ref> and let the m-th level eigen-gap be δ_m := 1/2( μ_m - μ_m+1). Further let α>0, B_m = 2𝒢^2/δ_m( 1 + √(α/2)) and p ≥4B_m^2 𝒢^2 /(min(√(ϵ),δ_m))^2. Then the finite dimensional kernels _m^o and _m satisfy the following properties with probability 1-e^-α,


  * sup_x,y ∈𝒜 |(x,y) - _m(x,y) | ≤ϵ.


  * The Mercer eigenvalues μ^(p)_1 ≥⋯≥μ^(p)_m and μ_1 ≥⋯≥μ_m of  and ^o are close, sup_i=1, ⋯, m |μ^(p)_i - μ_i| ≤ϵ/4.


Theorem <ref> shows that given ϵ> 0 the finite dimensional proxy  is a ϵ-approximation of  with high probability as long as sufficiently large number of samples are used.  Furthermore, the top m eigenvalues of the second moment matrix of  are at most √(ϵ)/2-away from the eigenvalues of the second moment matrix of  under ℙ.

[t]
ProxyKernel(𝒦,m,𝒜,ℙ,p) 
	
	Kernel , effective dimension m, set 𝒜, measure ℙ, number of samples p.
	OutputFunction
	Finite proxy feature map Φ_m(·)
			Sample x_1, ⋯, x_p ∼ℙ. 

Construct sample Gram matrix 𝕂̂_i,j = 1/p(x_i,x_j).

Calculate the top m eigenvectors of 𝕂̂→{ω_1,ω_2,…,ω_m }.

j=1,…,m  
      
      Set v_j ←∑_k=1^pω_jkΦ(x_k)/(∑_k=1^pω_jkΦ(x_k)_2)           (ω_jk is the k^th component of ω_j)
      

Define the feature map 

    Φ_m(·) := [ ⟨ v_1,Φ(·) ⟩_ℋ;              ⋮; ⟨ v_m,Φ(·) ⟩_ℋ ] = [ ∑_k=1^p ω_1k(x_k,·)/(∑_k=1^pω_1kΦ(x_k)_2);                                         ⋮; ∑_k=1^p ω_mk(x_k,·)/(∑_k=1^pω_mkΦ(x_k)_2) ].

	































To construct Φ_m(·) we need to calculate the top m eigenvectors of the sample covariance matrix Σ̂, however, it is equivalent to calculate the top m eigenvectors of the sample Gram matrix 𝕂 and use them to construct the eigenvectors of Σ̂ (for more details see Appendix <ref> where we review the basics of kernel PCA).




 §.§ Bandits Exponential Weights


In this section we present a modified version of exponential weights adapted to work with kernel losses. Exponential weights has been analyzed extensively applied to linear losses under bandit feedback <cit.>. Two technical challenges make it difficult to directly adapt their algorithms to our setting.

The first challenge is that at each round we need to estimate the adversarial action w_t. If the feature map of the kernel is finite dimensional this is easy to handle, however when the feature map is infinite dimensional, this becomes challenging and we need to build an approximate feature map Φ_m(·) using Function <ref>. This introduces bias in our estimate of the adversarial action w_t and we will need to control the contribution of the bias in our regret analysis. The second challenge will be to lower bound the minimum eigenvalue of the kernel covariance matrix as we will need to invert this matrix to estimate w_t. For general kernels which are infinite dimensional, the minimum eigenvalue is zero. To resolve this we will again turn to our construction of a finite dimensional proxy kernel. 



 §.§ Bandit Algorithm and Regret Bound
 
 
In our exponential weights algorithm we first build the finite dimensional proxy kernel  using Function <ref>. The rest of the algorithm is then almost identical to the exponential weights algorithm (EXP 2) studied for linear bandits. In Algorithm <ref> we set the exploration distribution ν_𝒥^𝒜 to be such that it induces John's distribution (ν_𝒥) over Φ_m(𝒜) : = {Φ_m(a) ∈ℝ^m : a ∈𝒜} (first introduced as an exploration distribution by <cit.>; a short discussion is presented in Appendix <ref>). 
Note that for finite sets it is possible to build an approximation to minimal volume ellipsoid containing conv(Φ_m(𝒜))–John's ellipsoid and John's distribution in polynomial time <cit.>[It is thus possible to construct ν_𝒥 over Φ_m(𝒜) in polynomial time. However, as 𝒜 is a finite set, using Φ_m(·) and ν_𝒥 it is also possible to construct ν_𝒥^𝒜 over 𝒜 efficiently.]. In this section we assume that the set 𝒜 is such that the John's ellipsoid is centered at the origin.

Crucially note that we construct the finite dimensional feature map Φ_m(·) only once before the first round. In the algorithm presented above we build Φ_m(·) using the uniform distribution ν_unif over 𝒜 assuming that kernel  has fast eigendecay under this measure. However, any other distribution say – ν_alt (with support 𝒜) could also be used instead of ν_unif in Algorithm <ref> if the kernel  enjoys fast eigendecay under ν_alt. 

In our algorithm we build and invert the exact covariance matrix Σ_m^(t), however this can be relaxed and we can instead work with a sample covariance matrix. We analyze the required sample complexity and error introduced by this additional step in Appendix <ref>. We now state the main result of this paper which is an upper bound on the regret of Algorithm <ref>.

 Let μ_i be the i-th Mercer operator eigenvalue of  for the uniform measure ν_unif over 𝒜. Let ϵ≤𝒢^2 and let m,p,α be chosen as specified by the conditions in Theorem <ref>. Let the mixing coefficient, γ = 4η𝒢^4m. Then Algorithm <ref> with probability 1 - e^-α has regret bounded by

    ℛ_n ≤ 4γ𝒢^2 n + (e-2)𝒢^4η m n + 2ϵ n + 
    2ϵ n/𝒢^2η+ 1/ηlog(|𝒜|).


We prove this theorem in Appendix <ref>. Note that this is similar to the regret rate attained for adversarial linear bandits <cit.> with additional terms that accounts for the bias in our loss estimates ŵ_t. In our regret bounds the parameter m plays the role of the effective dimension and will be determined by the rate of the eigendecay of the kernel. When the underlying Hilbert space is finite dimensional (as is the case when the losses are linear or quadratic) our regret bound recovers exactly the results of previous work (that is, ϵ = 0 and m=d). 

We note that the exploration distribution can also be chosen to be the uniform distribution over the Barycentric spanner of Φ_m(𝒜). But this choice leads to slightly worse bounds on the regret and we omit a detailed discussion here for the sake of clarity. Next we state the following different characteristic eigenvalue decay profiles.
 Let the Mercer operator eigenvalues of a kernel  with respect to a measure ℙ over a set 𝒜 be denoted by μ_1 ≥μ_2 ≥….


  *  is said to have (C,β)-polynomial eigenvalue decay (with C>0, β>1) if for all j ∈ℕ we have μ_j  ≤  Cj^-β.

  *  is said to have (C,β)-exponential eigenvalue decay (with C>0, β>0) if for all j ∈ℕ we have μ_j  ≤  Ce^-β j.


Under assumptions on the eigendecay we can establish bounds on the effective dimension m and μ_m, so that the condition stated in Lemma <ref> is satisfied and we are guaranteed to build an ϵ-approximate kernel . We establish bounds on m in Proposition <ref> presented in Appendix <ref>. Under the eigendecay profiles stated above we can now invoke Theorem <ref>. 












 Let the conditions stated in Theorem <ref> hold and let 𝒢=1. Then Algorithm <ref> has its regret bounded by the following rates with probability 1-e^-α. 


  * If  has (C,β)-polynomial eigenvalue decay under the uniform measure ν_unif, with β >2. Then by choosing the step size η = √(ϵ/(10m)) where, ϵ = log(|𝒜| )/(2n) and m =  [4Cℬ^2/(β-1)ϵ]^1/β-1, with n large enough such that η<1 and ϵ<1, the expected regret is bounded by

    ℛ_n    ≤√(160)·[2^β+2Cℬ^2/β-1]^1/2(β-1)·(log(| A |))^β-2/2(β-1)· n^β/2(β-1).


  * If  has (C,β)-exponential eigenvalue decay under the uniform measure ν_unif. Then by choosing the step-size η = √(ϵ/(10m)) where, ϵ = log(|𝒜| )/(2n) and m = 1/βlog(4C ℬ^2/βϵ) with n large enough so that ϵ<1, the expected regret is bounded by

    ℛ_n    ≤√(320·log(|𝒜|)/β·log( 40Cℬ^2 n /βlog(|𝒜|))·  n).



 Under (C,β)-polynomial eigendecay condition we have that the regret is upper bounded by ℛ_n ≤𝒪(n^β/2(β-1)). While when we have (C,β)-exponential eigendecay we almost recover the adversarial linear bandits regret rate (up to logarithmic factors), with ℛ_n ≤𝒪(n^1/2log(n)).

In the corollary above we assume that 𝒢 = 1 for ease of exposition; results follow in a similar vein for other values of 𝒢 with the constants altered. One way to interpret the results of Corollary <ref> in contrast to the regret bounds obtained for linear losses is the following. We introduce additional parameters into our analysis to handle the infinite dimensionality of our feature vectors – the effective dimension m and bias of our estimate ϵ. When the effective dimension m is chosen to be large we can build an estimate of the adversarial action ŵ_t which has low bias, however this estimate would have large variance (𝒪(m)). On the other hand if we choose m to be small we can build a low variance estimate of the adversarial action but with high bias (ϵ is large). We trade these off optimally to get the regret bounds established above. In the case of exponential decay we obtain that the choice m = 𝒪(log(n)) is optimal, hence the regret bound degrades only by a logarithmic factor in terms of n as compared to linear losses (where m would be a constant). When we have polynomial decay, the effective dimension is higher m = 𝒪(n^1/β-1) which leads to worse bounds on the expected regret. Note that asymptotically as β→∞ the regret bound goes to n^1/2 which aligns well with the intuition that the effective dimension is small. While when β→ 2 (the effective dimension m is large) and the regret upper bound becomes close to linear in n.



§ FULL INFORMATION SETTING
 


 §.§ Full information Exponential Weights


 
We begin by presenting a version of the exponential weights algorithm, Algorithm <ref> adapted to our setup. In each round we sample an action vector a_t ∈𝒜 (a compact set) from the exponential weights distribution p_t. After observing the loss, ⟨Φ(a_t),w_t ⟩_ℋ we update the distribution by a multiplicative factor, exp(-η⟨ w_t, Φ(a) ⟩_ℋ). In the algorithm presented we choose the initial distribution p_1(a) to be uniform over the set 𝒜, however we note that alternate initial distributions with support over the whole set could also be considered. We can establish a sub-linear regret of 𝒪(√(n)) for the exponential weights algorithm.

[Proof in Appendix <ref>] Assume that in Algorithm <ref> the step size η is chosen to be, η  = √(log(vol(𝒜))/e-2)·1/𝒢^2n^1/2,
with n large enough such that √(log(vol(𝒜))/e-2)1/n^1/2≤ 1. Then the expected regret after n rounds is bounded by, 
    ℛ_n  ≤√((e-2)log(vol(𝒜)))𝒢^2n^1/2.





 §.§ Conditional Gradient Descent


Next we present an online conditional gradient (Frank-Wolfe) method <cit.> adapted for kernel losses. The conditional gradient method is also a well studied algorithm studied in both the online and offline setting <cit.>. The main advantage of the conditional gradient method is that as opposed to projected gradient descent and related methods, the projection step is avoided. At each round the conditional gradient method involves the optimization of a linear (kernel) objective function over 𝒜 to get a point v_t ∈𝒜. Next we update the optimal mean action X_t+1 by re-weighting the previous mean action X_t by (1-γ_t) and weight our new action v_t by γ_t. Note that this construction also automatically suggests a distribution over a_1,v_1,v_2,…,v_t ∈𝒜 such that, X_t+1 is a convex combination of Φ(a_1),Φ(x_1),…,Φ(a_t). For this algorithm we can prove a regret bound of 𝒪(n^3/4).

 Let the step size be η = 1/2n^3/4. Also let the mixing rates be γ_t = min{1,2/t^1/2}, then Algorithm <ref> attains regret of 
    ℛ_n  ≤ 8 𝒢^2n^3/4.









§ APPLICATION: GENERAL QUADRATIC LOSSES
 

The first example of losses that we present are general quadratic losses. At each round the adversary can choose a symmetric (not necessarily positive semi-definite matrix) A ∈ℝ^d × d, and a vector b∈ℝ^d, with a constraint on the norm of the matrix and vector such that ‖ A ‖_F^2 + ‖ b ‖_2^2 ≤𝒢^2. If we embed this pair into a Hilbert space defined by the feature map (A,b) we get a kernel loss defined as – ⟨Φ(x) , (A,b) ⟩_ℋ = x^⊤Ax+ b^⊤x, where Φ(x) = (xx^⊤,x) is the associated feature map for any x ∈𝒜 and the inner product in the Hilbert space is defined as the concatenation of the trace inner product on the first coordinate and the Euclidean inner product on the second coordinate. The cumulative loss that the player aspires to minimize is, ∑_t=1^n x_t^⊤ A_t x_t + b_t^⊤ x_t. The setting without the linear term, that is when b_t = 0 with positive semidefinite matrices A_t is previously well studied in <cit.>. When the matrix is not positive semi-definite (making the losses non-convex) and there is a linear term, regret guarantees and tractable algorithms have not been studied even in the full information case. 

As this is a kernel loss we have regret bounds for these losses. We demonstrate in the subsequent sections in the full information case it is also possible to run our algorithms efficiently. First for exponential weights we show sampling is efficient for these losses.

























Let B ∈ℝ^d × d be a symmetric matrix and b ∈ℝ^d. Sampling from q(a) ∝exp( a^⊤ B a + a^⊤ b) for ‖ a ‖_2 ≤ 1, a ∈ℝ^d is tractable in 𝒪̃(d^4) time.



 §.§ Guarantees for Conditional Gradient Descent

We now demonstrate that conditional gradient descent also can be run efficiently when the adversary plays a general quadratic loss. At each round the conditional gradient descent requires the player to solve the optimization problem, v_t = _a∈𝒜⟨∇ F_t(X_t), Φ(a) ⟩_ℋ. When the set of actions is 𝒜 = a ∈ℝ^d : ‖ a ‖_2 ≤ 1 then under quadratic losses this problem becomes,

    v_t    = _a ∈𝒜 a^⊤ B a + b^⊤a,

for an appropriate matrix B and b that can be calculated by aggregating the adversary's actions up to step t. Observe that the optimization problem in Equation (<ref>) is a quadratically constrained quadratic program (QCQP) given our choice of 𝒜. The dual problem is the (semi-definite program) SDP,

    max - t  - μ    s. t.    [ B + μ I     b/2;     b/2       t ]≻ 0.

For this particular program with a norm ball constraint set it is known the duality gap is zero provided Slater's condition holds, that is, strong duality holds <cit.>. 

Another example of losses where our framework is computationally efficient is when the underlying losses are posynomials (class of polynomials). We present this discussion in Appendix <ref>.


§ CONCLUSIONS

Under bandit feedback it would be interesting to explore if it is possible to establish lower bounds on the regret under the eigendecay conditions stated. Another interesting technical challenge is to see if Lemma <ref> which we use to control the bias in our estimators can be sharpened to provide non-trivial regret guarantees even for slow eigendecay (1<β≤ 2). Finding more kernel losses where our algorithms are provably computationally efficient is another direction that is exciting. Finally analyzing a mirror descent type algorithm under this framework could be useful to efficiently solve a wider class of problems. 


  §.§.§ Acknowledgments

We gratefully acknowledge the support of the NSF through grant IIS-1619362 and of the Australian Research Council through an Australian Laureate Fellowship (FL110100281) and through the Australian Research Council Centre of Excellence for Mathematical and Statistical Frontiers (ACEMS).

*
 


Appendix




 §.§ Organization of the Appendix and Roadmap of the Proof

Here we describe the general organization of the proofs of the paper. We use the same notation for parameters as throughout the paper.

In Appendix <ref> we provide a proof of Theorem <ref> and Corollary <ref>. At a high level, the elements to prove this theorem are similar to that of proving regret bounds for linear losses. We first decompose the regret into an approximation error term that arises due to the construction of the finite dimensional proxy Φ_m(·) and another term which corresponds to the regret of a finite dimensional linear loss game (see Equation <ref>). To prove Theorem <ref> we then proceed in Appendix <ref> to control the regret of this finite dimensional linear bandit game by classical techniques. Crucially we also control terms that arise due to the bias in our estimators by invoking Lemma <ref>.


In Appendix <ref> we introduce and discuss ideas related to kernel principal component analysis (PCA). While in Appendix <ref> we prove Theorem <ref>. Recall that this theorem was vital in establishing that the finite dimensional feature map we construct in Algorithm <ref> induces a kernel  that is an ϵ-approximation of . In Appendix <ref> we establish bounds on the sample complexity and control the error if the sample covariance matrix is used instead of the full covariance matrix in Algorithm <ref>. 

The results about the full information setting, specifically the proofs of Theorems <ref> and <ref> are provided in Appendix <ref>. In Appendix <ref> we apply our framework to posynomial losses, in Appendix <ref> we discuss Hoeffding's inequality and John's Theorem. Finally in Appendix <ref> we present experimental evidence to verify our claims.

 









§ BANDITS EXPONENTIAL WEIGHTS REGRET BOUND


In this section we prove the regret bound stated in Section <ref>. Here we borrow all the notation from Section <ref>. As defined before the expected regret for Algorithm <ref> after n rounds is

    ℛ_n  = 𝔼[∑_t=1^n ⟨Φ(a_t),w_t⟩_ℋ - ⟨Φ(a^*),w_t⟩_ℋ]  = 𝔼[ ∑_t=1^n 𝔼_a_t∼ p_t[ ⟨Φ(a_t),w_t⟩_ℋ - ⟨Φ(a^*),w_t⟩_ℋ|ℱ_t-1] ],

where p_t is the exponential weights distribution described in Algorithm <ref>, a^* is the optimal action and ℱ_t-1 is the sigma field that conditions on (a_1,a_2,…,a_t-1,y_1,y_2,…,y_t-1,y_t), the events up to the end of round t-1. We will prove the regret bound for the case when the kernel is infinite dimensional, that is, the feature map Φ(a) ∈ℝ^D, where D = ∞. When D is finite the proof is identical with ϵ = 0. Recall that when D is infinite we constrain the adversary to play rank-1 actions. We are going to refer to the adversarial action as w_t =: Φ(y_t) for some y_t ∈ℝ^d. We now expand the definition of regret and get,

    ℛ_n  = 𝔼[ ∑_t=1^n 𝔼_a_t∼ p_t[ ⟨Φ(a_t),w_t⟩_ℋ - ⟨Φ_m(a_t),w_t⟩_ℋ|ℱ_t-1] ] 
     
     + 𝔼[ ∑_t=1^n 𝔼_a_t∼ p_t[ ⟨Φ_m(a^*),w_t⟩_ℋ - ⟨Φ(a^*),w_t⟩_ℋ|ℱ_t-1] ]
      + 𝔼[ ∑_t=1^n 𝔼_a_t∼ p_t[ ⟨Φ_m(a_t),w_t⟩_ℋ - ⟨Φ_m(a^*),w_t⟩_ℋ|ℱ_t-1] ]_=:ℛ_n^m.

Here ℛ_n^m is the regret when we play the distribution in Algorithm <ref> but are hit with losses that are governed by the kernel – (·,·) (with the same a^* as before). Observe that in R_n^m only the component of w_t in the subspace Ŝ_m contributes to the inner product, thus every term is of the form 

    ⟨Φ_m(a_t),w_t ⟩    = ⟨Φ_m(a_t),Φ_m(y_t) ⟩ = (y_t,a_t).

As the proxy kernel  is uniformly close by Theorem <ref> we have,

    ℛ_n    ≤ 2ε n + ℛ_n^m.





 §.§ Proof of Theorem <ref>
 
We will now attempt to bound ℛ_n^m and prove Theorem <ref>. First we define the unbiased estimator (conditioned on ℱ_t-1) of Φ_m(y_t) at each round,

    w̃_t := (a_t,y_t)  ((Σ_m^(t))^-1Φ_m(a_t)),      t∈{1,…,n },

where Φ_m(y_t) = P_Ŝ_m(Φ(y_t)) = P_Ŝ_m(w_t). We cannot build w̃_t as we do not receive (a_t,y_t) as feedback. Thus we also have

    𝔼_a_t ∼ p_t[ ŵ_t |ℱ_t-1] = 𝔼[(a_t,y_t)((Σ_m^(t))^-1Φ_m(a_t))|ℱ_t-1] 
        =Φ_m(y_t) + 𝔼[((a_t,y_t)-(a_t,y_t) ) ((Σ_m^(t))^-1Φ_m(a_t))_=:ξ_t,  the bias|ℱ_t-1], t∈{1,…,n }.

If Φ_m(·) = Φ(·) then the bias ξ_t would be zero. 
We now present some estimates involving w̃_t. In the following section we sometimes denote w̃_t and ŵ_t more explicitly as w̃_t(a_t) and ŵ_t(a_t) where there may be room for confusion.
  For any fixed a ∈𝒜 we have,

    𝔼_a_t ∼ p_t[⟨w̃_̃t̃(a_t),Φ_m(a)⟩|ℱ_t-1]     = (y_t,a) ,      t ∈{1,…,n }.

We also have for all t ∈{1,…,t },

    𝔼_a_t∼ p_t[ (y_t,a_t) |ℱ_t-1]   = 𝔼_a_t∼ p_t[∑_a ∈𝒜p_t(a)⟨w̃_t(a_t) , Φ_m(a) ⟩|ℱ_t-1] .


 The first claim follows by Equation (<ref>) and the linearity of expectation we have

    𝔼_a_t ∼ p_t[⟨w̃_t(a_t),Φ_m(a)⟩|ℱ_t-1]  = ⟨𝔼[ w̃_t(a_t) |ℱ_t-1],Φ_m(a) ⟩ 
     = (y_t,a).

where the expectation is taken over p_t. Now to prove the second part of the theorem statement we will use tower property. Observe that conditioned on ℱ_t-1, p_t and a_t are measurable.

    𝔼[(y_t,a_t) |ℱ_t-1] 
        = 𝔼[𝔼_a ∼ p_t[ ⟨w̃_t(a_t),Φ_m(a) ⟩| a_t]|ℱ_t-1] = 𝔼[∑_a ∈𝒜p_t(a)⟨w̃_t (a_t), Φ_m(a) ⟩|ℱ_t-1].


We are now ready to prove Theorem <ref> and establish the claimed regret bound.
[Proof of Theorem <ref>] The proof is similar to the regret bound analysis of exponential weights for linear bandits. We proceed in 4 steps. In the first step we decompose the cumulative loss in terms of an exploration cost and an exploitation cost. In Step 2 we control the exploitation cost by using Hoeffding's inequality as is standard in linear bandits literature, but additionally we need to control terms arising out of the bias of our estimate. In Step 3 we bound the exploration cost and finally in the fourth step we combine the different pieces and establish the claimed regret bound.

Step 1: Using Lemma <ref> and the fact that w̃_t is an unbiased estimate of Φ_m(y_t) we can decompose the cumulative loss, the first term in R_n^m as

    𝔼[∑_t=1^n(a_t,y_t) ]  = 𝔼[ ∑_t=1^n [ ∑_a ∈𝒜 p_t(a) ⟨w̃_t(a_t), Φ_m(a) ⟩|ℱ_t-1]]  
     = (1-γ)𝔼[ ∑_t=1^n [ ∑_a ∈𝒜q_t(a) ⟨w̃_t, Φ_m(a) ⟩|ℱ_t-1]]_Exploitation   + γ·𝔼[ ∑_t=1^n [ ∑_a ∈𝒜ν_𝒥^𝒜(a) ⟨w̃_t, Φ_m(a) ⟩|ℱ_t-1]]_Exploration,

where the second line follows by the definition of p_t. 

Step 2: We first focus on the `Exploitation' term. 

    := (1-γ)𝔼[ ∑_t=1^n [ ∑_a ∈𝒜q_t(a) ⟨w̃_t, Φ_m(a) ⟩|ℱ_t-1]] 
        = (1-γ)𝔼[ ∑_t=1^n [ ∑_a ∈𝒜q_t(a) ⟨ŵ_t, Φ_m(a) ⟩|ℱ_t-1]]_=: + (1-γ)𝔼[ ∑_t=1^n [ ∑_a ∈𝒜q_t(a) ⟨w̃_t-ŵ_t, Φ_m(a) ⟩|ℱ_t-1]]_=:.





 Under our choice of γ by Lemma <ref> (proved in Appendix <ref>) we know that η⟨ŵ_t, Φ(a_t) ⟩ > -1. Therefore by Hoeffding's inequality (Lemma <ref>) we get,

    = 𝔼[∑_t=1^n[∑_a ∈𝒜  q_t(a) ⟨ŵ_t, Φ_m(a) ⟩|ℱ_t-1] ]   ≤ -1/η𝔼[∑_t=1^nlog( 𝔼_a∼ q_t[ exp(-η⟨ŵ_t(a_t), Φ_m(a) ⟩)])]_=:Γ_1
         + (e-2) η𝔼[∑_t=1^n [∑_a ∈𝒜 q_t(a)( ⟨ŵ_t, Φ_m(a) ⟩)^2 |ℱ_t-1] ]_=:Γ_2.

Both Γ_1 and Γ_2 can be bounded by standard techniques established in the literature of adversarial linear bandits. We will see that Γ_1 is a telescoping series and is controlled in Lemma <ref>. While the second term Γ_2 is the variance of the estimated loss is bounded in Lemma <ref>. We defer the proof of both Lemma <ref> and Lemma <ref> to Appendix <ref>. Plugging in the bounds on Γ_1 and Γ_2 into Equation (<ref>) we get,

    (1-γ) = (1-γ)·𝔼[∑_t=1^n[∑_a ∈𝒜  q_t(a) ⟨ŵ_t, Φ_m(a) ⟩|ℱ_t-1] ] 
       ≤𝔼[∑_i=1^n(a^*,y_t) ] + 1/ηlog(  |𝒜|) + 𝔼[∑_t=1^n ⟨ŵ_t-w̃_t,Φ_m(a^*) ⟩] + (e-2)η𝒢^4 m n 
       ≤𝔼[∑_i=1^n(a^*,y_t) ] + 1/ηlog(  |𝒜|) + ϵ n/𝒢^2η + (e-2)η𝒢^4 m n,

where the last inequality follows by Lemma <ref>. Also by Lemma <ref> we get, ≤ϵ n/𝒢^2η. Combining this with Equation (<ref>) we get,

    ≤𝔼[∑_i=1^n(a^*,y_t) ] + 1/ηlog(  |𝒜|) + 2ϵ n/𝒢^2η + (e-2)η𝒢^4 m n.


Step 3: Next, observe that the exploration term is bounded above as

    γ·𝔼[ ∑_t=1^n 𝔼[ ∑_a ∈𝒜ν_𝒥^𝒜(a) ⟨w̃_t, Φ_m(a) ⟩|ℱ_t-1]]    ≤ 4γ𝒢^2 n,

where the above inequality follows by Lemma <ref> and Cauchy-Schwartz inequality along with the fact that ϵ≤𝒢^2.





Step 4: Putting these all these together into Equation (<ref>) we get the desired bound on the finite dimensional regret

    ℛ_n^m = 𝔼[∑_t=1^n ( (a_t,y_t) - (a^*,y_t) ) ]    ≤ 4 γ𝒢^2n + (e-2) 𝒢^4η m n + 2ϵ n/𝒢^2η + 1/ηlog(|𝒜|).

Plugging the above bound on ℛ_n^m into Equation (<ref>) we get a bound on the expected regret as

    ℛ_n ≤ 4γ𝒢^2 n + (e-2) 𝒢^4η m n + 2ϵ n + 2ϵ n/𝒢^2η+1/ηlog(|𝒜|),

completing the proof.



  §.§.§ Technical Results used in Proof of Theorem <ref>
 
First let us focus on bounding Γ_1. A term analogous to Γ_1 also appears in the regret bound analysis for exponential weights in the adversarial linear bandits setting; we adapt those proof techniques here to work with biased estimates (ŵ_t). 

Let Γ_1 be as defined in Equation (<ref>) then we have

    Γ_1    ≥ -η𝔼[ ∑_i=1^n(a^*,y_t)] -log(  |𝒜|) -η𝔼[∑_t=1^n ⟨ŵ_t-w̃_t,Φ_m(a^*) ⟩] .


 Expanding Γ_1 we get

    Γ_1     = 𝔼[∑_t=1^nlog(𝔼_a∼ q_t[ exp(-η⟨ŵ_t, Φ_m(a) ⟩)] ) ]
       (i)=𝔼[∑_t=1^nlog{∑_a ∈𝒜exp( -η∑_i=1^t-1⟨ŵ_i, Φ_m(a) ⟩)·exp( -η⟨ŵ_t, Φ_m(a) ⟩)/∑_a ∈𝒜exp( -η∑_i=1^t-1⟨ŵ_i, Φ_m(a) ⟩)}]
       (ii)=𝔼[log(∑_a ∈𝒜exp( -η∑_i=1^n⟨ŵ_i, Φ_m(a) ⟩) ) -log( |𝒜|) ],

where (i) follows by the definition of q_t(a) and (ii) follows as the sum telescopes and we start of with the uniform distribution over 𝒜. We have for any element a'∈𝒜,

    𝔼[log(∑_a ∈𝒜exp( -η∑_i=1^n⟨ŵ_i, Φ_m(a) ⟩) ) ]   ≥ -𝔼[η∑_i=1^n⟨ŵ_i, Φ_m(a') ⟩]
        = -η𝔼[∑_t=1^n ⟨w̃_t,Φ_m(a') ⟩] - η𝔼[∑_t=1^n ⟨ŵ_t-w̃_t,Φ_m(a') ⟩] 
        = -η𝔼[∑_t=1^n (a',y_t) ] -η𝔼[∑_t=1^n ⟨ŵ_t-w̃_t,Φ_m(a') ⟩],

where the last equality by Lemma <ref>. Choosing a' = a^* and plugging this lower bound into Equation (<ref>) completes the proof.


The next lemma controls of the variance of the expected loss – Γ_2. A term analogous to Γ_2 appears in the regret bound analysis of exponential weights in adversarial linear bandits which we adapt to our setting.
 
Let Γ_2 be defined as in Equation (<ref>) and the choice of parameters as specified in Theorem <ref> then we have

    Γ_2 = (e-2) η𝔼[∑_t=1^n 𝔼_a ∼ q_t[⟨ŵ_t,Φ_m(a) ⟩^2 |ℱ_t-1] ]    ≤ (e-2)𝒢^4η m n/(1-γ).


 Note that by definition of q_t, we have that (1-γ)q_t(a) ≤ p_t(a). To ease notation let Σ_t := Σ_m^(t) = 𝔼_p_t[Φ_m(x) Φ_m(x)^⊤]. Taking expectation over the randomness in ŵ_t for any fixed a we have,

    𝔼_a_t∼ q_t[ ⟨ŵ_t(a_t), Φ_m(a) ⟩^2 ]     = Φ_m(a)^⊤𝔼[ŵ_t ŵ_t^⊤] Φ_m(a) 
        = Φ_m(a)^⊤𝔼_a_t ∼ p_t[ (a_t,y_t)^2 Σ_t^-1Φ_m(a_t)Φ_m(a_t)^⊤Σ_t^-1] Φ_m(a)
       ≤𝒢^4Φ_m(a)^⊤Σ_t^-1Φ_m (a).

where the second equality follows by the definition of ŵ_t. Given this calculation we now also take expectation over the choice of a so we have,

    𝔼_a∼ p_t[𝔼_a_t ∼ p_t[ ⟨ŵ_t, Φ_m(a) ⟩^2] ]    ≤𝒢^4𝔼_a ∼ p_t[ tr(Φ_m(a)^⊤Σ_t^-1Φ_m(a))] 
        = 𝒢^4tr ( Σ_t^-1𝔼_a ∼ p_t[ Φ_m(a) Φ_m(a)^⊤]) = 𝒢^4tr(I_m × m) = 𝒢^4m.

Summing over t=1 to n establishes the result.

We now prove the bound on the terms that arise out of our biased estimates.
 Let γ =4η𝒢^4m  and let ϵ≤𝒢^2, then for all a∈𝒜 and for all t∈{ 1,…, n} we have

    |⟨ŵ_t - w̃_t,Φ_m(a) ⟩|   ≤ϵ/η𝒢^2.


 By the definition of w̃_t and ŵ_t,

    w̃_t - ŵ_t _2    = ((y_t,a_t) - (y_t,a_t)) (Σ_m^(t))^-1Φ_m(a_t) _2 
        = |(y_t,a_t) - (y_t,a_t)|(Σ_m^(t))^-1Φ_m(a_t) _2 
       ≤ϵ·m/γ· (𝒢+√(ϵ)),

where the inequality follows as  is an ϵ-approximation of , the minimum eigenvalue of Σ_m^(t) is γ/m by Proposition <ref>. So by Cauchy-Schwartz we get,

    |⟨ŵ_t - w̃_t,Φ_m(a) ⟩|≤w̃_t - ŵ_t _2Φ_m_2    ≤ϵ m (𝒢+√(ϵ))^2/γ,

the claim now follows by the choice of γ and by the condition on ϵ.

While using Hoeffding's inequality to arrive at Inequality (<ref>) we assume that the estimate of the loss is lower bounded by -1/η. The next lemma help us establish that under the choice of γ the exploration parameter in Theorem <ref> this condition holds.

 Let ϵ≤𝒢^2 then for any a ∈𝒜 and for all t=1,…,n we have

    |⟨ŵ_t,Φ_m(a) ⟩|≤𝒢^2 sup_c,d ∈𝒜|Φ_m(c)^⊤( 𝔼_a ∼ p_t[ Φ_m(a) Φ_m(a)^⊤])^-1Φ_m(d)|.

Further if the exploration parameter is γ > 4η𝒢^4m then we have a bound on the estimated loss at each round

    η|⟨ŵ_t,Φ_m(a) ⟩|≤ 1,        ∀ a ∈𝒜.



 Recall the definition of Σ_m^(t) = 𝔼_p_t[ Φ_m(a) Φ_m(a)^⊤] (we drop the index t to lighten notation in this proof). The proof follows by plugging in the definition of the loss estimate ŵ_t,

    |ŵ_t^⊤Φ_m(a) |    =  |(a_t,y_t)  ( Σ^-1_m Φ_m(a_t))^⊤Φ_m(a) |
       ≤|(a_t,y_t) |_≤𝒢^2|( Σ^-1_m Φ_m(a_t))^⊤Φ_m(a)|
       ≤ 4𝒢^2sup_c,d ∈𝒜|Φ_m(c)^⊤Σ_m^-1Φ_m(d)|.

Now note that the matrix Σ_m has its lowest eigenvalue lower bounded by γ/m by Proposition <ref> <cit.>. Thus we have,

    sup_c,d ∈𝒜|Φ_m(c)^⊤Σ_m^-1Φ_m(d)|   ≤4𝒢^2 m/γ,

where the inequality above follows by the assumption that ϵ≤𝒢^2. Combing this with Equation (<ref>) yields the desired claim.



 §.§ Proof of Corollary <ref>

In this section we present the proof of Corollary <ref>, which establishes the regret bound under particular conditions on the eigen-decay of the kernel.
[Proof of Corollary <ref>] Given our assumption 𝒢=1 and by the choice of γ = 4η𝒢^4m the regret bound becomes,

    ℛ_n ≤20η m n _=:R_1  +2ϵ n/η_=: R_2 +1/ηlog( |𝒜|)_=:R_3+ 2ϵ n_=: R_4.

Case 1: First we assume (C,β)-polynomial eigen-value decay. By the results of Proposition <ref> we have a sufficient condition on the choice of m for  to be an ϵ-approximation of ,

    m =  [4Cℬ^2/(β-1)ϵ]^1/β-1.

With this choice of m we equate the terms R_1,R_2 and R_3 with each other. This yields the choice, 

    ϵ = log(|𝒜|)/2n,     and    η^2 = ϵ/10 m.

Note that under this choice there exists a constant n_0(β,C,ℬ,log(|𝒜|))>log(|𝒜|)/2  such that when n>n_0 then, R_4< R_1. Also note when n > log(| A |)/2 then ϵ < 1 = 𝒢^2 so the conditions of Theorem <ref> are indeed satisfied. Plugging in these choice of ϵ,m and η for n > n_0 yields,

    ℛ_n ≤ 4 R_1 = √(160)·[2^β+2Cℬ^2/β-1]^1/2(β-1)·(log(| A |))^β-2/2(β-1)· n^β/2(β-1).























Case 2: Here we assume (C,β)-exponential eigen-value decay. Again by the results of Proposition <ref> we have a sufficient condition for the choice of m for  to be an ϵ- approximation of ,

    m = 1/βlog(4C ℬ^2/βϵ).

Again as before, by equating R_1,R_2,R_3 yields ϵ = log(|𝒜|)/(2n) and η^2 = ϵ/10 m.
Again as with Case 1, there exists a constant n_0(β,C,ℬ,log(|𝒜|))>log(|𝒜|)/2  such that when n>n_0 then, R_4< R_1. Plugging in these choice of ϵ,m and η for n > n_0 yields,

    ℛ_n ≤ 4R_1 = √(320·log(|𝒜|)/β·log( 40Cℬ^2 n /βlog(|𝒜|))·  n).






























§ KERNEL PRINCIPAL COMPONENT ANALYSIS


We review the basic principles underlying kernel principal component analysis (PCA). Let  be some kernel defined over 𝒜⊂ℝ^d and x_1, ⋯, x_p ∼ℙ a probability measure over 𝒜. Let us denote a feature map of  by Φ : ℝ^d →ℝ^D.

The goal of PCA is to extract a set of eigenvalues and eigenvectors from a sample covariance matrix. In kernel PCA we want to calculate the eigenvectors and eigenvalues of the sample kernel covariance matrix,

    Σ̂ = 1/p∑_i=1^pΦ(x_i)Φ(x_i)^⊤.

When working in a reproducing kernel Hilbert space ℋ in which no feature map is explicitly available, an alternative approach is taken by working instead with the sample Gram matrix.
 
Let Φ(x_1), ⋯, Φ(x_p) be p points in ℋ. The eigenvalues of the sample covariance matrix, 1/p∑_i=1^p Φ(x_i)Φ(x_i)^⊤ equal the eigenvalues of the sample Gram matrix 𝕂∈ℝ^p× p, where the sample Gram matrix is defined entry-wise as 𝕂_ij = (x_i, x_j)/p.


Let X ∈ℝ^p× D be such that the i^th row is Φ(x_i)/√(p). The singular value decomposition (SVD) of X is 

    X = U D V^⊤,

with U ∈ℝ^p × p, D ∈ℝ^p × D and V ∈ℝ^D × D. Therefore X^⊤ X = V D^⊤ D V^⊤ and XX^⊤ = U DD^⊤ U^⊤. We identify X^⊤X as the sample covariance matrix and XX^⊤ as the sample Gram matrix. Since DD^⊤ and D^⊤ D are both diagonal and have the same nonzero values this establishes the claim.


Another insight used in kernel PCA procedures is the observation that the span of the eigenvectors corresponding to nonzero eigenvalues of the sample covariance matrix 1/p∑_i=1^p Φ(x_i)Φ(x_i)^⊤ is a subspace of the span of the data-points {Φ(x_i) }_i=1^p. This means that any eigenvector v corresponding to a nonzero eigenvalue for the second moment sample covariance matrix can be written as a linear combination of the p-datapoints, v_i = ∑_j=1^p ω_ijΦ(x_j) (ω_ij denotes the j^th component of ω_i ∈ℝ^p). Observe that v_i are the eigenvectors of the sample covariance matrix, so we have

    [ 1/p∑_i=1^p Φ(x_i)Φ(x_i)^⊤] ( ∑_j=1^p ω_ijΦ(x_j)   ) = μ_i ∑_j=1^p ω_ijΦ(x_j).

This implies we may consider solving the equivalent system

    μ_i ( ⟨Φ(x_k) , v_i ⟩_ℋ) = ⟨Φ(x_k), (1/p∑_i=1^p Φ(x_i)Φ(x_i)^⊤)  v_i  ⟩_ℋ∀ k = 1, ⋯, p.


Substituting v_ i = ∑_j=1^p ω_ijΦ(x_j) into Equation (<ref>), and using the definition of 𝕂 we obtain

    μ_i 𝕂ω_i = 𝕂^2 ω_i.

To find the solution of this last equation we solve the eigenvalue problem,

    𝕂ω_i = μ_i ω_i.

Once we solve for α_i we can recover the eigenvector of the sample covariance matrix by setting v_ i = ∑_j=1^p ω_ijΦ(x_j).



§ PROXY KERNEL PROPERTIES

In this section we prove Theorem <ref>. We reuse the notation introduced in Section <ref> which we recall here. 

Let {μ_j }_j=1^∞ be the Mercer's eigenvalues of a kernel  under measure ℙ with eigenfunctions {ϕ_j }_j=1^∞, and we assume that sup_j∈ℕsup_x ∈𝒜|ϕ_j(x) |≤ℬ for some ℬ < ∞. Let m(ϵ) be such that ∑_j=m+1^∞μ_j ≤ϵ/4ℬ^2 and denote the m^th eigen-gap as δ_m = 1/2( μ_m - μ_m+1). Denote by S_m and Ŝ_m the subspaces spanned by the first m eigenvectors of the covariance matrix 𝔼_x ∼ℙ[ Φ(x) Φ(x)^⊤] and a sample covariance matrix 1/p∑_i=1^p Φ(x_i) Φ(x_i)^⊤ respectively. Define P_S_m and P_Ŝ_m to be the projection operators to S_m and Ŝ_m. Recall the definition of 

    ^o_m(x,y) = ⟨ P_S_m (Φ(x)), P_S_m (Φ(y)) ⟩_ℋ = ⟨Φ_m^o(x),Φ_m^o(y) ⟩_ℋ,

a deterministic approximate kernel and the stochastic proxy approximate kernel 

    ( x,y) = ⟨ P_Ŝ_m (Φ(x)), P_Ŝ_m (Φ(y)) ⟩_ℋ,
 
with associated feature map Φ_m(x) = P_Ŝ_mΦ(x). We first prove Lemma <ref> restated here.
*

By definition, for all x,y ∈𝒜

    (x,y) - ^o( x,y)     = ∑_j=m+1^∞μ_j ϕ_j(x) ϕ_j(y)  ≤∑_j=m+1^∞μ_j |ϕ_j(x) ϕ_j(y) |≤∑_j=m+1^∞μ_j ℬ^2 ≤ϵ/4.

The reverse inequality; ^o(x,y) - (x,y) ≤ϵ/4, is also true therefore,

    |(x,y) - ^o( x,y) |≤ϵ/4,

for all x,y ∈𝒜.


We now state and prove an expanded version of Theorem <ref> (where w = min(√(ϵ)/2,δ_m/2)) which is used to establish the ϵ-approximability of the stochastic kernel .

Let ϵ,m, ℙ be as in Lemma <ref>. Define the m-th level eigen-gap as δ_m = 1/2( μ_m - μ_m+1). Also let B_m = 2𝒢^2/δ_m( 1 + √(α/2)), δ_m/2>w>0  and p ≥B_m^2 𝒢^2 /w^2. The finite dimensional proxies _m^o and _m satisfy the following properties with probability 1-e^-α:


  * |(x,y) - _m(x,y) | ≤ϵ/4 + √(ϵ)w + w^2.

  * |_m(x,y) - _m^o(x,y) | ≤ w^2,             ∀ x,y ∈𝒜.

  * The Mercer operator eigenvalues μ^(m)_1 ≥⋯≥μ^(m)_m and μ_1 ≥⋯≥μ_m of  and ^o follow sup_i=1, ⋯, m |μ^(m)_i - μ_i| ≤ w^2.


Theorem <ref> shows that, as long as sufficiently samples p(m) are used, with high probability  is uniformly close to _m^o and therefore to . We prove this theorem by a series of lemmas and auxiliary theorems. We first prove part (1) and (2) and establish that under mild conditions on  we can extract a finite dimensional proxy kernel  by truncating the eigen-decomposition of  and estimating a feature map with samples. We leverage a kernel PCA result by <cit.> to construct . 
<cit.>

If m, p, S_m, Ŝ_m, δ_m, B_m and α are defined as in Theorem <ref> then with probability 1-exp(-α) we have

    ‖ P_S_m - P_Ŝ_m‖_F≤B_m/√(p(m)).

In particular,

    Ŝ_m ⊂{ g + h, g ∈ S_m, h ∈ S_m^⊥, ‖ h ‖_ℋ≤2B_m/√(p)‖ g ‖_ℋ}.


Now using this theorem we prove Part (1) of Theorem <ref>.
 
With probability 1-e^-α we have,

    |(x,y) - (x,y) |≤ϵ/4 + √(ϵ)w + w^2 ,         ∀ x,y ∈𝒜.



First we show this holds for x=y. 

    ‖Φ(x) - P_Ŝ_m (Φ(x)) ‖_ℋ   (i)≤‖Φ(x) - P_S_m (Φ(x)) ‖_ℋ + ‖ P_S_m (Φ(x)) - P_Ŝ_m (Φ(x)) ‖_ℋ
       (ii)≤√(ϵ)/2 + ‖Φ(x) ‖_ℋ‖ P_S_m - P_Ŝ_m‖_op(iii)≤√(ϵ)/2 + 𝒢B_m/√(p(m))(iv)≤√(ϵ)/2 + w,

where (i) follows by triangle inequality, (ii) is by the fact that P_S_m(Φ(x)) is an ϵ/4 approximation of , (iii) follows by Theorem <ref> and (iv) is by the choice of p(m). Therefore with probability at least 1-e^α for all x ∈𝒜

    |(x,x) - (x,x)|≤ϵ/4 + √(ϵ)w + w^2.

Now we prove the statement for general x,y ∈𝒜. We write Φ(x)  = Φ_m(x) + h_x and Φ(y) = Φ_m(y) + h_y. The above calculation implies that ‖ h_x ‖_ℋ≤√(ϵ)/2 + w and ‖ h_y ‖_ℋ≤√(ϵ)/2 + w. We now expand (x,y) to get

    ⟨Φ(x), Φ(y) ⟩_ℋ = ⟨Φ_m(x), Φ_m(y) ⟩_ℋ + ⟨ h_x, Φ_m(y) ⟩_ℋ + ⟨Φ_m(x), h_y ⟩_ℋ + ⟨ h_x ,  h_y ⟩_ℋ.

Since h_x and h_y both live in Ŝ_m^⊥:

    ⟨Φ(x), Φ(y) ⟩_ℋ = ⟨Φ_m(x), Φ_m(y) ⟩_ℋ + ⟨ h_x ,  h_y ⟩_ℋ .

Rearranging terms,

    |⟨Φ(x), Φ(y) ⟩_ℋ  - ⟨Φ_m(x), Φ_m(y) ⟩_ℋ|   = |⟨ h_x ,  h_y ⟩_ℋ|≤ϵ/4 + √(ϵ)w + w^2.

This establishes the claim.

We now move on to the proof of Part (2) in Theorem <ref>.

If p,B_m are chosen as stated in Theorem <ref> we have

    |(x,y) - ^o(x,y)|≤ w^2         ∀ x,y ∈𝒜



The feature map for ^o is P_S_m(Φ(x)) for all x ∈𝒜 while P_Ŝ_m(Φ(x)) is the feature map for . We first show that for all x ∈𝒜,

    ‖ P_S_m(Φ(x)) - P_Ŝ_m(Φ(x)) ‖_ℋ   ≤‖Φ(x) ‖_ℋ‖ P_S_m - P_Ŝ_m‖_op≤𝒢B_m/√(p(m))≤ w,

where the second inequality follows by applying Theorem <ref> and the last inequality follows by the choice of B_m. A similar argument as the one used in the proof of Lemma <ref> lets us then conclude that,

    |(x,y) - ^o(x,y)| ≤ w^2,     ∀ x,y ∈𝒜.


We now proceed to prove part (3) of Theorem <ref>. We will show that the Mercer operator eigenvalues of  are close to Mercer operator eigenvalues of ^o. We first recall a useful result by <cit.>.
<cit.>
Let 𝒦 be a kernel over 𝒜×𝒜 such that sup_x ∈𝒜𝒦(x,x) ≤𝒢^2. Also let μ̂_1 ≥μ̂_2 ≥⋯≥μ̂_N be the eigenvalues of the Gram matrix ((x_i, x_j)/N)_i,j = 1^N for {x_i}_i=1^N∼ℙ. Then there exists a universal constant c such that for every t > 0

    ℙ[sup_i ∈1,…,N|μ̂_i - μ_i |≥ t ] ≤ 2exp( -ct/𝒢^2√(N/log(N))),

where for i > N we define μ̂_i = 0.


The top m eigenvalues of the sample kernel covariance matrix equal that of the Gram matrix.

Recall that we established this proposition in Appendix <ref> as Lemma <ref>. Further note that for any set of samples x_1, ⋯, x_N ∼ℙ, the Gram matrices of ^o (𝕂_m^o(N)) and  (𝕂_m(N)) are close in Frobenius norm as the matrices are close element-wise by part (2) of Theorem <ref>.

    ‖𝕂_m^o(N) - 𝕂_m(N) ‖_F ≤ w^2.

Let μ̂^(m,o)_1 ≥μ̂^(m,o)_2 ≥⋯μ̂^(m,o)_N and μ̂^(m)_1 ≥μ̂^(m)_2 ≥⋯μ̂^(m)_N be the eigenvalues of 𝕂_m^o(N) and 𝕂_m(N) respectively. For both of these Gram matrices only the top m out of N eigenvalues will be nonzero, since both kernels are m-dimensional. By the Wielandt-Hoffman inequality <cit.> this implies that the ordered eigenvalues are close,

    sup_i=1,⋯ N |μ̂^(m,o)_i - μ̂^(m)_i| ≤ w^2.

Theorem <ref> and Proposition <ref> together imply the statement of Theorem <ref> with the Gram matrix replaced by the sample covariance matrix holds. 

The Mercer operator eigenvalues μ^(m)_1 ≥⋯≥μ^(m)_m and μ_1 ≥⋯≥μ_m of  and ^o follow

    sup_i=1, ⋯, m |μ^(m)_i - μ_i| ≤ w^2.



We will use the probabilistic method. By Theorem <ref>, for every t > 0 there is N(t) ∈ℕ large enough such that probability of the event – the eigenvalues of both sample Gram matrices 𝕂_m(N) and 𝕂_m^o(N) be uniformly close to the Mercer operator eigenvalues μ^(m)_1 ≥⋯≥μ^(m)_m and μ_1 ≥⋯≥μ_m – is greater than zero.
By triangle inequality this implies that for all t>0

    sup_i=1, ⋯, m |μ^(m)_i - μ_i|    ≤sup_i_1 |μ^(m)_i_1 - μ̂^(m)_i_1      | + sup_i_2 |   μ̂^(m)_i_2 - μ̂^(m,0)_i_2  | + sup_i_3| μ̂^(m,0)_i_3 -   μ_i_3 | 
       ≤  t + w^2 + t = w^2+2t.

Taking the limit as t → 0 yields the result.




 §.§ Bounds on the effective dimension m

In this section we establish bounds on the effective dimension m under different eigenvalue decay assumptions.
 Let the conditions stated in Theorem <ref> and Lemma <ref> hold. 


  * When the kernel  has (C,β)-polynomial eigenvalue decay then 

    m ≥[4Cℬ^2/(β-1)ϵ]^1/β-1,

suffices for ^o to be an ϵ/4-approximation of  and therefore for  to be an ϵ-approximation of . 

  * When the kernel  has (C,β)-exponential eigenvalue decay then 

    m ≥1/βlog(4C ℬ^2/βϵ),

suffices for ^o to be an ϵ/4-approximation of  and therefore for  to be an ϵ-approximation of . 



We need to ensure that the assumption in Lemma <ref> holds. That is,

    ∑_j=m+1^∞μ_j ≤ϵ/4ℬ^2.

We will prove the bound assuming a (C,β)-polynomial eigenvalue decay, the calculation is similar when we have exponential eigenvalue decay. Note that,

    ∑_j=m+1^∞μ_j    ≤∑_j=m+1^∞ C j^-β≤∫_m^∞ C x^-β dx  = C/β-11/m^β-1.

We demand that,

    C/β-11/m^β-1   ≤ϵ/4ℬ^2,

rearranging terms yields the desired claim.



§ PROPERTIES OF THE COVARIANCE MATRIX – Σ_M^(T)


We borrow the notation from Section <ref>. In this section we let μ_m be the smallest nonzero eigenvalue of 𝔼_x ∼ν[ Φ_m(x)Φ_m(x)^⊤] where ν is the exploration distribution over 𝒜. 


Let μ_m^(t) be the m-th (smallest) eigenvalue of Σ_m^(t). Then we have

    μ_m^(t)≥γμ_m.



Recall that in each step we set p_t = (1-γ) q_t + γν.  Let v ∈ℋ be a vector with norm 1. 

    v^⊤Σ_m^(t) v = (1-γ)· v^⊤𝔼_x ∼ q_t[    Φ_m(x) Φ_m(x)^⊤] v+ γ· v^⊤𝔼_x ∼ν[ Φ_m(x) Φ_m(x)^⊤]v.

Since both summands on the RHS are nonnegative, this quantity at least achieves a value of γ· v^⊤𝔼_x ∼ν[ Φ_m(x) Φ_m(x)^⊤]v ≥γμ_m.

Observe that by our discussion in Appendix <ref>, the minimum eigenvalue when the distribution is ν_𝒥 (John's distribution) over Φ_m(𝒜), then μ_m = 1/m. That is, if ν_𝒥^𝒜 is the exploration distribution over 𝒜 then μ_m = 1/m.
 If ν_𝒥^𝒜 is the exploration distribution then we have

    μ_m^(t)≥γ/m.




 §.§ Finite Sample Analysis

Next we analyze the sample complexity of the operation of building the second moment matrix in Algorithm <ref> using samples. Let Σ̂_m^(t) be the second moment matrix estimate built by using x_1, ⋯, x_r drawn i.i.d. from p_t.  

    Σ̂_m^(t) = 1/r∑_i=1^r Φ_m(x_i) Φ_m(x_i)^⊤.

We will show how to chose r appropriately to preserve the validity of the regret bound when we use Σ̂_m^(t) (built using finite samples) instead of Σ_m^(t). First we present some observations.

The eigenvalues μ_1^(t)≥⋯≥μ_m^(t) of 𝔼_x∼ p_t[ Φ_m(x) Φ_m(x)^⊤] are exactly Mercer operator eigenvalues for  under p_t. 


Assume r ≥ m. Let x_1, ⋯, x_r ∼ p_t. The eigenvalues of the sample covariance Σ̂_m^(t) coincide with the top m eigenvalues of the Gram matrix 𝕂_m,p^(t) = ( (x_i,x_j) )_i,j = 1^p.

We formalize the above remark in Lemma <ref>. We will use an auxiliary lemma by <cit.> which we present here for completeness.
<cit.>
Let 𝒦' be a kernel over 𝒳×𝒳 such that sup_x ∈𝒳𝒦'(x,x) ≤𝒢'. Let Σ' be the covariance of Φ'(x), x ∼ℙ. If Σ̂'_r is the sample covariance built by using r samples x_1, ⋯, x_r ∼ℙ, with probability 1-exp(-δ):

    ‖Σ' - Σ̂'_p ‖_op≤2𝒢'/√(r)( 1 + √(δ/2)).


The following lemma will allow us to derive an operator norm bound between the inverse matrices ( Σ_m^(t))
^-1 and (Σ̂_m^(t))^-1 from an operator norm bound between the matrices Σ_m^(t) and Σ̂_m^(t).

If ‖ A - B ‖_op≤ s, then ‖ A^-1 - B^-1‖_op≤s/λ_min(A) λ_min(B), where λ_min(A) and λ_min(B) denote the minimum eigenvalues of A and B respectively.


The following equality holds:

    A^-1 - B^-1 = A^-1( B- A ) B^-1.

Applying Cauchy-Schwartz for spectral norms yields the desired result.


We are now ready to show that given enough samples r, the operator norm between the inverse covariance and the inverse sample covariance is small.

 
Let g: ℝ^+_(1, ∞)→ℝ be defined as g(x) is the value such that g(x)/log(g(x)) = x. 
If the number of samples

    r ≥max( g( [ (ln(2) + ζ)2𝒢/c γμ_m]^2),  ( 4𝒢(1+√(ζ/2))/(γμ_m)^2ϵ_1)^2   ),
 where c is the same constant as in Theorem <ref>, then with probability 1-2e^-ζ:

    ‖( Σ_m^(t))^-1 - ( Σ̂_m^(t))^-1‖_op≤ϵ_1.


 We start by showing that if r follows the requirements stated in the lemma above, then the minimum eigenvalue of Σ̂_m^(t) is lower bounded by γμ_m/2 with probability 1-exp(-ζ). We invoke Theorem <ref> to prove this. Let us denote by μ_1^(t)≥⋯≥μ_m^(t) and μ̂_1^(t)≥⋯≥μ̂_m^(t) the eigenvalues of Σ_m^(t) and Σ̂_m^(t) respectively.

We want to ensure that the probability of sup_i | μ_i^(t) - μ̂_i^(t)| ≥γμ_m/2 be less than e^-ζ. Again by invoking Theorem <ref>, this is true if exp(-ζ) ≤ 2exp( -cγμ_m/2𝒢√(r/log(r)). This yields the condition,

    r/log(r)≥[(ln(2)+ζ) 2𝒢/cγμ_m]^2.

This together with triangle inequality (as μ_m^(t)≥μ_m ≥γμ_m) ensures that if r ≥ g( [ (ln(2) + ζ)2𝒢/c γμ_m]^2), then with probability 1-exp(-ζ),

    μ̂_m ≥γμ_m/2.

Setting A = Σ_m^(t) and B = Σ̂_m^(t) and invoking the concentration inequality Lemma <ref>, we have that 

    ‖Σ_m^(t) - Σ̂_m^(t)‖_op≤(γλ_m)^2ϵ_1/2,
 
with probability 1-exp(-ζ) as choose r to satisfy

    2𝒢/2√(r)( 1+ √(ζ/2)) = (γμ_m)^2ϵ_1/2.

As the matrices A and B are close with high probability, Lemma <ref> proves that the inverses are also close,

    ‖( Σ_m(t))^-1 - (Σ̂_m^(t))^-1‖_op≤ϵ_1.

with the same probability. By union bound as long as r ≥max( g( [ (ln(2) + ζ)2𝒢/c γλ_m]^2),  ( 4𝒢(1+√(ζ/2))/(γλ_m)^2ϵ_1)^2   ) the stated claim holds with probability 1-2exp(-ζ).




  §.§.§ Auxiliary Lemmas

Let us denote the pseudo-inverse of a symmetric matrix A by A^†. We now prove Lemma <ref> that formalizes the connection between the eigenvalues the Gram matrix and sample covariance matrix.
 
For any x,y ∈𝒜:

    Φ_m(x)^⊤( Σ̂_m^(t))^-1Φ_m(y) = A_x^⊤( 𝕂_m,p^(t))^2† A_y^⊤,

where A_x = ((x, x_1), ⋯, (x,x_p) )^⊤ and A_y = ((y, x_1), ⋯, (y,x_p) )^⊤.



The claim can be verified by a singular value decomposition of both sides.


Given Lemma <ref> we also prove a bound on the distance between the estimates of adversarial actions generated in Algorithm <ref>. Define w̃^(2)_t:= (Σ̂_m^(t))^-1Φ_m(a_t)(a_t,w_t) and let ŵ_t := w̃^(1)_t= (Σ_m^(t))^-1Φ_m(a_t)(a_t,w_t).
 We have that

    ‖w̃^(2)_t - w̃^(1)_t ‖_ℋ≤ϵ_1 𝒢.


In other words, the bias resulting from using the sample covariance instead of the true covariance is of order ϵ_1 as long as we take enough samples p at each time step. We can drive ϵ_1 to be as low as we like by choosing enough samples and hence this bias does not determine the rate in the regret bounds in Theorem <ref>.


§ FULL INFORMATION REGRET BOUNDS
 


 §.§ Exponential Weights Regret Bound

 
In this section we prove a regret bound for exponential weights and present a proof of Theorem <ref>. The analysis of the regret is similar to the analysis of exponential weights for linear losses <cit.>. In the proof below we denote the filtration at the end of round t by ℱ_t, that is, it conditions on the past actions of the player and the adversary (a_t-1,w_t-1,…,a_1,w_1).
[Proof of Theorem <ref>]
By the tower property and by the definition of the regret we can write the cumulative loss as,

    𝔼[∑_t=1^n⟨Φ(a_t), w_t ⟩]     = 𝔼[ ∑_t=1^n 𝔼_a_t ∼ p_t[ ⟨Φ(a_t), w_t ⟩|ℱ_t-1]] 
        = 𝔼[ ∑_t=1^n  [∫_𝒜 p_t(a) ⟨Φ(a), w_t ⟩ da |ℱ_t-1]].


Observe that our choice of η implies that η⟨Φ(a), w_t ⟩ > -1. By invoking Hoeffding's inequality (stated as Lemma <ref>) we get

    𝔼[∑_t=1^n[∫_𝒜  p_t(a) ⟨Φ(a), w_t ⟩ da |ℱ_t-1] ] 
       ≤ -1/η𝔼[∑_t=1^nlog( 𝔼_a ∼ p_t[ exp(-η⟨Φ(a), w_t ⟩)|ℱ_t-1])]_=:Γ + (e-2) η𝔼[∑_t=1^n ∫_𝒜[p_t(a) ⟨Φ(a), w_t ⟩^2 da|ℱ_t-1] ] 
       (i)≤ -Γ/η + (e-2)η𝒢^4 n,

where (i) follows by Cauchy-Schwartz and the bound on the adversarial and player actions. Next we bound Γ using Lemma <ref>. Substituting this bound into the expression above we get

    𝔼[∑_t=1^n⟨Φ(a_t), w_t ⟩] 
    
        ≤𝔼[∑_t=1^n⟨Φ(a^*),w_t⟩] + log(vol(𝒜))/η + (e-2)η𝒢^4 · n.

Rearranging terms we have the regret is bounded by

    ℛ_n    ≤  (e-2) 𝒢^4 η  n + log(vol(𝒜))/η.

The choice of η = √(log(vol(𝒜)))/√((e-2))𝒢^2n^1/2, optimally trades of the two terms to establish a regret bound of 𝒪(n^1/2).

Next we provide a proof of the bound on Γ used above.
 Assume that p_1(·) is chosen as the uniform distribution in Algorithm <ref>. Also let Γ be defined as follows

    Γ = 𝔼[∑_t=1^n log( 𝔼_a∼ p_t[exp( -η⟨Φ(a),w_t⟩_ℋ)|ℱ_t-1])].

Then we have that,

    Γ   ≥ -η𝔼[ ∑_i=1^n⟨Φ(a^*), w_i ⟩_ℋ]  -log( vol(𝒜)),

where a^* is the optimal action in hindsight in the definition of regret and vol(𝒜) is the volume of the set 𝒜.

Expanding Γ using the definition of p_t we have that,

    Γ   (i)=𝔼[∑_t=1^nlog{∫_𝒜exp( -η∑_i=1^t⟨Φ(a), w_i ⟩_ℋ)da/∫_𝒜exp( -η∑_i=1^t-1⟨Φ(a), w_i ⟩_ℋ)da}]
       (ii)=𝔼[log(∫_𝒜exp( -η∑_i=1^n⟨Φ(a), w_i ⟩_ℋ) da) ] -log( vol( 𝒜 )),

where (i) follows by the definition of p_t(a) and (ii) is by expanding the sum and canceling the terms in a telescoping series. The log(vol( 𝒜)) term is because we start off with a uniform distribution over all elements. Lastly observe that by optimality of a^* we have that,

    𝔼[log(∫_𝒜exp( -η∑_i=1^n⟨Φ(a), w_i ⟩) da) ]    ≥ -η𝔼[∑_i=1^n⟨Φ(a^*), w_i ⟩].

Plugging this into the above expression establishes the desired bound on Γ.

We now present a proof of Lemma <ref> that guarantees that it is possible to sample efficiently from the exponential weights distribution when the losses are quadratics.
[Proof of Lemma <ref>]
Let v_1, ⋯, v_d an orthonormal basis of eigenvectors of B with eigenvalues λ_1, ⋯, λ_d possibly negative. We express b using the basis {v_i}_i=1^d as b = ∑_i=1^d γ_i v_i. Also let a = ∑_i=1^d α_i v_i. By the definition of the set 𝒜 we have ∑_i=1^d α_i^2 ≤ 1. The distribution q(·) can be thus expressed as

    q(a) ∝exp( ∑_i=1^d (λ_i α_i^2 + γ_i α_i) ).

Completing the squares (whenever λ_i ≠ 0),

    q(a) ∝exp{∑_i=1^d λ_i ( α_i^2 + γ_i α_i/λ_i + (γ_i/2λ_i)^2) }.
 
Let us re-parametrize this distribution by setting β_i = (α_i + γ_i/2λ_i)^2. The inverse mapping is α_i=√(β_i) - γ_i/2λ_i. To sample from q(·) it is enough to produce a sample from a surrogate distribution β∼ t(β) and turn them into a sample of q where,

    t(β)    ∝exp( ∑_i=1^d λ_i β_i ),
    
    s.t.      0    ≤β_i, 
    ∑_i=1^d (√(β_i) - γ_i/2λ_i)^2    ≤ 1.

Let {ϵ_i}_i = 1^d be independent Bernoulli {-1, 1} variables, then a = ∑_i=1^d  ϵ_i (√(β_i)-γ_i/2λ_i)v_i is a sample from q. Note that the distribution t(β) is log-concave. We now show that the constraint set 𝒞 is convex, where 𝒞= {β | β_i ≥ 0, ∑_i=1^d (√(β_i) - γ_i/2λ_i )^2 ≤ 1}. 

Let β̂ and β̃ be two distinct points in 𝒞. We show that for any η∈ [0,1] the point ηβ̂ + (1-η) β̃∈𝒞. The non-negativity constraint is clearly satisfied (ηβ̂ + (1-η) β̃ )_i≥ 0, ∀ i. The second constraint can be rewritten as

    ∑_i=1^d β̂_i - γ_i√(β̂_i)/λ_i + (γ_i/2λ_i)^2 ≤ 1 
    ∑_i=1^d β̃_i - γ_i√(β̃_i)/λ_i + (γ_i/2λ_i)^2 ≤ 1 .

These equations imply that,

    η[∑_i=1^d β̂_i - γ_i√(β̂_i)/λ_i + (γ_i/2λ_i)^2] 
    + (1-η)[ ∑_i=1^d β̃_i - γ_i√(β̃_i)/λ_i + (γ_i/2λ_i)^2 ] ≤ 1.

By concavity of the square root function we have

    ∑_i=1^d ηγ_i√(β̂_i)/λ_i + (1-η)γ_i√(β̃_i)/λ_i≤∑_i=1^d γ_i √(ηβ̂_̂î + (1-η) β̃_̃ĩ)/λ_i,
 
these two observations readily imply that ηβ̂ + (1-η) β̃ satisfies the constraint of 𝒞 thus implying convexity of 𝒞. We can thus use Hit-and-Run <cit.> to sample from t(β) in Õ(d^4) steps and convert to samples from q(·) using the method described above. In case some eigenvalues are zero, say without loss of generality λ_1, ⋯, λ_R. Then set β_i = α_i^2 for i ∈{ R+1,…, d} and sample from the distribution,

    t(β)    ∝exp(∑_i=1^R γ_i α_i +  ∑_i=R+1^d λ_i β_i),
    
    s.t.      0    ≤β_i,
    ∑_i=1^R α_i^2     + ∑_i=R+1^d (√(β_i) - γ_i/2λ_i)^2  ≤ 1.

The analysis follows as before for this case as well.



 §.§ Conditional Gradient Method Analysis




The regret bound analysis for Algorithm <ref>, conditional gradient method over RKHSs follows by similar arguments to the analysis of the standard online conditional gradient descent <cit.>. To prove this we first prove the regret bound of a different algorithm – follow the regularized leader. 


 §.§ Follow the Regularized Leader


We present a version of follow the regularized leader <cit.> (FTRL, Algorithm <ref>) adapted to our setup. Note that this algorithm is not tractable in general as at each step we are required to perform an optimization problem over the convex hull of Φ(𝒜). However, we provide a regret bound that we will use in our regret bound analysis for the conditional gradient method. Let us define w_0 = X_1/η. We first establish the following lemma. 
  For any u ∈𝒜

    ∑_t=0^n ⟨ X_t , Φ(u) ⟩_ℋ≥∑_t=0^n ⟨ X_t , X_t+1⟩_ℋ.


This is the crucial lemma needed to prove regret bounds for FTRL algorithms and its  proof follows from standard arguments <cit.>. 
 Define a function g_t(·): ℝ^D ↦ R as,

    g_t(X) ≜[ η∑_s=1^t⟨ w_s, X ⟩_ℋ + ⟨ X,X ⟩_ℋ].


 
Define the Bregman divergence as,

    B_R(x||y) ≜ R(x) - R(y) - ⟨∇ R(y),(x-y) ⟩_ℋ.


Given these two definitions we now establish a lemma that will be used used to control the regret of FTRL.
 
For any t ∈{1,2,…, n } we have the upper bound,

    ⟨ w_t,X_t - X_t+1⟩_ℋ   ≤ 2η‖ w_t ‖^2_ℋ.



By the definition of Bregman divergence we have,

    g_t(X_t)     = g_t(X_t+1) + ⟨ X_t - X_t+1, ∇ g_t(X_t+1) ⟩_ℋ + B_g_t(X_t || X_t+1)
       ≥ g_t(X_t+1) + B_g_t(X_t || X_t+1),

where the inequality is because X_t+1 is the minimizer of g_t(·) over conv(Φ(𝒳)). After rearranging terms we are left with an upper bound on the Bregman divergence,

    B_g_t(X_t || X_t+1)    ≤ g_t(X_t) - g_t(X_t+1) 
        = ( g_t-1(X_t) - g_t-1(X_t+1)) + η⟨ w_t, X_t - X_t+1⟩_ℋ
       ≤η⟨ w_t, X_t - X_t+1⟩_ℋ,

where the last inequality follows because X_t-1 is the minimizer of the function g_t-1(·) over conv(Φ(𝒳)). Observe that B_g_t(X_t||X_t+1) = 1/2‖ X_t - X_t+1‖_ℋ^2. Thus by the Cauchy-Schwartz inequality we have,

    ⟨ w_t, X_t- X_t+1) ⟩_ℋ   ≤‖ w_t(X_t) ‖_ℋ‖ X_t - X_t+1‖_ℋ
        = ‖ w_t‖_ℋ√( 2 B_g_t(X_t||X_t+1)).

Substituting the upper bound from Equation (<ref>) we get,

    ⟨ w_t, X_t- X_t+1) ⟩_ℋ   ≤‖ w_t‖_ℋ·√(2η⟨ w_t, X_t - X_t+1⟩_ℋ).

Rearranging terms establishes the result.

 
Given a step size η >0, the regret suffered by Algorithm <ref> after n rounds is bounded by

    ℛ_n    ≤ 2 nη𝒢^2 + 2 𝒢^2/η.



By the definition of regret we have

    ℛ_n     =  𝔼[  ∑_t=1^n ⟨Φ(a_t),w_t⟩_ℋ -min_a ∈𝒜[∑_t=1^n  ⟨Φ(a_t),w_t ⟩_ℋ] ] 
       (i)=𝔼[∑_t=1^n 𝔼_a_t ∼𝒟_t[ ⟨ w_t,Φ(a_t) - Φ(a^*) ⟩_ℋ|ℱ_t-1] ](ii)=𝔼[ ∑_t=1^n  ⟨ w_t,X_t - Φ(a^*) ⟩_ℋ] 
       (iii)≤𝔼[ ∑_t=1^n⟨ w_t, X_t - X_t+1⟩_ℋ]  + 𝔼[ ∑_t=1^n⟨ w_t, X_t+1 - Φ(a^*) ⟩_ℋ] + 1/η (⟨ X_1,X_1 ⟩_ℋ - (⟨ X_0,X_0 ⟩_ℋ)
       (iv)≤𝔼[ ∑_t=1^n⟨ w_t, X_t - X_t+1⟩_ℋ] + 2𝒢^2/η.

The first equality follows as a^* is the minimizer, (ii) is by evaluating the expectation with respect to 𝒟_t, (iii) is an algebraic manipulation and finally (iv) follows by invoking Lemma <ref> and using Cauchy-Schwartz to bound the last term. We need to control the first term in Equation (<ref>) to get a regret bound. To control the first term we now invoke Lemma <ref>

    ℛ_n    ≤ 2η∑_t=1^n ‖ w_t ‖_ℋ^2 + 2𝒢^2/η≤ 2 nη𝒢^2 + 2𝒢^2/η.

This establishes the stated result.



 §.§ Regret Bound for Algorithm <ref>

In deploying Algorithm <ref> we will at each round find distributions over the action space 𝒜 as the player is only allowed play rank 1 actions in the Hilbert space at each round, while the action prescribed by the conditional gradient method might not be rank 1. Thus we find a distribution 𝒟_t such that,

    𝔼_a ∼𝒟_tΦ(a) = X_t,

where X_t is the action prescribed by Algorithm <ref>. We will strive to match the optimal action in expectation by choosing an appropriate distribution and get bounds on expected regret. For all t ∈{1,2,…,n } let X_t^* be defined as the iterates of the follow the regularized leader (Algorithm <ref>) with the regularization  set to R(X) = ‖ X - X_1 ‖_ℋ^2 and applied to the shifted loss function, ⟨ w_t, X - (X_t^* - X_t)⟩_ℋ. Notice that,

    |⟨ X,w_t ⟩_ℋ - ⟨ X-(X_t^*-X_t),w_t ⟩_ℋ|   ≤‖ w_t ‖_ℋ‖ X_t^* - X_t ‖_ℋ≤𝒢‖ X_t^* - X_t ‖_ℋ.

We are now ready to prove Theorem <ref>.
[Proof of Theorem <ref>] We denote the filtration up to round t by ℱ_t-1, that is, we condition on all past player and adversary actions. Also let us denote the optimal action in hindsight by a^*. We begin by expanding the definition of regret to get,

    ℛ_n     = 𝔼[∑_t=1^n 𝔼_a_t ∼𝒟_t[⟨ w_t,Φ(a_t) ⟩_ℋ - ⟨ w_t,Φ(a^*) ⟩_ℋ |ℱ_t-1] ] 
       (i)=𝔼[∑_t=1^n ⟨ w_t, X_t - Φ(a^*) ⟩_ℋ]  = 𝔼[∑_t=1^n ⟨ w_t, X_t -X_t^* ⟩_ℋ] + 𝔼[∑_t=1^n ⟨ w_t, X_t^* -Φ(a^*) ⟩_ℋ]
       (ii)≤𝔼[∑_t=1^n ⟨ w_t, X_t - X_t^* ⟩_ℋ] + 2 n η𝒢^2 + 2𝒢^2/η(iii)≤𝔼[∑_t=1^n ‖ w_t ‖_ℋ‖ X_t - X_t^* ‖_ℋ] _=:Ξ+ 2 n η𝒢^2 + 2𝒢^2/η,

where (i) follows by taking expectation with respect to 𝒟_t, (ii) follows by invoking Theorem <ref> and (iii) by Cauchy-Schwartz inequality. We finally need to control Ξ to establish a bound on the regret.

    Ξ    = 𝔼[∑_t=1^n ‖ w_t ‖_ℋ‖ X_t - X_t^* ‖_ℋ]  (i)≤𝔼[∑_t=1^n ‖ w_t ‖_ℋ√(F_t(X_t)- F_t(X_t^*))] (ii)≤ 2∑_t=1^n 𝒢^2√(γ_t),

here (i) follows by the strong convexity of F_t(·) and (ii) follows by the upper bound established in Lemma <ref>. Plugging this into the bound for regret we have

    ℛ_n    ≤ 2 ∑_t=1^n 𝒢^2 √(γ_t) + 2nη𝒢^2 + 2𝒢^2/η(i)≤ 4 𝒢^2n^3/4 + 2nη𝒢^2 + 2𝒢^2/η,

where (i) follows by summing the series 1/t^1/4 (√(γ_t)). The choice η =1/n^3/4 satisfies the conditions of Lemma <ref> and we can plug in this choice to get,

    ℛ_n    ≤ 4𝒢^2n^3/4+2𝒢^2n^1/4+ 2𝒢^2n^3/4≤ 8𝒢^2n^3/4.

This establishes the desired bound on the regret.

Finally we prove Lemma <ref> used to establish the regret bound above. We introduce a new function,

    h_t(X) ≜ F_t(X) - F_t(X_t^*).
 
Also the shorthand that h_t = h_t(X_t). These functions are defined conditioned on the filtration ℱ_t-1 and f_t. 
 
If the parameters η and γ_t are chosen as stated in Theorem <ref>, such that η𝒢√(h_t+1)≤𝒢^2 γ_t^2, the iterates X_t satisfy, h_t ≤ 4𝒢^2γ_t.


The functions F_t is 1-smooth therefore we have,

    h_t(X_t+1)     = F_t(X_t+1) - F_t(X_t^*)= F_t(X_t + γ_t(Φ(v_t) - X_t)) -F_t(X_t^*)
       (i)≤ F_t(X_t) - F_t(X_t^*) + γ_t⟨Φ(v_t) - X_t, ∇ F_t(X_t) ⟩_ℋ + γ_t^2/2‖Φ(v_t) - X_t ‖_ℋ^2
       (ii)≤ (1-γ_t)(  F_t(X_t) - F_t(X_t^*)) + γ_t^2 𝒢^2,

where (i) follows by the strong convexity of F_t and (ii) follows as Φ(v_t) is the minimizer of F_t(·). By the definition of F_t+1(·) and h_t we also have,

    h_t+1(X_t+1)     =  F_t(X_t+1) - F_t(X_t+1^*) + η⟨ w_t+1, X_t+1 - X_t+1^* ⟩_ℋ
       (i)≤ F_t(X_t+1) -  F_t(X_t^*)+ η⟨ w_t+1,X_t+1 - X_t+1^* ⟩_ℋ
       (ii)≤ h_t(X_t+1) + η𝒢‖ X_t+1 - X_t+1^*‖_ℋ,

where (i) follows as X_t^* is the minimizer of F_t and (ii) is by Cauchy-Schwartz inequality. Again by leveraging the strong convexity of F_t we have, ‖ X - X_t+1^*‖_ℋ^2 ≤ F_t+1(X) - F_t+1(X_t+1^*) = h_t+1 which leads to the string of inequalities,

    h_t+1(X_t+1)    ≤ h_t(X_t+1) + η𝒢‖ X_t+1 - X_t+1^*‖_ℋ≤ h_t(X_t+1) + η𝒢√(h_t+1(X_t+1)).

Plugging in the bound on h_t(X_t+1) from Equation (<ref>) into the above inequality gives us the recursive relation,

    h_t+1   ≤ h_t(1 - γ_t) + γ_t^2 𝒢^2  + η𝒢√(h_t+1)(i)≤  h_t(1 - γ_t) + 2γ_t^2𝒢^2,

where, the last step follows by our choice of the schedule for the mixing rate γ_t such that η𝒢√(h_t+1)≤𝒢^2 γ_t^2. We now complete the proof by an induction over t. 

For the base case t=1, we have h_1 = F_1(X_1) - F_1(X_1^*) =   ‖ X_1 - X_1^*‖^2≤ 4γ_1 𝒢^2. Thus, by the induction hypothesis for the step t+1 we have,

    h_t+1   ≤ h_t(1 - γ_t) + 2γ_t^2 𝒢^2(i)≤ 4𝒢^2(γ_t (1- γ_t)) + 2γ_t^2 𝒢^2=  4𝒢^2γ_t(1-γ_t/2)(ii)≤ 4𝒢^2 γ_t+1,

where (i) follows by the upper bound on h_t, (ii) is by the definition γ_t = min(1,2/t^1/2).



§ APPLICATION: POSYNOMIAL LOSSES


In this section we  will define a posynomial game, by introducing posynomial losses and prove that these losses can also be viewed as kernel inner products. We will use the connection between optimizing posynomials and Geometric Programs to prove that conditional gradient descent can be run efficiently on this family of losses. 

 A function f: ℝ_+^d ↦ℝ defined as

    f(x) = cx_1^α_1x_2^α_2⋯ x_d^α_d,

where c>0 and α_i ∈ℝ, is called a monomial function.

A non-negative linear combination of monomials is a posynomial.

A function f: ℝ_+^d ↦ℝ defined as

    f(x) = ∑_k=1^m c_k x_1^α_1kx_2^α_2k⋯ x_d^α_dk,

where c_k > 0 and α_i k∈ℝ, is called a posynomial function.

Note that posynomial functions are closed under addition, multiplication and non-negative scaling. Assume the adversary at each round plays a vector of dimension m with all non-negative entries, w_t = (c_1,c_2,⋯, c_m), while the player chooses a vector x ∈ℝ^d_+. This vector is then partitioned into m parts,

    x = (x_1,x_2_s_1,…, x_d-2,x_d-1,x_d_s_m),

and the feature vector is defined as 

    Φ(x) = [                x_1^α_1x_2^α_2;                             ⋮; x_d-2^α_d-2x_d-1^α_d-1x_d^α_d ].

Where the i^th component of Φ(·) is only a function of the i^th partition of the coordinates s_i. Then the loss obtained on the evaluation of the inner product between the adversary and player action is a posynomial loss function,

    ⟨ w_t, Φ(x) ⟩_ℋ = ∑_k=1^m c_k x_1^α_k1⋯ x_d^α_kd.

A number of scenarios can be modeled as a minimization/maximization problem over posynomial functions <cit.>. We now show that conditional gradient descent can be run efficiently over posynomial losses. If we again assume that the set of actions 𝒜 = {a ∈ℝ^d : ‖ a ‖_2 ≤ 1 }. Additionally we choose the initial action to be the solution to the optimization problem,

    a_1     = _a ∈𝒜∑_k=1^d Φ(a)_i.

The objective function is a posynomial subject to a posynomial inequality constraint. This is a geometric program that can be solved efficiently by changing variables and converting into a convex program <cit.>. At each round of the conditional gradient descent algorithm requires us to solve the optimization problem,

    v_t = _a ∈𝒜⟨η∑_s=1^t-1 w_t + 2(X_t - Φ(a_1)), Φ(a) ⟩_ℋ.

Given that posynomials are closed under addition, and given our choice of a_1, the objective function in Equation (<ref>) is still a posynomial and the constraint is a posynomial inequality. This can again be cast as a geometric program that can be solved efficiently at each round.


§ TECHNICAL RESULTS

We present a version of Hoeffding's inequality <cit.> that is used in the regret bound analysis of exponential weights.
 Let λ>0 and X be a bounded random variable such that λ X ≥ -1, then,

    log(𝔼[ e^-λ X]) ≤ (e-2)λ^2 𝔼[ X^2] - λ𝔼[X ],

and hence

    𝔼[ X] ≤ -1/λlog(𝔼[ e^-λ X] ) + (e-2)λ^2𝔼[ X^2].


We look at the log of the moment generating function to get,

    log(𝔼[exp(-λ X) ])    (i)≤𝔼[ exp(-λ X)] - 1 (ii)≤ -λ𝔼[X] + (e-2)λ𝔼[X^2],

where (i) follows by the inequality log(y) ≤ y-1 for all y>0 and (ii) is by the bound e^-x≤ 1-x +(e-2)x^2 for x≥ -1.



 §.§ John's Theorem



We present John's theorem <cit.> that we use to construct an exploration distribution.






 Let 𝒦⊂ℝ^d be a convex set, denote the ellipsoid of minimal volume containing it as,

    ℰ : = {x∈ℝ^d | (x-c)^⊤ H (x-c) ≤ 1  }.

Then there is a set {u_1,…,u_q}⊂ℰ∩𝒦 with q ≤ d(d+1)/2 +1 contact points and a distribution p (John's distribution) on this set such that any x ∈ℝ^d can be written as

    x = c + d∑_i=1^qp_i⟨ x-c,u_i-c ⟩_J (u_i - c),

where ⟨·, ·⟩_J is the inner product for which the minimal ellipsoid is the unit ball about its center c: ⟨ x,y⟩_J = x^⊤ H y for all x,y ∈ℝ^d.


This shows that 

    x -c     = d∑_i p_i (u_i - c)(u_i - c)^⊤H(x - c) 
    x̃   = d ∑_ip_i ũ_i ũ_i^⊤x̃
    1/dI_d× d    = ∑_ip_i ũ_̃ĩũ_̃ĩ^⊤

where ũ_i = H^1/2(u_i-c), and similarly for x̃. We see that for any a,b ∈𝒦,

    ã^⊤𝔼_u∼ p[uu^⊤]b̃ = 1/dã^⊤b̃.


To use this theorem, we need to perform a preprocessing of the action set 𝒜 following a similar procedure described in Section 3 by <cit.>:



  * First we map 𝒜 onto the RKHS generated by the kernel  to produce Φ_m(𝒜). 

  * We assume that Φ_m(𝒜) is full rank in ℝ^m. If not, we can redefine the feature map Φ_m as the projection onto a lower dimensional subspace.

  * Find John's ellipsoid for Conv(Φ_m(𝒜)) which we denote by ℰ = { x  ∈ℝ^m : (x-x_0)^⊤ H^-1 (x-x_0) ≤ 1}.

  * Translate Φ_m(𝒜) by x_0. In other words, assume that Φ_m(𝒜) is centered around x_0 = 0 and define the inner product ⟨ x , y ⟩_J = x^⊤ H y. 

  * We now play on the set Φ_m^J(𝒜) := H^-1Φ_m(𝒜) in ℝ^m. Let the loss of playing an action H^-1Φ_m(a) ∈Φ_m^J(𝒜) when the adversary plays z be ⟨ H^-1Φ_m(a), z ⟩_J = Φ_m(a)^⊤ z. 

  * The contact points, u_1,…,u_q are in Φ_m^J(𝒜) and are valid points to play. We now use p – John's distribution – to be the exploration distribution.

Mimicking <cit.> it can be shown that Algorithm <ref> works with a generic dot product and that all the steps in the regret bound in Appendix <ref> go through. 







§ EXPERIMENTS


We perform an empirical study of our algorithms in both the full information and the bandit settings and demonstrate their practicality. In the full information setting we conducted experiments with quadratic losses using exponential weights. We also plot the performance of exponential weights algorithm on Gaussian losses. In the bandit feedback setting we again study quadratic and Gaussian losses.


  §.§.§ Full information










Exponential weights requires us to sample from a distribution of the form p(x) ∝exp( μ∑_i=1^t (x, w_i) ). In general sampling from these distributions is possibly intractable, however they present good empirical performance.  The following plot shows a diffusion MCMC algorithm sampling from a distribution proportional to exp ( -η∑_i=1^t (x, z_i)) where  is the Gaussian kernel, η = 10, and x is restricted to an ℓ_2 ball of radius 10. 







In practice using exponential weights in the full information setting and sampling using a diffusion MCMC algorithm yields sublinear regret profiles and tractable sampling even for Gaussian losses. We ran experiments generating random loss sequences and we plot the average regret over 60 runs of the algorithm. 


  §.§.§ Bandits Experiments


The kernel exponential weights algorithm presents also a sublinear regret profile. The Gaussian experiments involved the construction of the finite dimensional kernel _m by kernel PCA. 

