This paper studies the Bayesian regret of the Thompson Sampling algorithm for bandit problems, building on the information-theoretic framework introduced by Russo and Van Roy [1]. Specifically, it extends the rate-distortion analysis of Dong and Van Roy [2], which provides near-optimal bounds for linear bandits. A key limitation of these results is the assumption of a finite action space. We address this by extending the analysis to settings with infinite and continuous action spaces. Additionally, we specialize our results to bandit problems with expected rewards that are Lipschitz continuous with respect to the action space, deriving a regret bound that explicitly accounts for the complexity of the action space.

This paper studies the Bayesian regret of a variant of the Thompson-Sampling algorithm for bandit problems. It builds upon the information-theoretic framework of [1] and, more specifically, on the rate-distortion analysis from [2], where they proved a bound with regret rate of O(d T log(T))for the d-dimensional linear bandit setting. We focus on bandit problems with a metric action space and, using a chaining argument, we establish new bounds that depend on the metric entropy of the action space for a variant of Thompson-Sampling. Under suitable continuity assumption of the rewards, our bound offers a tight rate of O(d√T) for d-dimensional linear bandit problems.

Hyperspherical Prototypical Learning (HPL) is a supervised approach to representation learning that designs class prototypes on the unit hypersphere. The prototypes bias the representations to class separation in a scale invariant and known geometry. Previous approaches to HPL have either of the following shortcomings: (i) they follow an unprincipled optimisation procedure; or (ii) they are theoretically sound, but are constrained to only one possible latent dimension. In this paper, we address both shortcomings. To address (i), we present a principled optimisation procedure whose solution we show is optimal. To address (ii), we construct well-separated prototypes in a wide range of dimensions using linear block codes. Additionally, we give a full characterisation of the optimal prototype placement in terms of achievable and converse bounds, showing that our proposed methods are near-optimal.

Hyperspherical Prototypical Learning (HPL) is a supervised approach to representation learning that designs class prototypes on the unit hypersphere. The prototypes bias the representations to class separation in a scale invariant and known geometry. Previous approaches to HPL have either of the following shortcomings: (i) they follow an unprincipled optimisation procedure; or (ii) they are theoretically sound, but are constrained to only one possible latent dimension. In this paper, we address both shortcomings. To address (i), we present a principled optimisation procedure whose solution we show is optimal. To address (ii), we construct well-separated prototypes in a wide range of dimensions using linear block codes. Additionally, we give a full characterisation of the optimal prototype placement in terms of achievable and converse bounds, showing that our proposed methods are near-optimal.

Hyperspherical Prototypical Learning (HPL) is a supervised approach to representation learning that designs class prototypes on the unit hypersphere. The prototypes bias the representations to class separation in a scale invariant and known geometry. Previous approaches to HPL have either of the following shortcomings: (i) they follow an unprincipled optimisation procedure; or (ii) they are theoretically sound, but are constrained to only one possible latent dimension. In this paper, we address both shortcomings. To address (i), we present a principled optimisation procedure whose solution we show is optimal. To address (ii), we construct well-separated prototypes in a wide range of dimensions using linear block codes. Additionally, we give a full characterisation of the optimal prototype placement in terms of achievable and converse bounds, showing that our proposed methods are near-optimal. GitHub: martinlindstrom/coding theoretic hpl

This paper studies the truncation method from Alquier [1] to derive high-probability PAC-Bayes bounds for unbounded losses with heavy tails. Assuming that the p-th moment is bounded, the resulting bounds interpolate between a slow rate 1/√n when p=2, and a fast rate 1/n when p→∞ and the loss is essentially bounded. Moreover, the paper derives a high-probability PAC-Bayes bound for losses with a bounded variance. This bound has an exponentially better dependence on the confidence parameter and the dependency measure than previous bounds in the literature. Finally, the paper extends all results to guarantees in expectation and single-draw PAC-Bayes. In order to so, it obtains analogues of the PAC-Bayes fast rate bound for bounded losses from [2] in these settings. The full version of the paper can be found in https://arxiv.org/abs/2403.16681.

In this thesis, we investigate the in-distribution generalization of machine learning algorithms, focusing on establishing rigorous upper bounds on the generalization error. We depart from traditional complexity-based approaches by introducing and analyzing information-theoretic bounds that quantify the dependence between a learning algorithm and the training data.

We consider two categories of generalization guarantees:

• Guarantees in expectation. These bounds measure performance in the average case. Here, the dependence between the algorithm and the data is often captured by the mutual information or other information measures based on ƒ-divergences. While these measures offer an intuitive interpretation, they might overlook the geometry of the algorithm's hypothesis class. To address this limitation, we introduce bounds using the Wasserstein distance, which incorporates geometric considerations at the cost of being mathematically more involved. Furthermore, we propose a structured, systematic method to derive bounds capturing the dependence between the algorithm and an individual datum, and between the algorithm and subsets of the training data, conditioned on knowing the rest of the data. These types of bounds provide deeper insights, as we demonstrate by applying them to derive generalization error bounds for the stochastic gradient Langevin dynamics algorithm.      
• PAC-Bayesian guarantees. These bounds measure the performance level with high probability. Here, the dependence between the algorithm and the data is often measured by the relative entropy. We establish connections between the Seeger--Langford and Catoni's bounds, revealing that that the former is optimized by the Gibbs posterior. Additionally, we introduce novel, tighter bounds for various types of loss functions, including those with a bounded range, cumulant generating function, moment, or variance. To achieve this, we introduce a new technique to optimize parameters in probabilistic statements.

