Cover Image

A Simple Geometric Proof of the Optimality of the Sequential Probability Ratio Test for Symmetric Bernoulli Hypotheses

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Pabbaraju, Chirag, Valiant, Gregory, Verma, Rishi
Format:	Preprint
Published:	2025
Subjects:	Statistics Theory Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Testing with Non-identically Distributed Samples
by: Garg, Shivam, et al.
Published: (2023)

Attainability of Two-Point Testing Rates for Finite-Sample Location Estimation
by: Compton, Spencer, et al.
Published: (2025)

A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities
by: Rivkin, Joey, et al.
Published: (2024)

Asymptotically Optimal Sequential Testing with Heterogeneous LLMs
by: Li, Guokai, et al.
Published: (2026)

Embedding Probability Distributions into Low Dimensional $\ell_1$: Tree Ising Models via Truncated Metrics
by: Charikar, Moses, et al.
Published: (2023)

On The MCMC Performance In Bernoulli Group Testing And The Random Max Set-Cover Problem
by: Lovig, Maxwell, et al.
Published: (2024)

On the Statistical Complexity of Sample Amplification
by: Axelrod, Brian, et al.
Published: (2022)

New and Improved Bounds for Markov Paging
by: Pabbaraju, Chirag, et al.
Published: (2025)

High Probability Latency Sequential Change Detection over an Unknown Finite Horizon
by: Huang, Yu-Han, et al.
Published: (2024)

A Characterization of List Regression
by: Pabbaraju, Chirag, et al.
Published: (2024)

Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan
by: Gomez-Leos, Alejandro, et al.
Published: (2024)

Probability Tools for Sequential Random Projection
by: Li, Yingru
Published: (2024)

Transfer Learning Beyond Bounded Density Ratios
by: Kalavasis, Alkis, et al.
Published: (2024)

Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel
by: Gupta, Shivam, et al.
Published: (2024)

Learning with Monotone Adversarial Corruptions
by: Larsen, Kasper Green, et al.
Published: (2026)

Lower Bounds for Greedy Teaching Set Constructions
by: Compton, Spencer, et al.
Published: (2025)

The Power of Two Matrices in Spectral Algorithms for Community Recovery
by: Dhara, Souvik, et al.
Published: (2022)

Minimax optimal testing by classification
by: Gerber, Patrik Róbert, et al.
Published: (2023)

Accurate Analysis of Sparse Random Projections
by: Skórski, Maciej
Published: (2024)

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
by: Garg, Sumegha, et al.
Published: (2026)

Almost-Optimal Local-Search Methods for Sparse Tensor PCA
by: Lovig, Max, et al.
Published: (2025)

Sampling and Identity-Testing Without Approximate Tensorization of Entropy
by: Gay, William, et al.
Published: (2025)

An Optimal Algorithm for Stochastic Vertex Cover
by: Brand, Jan van den, et al.
Published: (2026)

Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussians
by: Novikov, Gleb
Published: (2025)

Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
by: Yu, Xifan, et al.
Published: (2024)

Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination
by: Diakonikolas, Ilias, et al.
Published: (2024)

Robust Regression with Adaptive Contamination in Response: Optimal Rates and Computational Barriers
by: Diakonikolas, Ilias, et al.
Published: (2026)

Pareto-optimal Non-uniform Language Generation
by: Charikar, Moses, et al.
Published: (2025)

Exploring Facets of Language Generation in the Limit
by: Charikar, Moses, et al.
Published: (2024)

Optimal Robust Estimation under Local and Global Corruptions: Stronger Adversary and Smaller Error
by: Pittas, Thanasis, et al.
Published: (2024)

A Distribution Testing Approach to Clustering Distributions
by: Kumar, Gunjan, et al.
Published: (2025)

Testing Convex Truncation
by: De, Anindya, et al.
Published: (2023)

Optimal Rates for Differentially Private Hypothesis Testing with E-values
by: Jacobsen, Ben, et al.
Published: (2026)

Universal entrywise eigenvector fluctuations in delocalized spiked matrix models and asymptotics of rounded spectral algorithms
by: Chen, Shujing, et al.
Published: (2025)

The Entropy and Crossentropy of Generalized Mallows Models
by: Meilă, Marina
Published: (2025)

Random Matrices, Intrinsic Freeness, and Sharp Non-Asymptotic Inequalities
by: Bandeira, Afonso S.
Published: (2025)

Detecting Correlation Efficiently in Stochastic Block Models: Breaking Otter's Threshold in the Entire Supercritical Regime
by: Chen, Guanyi, et al.
Published: (2025)

On the Low-Temperature MCMC threshold: the cases of sparse tensor PCA, sparse regression, and a geometric rule
by: Chen, Zongchen, et al.
Published: (2024)

Random Multi-Type Spanning Forests for Synchronization on Sparse Graphs
by: Jaquard, Hugo, et al.
Published: (2024)

Finding planted cliques using gradient descent
by: Gheissari, Reza, et al.
Published: (2023)