Pith. sign in

REVIEW 3 major objections 5 minor 64 references

Minimax Rate-Optimal Algorithms for High-Dimensional Stochastic Linear Bandits

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The minimax regret for sparse linear bandits is $s_0(\log d + \log T)$, and a thresholded-Lasso algorithm attains it.

desk verdict Genuinely new minimax rates for sparse linear bandits, delivered with heavy machinery, but the upper bound depends on a covariance condition the abstract does not qualify. read the letter →

arxiv 2505.17400 v1 pith:A4VDFXR2 submitted 2025-05-23 math.ST stat.MLstat.TH

Jingyu Liu , Yanglei Song This is my paper · ORCID
classification math.STstat.MLstat.TH MSC 62L1262J07
keywords stochasticlinearbanditshigh-dimensionalcovariatesminimaxoptimalitythresholdedLassosequentialestimationcumulativeregretsparseregression
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to settle the minimax cumulative regret for high-dimensional stochastic linear bandits in which each arm's reward parameter is sparse. It shows that the unavoidable worst-case regret is proportional to $s_0(\log d + \log T)$, where $s_0$ is the sparsity, $d$ the covariate dimension, and $T$ the horizon, up to a $\log s_0$ factor over the full horizon and exactly once a short initial estimation period is ignored. The paper also shows that the routine strategy of running Lasso at every time step is provably suboptimal, while thresholded Lasso, which applies least squares to the support selected by thresholding an initial Lasso estimate, achieves the optimal cumulative estimation error. A three-stage algorithm that explores randomly, then exploits with Lasso, then switches to thresholded Lasso attains the claimed rate.

What carries the argument

The central object is OPT-Lasso (thresholded Lasso): first fit a Lasso estimator, keep only coordinates whose absolute value exceeds a threshold $\lambda^{\mathrm{OPT}}$, then run ordinary least squares on the selected support and zero out the rest. The argument turns on an instance-specific mean-squared-error decomposition in which only coordinates with $|\theta_j| \leq 2\lambda^{\mathrm{OPT}}$ contribute to the error; summing those contributions over $t$ via the identity $\sum_{t=1}^{T} a^2 \mathbf{1}\{|a| \leq \sqrt{b/t}\} \leq b$ removes the extra $\log T$ factor that a naive round-by-round worst-case bound would leave. A recent $\ell^\infty$ bound for Lasso at sample size $t = \Omega(s_0\log d)$ guarantees that the selected support contains all strong signals and excludes false positives, and log-concavity of the covariate density converts squared estimation error into expected instantaneous regret in the bandit setting.

What would settle it

Build a two-arm problem satisfying the paper's eigenvalue and log-concavity assumptions but with $\|(\Sigma^{(1)})^{-1}\|_\infty$ growing with $d$, for instance an autoregressive covariance with correlation $r_d \to 1$, and simulate the three-stage algorithm. If, after the warm-up period, cumulative regret grows faster than the claimed $O(s_0(\log d + \log T))$ rate, or the $\ell^2$ error of the Stage-3 thresholded estimator no longer obeys the instance-specific bound, the upper-bound proof's reliance on that norm condition is exposed.

Watch

Extended reading notes

Core claim

The central claim is that the minimax expected cumulative regret for a $K$-arm linear contextual bandit with $d$-dimensional covariates and $s_0$-sparse arm parameters is $\Theta(s_0(\log d + \log T))$ up to a $\log s_0$ factor over the whole horizon, and exactly $s_0(\log d + \log T)$ when the sum is started after round $O(s_0^5\log(dT))$. The upper bound is achieved by a three-stage procedure: uniform random arm selection for the first $\gamma_1 \approx s_0\log(dT)$ rounds, pure exploitation with Lasso for the next $\gamma_2 \approx s_0^5\log(dT)$ rounds, and pure exploitation with thresholded Lasso thereafter. The matching lower bound holds for every permissible rule under the same covariate and separation assumptions, using two prior constructions that isolate the $\log T$ and $\log d$ terms. In the isolated single-arm sequential estimation problem, the paper proves that plain Lasso suffers worst-case cumulative squared error $\Omega(s_0\log d\log T)$, while thresholded Lasso attains $O(s_0(\log d + \log T))$, matching a lower bound for all estimators.

Load-bearing premise

The load-bearing premise is Assumption 4(c): the inverse of each arm-conditional covariance matrix $\Sigma^{(k)}$ must have bounded $\ell^\infty$-to-$\ell^\infty$ norm, which limits how strongly correlated the covariates may be and is not implied by the eigenvalue bounds the paper already assumes.

Editorial extensions

