Structured Stochastic Linear Bandits

The stochastic linear bandit problem proceeds in rounds where at each round the algorithm selects a vector from a decision set after which it receives a noisy linear loss parameterized by an unknown vector. The goal in such a problem is to minimize the (pseudo) regret which is the difference between the total expected loss of the algorithm and the total expected loss of the best fixed vector in hindsight. In this paper, we consider settings where the unknown parameter has structure, e.g., sparse, group sparse, low-rank, which can be captured by a norm, e.g., $L_1$, $L_{(1,2)}$, nuclear norm. We focus on constructing confidence ellipsoids which contain the unknown parameter across all rounds with high-probability. We show the radius of such ellipsoids depend on the Gaussian width of sets associated with the norm capturing the structure. Such characterization leads to tighter confidence ellipsoids and, therefore, sharper regret bounds compared to bounds in the existing literature which are based on the ambient dimensionality.


Introduction
We consider the stochastic linear bandit problem [16,1] which proceeds in rounds t = 1, . . . , T where at each round t the algorithm selects a vector x t from some decision set X ⊂ R p and receives a noisy loss defined as ℓ t (x t ) = x t , θ * + η t where θ * is an unknown parameter and η t is martingale noise. The algorithm observes only ℓ t (x t ) at each round t and its goal is to minimize the cumulative loss. We measure its performance by the (pseudo) regret [10] defined as The stochastic linear bandit can be used to model problems in several real-world applications ranging from recommender systems to medical treatments to network security. Frequently, in such applications, one has knowledge of the structure of the unknown parameter θ * , for example, θ * may be sparse, group sparse, or low-rank. Previous works [16,1] either made no structural assumptions on θ * and proved regret bounds 1 of the form O(p √ T ) or assumed θ * was s-sparse (s non-zero elements) and showed [2] the regret sharpens to O( √ spT ). In this paper, we consider the setting for each of the K decisions and the expected loss is a linear function of the feature vector and an unknown parameter. For such a problem, a regret bound of O(log 3/2 (K) √ p √ T ) was shown. However, dependence on the number of decisions K can be problematic when it is large or infinite.
For such settings, [16] studied the stochastic linear bandit problem where the decision set is an arbitrary compact set in R p . They presented the algorithm ConfidenceBall2 based on the OFU principle which computes an estimateθ t of the unknown parameter θ * using ridge regression and constructs an ellipsoidal confidence set aroundθ t with radius √ β t . After which the vectors x t and θ t are selected optimistically from the decision set and confidence ellipsoid respectively, such that x t , θ t is minimized. They showed how to set β t such that θ * stays within the ellipsoid with high-probability for all t and showed a problem independent regret 3 of O(p √ T ) and a problem dependent regret of O( p 2 ∆ log 3 T ) where ∆ > 0 is the gap between the best and second best extremal points. Note, the regret depends on the ambient dimensionality p and not the number of decisions. Further, [24,1] showed how to construct tighter confidence ellipsoids, specifically, [1] used a selfnormalized tail inequality for vector-valued martingales which decreased the regret by a √ log T multiplicative factor.
Building on such works which had considered the problem without structural assumptions on θ * , two papers published simultaneously [12,2] considered the problem where θ * is s-sparse. [2] followed the same problem setting as [16] and presented a method which can use the predictions of any full information online algorithm with an upper bound on its regret to construct confidence sets. When constructing confidence sets using the algorithm SeqSEW [18] they showed a problem independent regret of O( √ spT ) and a problem dependent regret of O( sp ∆ log 2 T ). [12] uses initial rounds to estimate the sparse structure similar to our work however, they do not consider the standard stochastic linear bandit problem. Specifically, they define the loss as ℓ t (x t ) = x t , θ * + x t , η t where η t is i.i.d. whitenoise (not martingale) and they assume the decision set is the unit L 2 ball. During the random estimation rounds, they used techniques from compressed sensing to identify the subspace where θ * lives then ran ConfidenceBall2 where the decision set is a subset of the subspace and showed a problem independent regret of O(s √ T ).
Such papers show that sharper regret bounds can be obtained when θ * is structured however, only for a sparse θ * . Such results motivate our work to study the regret for any generally norm structured θ * . We organize the paper as follows. In Section 2 we give background on high-dimensional structured estimation which our analysis builds on. Section 3 we present the problem setting and algorithm. Section 4 we present our main regret bounds from a high-level and provide examples of popular types of structure. Section 5 we present the main technical results of the analysis and point to the detailed proofs in the appendix. Finally, we conclude in Section 6.

