A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits

Summary

The paper derives a new time-independent inequality for likelihood ratios in the Generalized Linear Model. The proof is based on a PAC-Bayesian approach with a well-chosen prior. The result is applied to GLM bandit models, improving a variant of GLM-UCB. The resulting regret bound removes a exponential dependency in the norm of the unknown parameter. Several examples of GLM are discussed, and minimal numerical experiments are reported. The comparison with OFULLog+ is convincingly exposed, both in theory and in practice.

Strengths

Overall, I consider that the submission is technically sound, somewhat incremental, but will be of interest to the community.

Weaknesses

The submission is correctly written, but with a number of clumsinesses (some are listed below). The main text contains not much more than the statement of the results and the (unsurprising) description of GLM-UCB+, while the supplementary material is written a collection of appendices that are not very well presented. For example, the first appendix is called "Missing Results", which is pretty unspecific. I did not check all the details, but the main lines look correct. l.69 undefined notation \mathcal{B}^d(1) l.77 give a reference l.80 could you precise what is R_\mu in those examples? l.95 the sentence is grammatically wrong, something is missing Thm. 3.1: replace "where" by "for the choice" l.129 it is not the log-likelihood but the likelihood l.583 is it not possible to suggest a proof instead of a reference to "WoframAlpha" (to a plot?)

Questions

How smaller can \beta_t(\delta) be for a confidence region valid only for a given t>0 (instead of all t>0)? This might be worth writing in the paper

Rating

6

Confidence

4

Soundness

4

Presentation

3

Contribution

3

Limitations

This section does not really seem relevant to this mostly theoretical submission

Summary

Confidence intervals for GLMs using a PAC-Bayes approach.

Strengths

Confidence sequences and bandit algorithms for GLMs are a hot topic, and the authors contribution to that topic is solid, both because of the strength of the result itself, and because the proof itself is very simple and easy to verify---something that cannot be said about some of the previous work on the topic.

Weaknesses

The paper is written in a style that might be described as "being written for the reviewers". It contains misleading and inaccurate claims which are meant to, presumably, impress the reader with the quality of the results. I give some examples shortly. Its unfortunate, because the ideas in the paper are good, and if only the authors had simply written about their work in a neutral, descriptive manner, I would absolutely recommend that the paper is accepted. However, I do not believe the overclaiming to be some sort of an accident---which if it were, the authors might fix upon my pointing it out---and so without any system for "revise and resubmit", must recommend rejection. Some examples of problematic claims (emphasis mine in all quotes): 1) Lines 1-2, the authors claim that "[...] for any generalised linear models (GLMs) that is guaranteed to be convex and numerically tight". To my understanding, the authors have no guarantee that their result is numerically tight for every GLM, and thus the first sentence of the abstract is false (is there even a guarantee in the paper that there exists a single GLM for which it is numerically tight?). 2) Line 53, "Our main novely lies in __cleverly__ using [...]"; whether the approach is clever or not is perhaps something for readers to judge, not for the authors to proclaim. 3) Line 107, "we completely remove the poly(S)-dependency from the radius, resolving one of the __open problems__ posited by Lee et al. (__2024__)." An open problem is an well-known unsolved problem in a field (that is, a problem that numerous other researchers have attempted and failed to solve). Your "open problem" is not that. Rather, it is a single sentence in the middle of a paper published at a conference that took place less than 3 weeks before this paper was submitted that simply states that the authors leave it for future work. 4) Line 111-112 authors claim that "perhaps more importantly, [ellipsoidal confidence sequences allow] one to equivalently rewrite the optimistic optimization in the UCB algorithm as a closed-form bonus-based UCB algorithm". Is this true? The claim appears to be that, if $\mathcal{X}$ is a subset of the unit ball and $\Theta$ is an ellipsoid, then the quantity $b(\Theta) = \\max_{x \in \mathcal{X}} \max_{\theta \in \Theta} \langle x, \theta \rangle$ has a closed form expression. Could the authors state the closed form expression they have in mind for, say, $\mathcal{X}$ being an irregular polytope with $2^d$-many vertices? And if the resulting expression requires $O(2^d)$ time to evaluate... then the statement is trivial, and ellipsoidal form of the confidence sequences is unimportant. (and of course, fit a spline to those 2^d vertices, and now you cannot even write the solution as a sum over the vertices!). 5) Lines 307-308: in the conclusion, the authors state that "[their algorithm] is numerically verified to be the best performing algorithm." The authors compared against __one baseline__ on a __single experiment__ varying only __one experimental parameter__ between __two values__, and the experiment was __two dimensional__. *Really?* Other than that, section 3.3 seems like it could contain interesting insight, but I'm worried that the way it is written, the only persons that might be able to understand it are either the authors themselves, or someone that has spent just as much time poring over the paper as the authors have done. I would suggest that the authors either expand on it and explain it better, or cut it. Some minor typos: - Line 312-313 you talk of "Bayesian randomized (exploration) algorithms for GLM bandits", but then cite 5 papers for these algorithms, out of which the four I am familiar with are frequentist algorithms, not Bayesian. - Line 95-97, second half of sentence seems to be missing - Line 129, the definition looks like the likelihood ratio, not the log-likelihood ratio as claimed - Theorem 3.2, second line - Line 82, the set in probability is wrong - Line 75 rewards should be in filtration

