Pith. sign in

REVIEW 2 major objections 5 minor 44 references

When action features are only partly observed, low intrinsic dimension still yields √T linear-bandit regret in that dimension, not the ambient one.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.5

2026-07-13 01:19 UTC pith:BOLOJFYP

load-bearing objection Solid theory paper: epoch-freeze + impute gets m√T regret under MAR low-rank actions, with a clean product lower bound; modeling restrictions are real but stated. the 2 major comments →

arxiv 2607.08971 v1 pith:BOLOJFYP submitted 2026-07-09 cs.LG math.STstat.MLstat.TH

Stochastic Linear Bandits with Partially Observed Actions

Gautam Dasarathy , Vineet Gattani , Lalit Jain This is my paper
classification cs.LG math.STstat.MLstat.TH
keywords stochastic linear banditspartial observabilitylow-rank action representationssubspace estimationimputationOFULregret boundsrank adaptivity
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

Standard linear bandits assume the learner sees every coordinate of every offered action. In practice that is often false: privacy, cost, or sensing limits hide many coordinates, and without structure sublinear regret is information-theoretically impossible. This paper shows the barrier lifts when the ideal action vectors live in an unknown low-dimensional subspace. The algorithm estimates that subspace from masked arms, freezes the estimate inside doubling epochs, imputes the current slate, and runs ordinary OFUL in the recovered coordinates. The resulting high-probability regret scales as √T in the intrinsic dimension m rather than ambient d, with explicit factors for missingness probability, slate size, and subspace conditioning. A rank-adaptive version needs no knowledge of m, and a matching-style lower bound separates ordinary reward uncertainty from an unavoidable missingness-discovery cost. The point is practical: recommendation and healthcare settings that only ever see sparse features can still learn efficiently once low-rank action structure is exploited.

Core claim

Under exact low-rank action support, incoherence, and Bernoulli coordinate masks, an epoch-wise estimate-impute-OFUL procedure (TOFU-POV) achieves high-probability regret that is ˜O(κ²m/(p⁴K) + m√T + κm√T/(p²√K)), replacing ambient dimension d by intrinsic dimension m; a rank-adaptive variant matches this scaling once a short burn-in ends.

What carries the argument

TOFU-POV: corrected covariance PCA on all offered masked arms, epoch-wise frozen subspace, least-squares imputation of missing coordinates, then ordinary OFUL in the resulting m-dimensional features, with misspecification controlled by the frozen approximation error.

Load-bearing premise

The ideal actions must truly live in a low-dimensional, well-spread subspace, and the chance of seeing each coordinate must be high enough that the observed rows stay well-conditioned; if the subspace is concentrated on a few coordinates or missingness is adversarial, the guarantee collapses.

What would settle it

Construct or sample action vectors that are only approximately low-rank or whose energy is concentrated on few coordinates, run TOFU-POV under the same Bernoulli masks, and check whether cumulative regret remains √T in m or reverts to linear in T as ambient dimension grows.

Watch this falsifier — get emailed when new claim-graph text bears on it.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The paper studies stochastic linear bandits when each offered action is observed only through independent Bernoulli-p coordinate masks, but the ideal actions lie in an unknown m-dimensional subspace of R^d. The authors propose TOFU-POV, which estimates a corrected covariance from all offered masked arms, freezes a subspace estimate within doubling epochs, imputes missing coordinates by least squares on the frozen basis, and runs OFUL in the resulting m-dimensional coordinates. Under bounded actions, full-rank action covariance, and µ-incoherence with p large enough for observed Gram conditioning, they prove high-probability regret ˜O(κ²m/(p⁴K) + m√T + κm√T/(p²√K)), replacing ambient dimension d by intrinsic dimension m. A rank-adaptive variant recovers the same scaling up to burn-in without knowing m. A product lower-bound construction separates ordinary reward-learning cost from a missingness-discovery cost. Synthetic and real-feature experiments (MNIST product-context, optical digits, 20 Newsgroups) support the theory and show gains under heavier missingness.