If this is right

  • The three-stage algorithm has full-horizon regret $O(s_0(\log s_0)(\log d + \log T))$, so when sparsity is constant the $\log s_0$ factor disappears and the rate is exactly $s_0(\log d + \log T)$.
  • Ignoring the first $O(s_0^5\log(dT))$ rounds, the algorithm is exactly minimax: no permissible rule can beat $\Omega(s_0(\log d + \log T))$ over the remaining horizon.
  • Using plain Lasso instead of thresholded Lasso for exploitation adds a $\log T$ factor, so thresholding is necessary, not a practical nicety.
  • The results hold without beta-min signal-strength assumptions and allow $s_0$ to grow with $d$ and $T$.
  • In the single-arm sequential problem, thresholded Lasso attains the minimax cumulative capped mean-squared error $s_0(\log d + \log T)$, while Lasso does not.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The $\log s_0$ gap in the full-horizon bound is an artifact of using Lasso in Stage 2 to bridge from $\Omega(s_0\log(dT))$ to $\Omega(s_0^5\log(dT))$ samples; a Stage-2 estimator that works from $\Omega(s_0\log(dT))$ onward without the extra $\ell^\infty$-sample cost would likely remove it.
  • The sequential-estimation finding generalizes: any online procedure that repeatedly re-estimates a fixed sparse parameter by Lasso inherits an extra $\log T$ in cumulative error, so thresholded Lasso should be preferred in other streaming settings such as online covariate selection or dynamic treatment regimes.
  • Assumption 4(c) suggests a testable design principle: when arm-conditional covariances are nearly collinear, practitioners should expect the exact minimax claim to fail even though eigenvalue conditions hold, and debiased or projection-based estimators might restore it.
  • The gap between the exploration length $s_0\log(dT)$ and the thresholded-Lasso-ready length $s_0^5\log(dT)$ is likely loose; tightening it would shorten the warm-up period and improve finite-horizon regret.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies high-dimensional sparse stochastic linear bandits, where d may exceed T and each arm parameter is s0-sparse. In the first part it isolates a sequential (single-arm) estimation problem with cumulative capped mean-squared error as the criterion and proves three results: the Lasso estimator has worst-case cumulative error of order s0(log d)(log T) (Theorem 5); a thresholded Lasso (OPT-Lasso) estimator achieves cumulative error of order s0(log d + log T) (Theorem 1); and no permissible estimator can do better than s0(log d + log T) (Theorem 3). In the second part, the paper proposes a three-stage bandit algorithm (random exploration, Lasso-based exploitation, OPT-Lasso-based exploitation), proves a cumulative regret bound of order s0(log s0)(log d + log T) and an improved s0(log d + log T) bound once an initial period of length O(s0^5 log(dT)) is excluded (Theorem 6), and establishes a lower bound of order s0(log d + log T) for K = 2 (Theorem 7, Corollary 8), together with a result showing that a Lasso-only variant is suboptimal (Theorems 9 and 10). The proofs are detailed and use restricted eigenvalues, ℓ-infinity bounds for Lasso from [9] and [42], log-concavity of the covariate density for margin-type arguments, and Bayesian lower bounds via van Trees and Fano inequalities.

Significance. If the claims hold as stated, the paper gives the first characterization, up to a log s0 factor over the full horizon and exactly after an initial period, of the minimax regret for high-dimensional sparse linear contextual bandits in the class of designs considered, improving on [7], [46], and [3] and removing the beta-min condition from the upper bound. The sequential-estimation results are of independent interest, and the demonstration that Lasso is suboptimal under a cumulative criterion is a valuable conceptual point. Strengths of the manuscript include the complete proofs in the main text and appendices, the clean three-stage construction that separates exploration from exploitation, the explicit use of recent ℓ-infinity bounds to obtain the s0(log d + log T) rate, and the transparent discussion of limitations (e.g., Remark 2 on beta-min, Remark 6 on the missing s0 dependence in Theorem 10). The main reservations concern the scope of the unqualified claims in the abstract: the bandit upper bound requires Assumption 4(c), which is not implied by the eigenvalue assumptions, and the lower bound is proven only for K = 2.