Questions

See weaknesses section.

Rating

3

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

.

Summary

This paper proposes Likelihood ratio based confidence sequences for generalized linear inference, who's width only depends logarithmically on $S$, the bound on norm of the parameter vector. This is achieved by utilizing a pac-bayesian change of measure inequality, with the prior and posterior distributions chosen very carefully. Tightness of the bounds are compared with some prior work and a small numerical experiment is provided to demonstrate potential benefits of the confidence bounds, for the application of logistic bandits.

Strengths

- Key contribution is reducing the $\mathrm{poly}(S)$ dependency of the width of the confidence sets to $\log S$. Practitioners typically do not use state-of-the-art CS prescribed by theory because 1) they are tough to compute 2) depend on unknown parameter. This paper takes a step towards mending this gap by addressing the second issue. Since dependence of the width on $S$ is logarithmically, then the practitioner can choose a conservatively large upper bound on $||\theta_\star||$ and not suffer from loose/uninformative CS. - The work benefits from versatility of LR-based CS and automatically gives results that are applicable to multiple data/noise models. - Gives convex CS for logistic bandits that have rate optimal dependence on $\kappa$ parameter. I might be wrong, but as far as I know, prior work with such dependency on $\kappa$ resort on non-convex sets [Faury 2022]. *I am not aware of the latest results, particularly [Lee 2024].* - The proof is light and combines simple ideas from not-so-connected areas. Compared to prior work on parallel topics (on GLM, logistic, or poisson models), this seems like a more elegant approach to prove anytime validity of confidence sequences.

Weaknesses

I think improving dependency on $S$ gains significant relevance, once it yields a practical algorithm. If there is no computationally efficient/stable way of calculating the confidence sets, then the relevance of the results is limited to a subset of the bandit theory community. Maximising the UCB on the proposed sets (Thm 3.1 and Thm 3.2) does not seem to be a computationally feasible task, particularly for higher dimensions. Further, I'm afraid that practical relaxations/approximations, would blow up the width, and loosing the current theoretical edge. - The ellipsoid sets are proposed as a easy-to-implement alternative (which actually might not be the case, due to the hessian in the norm). But it is not clear to me if they are similarly tight. Depending on the parameter $R_s$, these sets may again scale with $\mathrm{poly}(S)$. - While the paper makes a valuable theoretical contribution, I think it would need more experiments to appeal to a broader community. For instance, a proper benchmarking of the CS against practically common choices (vanilla GP-based CS based on a very loose Linear regression model that uses a sub-Gaussian noise with a large variance) and showing that the statistical gains are worth the computational effort by reporting the regret, and the computational efficiency (e.g. number of flops). - Experiments do lack comparison with relevant baselines and are only in the logistic case. In particular, Emmenegger 2023 and Faury 2022 are two algorithms that should be compared to. IIRC, Emmenegger 2023 does not work well for logistic bandits, so this would help strengthen the message of the paper. However, Faury 2022 seems to make a strong case on the joint computational and statistical efficiency of their algorithm (for logistic bandits). This is not a weakness, but I should mention that I am not personally aware of the common rates and parameter dependencies in LR-based confidence sequences. Therefore, I *could not* verify the dependence of the width on certain parameters, so I don't know if everything is optimal, or we are sacrificing something else on the path to $\log S$.