Background: High-Dimensional Structured Estimation
We rely on recent developments in the analysis of non-asymptotic bounds for structured estimation in high-dimensional statistics. In this section, we will discuss the main results needed for our analysis which can be found in the following papers [11,7,13,22,27,8,5,6].
In high-dimensional structured estimation, one is concerned with settings in which the dimension p of the parameter θ * to be estimated is significantly larger than the sample size n, i.e., p ≫ n. It is known that for n i.i.d. Gaussian samples, one can compute an estimateθ n using least squares regression which converges to θ * at a rate of O p n . The convergence rate can be improved when θ * is structured which is usually characterized as having a small value according to some norm R(·). For such problems, estimation is performed by solving a norm regularized regression problem where L(·, ·) is a convex loss function 4 , Z n is a dataset consisting of i.i.d. pairs {(x i , y i )} n i=1 where x i ∈ R p is a sample, y i ∈ R is the response, and λ n is the regularization parameter.
For such problems, letθ n −θ * be the estimation error vector, then for a suitably large λ n , [5] showed the error vector deterministically belongs to the restricted error set where ρ > 1 is a constant which we fix as ρ = 2 for ease of exposition. For such a ρ, E r,n is a restricted set of directions, in particular, the error vectorθ n − θ * cannot be in the direction of θ * . Using the restricted error set, bounds on the estimation error can be established which hold with high-probability under two assumptions. First, the regularization parameter λ n must satisfy the inequality where R * (·) is the dual norm of R(·). Second, the loss function must satisfy the restricted strong convexity (RSC) condition in the restricted error set E r,n as illustrated in [22]. Specifically, there exists a κ > 0 such that For the squared loss, the RSC condition simplifies to the restricted eigenvalue (RE) condition where X n ∈ R n×p is the design matrix [13]. Under such conditions, the following bound holds with high-probability [22,5] where ψ(E r,n ) = sup u∈Er,n R(u) u 2 is the norm compatibility constant and c > 0 is a constant. For an s-sparse θ * , one obtains θ n − θ * 2 ≤ O s log p n and for a group sparse θ * , one obtains where K is the number of groups, m is the maximum group size, and s G is the group sparsity level. Similar bounds can be computed for other types of structure including low-rank.

Structured Bandits: Problem and Algorithm
Here, we will formally define the problem, mention the assumptions under which our analysis works, and present our algorithm. The results and analysis are presented in subsequent sections.

Problem Setting
We consider the stochastic linear bandit problem [16,1] where in each round t = 1, . . . , T the algorithm selects a p-dimensional vector x t from the decision set X and receives a loss of ℓ t (x t ) = x t , θ * + η t . Our focus is on settings where the unknown parameter θ * ∈ R p is structured which we characterize as having a small value according to some norm R(·).
The goal of the algorithm is to minimize its cumulative loss t ℓ t (x t ) and we measure the performance of the algorithm in terms of the fixed cumulative (pseudo) regret defined as We require that the algorithm's regret grows sub-linearly in T , i.e., R T = o(T ), and desire it grows with the structure of θ * rather than the ambient dimensionality p with high-probability. The following assumptions under which our analysis holds are standard in the literature [16,1,2].

Assumptions and Definitions
Assumption 1 The decision set X ⊂ R p is a compact (closed and bounded) convex set with nonempty interior. For ease of exposition, we assume X ⊆B p 2 , the (closed) unit L 2 ball defined as B p 2 = {x ∈ R p : x 2 ≤ 1}, to avoid scaling factors. Assumption 2 The noise is a bounded martingale difference sequence (MDS), i.e., . , x t+1 , η 1 , . . . , η t } is a filtration (sequence of σ-algebras). We assume bounded noise for simplicity however, the results hold for any sub-Gaussian noise (refer to Section A for definitions of sub-Gaussian and related quantities). Assumption 3 We assume the unknown parameter θ * is fixed for all rounds, the structure is known, for example, for an s-sparse θ * the value of s is known, and θ * 2 = 1. Assumption 4 The number of rounds T is known a priori.

Definition 1
The Gaussian width [13] of a set A is defined as w(A) = E [sup u∈A g, u ] where the expectation is over g which is a zero mean, unit variance Gaussian random variable. Definition 2 For a set A, φ(A) = sup u,v∈A u − v 2 = sup u∈A u 2 measures the diameter of A.

Definition 4
The set A t is a spherical cap constructed as A t := cone(E r,t ) ∩ S p−1 where S p−1 is the unit sphere in p-dimensions and A max := cone(E r,max ) ∩ S p−1 is the largest such cap. Definition 5 Each x t has sub-Gaussian norm (refer to Section A for the definition of sub-Gaussian norm) satisfying | x t | ψ 2 ≤ K for some absolute constant K. This follows from Assumption 1. Definition 6 The unit norm R(·) ball is Ω R := {u ∈ R p : R(u) ≤ 1}. The norm compatibility constant with respect to vectors in the restricted error set at round t is ψ(E r,t ) = sup u∈Er,t R(u) Algorithm 1 Structured Stochastic Linear Bandit 1: Input: p, X , R(·), T , E r,max ,A max , Ω R , γ, ǫ, c 0 , c ′ , C 2: Set β = Cψ(E r,max )(w(Ω R ) + γ 2 + log T φ(Ω R )/2) (28) 3: Play n = c ′ w 2 (A max )(ǫ 2 + log T ) uniform i.i.d. random vectors x 1:n ∈ X and receive losses ℓ 1:n 4: For t = n, . . . , T