major comments (3)
  1. [Section 3.2, Assumption 4(c); Lemmas 22-24; Theorem 6] The upper-bound proof for the bandit problem depends essentially on Assumption 4(c), which bounds the infinity norm of the inverse of each arm-conditional covariance matrix Sigma^(k). This condition enters through Lemma 12 with A = Sigma^(k) in Lemmas 22 and 24 to control the Lasso L-infinity error, and it fixes the threshold lambda_t^OPT = 28 L3 lambda_t in equation (9); through Theorem 11(ii) and Lemma 23 it controls the Stage-3 regret, the dominant term in Theorem 6. Assumption 4(b) does not imply 4(c): take B = I + delta(e1 1^T + 1 e1^T) with delta = 1/(2 sqrt(d)); then Sigma = B^{-1} has bounded eigenvalues and bounded entries while |||Sigma^{-1}|||_infinity is of order sqrt(d), and in a two-arm symmetric design with Sigma^(1) = Sigma^(2) = Sigma/2, Assumptions 4(a) and 4(b) hold while 4(c) fails. The paper explicitly acknowledges the analogous gap between Assumption 2 and Assumption 1(d) in Section 2.1, but it makes no corresponding remark for Assumption 4(c) in Section 3.2. Since the lower bound in Theorem 7 does not require 4(c), the exact-minimax conclusion of Corollary 8 is established only on the subclass of designs satisfying 4(c); for the model class described in the abstract (bounded log-concave covariates with eigenvalue bounds), the minimax rate is left open. The abstract, the introduction, and Corollary 8 should be qualified accordingly, and a remark with the counterexample should be added.
  2. [Abstract and Section 1.2 vs. Theorem 7 and Corollary 8] The lower bound in Theorem 7 and the minimax characterization in Corollary 8 are proven only for K = 2, as stated in the paragraph immediately before Theorem 7 ('under the case K = 2'). The abstract, however, claims 'a matching lower bound' and 'the minimax regret rate' for the multi-arm problem without this restriction, and the contribution list in Section 1.2 likewise omits it. For K >= 3, the paper supplies only the upper bound of Theorem 6. The headline statements should be revised to make the K = 2 scope explicit.
  3. [Abstract and Section 2 (sequential estimation)] The sequential-estimation upper bound in Theorem 1 requires Assumption 1(d), namely |||Sigma^{-1}|||_infinity <= L0, while the lower bound in Theorem 3 requires only the eigenvalue condition in Assumption 2. The text is transparent about this gap in Section 2.1, but the abstract's first paragraph ('thresholded Lasso estimators achieve the minimax rate') does not carry the same qualification. Since this is the same type of inverse-covariance condition that is load-bearing for the bandit upper bound, the abstract should state the minimax claims as holding under the full assumptions used in the theorems.
minor comments (5)
  1. [Keywords and title page] The keywords contain the typo 'Threshoded Lasso', which should be 'Thresholded Lasso'.
  2. [Proof of Theorem 1, Section 2.2] In the proof of Theorem 1, the inequality is written as 'E[||theta_hat_t^OPT - theta||_2^2 /\ xi]^2 <= ...'; the exponent 2 after the bracket appears to be a typo, since the displayed bound is for E[||theta_hat_t^OPT - theta||_2^2 /\ xi] itself.
  3. [Theorem 6 statement, Section 3.2] Theorem 6 should state explicitly that the horizon condition T >= gamma_2 (or a bound that gamma_2 is at most T) is assumed, since the proof sums over m = 1, ..., gamma_2/gamma_1 in Stage 2 and the stated log(s0) factor relies on log(gamma_2/gamma_1) = O(log s0).
  4. [Section 3.4, simulation setup] In the bandit simulations the regularization parameters lambda_t^(k) use the arm-pull proportions p_hat_t^(k) and are data-dependent, whereas the theoretical analysis in (8) fixes lambda_t common to all arms; a sentence reconciling this mismatch would help the reader connect the simulations to the theory.
  5. [Theorem 10, Section 3.3] The lower bound in Theorem 10 holds for the special design Sigma^(1) = Sigma^(2) = 2^{-1} I and does not capture the dependence on s0; the paper notes this honestly, but the abstract-level comparison with the minimax rate should also mention this restriction.

Circularity Check

0 steps flagged · score 2.0 of 10

No constructive circularity: the minimax upper and lower bounds follow from external Lasso oracle inequalities, Fano/van Trees arguments, and a direct three-stage regret analysis. The only flags are minor self-citations to the authors' earlier van Trees and log-concave lemmas.

full rationale

I walked the derivation chain rather than the prose claims. The sequential upper bound (Theorem 1) is built on the external ℓ∞ Lasso bound in [9] and a deterministic OPT-Lasso analysis (Theorem 14, Lemma 12); the target rate s0(log d + log T) is obtained by summing instance-specific threshold terms through Lemma 2, not by assuming the rate. The sequential lower bound (Theorem 3) uses two standard prior families: one handled by a van Trees inequality and one by a Fano packing argument; these give the log T and log d terms separately. The bandit upper bound (Theorem 6) is a direct restricted-eigenvalue and martingale analysis of the three-stage algorithm, with λt and λOPT_t set to order log(dT)/t and the final regret bound obtained by summing the same instance-specific threshold contributions. The bandit lower bound (Theorem 7) reduces regret to ℓ2 estimation error via the log-concave-density Lemma 33 and then reuses the two-prior lower-bound structure; no fitted parameter is renamed as a prediction. The only self-citations are to [36], co-authored by the second author: Lemma 15 invokes 'Theorem 31 in [36]' for the van Trees Bayes-risk bound, and Lemma 33 invokes 'Lemma 3 in [36]' for converting ℓ2 error into regret. These are parameter-free mathematical lemmas with stated assumptions that do not include the target rate, so they are real supporting evidence rather than a constructive circular step. Assumption 4(c) is indeed a genuine additional condition not implied by Assumption 4(b), but that is a scope or correctness caveat about the upper bound, not a circularity. Overall score 2 reflects only the minor self-citation; the central minimax-rate derivation is self-contained.