Significance. Partial observability of action features is a realistic and under-studied obstacle in recommendation and healthcare bandits; without structure, sublinear regret is information-theoretically impossible, so the low-rank action model is a natural and useful way forward. The technical contribution is solid: epoch-wise freezing cleanly restores standard self-normalized and elliptical-potential arguments that continual projected-OFUL would break (Appendix A), the misspecification contraction (Lemma 4) avoids an extra √m factor, and the product lower bound is a genuine novelty. Rank adaptivity essentially for free, public code, and multi-seed experiments with real covariates strengthen the package. If the result holds as stated, it is a clear advance for structured linear bandits under missing features and a useful template for other representation-learning bandit settings.

major comments (2)
  1. [Theorem 2, Theorem 4, Section 9] Theorem 2 vs Theorem 4 / Section 9: the upper bound’s representation term scales as κm√T/(p²√K), while the lower bound’s missingness cost is only order SBX min{T, 1/(Kp²)} (constant for fixed p,K once T is large). Section 9 correctly flags that the √T/p²-type term may be an artifact, but the main theorem statement and abstract still present the full three-term bound as the scaling of the problem. Please either (i) strengthen the lower bound toward a √T missingness term, or (ii) restate the main guarantee so that the additive burn-in and the possibly non-tight representation term are clearly separated from the intrinsic m√T reward-learning cost.
  2. [Section 4.1, Eq. (5), Lemma 2] Eq. (5) and Lemma 2: the burn-in tb scales as κ²m/(p⁴K) and the imputation analysis requires p ≳ (µ²m/d) log(mTK/δ). Both are load-bearing for the post-burn-in √T regime. The p⁻⁴ dependence is acknowledged as technique-specific, but for moderate missingness (e.g., p=0.2 as in the experiments) this burn-in can dominate practical horizons. A short discussion of when tb is negligible relative to T, and whether a milder conditioning target than ϵt ≤ p/32 is possible, would make the applicability of Theorem 2 clearer.
minor comments (5)
  1. [Algorithm 1, Section 8] Algorithm 1 and the paragraph after it: the theory analyzes the cold-start epoch design, while experiments use full-history replay / warm-start. Please mark this distinction more prominently in Section 8 (e.g., a short “theory vs practice” note) so readers do not attribute experimental gains solely to the analyzed algorithm.
  2. [Section 3] Definition of κ in Section 3: κ := BX √λ̄ /(λm √m) is used throughout; a one-line remark that κ = Θ(1) under flat spectrum λm ≍ λ̄ ≍ B²X/m would help readers parse the “˜O(m√T)” special case stated after Theorem 2.
  3. [Figure 1, Section 8] Figure 1 caption and legend: RA-ZF-PSLB appears in plots but is only briefly named; a one-sentence definition next to ZF-PSLB would improve readability.
  4. [Section 3, Appendix D] Typos / polish: “Toreasonaboutsubspacerecovery” (Section 3) needs spaces; “ineqiality” in Appendix D; occasional missing spaces after periods in the arXiv text. A pass for spacing and hyphenation would help.
  5. [Section 2] Related work: the comparison to Kim et al. (2025) and Park & Faradonbeh (2022) is clear on observation models; a sentence on whether their techniques could be combined with low-rank action structure would round out the positioning.

Circularity Check

0 steps flagged

No significant circularity: regret and lower-bound claims are derived from stated assumptions via standard concentration and OFUL arguments, not by construction from fitted inputs or load-bearing self-citation.

full rationale

