FUNDAMENTAL PERFORMANCE LIMITS OF STATISTICAL PROBLMES: FROM HYPOTHESIS TESTING TO THE LOTTERY TICKETS HYPOTHESIS

Abstract

Understanding the fundamental limits of various statistical problems is of paramount importance. As machine learning continues to evolve, it is critical to understand fundamental limits in the context of new problems. In this thesis, we investigate fundamental performance limits in three problems that have emerged with the rise of machine learning. These problems are sequential composite hypothesis testing, sequential adversarial hypothesis testing game, and explaining the mask-reconstruction-based self-supervised learning using the lottery ticket hypothesis. For sequential composite hypothesis testing, we obtain its first-order and second-order asymptotics of type-I and type-II error probabilities under probabilistic constraints. In sequential adversarial hypothesis testing game, we evaluate the asymptotic Nash equilibrium between the decision maker and the adversary and identify the payoff at this equilibrium. Finally, by leveraging the lottery ticket hypothesis, we theoretically explain the effectiveness of feature learning in mask-reconstruction-based self-supervised learning and derive its performance bound on downstream classification tasks.