Assumptions & free parameters 2 free parameters · 7 assumptions · 0 invented entities

The central claims rest on a specific model: sparse parameters, i.i.d. Gaussian or log-concave contexts, sub-Gaussian noise, and covariance conditions. The proofs use established Lasso oracle inequalities and Bayesian lower-bound toolkits; no new physical entities or fitted constants enter the rates. The main load is the collection of domain assumptions, especially the inverse infinity-norm bounds in Assumptions 1(d) and 4(c) and the separation Assumption 5(b).

free parameters (2)
  • stage length constants Cgamma1 and Cgamma2 = O(1), chosen sufficiently large
    Stage boundaries in equation (10) are set as constants times s0 log(dT) and s0^5 log(dT); exact values do not affect asymptotic rates but must exceed proof-dependent thresholds.
  • regularization and threshold constants C0, C0^hard, 6mX sigma, 28L3 = explicit constants in equations (3) and (9)
    Lasso penalty and threshold sequences are chosen with sufficient constants; they are hand-chosen rather than fitted to data, and the rates do not depend on their exact values.
assumptions (7)
  • domain assumption Assumption 1: sparse Riesz condition and bounded infinity norm of Sigma^{-1}
    Used in Theorem 1 for the Lasso infinity-norm bound and OPT-Lasso upper bound; not satisfied by every covariance matrix with bounded spectrum.
  • domain assumption Assumption 2: bounded eigenvalues of Sigma
    Used in the sequential lower bound Theorem 3; satisfied by isotropic or well-conditioned designs.
  • domain assumption Assumption 4: bounded log-concave covariate distribution with eigenvalue bounds and inverse arm-covariance infinity bound
    Underpins the margin condition, restricted eigenvalue properties, and OPT-Lasso analysis in the bandit upper bound; excludes heavy-tailed or unbounded contexts.
  • domain assumption Assumption 5: arm parameters are bounded and linearly separated
    Required to convert estimation error into regret and to avoid adversarial parameter ties; without it the margin structure needed for logarithmic regret is absent.
  • standard math Lasso oracle inequalities and infinity-norm bounds from [9, 42, 45]
    Unproved background inequalities used to control Lasso and OPT-Lasso estimation error.
  • standard math van Trees inequality and Fano's inequality from [15, 31, 36]
    Used to derive lower bounds on Bayes risk in Theorems 3 and 7.
  • domain assumption Sparsity class Theta_d[s0] and sigma-sub-Gaussian noise
    Problem formulation; all claims are relative to this model.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Minimax Rate-Optimal Algorithms for High-Dimensional Stochastic Linear Bandits." pith.science (2026). https://pith.science/paper/A4VDFXR2

@misc{pith2026250517400,
  author       = {Pith},
  title        = {Pith review of: Minimax Rate-Optimal Algorithms for High-Dimensional Stochastic Linear Bandits},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/A4VDFXR2}},
  note         = {Machine review of arXiv:2505.17400}
}
abstract

We study the stochastic linear bandit problem with multiple arms over $T$ rounds, where the covariate dimension $d$ may exceed $T$, but each arm-specific parameter vector is $s$-sparse. We begin by analyzing the sequential estimation problem in the single-arm setting, focusing on cumulative mean-squared error. We show that Lasso estimators are provably suboptimal in the sequential setting, exhibiting suboptimal dependence on $d$ and $T$, whereas thresholded Lasso estimators -- obtained by applying least squares to the support selected by thresholding an initial Lasso estimator -- achieve the minimax rate. Building on these insights, we consider the full linear contextual bandit problem and propose a three-stage arm selection algorithm that uses thresholded Lasso as the main estimation method. We derive an upper bound on the cumulative regret of order $s(\log s)(\log d + \log T)$, and establish a matching lower bound up to a $\log s$ factor, thereby characterizing the minimax regret rate up to a logarithmic term in $s$. Moreover, when a short initial period is excluded from the regret, the proposed algorithm achieves exact minimax optimality.

Figures

Figures reproduced from arXiv: 2505.17400 by the authors.