Questions

### Questions: 1) For equation (3), I did not understand why this is a batched estimator and not a sequential one. Can you clarify your terminology of batched vs sequential estimator? 2) Is there theoretical benefit/necessity to solving the constrained problem rather than regularizing? I realize that for validity of the CS, we require $\hat \theta_t$ to also lie within $\Theta$, but is there any other reason why we consider the MLE rather than generalized ridge loss? Asking because from a practical perspective, the latter is better/more stable. 3) What is the dependency of Theorem 3.2 on $S$? Mainly, do the ellipsoid sets blow up for logistic bandits? 4) Can you comment on the computational complexity of calculating the CS of Theorem 3.1 and Theorem 3.2? My feeling is that both are computationally tough to calculated (e.g. due to the lipschitz constant, or the matrix norm wrt the hessian matrix). 5) Do you see a clear kernelized extension? In particular, is there a choice of prior-posterior for which the KL divergence is bounded and allows for a similar rate? 6) Is Theorem 4.1 minimax optimal, e.g. wrt the lower-bound of Abeille 2021? 7) In Fig 1-(c), is the logistic CS is automatically an ellipsoid, or is it just resembling one? 8) Are you using the theoretical $\beta_t(\delta)$ for Fig (1-a) and (1-b)? _____ ### Small typos & Suggestions - [Lines 57, 67, 69] space before parenthesis missing - [Line 72] notation for derivates isn't coherent. Both $\dot{}$ and ${}^\prime$ are used. - [Line 73] would make more sense to write for $t \geq 1$, since all statements are anytime. - [Line 95] The sentence does not have a verb. Perhaps instead of "Despite" authors meant "Exists". - [Line 100] First time I read "unbounded GML" I was confused. Would be good to mention that this refers to values o $\mu$. - [Theorem 3.1] Second line should be $\mathcal L_t$, the subscript is missing. - [Line 156] It is not clear what "it" refers to. Perhaps swap it out for "the analysis". - [Line 161] Would be good to include a reference for the first equality in the equation. Does this hold in equality or is it an upper bound? Is this common knowledge? I did not know it. - [Line 173] This line reads vaguely and informally, "even" is used twice. It's best if the justification is made rigorous or removed entirely. - [Fig 1] To demonstrate the robustness of the algorithm to $S$ you could've chosen a much larger value and still significantly outperform the baseline. Would be nice to see the effect of S = 10**{1, 2, 3, 4}.

Rating

7

Confidence

4

Soundness

4

Presentation

4

Contribution

2

Limitations

The proof technique might be limited to linear setting, with in my opinion can be viewed as a limitation, if one of the contribution points of the paper is the proof technique. Practical limitations and applicability are not adequately addressed.

Summary

This work considers generalized linear models where the distribution of observations, conditionally on a context vector $x$ and an unknown parameter $\theta^\star$, are generated from a (known) exponential family of distribution. Their main contribution is a new confidence sequence for online estimates of $\theta^\star$, leading to improved regret in the context of Generalized Linear Bandits when used to calibrate a UCB algorithm corresponding to the model for the observations.

Strengths

The paper is well written and easy to follow, and the presentation of the technical arguments is very pedagogical. The literature review seems extensive, and the authors carefully separated the literature that inspired the design of the confidence sequence and the literature related to GLM and bandits. The results are also well presented, with explicit constants so that it is not difficult to reproduce the results from the paper. In that regard, I appreciated how the authors cared about facilitating future implementation of their approach. I also appreciated the precise derivations proposed for some specific families of distributions, that are good illustrations of the results.

