Open Collections

Sanches Portella, Victor

University of British Columbia

In this thesis, we describe new results on three problems in learning theory and probability theory: private estimation of Gaussian covariance matrices, prediction with experts’ advice, and the expected norm of martingales. Interestingly, in all of them one of the key ingredients is the use of analytical tools in mathematics. Estimation of the covariance matrix of a Gaussian distribution from samples is a classical problem in statistics that has been thoroughly studied in the literature. Recently researchers proposed the model of differential privacy, a mathematical framework to provide formal guarantees on the amount of sensitive information leaked by algorithms. This compelled researchers to revisit classical problems such as covariance matrix estimation to better understand the limits of statistical estimation under differential privacy. In this thesis we provide tight lower bounds on the accuracy of estimation of Gaussian covariance matrices under the broadest regime of parameters compared to previously known lower bounds. The framework of prediction with experts’ advice is a theoretical model where a player and an adversary play a game with multiple rounds. At each round, the player selects one of multiple experts whose advice to follow while the adversary decides on the cost of following the advice of each expert. In this thesis, we study a continuous-time model of the experts’ problem and provide several results in this setting—that often translate to the discrete problem—with a focus on anytime strategies, that is, those that do not require knowledge on the length of the game. We describe new anytime algorithms with best-known guarantees against the top-quantile of experts in hindsight. Moreover, we show an anytime strategy in continuous time whose guarantees against independent experts match the guarantees of optimal algorithms in the fixed-time setting. Finally, motivated by our investigations of the continuous-time experts’ problem, we study the problem of bounding the infinity norm of high-dimensional martingales under a large class of stopping times. We show asymptotically tight upper and lower bounds to the expected norm of range of continuous and discrete time martingales, generalizing results known for one dimensional martingales.

Text

2024-08-29

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/89084

Computer Science

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/