Figure 1
Figure 1. The x-axis represents time, and the y-axis the cumulative error from time T /10 to time t ∈ [T /10, T]. For scenario (c), we report the running cumulative estimation error of OPT-Lasso, Lasso and an Oracle (“LS”). The left plot corresponds to C0 = 0.8, Chard 0 = 0.6 and the right plot to C0 = 1, Chard 0 = 0.4. 0 1000 2000 3000 4000 0 5 10 15 20 25 30 35 time False Positive Lasso OPT−Lasso 0 1000 2000 3000 4000 0 1 2… view at source ↗
Figure 2
Figure 2. We consider scenario (c) and set C0 = 0.8, Chard 0 = 0.6. The left (resp. right) plot shows the number of false positives (resp. negatives) at each time t ∈ [T] for Lasso and OPT-Lasso. rounds, and at each round/time t ∈ [T], we observe a covariate vector Xt ∈ R d , select an arm At ∈ [K], and receive a reward Yt ∈ R, which satisfies the following linear model: Yt = X′ tθ (At) + ϵt . We assume that the covariate vec… view at source ↗
Figure 3
Figure 3. An illustration of the three-stage algorithm. The three stages are as follows: a pure [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: The y-axis represents the cumulative regret up to time t ∈ [γ2, T]. The left plot is for scenario (e) with C0 = 2, Chard 0 = 0.6, γ2 = 400, while the right plot is for scenario (f) with C0 = 2, Chard 0 = 1, γ2 = 800. In [PITH_FULL_IMAGE:figures/full_fig_p020_4.png]
Figure 5
Figure 5. Figure 5: We consider scenario (e) and (f) with C0 = 2, Chard 0 = 0.6. The left plot shows the number of false positives, while the right plot shows the number of false negatives at each time t ∈ [T /2], averaged across K arms. The trend after time T /2 remains similar and is th…
Figure 6
Figure 6. Figure 6: The x-axis represents time, and the y-axis shows the cumulative estimation error from time T /10 to time t ∈ [T /10, T]. The three rows correspond to scenarios (a), (b), and (d), respectively, while the first and second columns correspond to the parameter settings (C0 …
Figure 7
Figure 7. Figure 7: The x-axis represents time, and the y-axis denotes the cumulative regret up to time t ∈ [γ2, T]. The three rows in the left column correspond to scenarios (a), (c), and (g), with C0 = 2 and C hard 0 = 0.6, while the three rows in the right column correspond to scenario…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

64 extracted references · 59 canonical work pages

  1. [9]

    B ELLEC , P. C. and Z HANG , C.-H. (2022). De-biasing the lasso with degrees-of-freedom adjustment. Bernoulli 28 713–743

    work page 2022

  2. [42]

    V AN DE GEER , S. A. (2016). Estimation and testing under sparsity. Springer

    work page 2016

  3. [7]

    and B AYATI, M

    B ASTANI , H. and B AYATI, M. (2020). Online decision making with high-dimensional covariates. Opera- tions Research 68 276–294

    work page 2020

  4. [46]

    and Y AO, T

    W ANG , X., W EI, M. and Y AO, T. (2018). Minimax concave penalized multi-armed bandit model with high-dimensional covariates. In International Conference on Machine Learning 5200–5208. PMLR

    work page 2018

  5. [3]

    and P ROUTIÈRE , A

    A RIU , K., A BE, K. and P ROUTIÈRE , A. (2022). Thresholded lasso bandit. In International Conference on Machine Learning 878–928. PMLR

    work page 2022

  6. [1]

    and S ZEPESVÁRI , C

    A BBASI -YADKORI , Y., P ÁL, D. and S ZEPESVÁRI , C. (2011). Improved algorithms for linear stochastic bandits. Advances in neural information processing systems 24 2312–2320

    work page 2011

  7. [2]

    and G OYAL, N

    A GRAWAL , S. and G OYAL, N. (2012). Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory 39–1. JMLR Workshop and Conference Proceedings

    work page 2012

  8. [4]

    and B UBECK , S

    A UDIBERT , J.-Y. and B UBECK , S. (2009). Minimax Policies for Adversarial and Stochastic Bandits. In 22nd Conference on Learning Theory 217–226

    work page 2009

Show all 64 references
  1. [5]

    and F ISCHER , P

    A UER , P., C ESA -BIANCHI , N. and F ISCHER , P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine learning 47 235–256

    2002

  2. [6]

    and S CHAPIRE , R

    A UER , P., C ESA -BIANCHI , N., F REUND , Y. and S CHAPIRE , R. E. (2002). The nonstochastic multiarmed bandit problem. SIAM journal on computing 32 48–77

    2002

  3. [8]

    and K HOSRAVI , K

    B ASTANI , H., B AYATI, M. and K HOSRAVI , K. (2021). Mostly exploration-free algorithms for contextual bandits. Management Science 67 1329–1349

    2021

  4. [10]

    and C HERNOZHUKOV , V

    B ELLONI , A. and C HERNOZHUKOV , V. (2013). Least squares after model selection in high-dimensional sparse models. Bernoulli 19 521–547

    2013

  5. [11]

    and CESA -BIANCHI , N

    B UBECK , S. and CESA -BIANCHI , N. (2012). Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems. Found. Trends Mach. Learn.5 1–122. https://doi.org/10.1561/2200000024

    2012 doi

  6. [12]

    and VAN DE GEER , S

    B ÜHLMANN , P. and VAN DE GEER , S. (2011). Statistics for high-dimensional data: methods, theory and applications. Springer Science & Business Media

    2011

  7. [13]

    and L I, L

    C HAPELLE , O. and L I, L. (2011). An empirical evaluation of thompson sampling. Advances in neural information processing systems 24

    2011

  8. [14]

    and S HARPNACK , J

    D ING , Q., H SIEH , C.-J. and S HARPNACK , J. (2021). An efficient algorithm for generalized linear bandit: Online stochastic gradient descent and thompson sampling. In International Conference on Artificial Intelligence and Statistics 1585–1593. PMLR

    2021

  9. [15]

    G ILL , R. D. and L EVIT , B. Y. (1995). Applications of the van Trees inequality: a Bayesian Cramér-Rao bound. Bernoulli 59–79

    1995

  10. [16]

    and Z EEVI , A

    G OLDENSHLUGER , A. and Z EEVI , A. (2013). A linear response bandit problem. Stochastic Systems 3 230–261

    2013

  11. [17]

    and B AYATI, M

    H AMIDI , N. and B AYATI, M. (2020). A General Framework to Analyze Stochastic Linear Bandit. CoRR abs/2002.05152

    2020 arXiv

  12. [18]

    and W ANG , M

    H AO, B., L ATTIMORE , T. and W ANG , M. (2020). High-dimensional sparse linear bandits. Advances in Neural Information Processing Systems 33 10753–10763

    2020

  13. [19]

    J IN, C., N ETRAPALLI , P., GE, R., K AKADE , S. M. and J ORDAN , M. I. (2019). A short note on concentra- tion inequalities for random vectors with subgaussian norm. arXiv preprint arXiv:1902.03736

    2019 arXiv

  14. [20]

    and W ILLETT , R

    J UN, K.-S., B HARGAVA , A., N OWAK, R. and W ILLETT , R. (2017). Scalable generalized linear bandits: Online computation and hashing. Advances in Neural Information Processing Systems 30

    2017

  15. [21]

    M., S HALEV -S HWARTZ , S

    K AKADE , S. M., S HALEV -S HWARTZ , S. and T EWARI , A. (2008). Efficient bandit algorithms for online multiclass prediction. In Proceedings of the 25th international conference on Machine learning 440– 447

    2008

  16. [22]

    and P AIK , M

    K IM, G.-S. and P AIK , M. C. (2019). Doubly-robust lasso bandit. Advances in Neural Information Process- ing Systems 32

    2019

  17. [23]

    L., R OBBINS , H

    L AI, T. L., R OBBINS , H. et al. (1985). Asymptotically efficient adaptive allocation rules. Advances in applied mathematics 6 4–22

    1985

  18. [24]

    and S ZEPESVÁRI , C

    L ATTIMORE , T. and S ZEPESVÁRI , C. (2020). Bandit algorithms. Cambridge University Press

    2020

  19. [25]

    and S CHAPIRE , R

    L I, L., C HU, W., L ANGFORD , J. and S CHAPIRE , R. E. (2010). A contextual-bandit approach to person- alized news article recommendation. In Proceedings of the 19th International Conference on World Wide Web661–670. ACM

    2010

  20. [26]

    and S CHAPIRE , R

    L I, L., C HU, W., L ANGFORD , J. and S CHAPIRE , R. E. (2010). A contextual-bandit approach to personal- ized news article recommendation. In Proceedings of the 19th international conference on World wide web 661–670

    2010

  21. [27]

    and Z EEVI , A

    O H, M.- H., I YENGAR , G. and Z EEVI , A. (2021). Sparsity-agnostic lasso bandit. In International Confer- ence on Machine Learning 8271–8280. PMLR. 25

    2021

  22. [28]

    and R IGOLLET , P

    P ERCHET , V. and R IGOLLET , P. (2013). The multi-armed bandit problem with covariates. The Annals of Statistics 41 693–721

    2013

  23. [29]

    R ASKUTTI , G., WAINWRIGHT , M. J. and Y U, B. (2011). Minimax rates of estimation for high-dimensional linear regression over ℓq-balls. IEEE transactions on information theory 57 6976–6994

    2011

  24. [30]

    and Z HOU , Z

    R EN, Z. and Z HOU , Z. (2024). Dynamic batch learning in high-dimensional sparse linear contextual ban- dits. Management Science 70 1315–1342

    2024

  25. [31]

    and HÜTTER , J.-C

    R IGOLLET , P. and HÜTTER , J.-C. (2023). High-Dimensional Statistics

    2023

  26. [32]

    R OBBINS , H. (1952). Some aspects of the sequential design of experiments.Bulletin of the American Math- ematical Society 58 527–535

    1952

  27. [33]

    and Z HOU , S

    R UDELSON , M. and Z HOU , S. (2012). Reconstruction from Anisotropic Random Measurements. In Pro- ceedings of the 25th Annual Conference on Learning Theory . Proceedings of Machine Learning Re- search 23 10.1–10.24. PMLR, Edinburgh, Scotland

    2012

  28. [34]

    and V AN ROY, B

    R USSO , D. and V AN ROY, B. (2018). Learning to optimize via information-directed sampling. Operations Research 66 230–252

    2018

  29. [35]

    S HALEV -S HWARTZ , S. et al. (2012). Online learning and online convex optimization. Foundations and Trends® in Machine Learning 4 107–194

    2012

  30. [36]

    and Z HOU , M

    S ONG , Y. and Z HOU , M. (2022). Truncated LinUCB for Stochastic Linear Bandits. arXiv preprint arXiv:2202.11735

    2022 arXiv

  31. [37]

    and M URPHY , S

    T EWARI , A. and M URPHY , S. A. (2017). From ads to interventions: Contextual bandits in mobile health. In Mobile Health 495–517. Springer

    2017

  32. [38]

    T HOMPSON , W. R. (1933). On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25 285–294

    1933

  33. [39]

    T IBSHIRANI , R. (1996). Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological) 58 267–288

    1996

  34. [40]

    and Z HOU , S

    V AN DE GEER , S., B ÜHLMANN , P. and Z HOU , S. (2011). The adaptive and the thresholded Lasso for potentially misspecified models (and a lower bound for the Lasso)

    2011

  35. [41]

    V AN DE GEER , S. A. (2008). High-dimensional generalized linear models and the lasso. The Annals of Statistics 36 614–645

    2008

  36. [43]

    V ERSHYNIN , R. (2018). High-dimensional probability: An introduction with applications in data science

    2018

  37. [44]

    W AINWRIGHT , M. J. (2009). Sharp thresholds for High-Dimensional and noisy sparsity recovery using ℓ1-Constrained Quadratic Programming (Lasso). IEEE transactions on information theory 55 2183– 2202

    2009

  38. [45]

    W AINWRIGHT , M. J. (2019). High-dimensional statistics: A non-asymptotic viewpoint 48. Cambridge Uni- versity Press

    2019

  39. [47]

    Cambridge university press

  40. [48]

    and LIN, Y

    Y UAN, M. and LIN, Y. (2006). Model selection and estimation in regression with grouped variables.Journal of the Royal Statistical Society: Series B (Statistical Methodology) 68 49–67

    2006

  41. [49]

    and H UANG , J

    Z HANG , C.-H. and H UANG , J. (2008). The sparsity and bias of the Lasso selection in high-dimensional linear regression. The Annals of Statistics 36 1567 – 1594. https://doi.org/10.1214/07-AOS520

    2008 doi

  42. [50]

    and Y U, B

    Z HAO, P. and Y U, B. (2006). On model selection consistency of Lasso. The Journal of Machine Learning Research 7 2541–2563

    2006

  43. [51]

    Z OU, H. (2006). The adaptive lasso and its oracle properties.Journal of the American statistical association 101 1418–1429

    2006

  44. [52]

    and H ASTIE , T

    Z OU, H. and H ASTIE , T. (2005). Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society Series B: Statistical Methodology 67 301–320. 26 APPENDIX A: LASSO AND OPT-LASSO: DETERMINISTIC ANALYSIS In this Appendix, we consider the foll...

    2005

  45. [53]

    By the same argument, we also have (22) Eθ∼ω2 bθn − θ ∥θ∥2 2 2 ! ≥ δ2 4(r2 + 2δ2) inf ψ∈FM 1 M MX i=1 Pαi(ψ(Y , Z) ̸= i)

    ≥ δ2 4 inf ψ∈FM 1 M MX i=1 Pαi(ψ(Y , Z) ̸= i), where Pαi denotes the conditional distribution of (Y , Z) on the event {θ = αi}. By the same argument, we also have (22) Eθ∼ω2 bθn − θ ∥θ∥2 2 2 ! ≥ δ2 4(r2 + 2δ2) inf ψ∈FM 1 M MX i=1 Pαi(ψ(Y , Z) ̸= i). Step 2: lower bound the ave...

  46. [54]

    That is, the conditions (3.5)-(3.8) in Assumption 3.1 of [9] hold with a modified λ0 defined above

    log(8dt) t , and s∗ = s0 + m + k; iv) finally, 2(m + k) + s0 + 1 ≤ (t − 1) ∧ (d + 1), ϵ 1 + ϵ2 < 1, ϵ 3 + ϵ4 = ϵ2 2/8, s0 + m + k + 1 ≤ (d + 1) ∧ (ϵ2 1t/2), log d − s0 m + k ≤ ϵ3t. That is, the conditions (3.5)-(3.8) in Assumption 3.1 of [9] hold with a modified λ0 defined abo...

  47. [55]

    P (X ′ [t],SX [t],S)−1/2W 2 2 > α2 b2 j s0 | X [t],S ! ; A1,t # ≤E

    log(dt) in Proposition A.6 of [9], we have P Ω(1) noise ∩ Ω(2) noise ≥ 1 − t−1. The remainder of the argument closely follows the proof of Theorem 5.1 in [9] and is therefore omitted. LEMMA 19. Suppose that Assumption 1 (c) holds, and that the support S of θ is non- empty. Let...

  48. [56]

    (Lemma 25) with probability at least 1 − 2K/T 4, for each arm k ∈ [K], v′ 1 γ1 γ1X t=1 X tX ′ t1 {At = k} ! v ≥ 1 4KL3 ∥v∥2 2, for all v ∈ C(s0, 3).(32) 39

  49. [57]

    (Lemma 26) with probability at least 1 − 2K/T 4, for each arm k ∈ [K], (33) v′ 1 n nX t=1 X tX ′ t1 {X t ∈ U(k) h∗ } ! v ≥ ℓ∗ 0∥v∥2 2, for all v ∈ C(s0, 3), where we recall the definition of U (k) h in (27)

  50. [58]

    (Lemma 27) for any u ∈ Rd with ∥u∥2 ≤ ℓ∗ 1, with probability at least 1 − 2/T 4, (34) v′ 1 n nX t=1 X tX ′ t1 {|u′X t| ≥h∗/2} ! v ≤ K − 1 K a∗∥v∥2 2, for all v ∈ C(s0, 3) where we define (35) a∗ = min{(ℓ∗ 0/K), 1/(4KL3)}

  51. [59]

    (Lemma 30) for any t ∈ [T ], with probability at least 1 − K/T 2, for each arm k ∈ [K] ∥(X (k) [t] )′ Skϵ[t]/t∥2 ≤ C∗mX σ r 3s0 log(dT ) t .(36) where (X (k) [t] )′ Sk ϵ[t] = 0 if Sk is empty

  52. [60]

    too close

    (Lemma 35) for any u ∈ Rd such that u ̸= 0d, P(|u′X 1| ≤τ ) ≤ C∗ ∥u∥2 τ, for all τ >0.(37) Note that the events in (33), (34), and (37) depend only on the properties of the i.i.d. ran- dom vectors {X t : t ∈ [T ]}, and not on the arm selection mechanism. Moreover, the fourth p...

  53. [61]

    By the definition of a∗ in (35), ℓ∗ 0 ≥ a∗K

    Thus, since {X t : mγ2 < t≤ (m + 1)γ2} are independent from Fmγ2 and ˜E OPT m ∈ Fmγ2, due to (34) with u = eθ (k) mγ2 − θ(k), we have that almost surely, P ˜A′ m+1|Fmγ2 1 { ˜E OPT m } ≥(1 − 2K/T 4)1 { ˜E OPT m }. By the definition of a∗ in (35), ℓ∗ 0 ≥ a∗K. Thus, due to (41) a...

  54. [62]

    Due to the assumption, L−1 ≤ v′AS,Sv ≤ L, which implies that L−1 − C × s ≤ v′BS,Sv ≤ L + C × s

    = C × s. Due to the assumption, L−1 ≤ v′AS,Sv ≤ L, which implies that L−1 − C × s ≤ v′BS,Sv ≤ L + C × s. The proof is then complete. LEMMA 39. Let {Bi : i ∈ [n]} be a sequence of independent Bernoulli random variables. Assume that for some δ ∈ [0, 1], E[Bi] ≤ δ for i ∈ [n]. Th...

  55. [63]

    Now, we focus on the second claim

    Thus, A satisfies RE(s, κ, a2/(1 + κ)). Now, we focus on the second claim. Let v ∈ Rd\{0d}, and J ⊆ [d] such that |J| ≤s and ∥vJ c∥1 ≤ κ∥vJ ∥1. By definition, v ∈ C(s, k). As a result, a ≤ ∥Av∥2 2 n∥v∥2 2 ≤ ∥(A/√n)v∥2 2 ∥vJ ∥2 2 . Since the above holds for any such pair v, J, ...

  56. [64]

    Two-stage with Lasso

    The proof is then complete since Z = ΨA1/2. APPENDIX H: ADDITIONAL SIMULATION RESULTS Sequential Estimation. We present additional simulation results for the sequential esti- mation setting, focusing on scenarios (a), (b), (c), and (d) as described in Section 2.4. Figure 6 dis...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.