Weaknesses

I am not very familiar with a large part of the literature invoked by the authors, basically the literature presented in Section 3.3. Hence, it is quite difficult for me to assess the technical contribution of the paper (not a weakness, but I'm using this space to say it). For a non-expert reader, Section 3.2 is a bit hard to follow. In particular, I did not see the connection between the result and Theorem 3 of Foster et al. (2018). Regarding the bandit part, it might be beneficial to extend the "proof sketch" part to establish the main arguments that are different from previous works. In particular, l. 215 the authors say "one needs extra care in the analysis to ensure that the regret bound is also tight", but after that it seems that all arguments are standard. It might be interesting to provide more details or to remove that sentence.

Questions

* The main novel arguments seem to be located in l.153-167. My understanding of the results (please correct me) is that the goal is to use Lemma 3.3 with a nice choice of prior/posterior distributions such as to make the KL divergence as small as possible. However, in Eq. (9) l.159 I fail to see why $P_t$ is a valid posterior given the prior and empirical data. Again, I am not a specialist of the PAC-Bayes literature so I'm sorry if the answer is obvious. * In the bandit part, bounds are established for Self-Concordant GLM. Does the constant $R$ need to be known by the algorithm or is it just involved in the analysis? * Can you elaborate on the connection with Theorem 3 of Foster et al. on Section 3.2?

Rating

7

Confidence

2

Soundness

3

Presentation

4

Contribution

3

Limitations

N/A

References for the rebuttal

Let us collect all the relevant references for our rebuttal below. [1] Lee et al. “Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion.” AISTATS 2024. [2] Abeille et al. “Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits.” AISTATS 2021. [3] Faury et al. “Jointly Efficient and Optimal Algorithms for Logistic Bandits.” AISTATS 2022. [4] Emmenegger et al., “Likelihood Ratio Confidence Sets for Sequential Decision Making.” NeurIPS 2023. [5] Sawarni et al. “Generalized Linear Bandits with Limited Adaptivity.” arXiv preprint arXiv:2404.06831. [6] Neiswanger & Ramdas. “Uncertainty quantification using martingales for misspecified Gaussian processes.” ALT 2021. [7] Flynn et al. “Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixtures.” NeurIPS 2023 [8] Boyd & Vandenberghe. “Convex Optimization.” Cambridge University Press, 2004. [9] Alquier. “User-friendly Introduction to PAC-Bayes Bounds.” Foundations and Trends in Machine Learning: Vol. 17: No. 2, pp 174-303, 2024. [10] Chugg et al. “A Unified Recipe for Deriving (Time-Uniform) PAC-Bayes Bounds.” Journal of Machine Learning Research, 24(372):1-61, 2023. [11] Faury et al. “Improved Optimistic Algorithms for Logistic Bandits.” ICML 2020. [12] Foster et al. “Logistic Regression: The Importance of Being Improper.” COLT 2018. [13] Gawarecki & Mandreka. “Stochastic Differential Equations in Infinite Dimensions with Applications to Stochastic Partial Differential Equations.” Springer Berlin, Heidelberg, 2010. [14] McCullagh & Nelder. “Generalized Linear Models.” Chapman & Hall/CRC, 2 edition, 1989. [15] Carpentier & Locatelli. “Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem.” COLT 2016. [16] Lattimore & Szepesvari. “Bandit Algorithms.” Cambridge University Press, 2020. [17] Jun et al. “Improved Confidence Bounds for the Linear Logistic Model and Applications to Bandits.” ICML 2021.

Reviewer discussion

Thank you for your response and the new benchmarks. Interesting to see how close EMK and OfUGLB perform (statistically and computationally). I still think that you might be able to demonstrate a bigger advantage, if you consider significantly larger values for $S$ in the experiments, or consider benchmarks in which the true $S$ is not known.