TOFU-POV’s main guarantees (Theorems 2–3) are obtained from explicit modeling assumptions (bounded low-rank actions, action-covariance rank, µ-incoherence, Bernoulli-p masks with p large enough for observed Grams) through a transparent chain: inverse-probability corrected covariance (Lemma 5) + matrix Bernstein (Lemma 7) → Davis–Kahan subspace rate (Lemma 1); burn-in for Gram conditioning; frozen-epoch least-squares imputation (Lemma 2) → controlled misspecification be (Lemma 3); contraction control of aggregated misspecification (Lemma 4) plus self-normalized OFUL inside epochs; doubling schedule summing to √T. The lower bound (Theorem 4) uses an independent four-instance product construction separating reward-learning and missingness-discovery costs. Self-citations (e.g., multi-fidelity/active-learning pointers in Discussion) are background only and do not underwrite the theorems. No parameter is fitted to data and re-labeled a prediction; no uniqueness theorem is imported from the authors; no ansatz is smuggled in as a derivation. The paper is a standard self-contained theory contribution with experimental support.

Axiom & Free-Parameter Ledger

4 free parameters · 6 axioms · 3 invented entities

The central √T claim rests on standard linear-bandit noise and OFUL machinery plus domain assumptions that actions are exactly low-rank, bounded, covariance-full-rank on the subspace, µ-incoherent, and observed via known-p Bernoulli masks. Free parameters are analysis/algorithm constants (burn-in, ridge λ, confidence splits), not data-fitted physical constants. Invented entities are algorithmic constructs and a hard-instance family, not new physical objects.

free parameters (4)
  • burn-in length tb / Cb
    Chosen from subspace error threshold ϵ_t ≤ p/32; universal Cb = (32 C_sub)² appears in analysis and sets additive burn-in cost.
  • ridge regularization λ
    Set to λ := 4 B_X² for potential control after burn-in; algorithmic free choice constrained by theory.
  • confidence allocations δ_rep, δ_e, δ_rank
    Failure probabilities split across representation, epoch OFUL, and rank events; affect log factors only.
  • experimental ranks/thresholds/confidence widths
    On real-feature tasks, ranks and thresholds are chosen on validation seeds disjoint from reporting seeds; not used in theorems.
axioms (6)
  • domain assumption Bounded actions: ||X_{t,i}||_2 ≤ B_X a.s. (Assumption 1)
    Standard bandit normalization; used throughout concentration and regret.
  • domain assumption Action covariance Σ has rank m with eigenvalues bounded by λ̄ and λ_m > 0 (Assumption 2)
    Defines intrinsic dimension and conditioning κ; load-bearing for subspace recovery rate.
  • domain assumption True subspace is µ-incoherent w.r.t. coordinate basis (Definition 1)
    Needed so random masks still excite all latent directions (Lemma 9).
  • domain assumption Independent Bernoulli(p) coordinate masks, independent of actions and policy
    Enables unbiased corrected covariance (Lemma 5) and MAR analysis; MNAR not covered.
  • domain assumption Rewards are linear in ideal actions with R-sub-Gaussian noise; θ⋆ in span(U)
    Classical stochastic linear bandit model restricted to the latent subspace.
  • standard math Matrix Bernstein, Matrix Chernoff, Davis–Kahan, self-normalized martingale bounds
    Standard concentration tools cited and applied in Appendices C–F.
invented entities (3)
  • TOFU-POV (epoch-wise freeze, impute, OFUL) independent evidence
    purpose: Algorithm that makes subspace estimation compatible with OFUL confidence sets under missing coordinates
    Core method; independent_evidence via regret theorems and experiments, not an external physical entity.
  • Corrected covariance estimator Σ̇_t with inverse-probability diagonal/off-diagonal correction independent evidence
    purpose: Unbiased subspace estimation from masked offered arms
    Adapted from missing-data covariance literature; used as algorithmic primitive.
  • Four-instance product hard family I_{ν,σ} for lower bound no independent evidence
    purpose: Separate ordinary reward-sign uncertainty from missingness-discovery of a completion sign
    Proof construction in Appendix H; not claimed as a real-world system.

pith-pipeline@v1.1.0-grok45 · 46120 in / 3367 out tokens · 39231 ms · 2026-07-13T01:19:07.351926+00:00 · methodology

0 comments
read the original abstract

