mlsanityData to 7 Oct 2026

Bandit Phase Retrieval

arXiv 2106.01660 ↗First posted 3 Jun 2021stat.ML cs.LG math.STcited by 12

Not on the map. Why?

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.

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

Builds on

14 of 27 references.

References · 14

  1. 2014Learning to Optimize via Information-Directed Samplingcited by 168
  2. 2014Phase Retrieval via Wirtinger Flow: Theory and Algorithmscited by 123
  3. 2016A Geometric Analysis of Phase Retrievalcited by 92
  4. 2018Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrievalcited by 71
  5. 2019Bilinear Bandits with Low-rank Structurecited by 54
  6. 2015Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systemscited by 50
  7. 2020Low-Rank Generalized Linear Bandit Problemscited by 48
  8. 2020Information Directed Sampling for Linear Partial Monitoringcited by 39
  9. 2015Optimal Rates of Convergence for Noisy Sparse Phase Retrieval via Thresholded Wirtinger Flowcited by 23
  10. 2016Stochastic Rank-1 Banditscited by 23
  11. 2019Solving Bernoulli Rank-One Bandits with Unimodal Thompson Samplingcited by 23
  12. 2017Bernoulli Rank-1 Bandits for Click Feedbackcited by 11
2 more
  1. 2019Bandit Principal Component Analysiscited by 8
  2. 2021A Bit Better? Quantifying Information for Bandit Learningcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 2; 2023: 5; 2024: 1; 2025: 2; 2026: 1.

12 papers.

  1. 2022Nearly Minimax Algorithms for Linear Bandits with Shared Representationcited by 16
  2. 2021Optimal Gradient-based Algorithms for Non-concave Bandit Optimizationcited by 15
  3. 2023Statistical Complexity and Optimal Algorithms for Non-linear Ridge Banditscited by 7
  4. 2023Multi-task Representation Learning for Pure Exploration in Linear Banditscited by 6
  5. 2022Gaussian Imagination in Bandit Learningcited by 5
  6. 2023Context-lumpable stochastic banditscited by 3
  7. 2023Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithmscited by 2
  8. 2024Robust Gradient Descent for Phase Retrievalcited by 2
  9. 2025Evolution of Information in Interactive Decision Making: A Case Study for Multi-Armed Banditscited by 2
  10. 2026Interactive Learning of Single-Index Models via Stochastic Gradient Descentcited by 1
  11. 2023Reward Learning as Doubly Nonparametric Bandits: Optimal Design and Scaling Lawscited by 0
  12. 2025Physics-Informed Parametric Bandits for Beam Alignment in mmWave Communicationscited by 0