Algorithm
For the initial t = 1, . . . , n = c ′ w 2 (A max )(ǫ 2 +log T ) rounds where c ′ > 0 is a constant, our algorithm selects vectors x 1:n := {x 1 , . . . , x n } uniformly at random from X and receives the corresponding losses ℓ 1:n := {ℓ 1 (x 1 ), . . . , ℓ n (x n )}. The length of such random estimation rounds depends on the Gaussian width of the largest spherical cap induced by the structure of θ * and a parameter ǫ > 0 which controls the success probability and will become clear in the analysis in Section 5. The random estimation rounds can be considered the "burn-in" period similar to the use of a barycentric spanner or identity matrix as in [16,1].
After the loss ℓ n (x n ) is received in round n, the algorithm constructs an (n × p)-dimensional design matrix X n = [x 1 . . . x n ] ⊤ , a sample covariance matrix D n = X ⊤ n X n , and an n-dimensional response vector y n = [ℓ 1 (x 1 ) . . . ℓ n (x n )] ⊤ . The algorithm then computes an estimateθ n by solving a norm regularized regression problem, constructs a confidence ellipsoid using the Mahalanobis distance defined as θ −θ n 2,Dn = (θ −θ n ) ⊤ D n (θ −θ n ), then selects a sample to play. Specifically, the algorithm performs the following four main steps sequentially in each round thereafter.

Discussion
Step 1. An estimate is computed by solving a norm regularized regression problem following existing results discussed in Section 2. This generalizes previous works [16,1] which only consider computing an estimate by solving the ridge regression problem.
Step 2. A confidence ellipsoid is constructed in order to allow the algorithm to explore in certain directions. Since the confidence ellipsoid is defined as C t = {θ ∈ R p : θ −θ t 2,Dt ≤ β}, we focus on bounds for θ t − θ * 2,Dt . Extending the results in Section 2, we will show in Section 5 highprobability bounds on the estimation error of the form θ t − θ * 2,Dt ≤ cψ(E r,t ) λt κ √ t. Therefore, setting β to the right hand side will give bounds such that θ * ∈ C t with high-probability. The value of β then depends on two key terms: the regularization parameter λ t and the restricted eigenvalue (RE) constant κ detailed in (6). The value of λ t is set by the user and we will provide an explicit characterization of its value in Section 5. Moreover, the estimation error bound will only hold when the RE constant κ is positive and we will show in Section 5 that after a suitable number of random estimation rounds and by selecting samples via Step 3, it will be positive for all rounds.
Steps 3 and 4. These steps are motivated from the regret analysis established in [16] and the need to satisfy the RE condition. Let the instantaneous regret at round t + 1 be defined as r t+1 = x t+1 , θ * − x * , θ * where x * = argmin x∈X x, θ * . As shown in [16], by selecting an x t+1 and θ t+1 via the instantaneous regret can be upper bounded as , θ t+1 because we optimize over both x and θ. Therefore, one obtains the following inequality x t+1 , θ t+1 ≤ x * , θ * on which the entire regret analysis relies. We will use the regret analysis from [16] therefore, we need to select an x t+1 and θ t+1 such that the above inequality holds.
Additionally, recall the RE condition in (6) 1 We must have κ > 0 for the estimation error bound used to compute β to hold. Therefore, in order to show such a κ exists, we need samples which are not too correlated otherwise the design matrix will be ill-conditioned.
To use the regret analysis and satisfy the RE condition, we cannot exactly follow existing work [16,1,2] and select an x t+1 by solving (12) since we may obtain a single unique solution and the rows of the design matrix will be too correlated. Instead, we select samples uniformly at random from specific subsets of X which spreads the samples out enough to show the RE condition holds. Moreover, as we will show in Section C, for any random sample x t+1 we select, we can deterministically compute a θ t+1 ∈ C t such that the inequality x t+1 , θ t+1 ≤ x * , θ * holds.
Step 3 is computationally difficult in general (similar to all previous work) however, for simple decision sets such as the unit the L 2 ball, a solution can be computed efficiently by solving the corresponding quadratically constrained quadratic program. Our algorithm for structured stochastic linear bandits is presented in Algorithm 1.