We also study the limitations of these approaches. We present a counter-example where most of the existing (relative entropy-based) information-theoretic bounds fail, and where traditional approaches do not. Finally, we explore the relationship between privacy and generalization. We show that algorithms with a bounded maximal leakage generalize. Moreover, for discrete data, we derive new bounds for differentially private algorithms that vanish as the number of samples increases, thus guaranteeing their generalization even with a constant privacy parameter. This is in contrast with previous bounds in the literature, that require the privacy parameter to decrease with the number of samples to ensure generalization.

I denna avhandling undersöker vi maskininlärningsalgoritmers generaliseringsförmåga för likafördelad data, med fokus på att upprätta stränga övre gränser för generaliseringsfelet. Vi avviker från traditionella komplexitetsbaserade metoder genom att introducera och analysera informationsteoretiska gränser som kvantifierar beroendet mellan en inlärningsalgoritm och träningsdata.

Vi studerar två kategorier av generaliseringsgarantier:

• Väntevärdegarantier. Dessa gränser mäter prestanda i genomsnitt. I detta fall fångas beroendet mellan algoritmen och data ofta av ömsesidig information eller andra informationsmått baserade på ƒ-divergenser. Trots att dessa mått erbjuder en intuitiv tolkning, kan de förbise geometrin hos algoritmens hypotesklass. För att hantera denna begränsning introducerar vi gränser som använder Wassersteinavstånd, vilket innehåller geometriska överväganden på bekostnad av att vara mer matematiskt invecklat. Dessutom föreslår vi en strukturerad, systematisk metod för att härleda gränser som fångar beroendet mellan algoritmen och en enskild datapunkt, samt mellan algoritmen och delmängder av träningsdata, under förutsättning att resten av datan är känd. Dessa typer av gränser ger djupare insikter, vilket vi demonstrerar genom att tillämpa dem för att härleda generaliseringsgarantier för algoritmen stokastisk gradient Langevindynamik.   
• PAC-Bayesiska garantier. Dessa gränser mäter prestandanivån med hög sannolikhet. I detta fall fångas beroendet mellan algoritmen och data ofta av relativ entropi. Vi härleder samband mellan Seeger--Langfords- och Catonis gränser, vilket avslöjar att den förra optimeras av Gibbsfördelningen. Dessutom introducerar vi nya, starkare gränser för olika typer av kostnadsfunktioner, inklusive de med begränsad värdemängd, momentgenererande funktion, moment, eller varians. För att uppnå detta introducerar vi en ny teknik för att optimera parametrar i sannolikhetsuttryck.

Vi studerar också begränsningarna för dessa metoder. Vi presenterar ett motexempel där de flesta av de existerande (relativ entropibaserade) informationsteoretiska gränserna misslyckas, och där traditionella metoder fungerar. Slutligen utforskar vi sambandet mellan dataintegritet och generaliseringsförmåga. Vi visar att algoritmer med ett begränsad maximalt läckage generaliserar. Dessutom härleder vi för diskreta data nya gränser för algoritmer med differentiellt dataintegritet, som försvinner när antal sampel ökar, vilket garanterar deras generaliseringsförmåga även med en konstant dataintegritetsparameter. Detta står i kontrast till tidigare gränser i litteraturen, som kräver att dataintegritetsparametern minskar med antalet sampel för att säkerställa generaliseringsförmåga.

In this paper, we present new high-probability PAC-Bayes bounds for different types of losses. Firstly, for losses with a bounded range, we recover a strengthened version of Catoni's bound that holds uniformly for all parameter values. This leads to new fast-rate and mixed-rate bounds that are interpretable and tighter than previous bounds in the literature. In particular, the fast-rate bound is equivalent to the Seeger-Langford bound. Secondly, for losses with more general tail behaviors, we introduce two new parameter-free bounds: a PAC-Bayes Chernoff analogue when the loss' cumulative generating function is bounded, and a bound when the loss' second moment is bounded. These two bounds are obtained using a new technique based on a discretization of the space of possible events for the "in probability" parameter optimization problem. This technique is both simpler and more general than previous approaches optimizing over a grid on the parameters' space. Finally, using a simple technique that is applicable to any existing bound, we extend all previous results to anytime-valid bounds.

In this article, we study the fundamental limits in the design of fair and/or private representations achieving perfect demographic parity and/or perfect privacy through the lens of information theory. More precisely, given some useful data X that we wish to employ to solve a task T, we consider the design of a representation Y that has no information of some sensitive attribute or secret s, that is, such that I(Y;S)=0. We consider two scenarios. First, we consider a design desiderata where we want to maximize the information I(Y;T) that the representation contains about the task, while constraining the level of compression (or encoding rate), that is, ensuring that I(Y;X)≤q r. Second, inspired by the Conditional Fairness Bottleneck problem, we consider a design desiderata where we want to maximize the information I(Y, Tvert S) that the representation contains about the task which is not shared by the sensitive attribute or secret, while constraining the amount of irrelevant information, that is, ensuring that I(Y;Xvert T, S)≤q r. In both cases, we employ extended versions of the Functional Representation Lemma and the Strong Functional Representation Lemma and study the tightness of the obtained bounds. Every result here can also be interpreted as a coding with perfect privacy problem by considering the sensitive attribute as a secret.

To date, no “information-theoretic” frameworks for reasoning about generalization error have been shown to establish minimax rates for gradient descent in the setting of stochastic convex optimization. In this work, we consider the prospect of establishing such rates via several existing information-theoretic frameworks: input-output mutual information bounds, conditional mutual information bounds and variants, PAC-Bayes bounds, and recent conditional variants thereof. We prove that none of these bounds are able to establish minimax rates. We then consider a common tactic employed in studying gradient methods, whereby the final iterate is corrupted by Gaussian noise, producing a noisy “surrogate” algorithm. We prove that minimax rates cannot be established via the analysis of such surrogates. Our results suggest that new ideas are required to analyze gradient descent using information-theoretic techniques.