The stochastic linear bandit, where actions are represented as vectors and rewards are linear, is a central paradigm for sequential decision making. We study a partially observed variant of this problem in which the learning agent only sees a random subset of coordinates for each action. Such partial observability arises naturally in settings like recommendation and healthcare, where full action descriptions can be expensive or even impossible to obtain. In general, this makes sublinear regret information-theoretically impossible. However, we show that this barrier can be overcome when the action vectors have low intrinsic dimension. We propose an algorithm, TOFU-POV, that estimates the latent action subspace using the masked actions, imputes current actions using an epoch-wise frozen representation, and runs OFUL in the resulting low-dimensional coordinates. Our theory shows that TOFU-POV enjoys a $\sqrt{T}$ regret that scales with the intrinsic action subspace dimension as opposed to the ambient dimension and quantifies the interaction between these quantities and the missingness, decision set size, and subspace conditioning. We also devise a rank-adaptive algorithm that does not require the knowledge of the intrinsic dimension. We complement these guarantees with a lower bound based on a novel product construction that separates usual reward-learning uncertainty from a missingness-dependent cost intrinsic to partial observation. Synthetic and real data experiments support our theory and show that TOFU-POV can substantially improve upon natural baselines in this challenging problem.

Figures

Figures reproduced from arXiv: 2607.08971 by Gautam Dasarathy, Lalit Jain, Vineet Gattani.