Regret Bound for Structured Bandits
Here, we present the main result which is a high-probability bound on the regret of Algorithm 1 and show examples for popular types of structure. The analysis of the bound is presented in Section 5.
First, we review some of the assumptions from Section 3.2. We assume X is a compact convex set with non-empty interior. Further, we assume X ⊆ B p 2 , the unit L 2 ball, for ease of exposition. Examples of such decision sets include: L p balls for 1 ≤ p < ∞, ellipsoids, polytopes, norm cones, and hypercubes. We assume the noise η t is a bounded MDS where |η t | ≤ B, ∀t and the number of rounds T is known a priori.
Further, we recall a few definitions introduced in Section 3.2 which will help interpret the main result. We define the set Ω R as the unit norm R(·) ball and A max ⊂ S p−1 as the spherical cap of the largest restricted error set. For such sets, w(Ω R ) and w(A max ) are the Gaussian widths. Moreover, we define φ(Ω R ) to be the diameter of the set Ω R , E r,max as the largest restricted error set, and ψ(E r,max ) as the norm compatibility constant of the largest restricted error set.
Under such assumptions, we present the main result in a high-level form, which hides the exact nature of the constants involved. A more explicit form of the constants is presented in the appendix.
The main result consists of two theorems for the problem independent and problem dependent settings [16]. Let E be the set of all extremal points. The problem independent setting occurs when the difference between the expected loss of the best extremal point x * and the expected loss of the second best extremal point is zero, i.e., ∆ = inf x∈E x, θ * − x * , θ * = 0. Such a setting occurs, for example, when the decision set is the unit L 2 ball. The problem dependent setting occurs when ∆ > 0, for example, when the decision set is a polytope.
Theorem 2 (Problem Dependent Regret Bound) For any ǫ, γ > 0, choose the radius of the ellipsoid in Algorithm 1 as , the fixed cumulative regret of Algorithm 1 with a decision set which has non-zero gap ∆ > 0 is at most where c ′ , c 0 , c 1 , c 2 > 0 are constants.

