# Bandit Phase Retrieval

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 27 references that are in the map.
- First posted on arXiv 3 Jun 2021.

## Builds on (most cited first, 14 of 14)

- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014)
- [A Geometric Analysis of Phase Retrieval](https://mlsanity.com/paper/1602.06664/) (2016)
- [Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval](https://mlsanity.com/paper/1803.07726/) (2018)
- [Bilinear Bandits with Low-rank Structure](https://mlsanity.com/paper/1901.02470/) (2019)
- [Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems](https://mlsanity.com/paper/1505.05114/) (2015)
- [Low-Rank Generalized Linear Bandit Problems](https://mlsanity.com/paper/2006.02948/) (2020)
- [Information Directed Sampling for Linear Partial Monitoring](https://mlsanity.com/paper/2002.11182/) (2020)
- [Optimal Rates of Convergence for Noisy Sparse Phase Retrieval via Thresholded Wirtinger Flow](https://mlsanity.com/paper/1506.03382/) (2015)
- [Stochastic Rank-1 Bandits](https://mlsanity.com/paper/1608.03023/) (2016)
- [Solving Bernoulli Rank-One Bandits with Unimodal Thompson Sampling](https://mlsanity.com/paper/1912.03074/) (2019)
- [Bernoulli Rank-1 Bandits for Click Feedback](https://mlsanity.com/paper/1703.06513/) (2017)
- [Bandit Principal Component Analysis](https://mlsanity.com/paper/1902.03035/) (2019)
- [A Bit Better? Quantifying Information for Bandit Learning](https://mlsanity.com/paper/2102.09488/) (2021)

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

- [Nearly Minimax Algorithms for Linear Bandits with Shared Representation](https://mlsanity.com/paper/2203.15664/) (2022)
- [Optimal Gradient-based Algorithms for Non-concave Bandit Optimization](https://mlsanity.com/paper/2107.04518/) (2021)
- [Statistical Complexity and Optimal Algorithms for Non-linear Ridge Bandits](https://mlsanity.com/paper/2302.06025/) (2023)
- [Multi-task Representation Learning for Pure Exploration in Linear Bandits](https://mlsanity.com/paper/2302.04441/) (2023)
- [Gaussian Imagination in Bandit Learning](https://mlsanity.com/paper/2201.01902/) (2022)
- [Context-lumpable stochastic bandits](https://mlsanity.com/paper/2306.13053/) (2023)
- [Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms](https://mlsanity.com/paper/2306.12383/) (2023)
- [Robust Gradient Descent for Phase Retrieval](https://mlsanity.com/paper/2410.10623/) (2024)
- [Evolution of Information in Interactive Decision Making: A Case Study for Multi-Armed Bandits](https://mlsanity.com/paper/2503.00273/) (2025)
- [Interactive Learning of Single-Index Models via Stochastic Gradient Descent](https://mlsanity.com/paper/2602.17876/) (2026)
- [Reward Learning as Doubly Nonparametric Bandits: Optimal Design and Scaling Laws](https://mlsanity.com/paper/2302.12349/) (2023)
- [Physics-Informed Parametric Bandits for Beam Alignment in mmWave Communications](https://mlsanity.com/paper/2510.18299/) (2025)

## Abstract (arXiv)

We study a bandit version of phase retrieval where the learner chooses actions (At)t=1n in the d-dimensional unit ball and the expected reward is langle At, θ_starrangle2 where θ_star ∈ mathbb Rd is an unknown parameter vector. We prove that the minimax cumulative regret in this problem is smashtilde Theta(d √n), which improves on the best known bounds by a factor of smash√d. We also show that the minimax simple regret is smashtilde Theta(d / √n) and that this is only achievable by an adaptive algorithm. Our analysis shows that an apparently convincing heuristic for guessing lower bounds can be misleading and that uniform bounds on the information ratio for information-directed sampling are not sufficient for optimal regret.