# Bandit Principal Component Analysis

arXiv: https://arxiv.org/abs/1902.03035 · HTML: https://mlsanity.com/paper/1902.03035/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Feb 2019.

## Built on by (most cited first, 8 of 8)

- [Optimal Gradient-based Algorithms for Non-concave Bandit Optimization](https://mlsanity.com/paper/2107.04518/) (2021)
- [Bandit Phase Retrieval](https://mlsanity.com/paper/2106.01660/) (2021)
- [Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Bandits](https://mlsanity.com/paper/2402.11156/) (2024)
- [Online Self-Concordant and Relatively Smooth Minimization, With Applications to Online Portfolio Selection and Learning Quantum States](https://mlsanity.com/paper/2210.00997/) (2022)
- [Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms](https://mlsanity.com/paper/2306.12383/) (2023)
- [Faster Stochastic First-Order Method for Maximum-Likelihood Quantum State Tomography](https://mlsanity.com/paper/2211.12880/) (2022)
- [Optimal Bound for PCA with Outliers using Higher-Degree Voronoi Diagrams](https://mlsanity.com/paper/2408.06867/) (2024)
- [Physics-Informed Parametric Bandits for Beam Alignment in mmWave Communications](https://mlsanity.com/paper/2510.18299/) (2025)

## Abstract (arXiv)

We consider a partial-feedback variant of the well-studied online PCA problem where a learner attempts to predict a sequence of d-dimensional vectors in terms of a quadratic loss, while only having limited feedback about the environment's choices. We focus on a natural notion of bandit feedback where the learner only observes the loss associated with its own prediction. Based on the classical observation that this decision-making problem can be lifted to the space of density matrices, we propose an algorithm that is shown to achieve a regret of O(d3/2√T) after T rounds in the worst case. We also prove data-dependent bounds that improve on the basic result when the loss matrices of the environment have bounded rank or the loss of the best action is bounded. One version of our algorithm runs in O(d) time per trial which massively improves over every previously known online PCA method. We complement these results by a lower bound of Omega(d√T).