Examples
We present the problem independent regret of popular types of structured θ * using Theorem 1 and the values of ψ(E r,max ) and w(Ω R ) from [13,6,14]. The problem dependent regret can be similarly computed. Only unstructured and sparse structures have been considered [16,1,2,12]. No previous works have considered any other types of structure including group sparse and low-rank.
Example 1 (Unstructured) For problems where θ * is not structured, we simply use R(θ) = θ 2 2 and solve the ridge regression problem We compute the regret by plugging in the values ψ(E r,max ) = O(1) and w( . Such a regret matches [16,1] up to log and constant factors. Example 2 (Sparse) For problems where θ * is s-sparse (s non-zeros), one common regularizer to induce sparse solutions is R(θ) = θ 1 . With such a regularizer, we solve the Lasso problem We compute the regret by plugging in the values [2] up to log and constant factors. Note, it is worse than the regret from [12] which is O(s √ T ) however, they consider a different noise model in the loss function.
Example 3 (Group Sparse) Let {1, . . . , p} be an index set of θ * , G = {G 1 , . . . , G K } be a known set of K groups which define a disjoint partitioning of the index set. For group sparse problems, one common regularizer is R(θ) = K i=1 θ G i 2 where θ G i is a vector with elements equal to θ for indices in G i and 0 otherwise. With such a regularizer, we solve the group lasso problem With maximum group size m = max i |G i | and subset S G ⊂ {1, . . . , K} of the groups with cardinality s G which denotes the number of active groups, we compute the regret by plugging in the values Example 4 (Low-Rank) Let Θ * ∈ R d×p be a matrix with rank r and we select the matrix X t ∈ R d×p at each round. Define the loss we receive as ℓ t (X t ) = trace(X ⊤ t Θ * ) + η t . For problems where the rank of Θ * is small, for example, r ≤ min(d, p), one common regularizer to use is the nuclear norm R(Θ) = Θ * = min{d,p} j=1 σ j (Θ) where σ j (Θ) are the singular values of the Θ. With such a regularizer, we solve the trace-norm regularized least squares problem We compute the regret by plugging in the values ψ(E r,max ) = O( √ r) and w(

Overview of the Analysis
The analysis starts from a regret result established in [16]. Let r t = x t , θ * − x * , θ * denote the instantaneous regret acquired by the algorithm on round t where x * = argmin x∈X x, θ * is the optimal vector. Then for Algorithm 1, as long as we have θ * ∈C t over all rounds t, [16,Theorem 6] shows that T t=1 r 2 t ≤ 8β 2 p log T . Then, to establish a problem independent regret bound we directly apply the Cauchy-Schwarz inequality to get which holds conditioned on θ * ∈ C t over all rounds t. Moreover, for a problem dependent regret bound, we follow the proof of [16, Theorem 1] which shows which holds conditioned on θ * ∈ C t over all rounds t.
The focus of our analysis is then to choose a β such that the condition holds with high-probability uniformly over all rounds. From Algorithm 1, since C t := {θ : θ −θ t 2,Dt ≤ β} and we want to have θ * ∈ C t , we focus on bounds for θ t − θ * 2,Dt , the instantaneous estimation error. Building on ideas for high-dimensional structured estimation as discussed in Section 2, deterministic bounds on the instantaneous estimation error can be obtained under two assumptions. First, we need to choose the regularization parameter λ t such that Second, for allθ t − θ * ∈ E r,t , we need to have the restricted eigenvalue (RE) condition for constant Under these two assumptions, following existing analysis for high-dimensional estimation, we have the following theorem (refer to Section B for the proof).
Theorem 3 Assume that the RE condition is satisfied in the set E r,t with parameter κ and λ t is suitably large. Then for any norm R(·), we have for constant c > 0 In the Sections D and E, we show that the two assumptions in fact hold with high-probability. In particular, for the assumption in (23), we show the following result.
Theorem 4 For any γ > 0 and for absolute constant L > 0, with probability at least 1−L exp(−γ 2 ), the following bound holds uniformly for all rounds t = 1, . . . , T : Then, from (23), for c 0 = 4LKB we set λ t as As for the assumption in (24), we show the following result.
Theorem 5 shows that after round t crosses a suitably scaled version of w 2 (A max ) then there exists a constant κ such that the RE assumption holds with high-probability. Note that this requirement implies a phase shift at which point the estimator starts to work and forms the basis of sampling the arms i.i.d. for the initial set of rounds in Algorithm 1.
For a bound on the instantaneous ellipsoidal estimation error, we plug in the value of λ t from (27) into (25) and use the norm compatibility constant of the largest restricted error set to obtain where C = c 0 c/κ is a constant which holds with high-probability across all rounds t = 1, . . . , T . Therefore, if we set the confidence ellipsoid C t will contain θ * across all rounds with high-probability. Substituting our β into the regret bounds in (21) and (22) gives our main result in Theorem 1 and Theorem 2.

Conclusions
We studied the stochastic linear bandit problem under structural assumptions on θ * and focused on constructing confidence ellipsoids which contain the unknown parameter θ * across all rounds with high-probability. We showed how to construct such confidence ellipsoids which are general enough to hold for any norm structured θ * and are tighter than previous works leading to sharper regret bounds which, for the problem independent regret scales as O(ψ(E r,max )w(Ω R ) √ p √ T ) and for the problem dependent regret scales as O(ψ 2 (E r,max )w 2 (Ω R )p log T /∆). For unstructured and s-sparse θ * , such regret bounds match existing results on the standard stochastic linear bandit problem. For all other types of structured θ * including group sparse and low-rank, the bounds are sharper.

Appendix A Definitions and Background
The following definitions and lemmas can be found in [5,6,27].

Definition 7 A random variable x is sub-Gaussian if the moments satisfies
for any p ≥ 1 with constant K. The minimum value of K is called the sub-Gaussian norm of x and denoted by | x | ψ 2 .
Additionally, every sub-Gaussian random variable satisfies for all t ≥ 0.
Definition 8 A random vector X ∈ R p is sub-Gaussian if the one-dimensional marginals X, x are sub-Gaussian random variables for all x ∈ R p . The sub-Gaussian norm of X is defined as Definition 9 For any set A ∈ R p , the Gaussian width of the set A is defined as where the expectation is over g ∼ N (0, I p×p ) which is a vector of independent zero-mean unitvariance Gaussian random variables.
Lemma 1 For any bounded random variable |X| ≤ B, then X is a sub-Gaussian random variable with X ψ 2 ≤ B.
Lemma 2 Consider a sub-Gaussian random vector X with sub-Gaussian norm K = max i | X i | ψ 2 , then, for vector a, Z = X, a is a sub-Gaussian random variable with sub-Gaussian norm | Z | ψ 2 ≤ CK a 2 for absolute constant C.

B Ellipsoid Bound
Theorem 3 Assume that the RE condition is satisfied in the set E r,t with parameter κ and λ t is suitably large. Then for any norm R(·) we have for constant c > 0 Proof: Proof of Theorem 3. For anyθ t − θ * t ∈ E r,t and by the definition of a convex function Moreover, by the definition of a dual norm we have By construction following (4) from Section 2, for any ρ > 0 (not just ρ = 2) we get Therefore, By the definition of the norm compatibility constant ψ(E r,t ) = sup u∈Er,t R(u) Therefore, for the squared loss, since L(θ t ) − L(θ * ) = 1 t X t (θ t − θ * ) 2 2 we get Using the bound in (7) from Section 2 for θ t − θ * 2 we obtain Finally, noting X t (θ t − θ * ) 2 2 = θ t − θ * 2 2,Dt , multiplying each side by t, and taking the square root of both sides we get the final bound for constant c > 0 which ends the proof.

C Algorithm
In this section, we will show that selecting an x t+1 following Algorithm 1, that we can compute a θ t+1 such that the inequality x t+1 , θ t+1 ≤ x * , θ * holds. In Algorithm 1, we select x t+1 by computing (x ′ t+1 , θ ′ t+1 ) = argmin x∈X ,θ∈Ct∩S p−1 x, θ and sampling uniformly at random from a closed L 2 ball centered at x ′ t+1 with radius x ′ t+1 2 /2. In the following lemma, we show a specific way of computing such a sample which shows why the radius is set to such a value. Moreover, we will prove that we can deterministically compute a θ t+1 such that the inequality above holds.
Lemma 3 For a decision set X and a confidence ellipsoid C t , if we compute and set x t+1 and θ t+1 as Proof: First, the inequality x ′ t+1 , θ ′ t+1 ≤ x * , θ * holds because we assume θ * 2 = 1 and the optimization is over both x and θ. Second, conceptually, we sample x t+1 from the intersection of the decision set and a ball. Above, we provided a specific example of how to set the radius of such a ball and sample x t+1 and θ t+1 . Now, we will show that selecting x t+1 and θ t+1 and setting the radii as above satisfies the inequality x t+1 , θ t+1 ≤ x ′ t+1 , θ ′ t+1 . First, observe We need to show that From the Cauchy-Schwarz inequality we have Plugging this in (34) completes the proof.

D Bound on Regularization Parameter λ t
We will prove the following main theorem.
Theorem 4 For any γ > 0 and for absolute constant L > 0, with probability at least 1−L exp(−γ 2 ), the following bound holds uniformly for all t = 1, . . . , T : Proof: Proof of Theorem 4. Recall the regularization parameter λ t needs to satisfy the inequality for ρ > 1. Two issues of the right hand side are (1) the expression depends on the unknown parameter θ * and (2) the expression is a random variable since it depends on n vectors selected uniformly at random from the decision set X and a sequence of random noise terms η 1 , . . . , η t . We can remove the dependence on θ * by observing that y t − X t θ * is precisely the t-dimensional noise vector ω t = [η 1 . . . η t ] ⊤ . Therefore,

u Concentrates as a Sub-Gaussian
where q = u u 2 . We focus on the term 1 √ t X ⊤ t ω t , q . We can construct a martingale difference sequence (MDS) by observing that for z τ = η t x τ , q . Recall from Assumption 2 the filtration is defined as F t = {x 1 , . . . , x t+1 , η 1 , . . . , η t }.
Each z τ can be seen as a MDS since Additionally, each z τ follows a sub-Gaussian distribution with parameter KB because | η τ x τ , q | ψ 2 ≤ KB (Assumption 2 and Definition 5). Since each z τ is a bounded MDS, we can use the Azuma-Hoeffding inequality to show that the sum t τ =1 z τ concentrates as a sub-Gaussian with parameter KB. For all γ ≥ 0 where ζ = γ/ √ t which implies γ = √ tζ. From (42) and (30) in Definition 7 (Section A) we can see that the term 1 where ǫ = u 2 ζ which implies ζ = ǫ/ u 2 . The reason we went through showing the above is because the generic chaining argument we will invoke to bound sup R(u)≤1

u via Generic Chaining
We obtain a high-probability bound on sup R(u)≤1 1 √ t X ⊤ t ω t , u using a generic chaining argument from [25,26]. This involves (1) showing that the absolute difference of two sub-Gaussian processes concentrates as a sub-Gaussian, (2) showing the expectation over the supremum of the absolute difference of two sub-Gaussian processes is upper bounded by the sub-Gaussian width of a set from which the processes are indexed from, and (3) showing the supremum of a sub-Gaussian process is concentrated around its expectation and therefore, around the sub-Gaussian width with high-probability.

(1) Sub-Gaussian Process Concentration
First, we show that the absolute difference of two sub-Gaussian processes concentrates as a sub- Using the bound we established in (43), we obtain the following bound on the absolute difference of two sub-Gaussian random processes Y u and Y v as (2) Bound on E sup R(u)≤1 Lemma 4 ([25], Theorem 2.1.5) Consider two processes (Y u ) u∈Ω R and (X u ) u∈Ω R indexed by the same set. Assume that the process (X u ) u∈Ω R is Gaussian and that the process (Y u ) u∈Ω R satisfies the condition where L is an absolute constant.
First, notice that E sup u∈Ω R X u is exactly the Gaussian width w(Ω R ) of the set Ω R as seen by the Definition 9 (Section A). For our purposes, we make one modification to the above lemma similar to [6,Theorem 8]. In (44), we see that |Y u − Y v | concentrates as a sub-Gaussian with parameter u−v 2 KB. To bound the expectation of two sub-Gaussian processes, we scale the Gaussian width by the additional term KB to get This shows for two sub-Gaussian processes Y u and Y v , the expectation of the supremum of their absolute difference is upper bounded by the Gaussian width scaled by the sub-Gaussian norm, i.e., the sub-Gaussian width.
The second result we need is the following lemma.
We know from above that our processes t ω t , v are symmetric. As such we get the following lemma.
Lemma 6 From (44) we can see that the condition of Lemma 4 is satisfied in the sub-Gaussian case so using Lemma 4 and Lemma 5 for some absolute constant L we obtain To complete the argument, we need the following lemma.
Note, the function ∆(Ω R ) = sup u,v∈Ω R d(u, v) is the diameter of the set Ω R . For our setting, d(u, v) = u − v 2 so we replace ∆(Ω R ) with φ(Ω R ) as detailed in Definition 2 in Section 3.2. The specifics of the γ 2 (·, ·) function are not necessary for this work since we can bound it and simplify Lemma 7 by using the following lemma.
Combining Lemma 7 with Lemma 8, using Lemma 6, and our definitions of Y u and Y v for any ǫ > 0 we get (52) Proof: Proof of Lemma 9.
where the first line comes from the left-hand side of Lemma 7, the second line comes from the fact that ∆(Ω R ) ≤ γ 2 (Ω R , d(u, v)) from [26] Definition 2.2.19, the third line comes from Lemma 8, the fourth line comes from Lemma 5, the fifth line comes from Lemma 6, and the last line follows from our construction of the process Y u and the right-hand side of Lemma 7.
Dividing the other √ t through and setting ǫ/ √ t = α2LKBw(Ω R )/ √ t we get Lemma 10 Proof: Proof of Lemma 10 where the first inequality is from Lemma 9, the second inequality is from multiplying both sides by 1 √ t and setting γ = ǫ √ t , and the third inequality is from setting γ = α2LKB w(Ω R ) √ t .
Lemma 10 gives a high-probability bound on the value of R * X ⊤ t ω t for round t but to complete the proof of Theorem 4 we need a bound which holds simultaneously for all rounds T with highprobability. To obtain such a bound, we can set α 2 = (γ 2 + log T ) φ(Ω R ) 2w(Ω R ) 2 and apply a union bound for all t Rearranging the terms ends the proof of Theorem 4.

E Restricted Eigenvalue (RE) Condition
We will prove the following theorem.
Proof: Proof of Theorem 5. For a design matrix X t with t rows, a response vector y t , and parameter κ the RE condition is We need the above equation to be satisfied ∀θ t − θ * ∈ E r,t for Theorem 3 to hold. Note, the restricted error set has dependence on t because at each round we compute a new estimateθ t . Refer to (3) in Section 2 to review the definition and see why we need to make this distinction. To that end, we consider the following problem Clearly if (55) is true then it is true for allθ t − θ * ∈ E r,t since E r,t ⊆ cone(E r,t ). Additionally, since only the direction matters and not the magnitude we consider just the vectors on the spherical cap where S p−1 is the unit sphere in R p . Since u 2 = 1 for all u ∈ A t we simply focus on which suffices in proving the RE condition for the restricted error set. Now, to show a bound, we perform the following decomposition. Let X t = [x 1 , . . . , x t ] ⊤ , then Definition 5). Therefore, by the Azuma-Hoeffding inequality we obtain From (60) and using the generic chaining argument [26] similar to our λ t analysis (Section D) it follows that for an absolute constant L > 0, Therefore, (62) Now, since the set A t changes each round and the bound must hold across all rounds, we put the bound in terms of the largest spherical cap A max which is defined in Definition 4. Then, setting , and taking a union bound such that across all rounds we have Dividing the other √ t through and multiplying by 2 we obtain sup u∈At λ min (Σ t ) = 0 this implies that E z∼Zt [ z, v p 2 ] = 0. If we define the set Z vp = {z ∈ Z t : z, v p = 0} then for our assumption to be true it must be true that P (z ∈ Z vp ) = 1 a.s. However, since there is zero probability density outside of Z t this implies the density is concentrated on a subspace. Such an implication cannot be true because the span of Z t is R p , i.e., the set contains all directions. Therefore, our assumption is false and λ min (Σ t ) = 0 which implies there exists some constant ν such that λ min (Σ t |A t ) ≥ λ min (Σ t ) ≥ ν > 0 for all t. Now, given the argument that λ min (Σ i ) > 0 ∀i, we define λ min (Σ 1:t ) = min{λ min (Σ 1 ), . . . , λ min (Σ t )}. Then, we can use Lemma 11 with the largest spherical cap A max to obtain the following bound which holds for any of the t rounds and any ζ > 0.
Setting ζ 2 = ǫ 2 c 0 + log T c 0 w 2 (Amax) and applying a union bound we get the following bound which holds simultaneously for all rounds t = 1, . . . , T and any ǫ > 0.
Combining (58), (64), and (67) with probability at least 1 − 2L exp(−w 2 (A max )ǫ 2 ) we obtain For some constant C > 0 it is true that C − C 2 − C 4 > 0 (where we have chosen to divide C by 2 and 4 somewhat arbitrarily) therefore, setting C = λ min (Σ 1:t ), if we can show when and when 2LK w(A max ) 2 + ǫ 2 φ 2 (A max ) + log T φ 2 (Amax) X t u 2 2 > 0 will be satisfied. With some algebraic manipulations, we can see that (69) is satisfied when (70) is satisfied when Therefore, the RE condition will be satisfied when t ≥ c ′ w 2 (A max )(ǫ 2 + log T ) for some constant c ′ > 0 which completes the proof.

E.1 Anisotropic Sub-Gaussian Design Extension to Martingales
We extend [6, Theorem 12] to martingale difference samples which is an application of Theorem D from [20]. Theorem D relies on Lemma 1.2 [20] which shows concentrations for i.i.d random samples and is the only part of the proof which needs to be modified for martingales. As such, we present an extension of Lemma 1.2 to martingales which generalizes Theorem D to martingales which can be applied to prove Theorem 11. Note, the following result can be considered independent from the rest of the paper and, as such, the notation is not inherited but will be re-defined here. Theorem D is as follows.

Lemma 12 (Mendelson et al. Theorem D)
There exists absolute constants c 1 , c 2 for which the following holds. Let (Ω, µ) be a probability space, set F be a subset of the unit sphere of L 2 (µ),i.e., F ⊆ S L 2 = {f : | f | L 2 = 1}, and assume that diam(F, · ψ 2 ) = α. Then, for any θ > 0 and n ≥ 1 satisfying with probability at least 1 − exp −c 2 In [20], the proof assumes the samples x 1 , . . . , x n ∈ R p are i.i.d. isotropic sub-Gaussian random vectors. For the problem we are considering, the samples x 1 , . . . , x n ∈ R p are a bounded martingale difference sequence (MDS), i.e., . , x i } is a filtration. Also we consider the following class of functions: We allow the covariance matrix Σ i = E[x i x ⊤ i |F i−1 ] to be different for each sample x i . The main lemma we will prove is as follows.
Lemma 13 For a bounded martingale difference sequence x 1 , . . . , x n ∈ R p where each x i is bounded as x i 2 ≤ A, there exists absolute constants c 1 , c 2 > 0 for which the following holds. Let F be the set of linear functionals over the unit sphere F := 1 √ u T Σ i u ·, u : u ∈ A ⊆ S p−1 and assume that diam(F, · ψ 2 ) = α. Then, for any θ > 0 and n ≥ 1 satisfying with probability at least 1 − exp −c 2 where X = [x 1 , . . . x n ] ⊤ ∈ R n×p is the design matrix and Σ i = E[x i x ⊤ i ] ∈ R p×p is the population covariance matrix for sample x i .
The proof follows using analogous arguments from [20]. For f u ∈ F , we define the random variables Z fu and W fu as We prove the following lemma, which is an analogous result to Lemma 1.2 in [20].