Figure 1
Figure 1. Figure 1: Synthetic missing-feature experiments. TOFU and RA-TOFU gain most when missingness is substantial: ZF-OFUL and ZF-PSLB degrade as p decreases, while the TOFU variants continue to exploit the corrected low-rank structure. ten product-context arms into R 100 by a fixed orthonormal map and mask coordinates. Rewards are classification rewards; T = 5000, tb = 500, p ∈ {0.7, 0.5, 0.3, 0.2}, and ranks, thresholds… view at source ↗
Figure 2
Figure 2. Figure 2: MNIST experiment. TOFU-FH wins or ties, and the gap over baselines grows as p decreases . This paper studies contextual decision making when the learner must act from incomplete action descrip￾tions. We focus on the case of i.i.d. action sets with low-rank structure and missing-at-random coordi￾nates. Natural extensions include approximately low￾rank action models, where the tail of the spectrum would crea… view at source ↗
Figure 3
Figure 3. Figure 3: Full-history synthetic counterpart. TOFU-FH and RA-TOFU-FH use the same subspace [PITH_FULL_IMAGE:figures/full_fig_p049_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Real-feature synthetic experiment. Real covariates replace Gaussian arms, but the [PITH_FULL_IMAGE:figures/full_fig_p050_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Synthetic adaptive-rank summary. The final selected ranks are shown here rather than [PITH_FULL_IMAGE:figures/full_fig_p051_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Synthetic diagnostics. Adaptive TOFU reduces sensitivity to rank choice, the corrected [PITH_FULL_IMAGE:figures/full_fig_p052_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: MNIST product-context diagnostics. The rank behavior is consistent with the constructed [PITH_FULL_IMAGE:figures/full_fig_p053_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Text product-context experiment from four-class 20 Newsgroups. Fixed-rank full-history [PITH_FULL_IMAGE:figures/full_fig_p054_8.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

44 extracted references · 1 canonical work pages

  1. [1]

    Improved algorithms for linear stochastic bandits.Advances in neural information processing systems, 24, 2011

    Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits.Advances in neural information processing systems, 24, 2011

    2011

  2. [2]

    Linearly parameterized bandits.Mathematics of Operations Research, 35(2):395–411, 2010

    Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits.Mathematics of Operations Research, 35(2):395–411, 2010

    2010

  3. [3]

    Cambridge University Press, 2020

    Tor Lattimore and Csaba Szepesvári.Bandit algorithms. Cambridge University Press, 2020

    2020

  4. [4]

    A contextual-bandit approach to personalized news article recommendation

    Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandit approach to personalized news article recommendation. InProceedings of the 19th international conference on World wide web, pages 661–670, 2010. 15

    2010

  5. [5]

    Contextual bandits with linear payoff functions

    Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. InProceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208–214. JMLR Workshop and Conference Proceedings, 2011

    2011

  6. [6]

    Online decision making with high-dimensional covariates

    Hamsa Bastani and Mohsen Bayati. Online decision making with high-dimensional covariates. Operations Research, 68(1):276–294, 2020

    2020

  7. [7]

    Linear bandits with partially observable features.arXiv preprint arXiv:2502.06142, 2025

    Wonyoung Kim, Sungwoo Park, Garud Iyengar, Assaf Zeevi, and Min-hwan Oh. Linear bandits with partially observable features.arXiv preprint arXiv:2502.06142, 2025

    Pith/arXiv arXiv 2025

  8. [8]

    A regret bound for greedy partially observed stochastic contextual bandits

    Hongju Park and Mohamad Kazem Shirani Faradonbeh. A regret bound for greedy partially observed stochastic contextual bandits. InProceedings of the 39th International Conference on Machine Learning, volume 162, pages 1805–1812. PMLR, 2022

    2022

  9. [9]

    Stochastic linear bandits with hidden low rank structure.arXiv preprint arXiv:1901.09490, 2019

    Sahin Lale, Kamyar Azizzadenesheli, Anima Anandkumar, and Babak Hassibi. Stochastic linear bandits with hidden low rank structure.arXiv preprint arXiv:1901.09490, 2019

    Pith/arXiv arXiv 1901

  10. [10]

    Abbasi-Yadkori, D

    Y. Abbasi-Yadkori, D. Pal, and C. Szepesvari. Online-to-confidence-set conversions and application to sparse stochastic bandits. InArtificial Intelligence and Statistics, pages 1–9, 2012

    2012

  11. [11]

    Carpentier and R

    A. Carpentier and R. Munos. Bandit theory meets compressed sensing for high dimensional stochastic linear bandit. InArtificial Intelligence and Statistics, pages 190–198, 2012

    2012

  12. [12]

    Sparse stochastic bandits.arXiv preprint arXiv:1706.01383, 2017

    Joon Kwon, Vianney Perchet, and Claire Vernade. Sparse stochastic bandits.arXiv preprint arXiv:1706.01383, 2017

    Pith/arXiv arXiv 2017

  13. [13]

    Popart: Efficient sparse regression and experimental design for optimal sparse linear bandits.Advances in Neural Information Processing Systems, 35:2102–2114, 2022

    Kyoungseok Jang, Chicheng Zhang, and Kwang-Sung Jun. Popart: Efficient sparse regression and experimental design for optimal sparse linear bandits.Advances in Neural Information Processing Systems, 35:2102–2114, 2022

    2022

  14. [14]

    Bilinear bandits with low-rank structure

    Kwang-Sung Jun, Rebecca Willett, Stephen Wright, and Robert Nowak. Bilinear bandits with low-rank structure. InProceedings of the 36th International Conference on Machine Learning, volume 97 ofProceedings of Machine Learning Research, pages 3163–3172. PMLR, 2019

    2019

  15. [15]

    Low-rank generalized linear bandit problems

    Yangyi Lu, Amirhossein Meisami, and Ambuj Tewari. Low-rank generalized linear bandit problems. InProceedings of the 24th International Conference on Artificial Intelligence and Statistics, volume 130 ofProceedings of Machine Learning Research, pages 460–468. PMLR, 2021

    2021

  16. [16]

    Improved regret analysis for bilinear bandits

    Young-Hwan Jang, Kwang-Sung Jun, and Se-Young Yun. Improved regret analysis for bilinear bandits. InProceedings of the 38th International Conference on Machine Learning, volume 139 ofProceedings of Machine Learning Research, pages 4753–4763. PMLR, 2021

    2021

  17. [17]

    Yang Kang, Cho-Jui Hsieh, and Thomas C. M. Lee. Efficient frameworks for generalized low-rank matrix bandit problems.Advances in Neural Information Processing Systems, 35: 19971–19983, 2022

    2022

  18. [18]

    Spectral bandits for smooth graph functions

    Michal Valko, Rémi Munos, Branislav Kveton, and Tomáš Kocák. Spectral bandits for smooth graph functions. InInternational Conference on Machine Learning, 2014. 16

    2014

  19. [19]

    Baraniuk

    Daniel LeJeune, Gautam Dasarathy, and Richard G. Baraniuk. Thresholding graph bandits with GrAPL. InInternational Conference on Artificial Intelligence and Statistics, 2020

    2020

  20. [20]

    Maximizing and satisficing in multi-armed bandits with graph information

    Parth Thaker, Mohit Malu, Nikhil Rao, and Gautam Dasarathy. Maximizing and satisficing in multi-armed bandits with graph information. InAdvances in Neural Information Processing Systems, 2022

    2022

  21. [21]

    Exact matrix completion via convex optimization

    Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foundations of Computational mathematics, 9(6):717–772, 2009

    2009

  22. [22]

    Robust principal component analysis?Journal of the ACM (JACM), 58(3):1–37, 2011

    Emmanuel J Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis?Journal of the ACM (JACM), 58(3):1–37, 2011

    2011

  23. [23]

    Simplified neuron model as a principal component analyzer.Journal of mathematical biology, 15(3):267–273, 1982

    Erkki Oja. Simplified neuron model as a principal component analyzer.Journal of mathematical biology, 15(3):267–273, 1982

    1982

  24. [24]

    High-dimensional robust subspace tracking under missing data and outliers

    Laura Balzano, Robert Nowak, and Benjamin Recht. High-dimensional robust subspace tracking under missing data and outliers. In2010 Conference Record of the Forty Fourth Asilomar Conference on Signals, Systems and Computers, pages 2087–2091. IEEE, 2010

    2087

  25. [25]

    Petrels: Parallel subspace estimation and tracking by recursive least squares from partial observations.IEEE Transactions on Signal Processing, 61(23):5947–5959, 2013

    Yuejie Chi, Yonina C Eldar, and Robert Calderbank. Petrels: Parallel subspace estimation and tracking by recursive least squares from partial observations.IEEE Transactions on Signal Processing, 61(23):5947–5959, 2013

    2013

  26. [26]

    An exponential convergence rate for subspace estimation from partial observations.arXiv preprint arXiv:1905.13595, 2019

    Yingyu Liang, Zhuoran Xu, and Dale Schuurmans. An exponential convergence rate for subspace estimation from partial observations.arXiv preprint arXiv:1905.13595, 2019

    Pith/arXiv arXiv 1905

  27. [27]

    Thompson sampling for contextual bandits with linear payoffs

    Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. InInternational Conference on Machine Learning, pages 127–135, 2013

    2013

  28. [28]

    Linear Thompson sampling revisited

    Marc Abeille and Alessandro Lazaric. Linear Thompson sampling revisited. InArtificial Intelligence and Statistics, pages 176–184, 2017

    2017

  29. [29]

    Semiparametric contextual bandits

    Akshay Krishnamurthy, Zhiwei Steven Wu, and Vasilis Syrgkanis. Semiparametric contextual bandits. InInternational Conference on Machine Learning, pages 2776–2785, 2018

    2018

  30. [30]

    High-dimensional covariance matrix estimation with missing observations

    Karim Lounici. High-dimensional covariance matrix estimation with missing observations. Bernoulli, 20(3):1029 – 1058, 2014. doi: 10.3150/12-BEJ487. URL https://doi.org/10. 3150/12-BEJ487

    work page doi:10.3150/12-bej487 2014

  31. [31]

    The rotation of eigenvectors by a perturbation

    Chandler Davis and William Morton Kahan. The rotation of eigenvectors by a perturbation. iii.SIAM Journal on Numerical Analysis, 7(1):1–46, 1970

    1970

  32. [32]

    Gradient-based learning applied to document recognition.Proceedings of the IEEE, 86(11):2278–2324, 1998

    Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition.Proceedings of the IEEE, 86(11):2278–2324, 1998

    1998

  33. [33]

    Optical recognition of handwritten digits

    Ethem Alpaydin and Cenk Kaynak. Optical recognition of handwritten digits. UCI Machine Learning Repository, 1998. DOI: 10.24432/C50P49

    doi:10.24432/c50p49 1998

  34. [34]

    Newsweeder: Learning to filter netnews

    Ken Lang. Newsweeder: Learning to filter netnews. InProceedings of the Twelfth International Conference on Machine Learning, pages 331–339. Morgan Kaufmann, 1995. 17

    1995

  35. [35]

    Active learning algorithms for graphical model selection

    Gautam Dasarathy, Aarti Singh, Maria-Florina Balcan, and Jong Hyuk Park. Active learning algorithms for graphical model selection. InArtificial Intelligence and Statistics, 2016

    2016

  36. [36]

    The multi-fidelity multi-armed bandit

    Kirthevasan Kandasamy, Gautam Dasarathy, Barnabás Póczos, and Jeff Schneider. The multi-fidelity multi-armed bandit. InAdvances in Neural Information Processing Systems, 2016

    2016

  37. [37]

    Oliva, Jeff Schneider, and Barnabás Póczos

    Kirthevasan Kandasamy, Gautam Dasarathy, Junier B. Oliva, Jeff Schneider, and Barnabás Póczos. Gaussian process bandit optimisation with multi-fidelity evaluations. InAdvances in Neural Information Processing Systems, 2016

    2016

  38. [38]

    Multi- fidelity Bayesian optimisation with continuous approximations

    Kirthevasan Kandasamy, Gautam Dasarathy, Jeff Schneider, and Barnabás Póczos. Multi- fidelity Bayesian optimisation with continuous approximations. InInternational Conference on Machine Learning, 2017

    2017

  39. [39]

    Oliva, Jeff Schneider, and Barnabás Póczos

    Kirthevasan Kandasamy, Gautam Dasarathy, Junier B. Oliva, Jeff Schneider, and Barnabás Póczos. Multi-fidelity Gaussian process bandit optimisation.Journal of Artificial Intelligence Research, 66:151–196, 2019

    2019

  40. [40]

    Joel A. Tropp. An introduction to matrix concentration inequalities, 2015. URL https: //arxiv.org/abs/1501.01571

    Pith/arXiv arXiv 2015

  41. [41]

    Numerical methods for computing angles between linear subspaces.Mathematics of Computation, 27(123):579–594, 1973

    Åke Björck and Gene H Golub. Numerical methods for computing angles between linear subspaces.Mathematics of Computation, 27(123):579–594, 1973

    1973

  42. [42]

    Academic Press, 1990

    Gilbert W Stewart and Ji-guang Sun.Matrix Perturbation Theory. Academic Press, 1990

    1990

  43. [43]

    Horn and Charles R

    Roger A. Horn and Charles R. Johnson.Matrix Analysis. Cambridge University Press, 2 edition, 2012. 18 Stochastic Linear Bandits with Partially Observed Actions: Appendices A Technical Comparison with PSLB and the Role of Epoch-wise Freezing The closest predecessor to our work is the projected stochastic linear bandit framework of [9]. PSLB estimates a low...

    2012

  44. [44]

    context-limited

    In this situation, notice that Lemma 8 gives us min O ∥ˆUtO−U∥2≤ √ 2∥ˆPt−P∥2≤ √ 2≤ϵt. Case 2:ϵt< √ 2 Here, Case 2 of the preceding proof gives∥ˆPt−P∥2≤(8/Csub)ϵt. This, along with Lemma 8, implies that min O ∥ˆUtO−U∥2≤(8 √ 2/Csub)ϵt≤ϵt, where we used the fact thatCsub = 12≥8 √ 2. D Imputation Error: Proof of Lemma 2 In Section C, we showed that the projec...

    arXiv 2021