Lemma 14
There exists an absolute constant c 1 > 0 for which the following holds. For every f u , f v ∈ F and every ǫ > 2 we have, Also, for every u > 0, P |Z fu | ≥ ǫα 2 ≤ 2 exp(−c 1 nǫ 2 ) , Proof: First, we prove (78). The process W fu−fv is defined as follows: We define the random variable z i = (u−v) T Σ i (u−v) |F i−1 which implies z i is a bounded MDS as E[z i |F i−1 ] = 0 and |z i | ≤ cA 2 = B for some constant c. Therefore, by the Azuma-Hoeffding inequality, The first equality follows by replacing the value of z i , the second by noting that E We use similar arguments to prove (79). Let z i = x i ,u 2 u T Σ i u − E x i ,u 2 u T Σ i u |F i−1 . By the argument given earlier, z i is a bounded MDS and |z i | ≤ cB for some constant c. Using the Azuma-Hoeffding inequality we obtain Let t = ǫcB and noting that α 2 = cB we get the following bound for some constant c 1 > 0 P |Z fu | ≥ ǫα 2 ≤ 2 exp(−c 1 nǫ 2 ) .
For the proof of (80) note that The second inequality follows since E x i ,u 2 u T Σ i u − x i ,v 2 v T Σ i v |F i−1 = 0 and the last equality follows by setting t = c 2 Bα f u − f v ψ 2 ǫ. This concludes the proof of Lemma 14 and following the same proof of Theorem D using Lemma 14 instead of Lemma 1.2 [20] we prove Lemma 13.
Finally, for the proof of Lemma 11, we follow the same application as in [6,Theorem 12]. This concludes the proof of Lemma 11.