An elementary concentration bound for Gibbs measures arising in statistical learning theory
Authors: Kelly Ramsay
Aukosh Jagannath
Shojaeddin Chenouri
Venue: Accepted by TMLR ()

Abstract: We present an elementary concentration bound for Gibbs measures whose log-likelihood is a function of the empirical risk. This bound controls the distance between samples from the (random) Gibbs measure and the minimizers of the population risk function. This bound is a generalization of a recent inequality developed by Ramsay et al., 2024. As a corollary, we obtain sample complexity bounds and bounds on the inverse temperature so that the samples are within a prescribed error of the population value. The latter bound on the inverse temperature is essentially sharp.  We demonstrate our work on three canonical classes of examples: classification of two component mixture models, robust regression, and spiked matrix and tensor models.

Published in Transactions on Machine Learning Research (02/2025)
An elementary concentration bound for Gibbs measures aris- ing in statistical learning theory
Kelly Ramsay
kramsay22@yorku..o
Deportment of Mathematics ond Statistics
York University
North York, ON M3JIP3, Canada
Aukosh Jagannath
Department of Statistics and Actuarial Science University of Waterloo Waterloo, ON N2L3G1, Canada
Shoja'eddin eddin Chenouri
schenouri@@unaterroo..o
Department of Statistics and Actuarial Science
University of Waterloo Waterloo, ON N2L3G1, Canada
Reviewed on OpenReview: https: openreview. net/ formmf id= Z. kQ3
Abstract
We present an elementary concentration bound for Gibbs measures whose log-likelihood is function of the empirical risk. This bound controls the distance between samples from the (random) Gibbs measure and the minimizers of the population risk function. This bound is a generalization of a recent inequality developed by Ramsay et al. (2024). As corollary, we obtain sample complexity bounds and bounds on the inverse temperature so that the samples are within prescribed error of the population value. The latter bound on the inverse temperature essentially sharp. We demonstrate our work on three canonical classes of examples: classification of two component mixture models, robust regression, and spiked matrix and tensor models.
1 Introduction
A basic task learning theory empirical risk minimization. Empirical risk minimization can be challenging: for example, the empirical risk can be non-convex involve combinatorial constraints. There is a vast literature tackling these challenges from many perspectives.
One popular approach to circumvent the aforementioned issues is to (approximately) sample from Gibbs measure whose log- lieeliidl is proportional to the empirical risk, where the proportionality constant, called the inverse temperature a hyperparameter to be tuned. This perspective the main motivation for the popular method of "simulated annealing" (Kirkpatrick et. al., 1983). That said, recent years, this perspective has motivated analyscs for other algorithms such as Stochastic Gradient Langevin Dynamics (Welling & Teh 2011 Raginsky et al.) 2017 Zhang et. al. (2017) and Stochastic Gradient Descent. (Mandt et al. 2017 Cheng et al., 2020 Yu et al.
2021). Methods involving samples from Gibbs measures of
this type have been used to tackle broad
range of problems in learning theory ranging from supervised
and unsupervised learning (Aubin et al.)
2018
Coja-Oghlan et. al.
2018 Barbier et al. 2019), to inference
problems with combinatorial structure Jerrum
1992
Gamarnik el. al. 2021
Ben Arous el al. 2020), to
differential privacy (McSherry Talwar
2007).
When studying such approaches there are two important, but distinct issues to consider: one algorithmic in nature, namely determining the run time rate of convergence of the sampling scheme, and one statistical

---

Published in Transactions on Machine Learning Research (02/2025)
in nature, namely determining the quality of sample from the Gibbs measure as estimator. We focus
on the statistical aspects of the problem. For the algorithmic setting, see, e.g., (Mandt et. al. 2017 Zhang
et al.
2017 Raginsky et al. 2017 Green et al. 2015) and the references therein.
There are many deep analyses for specific problems, e.g., (Lelarge & Miolane
2017
Perry et al. 2020
Jagannath et al. 2020: Bhattacharya & Martin 2022). Statistical analyses taking a general perspective have
focused mainly on asymptotic theory (Ghosal al. 2000
Shen & Wasserman 2001;
Chernozhukov & Hong
2003 Grünwald & Mchta 2016; SSyring & Martin 2020 Bhattacharya & Martin
2022 Bochkina 2022
Another line of work concerns the population risk of the model sampled from the Gibbs measure (Aminian
ct al. 2021 Bu 2024 Perlaza et al. 2024 Zou et al.; (024). In particular, PAC- bounds, which
are high probability bounds on the generalization error of the model sampled from the Gibbs measure, are an active area of research, see (Alquier et al. 2024) and the references therein. Furthermore, Bu (2024)
considered the choice of inverse temperature. They derive the inverse temperature that minimizes the population risk of the model sampled from the Gibbs measure. We also consider the finite sample performance of these estimators, along with the choice of inverse temperature, however, our goal is conceptually different. We seek concentration bounds for these estimators with the aim of answering the following, naive question:
How large should the inverse temperature, B, and the sample size, n, be to guarantce that a sample from the Gibbs measure is within distance L of minimizer of the population risk?
Observe that there is an importance conceptual difference between bounding the distance to the minimizer of the population risk-the problem considered here-and bounding the value of the population risk achieved by the estimator, the problem canonically studied in the PAC-Bayes literature. (Under certain additional assumption one may relate the two, e.g., if the population risk is known to be monotone in this distance.)
As mentioned above, in this paper, we provide an clementary, quantitative concentration bound on the distance bet the sampled parameter and the true minimizer of the population risk. This bound depends on the accuracy of the prior, the inverse temperature, and the number of samples, thereby allowing us to provide a quantitative answer to the above question. As one might expect, this bound depends on a quantification of the trade-off between the two inherent sources of randomness in the problem: the "energy- entropy" trade off of the Gibbs measure and the randomness in the underlying data. As direct consequence, we obtain quantitative answer to the above question, namely bounds on the sample complexity and the inverse temperature required to obtain a prescribed error level with high probability.
Our bound is an extension of a concentration bound recently introduced by Ramsay et al. (0024) in the context of differential privacy. Indeed, their bound can be recovered by our bound. The goal of this paper is to illustrate how one can apply the main technical idea of Rarssa et al. (2024) to a broader class of problems in statistical learning beyond differential privacy. In particular, our main result has weaker conditions than that paper: Conditions 1 and 2 are the same in both papers. Condition 3 of |Ramaay ct al. (2024) implics Condition 3 in our paper by Talagrand's inequality for empirical processes. By relaxing this condition, the range of problems to which this lemma applies is dramatically increased. In plain language, Condition 3 of Ramsay et al. 2024) implies that changing one observation in the dataset to an arbitrary value cannot affect the empirical risk function greatly at any point in its domain. This is a common requirement in differential privacy, but not in the non-private setting- Here, we relax Condition 3 of |Ramsay et al. (2024) so that the inequality can be used in a broad range of settings in statistical learning theory, beyond differential privacy,
We demonstrate our bound on three classes of learning problems: classification of two component mixture model, robust regression, and inference for spiked matrix and spiked tensor models. (Finally, we note here that, as shown in Remark 6.2 below, the bound we obtain is essentially sharp.)
2 A concentration inequality
Let us begin by stating our main concentration inequality, which is a generalization of a concentration bound first shown by Ramsay et al. (2024). In particular, we present a bound which applics to learning problems beyond differential privacy through relaxing the main conditions. Suppose that we are given n i.i.d observations, XI,..., X,, from a probability measure y on complete separable metric space (x, d).
2

---

Published in Transactions on Machine Learning Research (02/2025)
Given loss function &: θ x X - R, we seek to estimate a minimizer of the population risk, namely R(0)- (0, X). Here @ is the parameter space the set of candidate minimizers. We assume that (0,d) is also a metric space. Our estimate is given by one draw from the Gibbs distribution,
U (dT) exp( (xp(-BRn(0))dt,
(2.1)
that is, On ~ u/ π is prior on the unknown parameter, (0) = Ei= (() is the empirical risk fixed hyperparameter called the inverse lemperature. Note that if 0n concentrates around minimizer of the population risk, this generally implies bounds on the accuracy of other familiar estimates based on the above Gibbs mcasure. For instance, if 6, concentrates around the minimizer of the population risk then we immediately get a bound on f Odv, Let. A" = {0 R(O) = min R(r)} denole the set of (global) minimizers of R(0), which is assumed to contain at. least one point (but may contain more). Our bound requires the following three conditions on the triple TT).
and B >
Condition 1. The function R(0) has a minimizer and f eexp(-pp -3,, (0))dT < 00.
Condition 2. The function R(0) is L-Lipschitz for some L > 0.
Condition 3. There exists to tn, θ) c1 == cn Q), 02 = c2 (e) 0, such that for all 2 to, it holds that
R (0) R(0) 21) S c cant"
Pr
sup #Ee
Condition [ ensures the problem is well-defined. Condition 2 is a smoothness condition on the risk function.
This can be relaxed to a uniform contimuity condition if needed, see (Ramsay et al. (024) for a similar modification. Condition 3 says that the empirical risk concentrales uniformly around the population risk at sub-Gaussian rate. Condition 3 in principle the hardest to check. It can be checked by various methods
from concentration of measure, such as Talagrand's inequality for empirical processes (Tallgrand 1994 (see Section 4 Logarithmie-Sobole inequality (see Section 3
We also need the following important quantities to state our concentration result. For set E C θ let B, (E) - 10: d(o, < r). Specifically, the minimum ezcess risk is given by
all)=
inf R(0) inl R(0). (EA)(A))
(2.2)
It measures the minimum excess risk of a point 0 that is at least t distance away from the minimizing set. The calibration function is given by
d (A) min X L. - log Tlog:(Bag (B,())))
(2.3)
The calibration function small when the risk is smooth and there a small neighborhood of the minimizing set on which the prior is non-negligible. Lastly, the rate function of the prior
I(t) log π (B; (A*))
(2.4)
measures the rate of decay of the tails of the prior. Our main result is then as follows.
Theorem 2.1. Suppose that the triple (E, satisfy Conditions 3 for some to, L, > 0. Then, for
any T(t) V (())= 2 2to; we have
Pr
max d(ān, 0) 21)== < cie = D
(a0 -200t)/2-11)))200000
(2.5)
The upper bound given in Theorem 2.1 consists of two terms. The first term represents the error from using the empirical risk (0) to approximate the population risk function R(0), and the second term represents the error from using draw from the Gibbs measure, rather than the minimizer of the empirical risk. For the sake of discussion, let us call these the sampling error term and the energy-entropy term, respectively.
3

---

Published in Transactions on Machine Learning Research (02/2025)
Theorem 2.1 can be used to prove bounds on B under which the estimate 8, achieves optimal sample complexity. To see this, observe that by Markov's inequality, Theorem 2. also implies high-probability bound on the probability of V, (B). Now, for quantities a, b, we write a S b when there is universal constant C' > O such that a I Cb. Next, when n 2 log(t/>)/cza(t)² the sampling error term is bounded by 7. This bound on n yields an upper bound on the sample complexity which is oflen optimal, up to logarithmic factors, see the example applications in the sections that follow. Then, if one chooses such that B 2 (v/x V log(l/>))/o(t) the energy-entropy error term is also bounded by 7. Then, the problem amounts to bounding log((T (B(((((())A)) for small t, see Lemma 6.1 It is interesting to note that bounding (B (A*))) is akin to the conditions on the prior necessary to apply the results given by Shen & 20010; Syring & Martin 2020).
W Wasserman
Theorem 2.1 requires that 3 ((t)(t) 2 26g, the impact of which depends on the application. For instance, in all our example applications, it ends up being unimportant. When applying Theorem [2. we use the fact that a(t) > to implics s-1 a(t) > to: and then the bound a(t) > to is cither always satisfied, or is implied by other bounds on n required to achieve optimal sample complexity.
Remark 2.2. Condition g can be weakened at the expense of slower concentration rates. For example, if instead the supremum of the centered empirical risk process has a large deviations upper bound with rate n, i.e,
Pr
sup 1E
R. (0)
R(0) 21)
S cie canJ(()
for some monotone rate J, then the sampling error term in equation 2.5 becomes exp(-conJ($-1100 ((())/4). Remark 2.3. Note that, when I becomes large, we expect the error of 0. to be similar to that of the true minimizer of the empirical risk, say dn- This is reflected in equation 2.5 where, under weak condition, the energy-entropy term disappears as 3 - xc. The condition is that 3 co faster than 1²(3), which holds when the prior has sufficient density on the minimizing set and the risk is smooth enough. Going further, taking n + 0o, we have that equation 2.5 implics that 6n is weakly consistent for A.
3 Classification for a two component mixture model
As our first example, consider the basic task of supervised classification of a two component Gaussian mixture model via a single-layer neural network. Suppose that we are given data of the form {(X,, Y))= where Y; are i.i.d. Rademacher random variables and X; Y,Z, where Z; (v, 7) are i.i.d. and v is a fixed, but unknown, vector satisfying ||o||= We view X; Rd as the features and Y, E {-1,+1} as the class labels and our goal is to develop classifier for this problem. The standard approach is to develop such classifier via a single-layer neural network. More precisely, we take the loss function to be
(X, - log (Y 0)),
where (xx) = (1 + exp(-x))-1 is the usual sigmoid function and 0 E gd-1, The corresponding classifier is then obtained by simple thresholding: 7(z) (2 ((a((x, 8)) 1/2) 1) For this example, we take æ be the uniform distribution over the sphere $d-1
We check the conditions of Theorem 2.1 in turn: It is straightforward to check that the risk function R(()) is minimized at 6n = and that R(0) is (Vd + 1)-Lipschitz, so that Conditions | and 2 hold. Checking Condition 3 is more involved, but it is a straightforward consequence of Gaussian concentration of measure, that Condition 3 holds with to = dd/n, aa = and C2 = 1/32. See Lemma B.3 in the Supplementary Material.
Let us now determine sufficient values of 3 and such that 110, 6oll S with probability at least 1 y- To this end, let W, W ~ ~N(0, 1) and W be independent of W then may write the minimum excess risk
(t) E log (W + +1) - E log (W" +1 -1- 122).
(3.1)
1 As effectively the normal vector for the separating hyperplane for the data, we need only to consider 0 gd-1 as rescaling @ will affect the classifier after thresholding.
4

---

Published in Transactions on Machine Learning Research (02/2025)
Note that this is a one-dimensional Gaussian integral and does not depend on d. To visualize this integral, we have included graph of o<() in the Supplementary Material, see Figure 1 Next, note that, as shown in Lemma B.1 in the Supplementary Material, for all d >> 2 and all 0 < t < 2,
- (T & d loo h(t 1),
where h(t) = (1[]=[[1)/)/|111-/1-00-10
Combining this fact with Theorem 2.1 gives the following result.
Theorem 3.1. For the triple (c, T) as in the described two component misture model, all d > 2 and > 0,
[| -oll S t with probability ot least provided that
1og(1/7) (M((()/VVa)
(og(1/))Vd n 2
B
N
a(l)²
a(l)
where is given in equation 3.1
One way to interpret Theorem 3.1 is follows. For fixed t and y e have that log h(a(t)/VVd)) O(log d). Theorem 3.1 then says that taking / Z dloog d/a(t) guarantees an error level of t with success probability 1 - e e- provided that the number of samples satisfies
n n d/a(t)²
By way of comparison, the standard result for logistic regression is the PAC learning bound (Hanneke) 2016 One can show that in this case, the PAC learning bound can be written in terms of the minimum excess risk, which says that the number of samples needed to produce estimator with error level with probability at least 1 - --d, is given by
n 2 d/a(t)²
Comparing the bounds shows that 3 Z dlog (/oo)//(tt). then drawing a sample from the Gibbs measure does not increase the sample complexity of the estimator. Lastly, the bound given on / is tight up logarithmic factors in d, see Remark 6.2
4 Robust Regression
For our remaining examples, we focus on problems that are non-convex. One standard problem of this type is robust regression. Suppose that we observe ii.d. data points, {(x,, Y)) such that Y; X, 0g G;s where X; ~ (N,,, 6i Cauchy(O, 1) and Op is some unknown, fixed vector of regression coefficients. In this case, the standard Ordinary Least Squares procedure will not perform well: if é is the squared error loss, then for all E Rd, R(0) = co. Similarly, using the Huber loss function, commonly used in robust statistics due to its convexity and robustness, will also result in a population risk that infinite everywhere. A popular approach to resolving this issue to work with the Tukey loss (rros al. 1973). also known as Tukey's biweight function
x²
1
1
X XTe-Y
X 1-T0-10 -Y <
{(0, (X, Y))
6
(4.1)
R22 /
| 0 - Y 2 K,
where k. > 0 is a hyperparameter. Under the Tukey loss, R(0) is no longer degenerate. However, the Tukey loss is not convex. It may thus be difficult to compute the corresponding empirical risk minimizer. Let then consider the performance of 0, as an estimator of the minimizer of R(0).
We begin by checking the conditions of Theorem 2.1 It is immediate that the risk function R(0) is minimized 2
at 0 and is Lipschitz with constant L = 2x( ddv | so that Conditions 1
2 are satisfied. To check Condition
we rely on the fact that the class of loss functions f (e(0,-): E Rda has the property VC( = d
where VC denotes the Vapnik- Chenil-nherv dimension of the class of functions F. see Lemma B.2 in the Supplementary Material. Observe that in this case, the empirical risk is bounded empirical process
5

---

Published in Transactions on Machine Learning Research (02/2025)
with finite VC-dimension, and so can apply Talagrand's incquality (Talagrand 1994). This observation implies that Condition 3 is satisfied with io = 0, (en/d)4 and = =72/ 72/n", where e > 0 is universal constant, see equation B.1 and related discussion in the Supplementary Material for more detail. Now that the conditions of Theorem 2.1 have been chocked, we nowcompute the minimum excess risk. Suppose we take π = (m,,pp)) First, observe that if W ~ NN(, 1) and e, ~ Cauchy(O01) where 6 is independent of c' then
x2 E
([|1-
[1
27 xt I
[[e < x} - [1 (Wo + + t 1 [[WWo]+eel <x)] )
(1
6
x²
Again, this is a relatively simple expression which does not depend on the dimension. Lastly, using elementary properties of the normal distribution, we have that if p 2 1/4, then for all S p, we have that
110 nll?
d doog (6 vd).
- n (B.
p²
see the proof of Lemma 15 of Ramsay et al. (2024) for more details. We are now in a position to apply
Theorem 2.1 which gives the following result.
Theorem 4.1. For the triple (L, as in the described robust regression problem and all t > it holds that 110, foll S with probability at least 1 ? provided that
log(1/7) V d(log( ( (t V1)
log(1/>) v [10 - n112/0² + dllg
[sp(dv][=ll) a(l)
]
n 2
and
B Z
(1)2
a(t)
1973 Kaladar 1983). , and so suppose k O(1). If in addition, t = O1),, ||a||| is polynomial in d and |100 - nl/p- O(vd), then choosing the inverse temperature such that 3 = (d d) implics the sample complexity is O(d d). Under the Cauchy error model, the sample complexity of the robust regression estimator is linear in d. Standard minimax theory provides a lower bound on the sample complexity of sub-Gaussian regression with identity covariance of Od). Therefore, we cannot hope to do much better (d) in the more challenging case of Cauchy errors. Note that the same analysis can be applied to nonlinear regression, where the conditional mean given by f(X, 0), and the class g (I(:;))) 0); 0 E θ) satisfies VC(() < co.
Note that is typically chosen to be O(1) (Gross et al.
5 Spiked matrix and tensor models
Spiked matrix models (SMMs) and tensor models are popular statistical models used for a wide variety of inference and compression tasks (Johnstone) 2001 Richard & Montanari] 2014 Anandkumar et al. 2014). In these settings, however, the relevant loss functions are non-convex, which makes both information theoretic analysis and computation challenging. Despite this, there have been many breakthroughs in these areas over the past two decades using a variety of sophisticated techniques from random matrix theory and spin glass theory, c.g., (Johnstone 2001 Baik et al. 20055] Senaych-Georgee & Nadakuditi] 2011 El Alaoui et al. 2020) Jagannath et al.) 20200 Perry et al. 2020). As a result, much is known about these models and the goal of this section is not present new results concerning spiked matrix and tensor models, but to demonstrate that Theorem 2.1 can be used to quickly obtain information theoretic bounds for certain difficult problems
rather easily.
We begin by analyzing several spiked matrix models via Theorem 2.1 under various popular assumptions on the unknown models, namely the spherical, Radernacher, and sparse settings. We can summarize these as follows, let E c s for some fixed 5 > 0, where s (x Rd: ||ж||| = r). Suppose we have observed n i.i.d. random matrices [A0)]z such that for some 0g E E and all i I...., n,
( = (0 + 20,0
where A > 0, and each (i is a d x d matrix whose elements are independent and satisfy jk
= w
(NO0, 1 + 1 {j- =k)). In these problems, the goal is to produce an estimate of 0g For (0, A) E E Ruxd
6

---

Published in Transactions on Machine Learning Research (02/2025)
Table 1: Values of key quantities for different spiked matrix models. Note that we let Ber(p) be the Bernoulli measure with success probability p. then for P,q E (0, 1) [L(p, q) is the Kullback-Leibler divergence of Ber(p) with respect Ber(g). Note that f(() = a(t)/> X and y is a bound on - log (Ba()//8 (Oo)). See Theorem 5.1 and its proof in the Supplementary Material for more details on f and g.
Classical
Rademacher
Sparse
L
2X
2/d
2
E'
gd-1
{=1]2
f(t)
(11 -11-12/4)
4[ [2 [t221]
[t2/2](272 -
g(d,T,t)
dlog (((((1-//4)/1666
KL(t%/d", 1/2) log d 7² 1o d
the appropriate loss function is (), 0 A0. Specific choices of E' recover well-known problems: taking E gd-1 gives the classical spherical setting, taking E [=1]d gives the Rademacher prior and taking E (0. 10 n gives the sparse models.
2.1 First, it is easy to see that R(0) is minimized at A(0 A(0T0)² 0))² which 2 For a matrix V and let W = n - W(),, Condition 3 holds by Gaussian concentration of mcasure, i.c., noting that vnW and W1 are identically distributed, we have that there exists universal conslants C, such that for 1 Cdd/n,
We now turn to checking the conditions of Theorem
= 0, and so Condition | is satisfied. Further, R(0)
let ||V|| be the operator norm
Pr (r[ 21)= S sen
Now, we are in a position to apply Theorem by
2.1 Note that for E [0, the minimum excess risk is given
a(1) A
sup (0EE: [10-0o
A(TT0))
Observe that for each SMM, we can write at) = (tt).. Values of f for specific SMMs can be seen in Table 5 For cach of these problems, we may take ı be uniform on E. Lastly, by plugging in the specific values of æ for each problem, we can work out a bound on log (Ba(t)/sz(0))) which we call g(d, T, r, The values of g for each problem are given in Table 5 for more details on their dcrivation, For E (sph, rud, spa), let Tÿ be the uniform measure on E as in the classical, the Rademacher, and the sparse spiked matrix models, respectively and let Ong denote sample from equation 2.1 corresponding to the triple (4,)4,TT)) implied by for the classical, the Rademacher, and the sparse spiked matrix models, respectively.
the proof of Theorem 5.1
Theorem 5.1. For all j E tsph, rad, spa), for each triple (E, p. Tz), there are positive functions f.g such that for all and all d > 2 it holds that Il@m.. - Bull St with probability at least Y, provided that
log(1/7)Vd vd
log(1/7) V g(d,
n x X²((122
B z
(5.1)
Xfz(t)
Much of the SMM literature has focused on the case where n = 1, e.g., see Johnstone (2001); Perry et al. 2018): Gamarnik et al. (2021) and the references therein. One important question is that of weak recovery: How small can À be such that there is estimator Ø of On which has non-trivial correlation with On as d -> oo? A well-known result, known the BBP transition, show that the smallest value of À for which we can weakly recover 0g is vd. We see that reflected in Theorem 2.1 Indeed, taking n = 1 in equation 5.1 gives an upper bound of ( d) on the smallest À for which an istimate weakly recovers 0g Another example can be taken from the sparse SMM. Suppose we assume that 22 =p pd, which implics that d/72 1/p. Gamarnik et al. (2021) show that the smallest value of X for which we can weakly recover On O(v log p/T), which again matches the upper bound implied by equation 5.1 in Theorem 2.1
Specific values of and f are given in Table 5
We may also extend these results to Tensor principal component analysis. Specifically, define wa,,... ..., W(n), (Rdy+ such that each element é ;,,-..,44 ig of each tensor j is such that W ii ~N,

---

Published in Transactions on Machine Learning Research (02/2025)
and all elements independent. Suppose instead that for some À 0 and 8o E s we observe A W + o where z denotes the kth tensor of vector. In this problem, we have that
R(O) -0 0 X
with oquality at A = 80. Therefore, R(0) is minimized at = 8u and so Condition is satisfied. Further, the risk function is k A-Liissciiz and so Condition 2 is also satisfied. For tensor, let [[]] be the operalor norm of V. Condition holds again by Gaussian concentration. It follows from (Ben Arous al., 2019 see
Lemma 4.7) that for all
Pr 2) I edd dllog 1ogg--1//8
(5.2)
The next step is to compute the minimum excess risk, which, in this case, for 1 < 22
a(t) - A 1222").
It is again intuitive to set the prior to be the uniform measure on Sd-1 We are in a position to apply Theorem 2.1 which results in the following
Theorem 5.2. For the triple (l, (,, π) as in the described Tensor PCA model and all k E N, 1 1> 0, d>2
and À > O, we have that |0,- Poll S t with probobility at least 1 - provided that
log(1/7) dllog k
n ズ X² - -1- (1-22/2)9)3
B log (1/7) V log (1 1- -122))/)/)))/
X(1 - -1- (3/2
Since our bounds are general, they are necessarily not sharp. NeverCheless, they can be seen to match the correct order of growth as shown by other authors: Letting X be the threshold below which weak recovery is impossible, it is casy to see that Theorem 2.1 iiplics that X s Kydlog K, for constant K > v2 which matches scaling in k and d obtained by Perry et al. (2020).
6 Technical details
We now turn to proving the technical results in the manuscript.
The proof is in the same spirit as that of Ramsay et al. (2024). For brevity, let Dn,t = max d(O,, > J: and for any y > O, let En.y = sup
Proof of Theorem
2.1
R,,()) (0) - R(0) < y Note that from
BEE
Loee
Condition we have that for any y > to holds that
Pr
max d(O,, 0) 11) S Cie cce-esay HEA
+ Pr (F O Dr,))
(6.1)
By definition, we have that
SEq(Ar) exp (3 (x) du du.
1
log Pr (En.y n Dm,r) log
(6.2)
F.n. fx exp
33 (.) dr
On Ens holds that
cxp(-3R(8)) x))(-By) S exp (-3 <
exp (8
(6.3)
We can then apply equation 6.3 to the right-hand side of equation 6.2 which yields
SBC(A)) exp exp((3R(0)dds
1
log Pr (Dna O En,y) < log
Jx exp (-3R(0))dt + 2y.
(6.4)
B
8

---

Published in Transactions on Machine Learning Research (02/2025)
The next step is to bound the denominator below. For any 0, Condition implies that
8 log / exp(=3R(0)dr
1
2 log exp exp(-BR(0)ddr
(.(AA)
1
inf R(0) + sup
log
exp (xp(-B(R(0) R(
8E0
6.EA
3
B.(A")
inl R(0) L r + 8 log (A*)). dE0
Maximizing the right-hand side of the above, and recalling the definition of equation 2.3 yields that
log
exp (-BR(0))d= 2
inf R(0) (B)/BB BEB
B
We can then plug this lower bound into equation 6.4
resulting in
1 log Pr (Dn, n Enw)) S log exp (-BR(0))dT + inf R(00) + (B)/B+ deB
1
3
B
(A*)
inf (A))(A))
R(0) + inf R(Oo) + log x (B;(() v/3)/B 2y B.E0
- (t)) - I(t)B (B3 B 2y:
where the last line follows from the definitions of a(t) and I(t). Rewriting the last incquality gives that
Pr (Dn, O Fn,y) S exp (- (a(( T(t) + x(3) 23y)
(6.5)
Now, setting = = and plugging equation 6.5 into equation 6.1 results in
Pr
max d(On, 0) >1) BEA
I cie c nes + Pr (Dn,t O An.(()))))
S cee nos +0000000770000000440000000
(6.6)
Now, note that
((1) + -())--())(( a() T(1)22B.
Plugging this inequality into equation 6.6
results in
Pr max d(O 0) >t) DE
S cie sceeenns (na
+ (0)22221(0))2)000
The following lemma is useful for proving the remaining theorems.
Lemma 6.1. If the Conditions of Theorem 2.1 hold then, for all 0 satisfying att) V 1(1/3 2 2to we have lhat su d(On, 0o) with probability al least - provided
log(e/2017) c2a(t)2
B log(1/7)V - it ( (a(()/s((")))
n
and
(6.7)
a(t)
d(On, 0o) 2)) S Focusing the left-hand term, when Proof. The aim is to show that Pr (max
n Dog(e/2c11)
cza(t)2
have that
Ge (e(( 2/2
9

---

Published in Transactions on Machine Learning Research (02/2025)
Next, note that together, (3) & Ba(t)/4 and B 2 4log(1/1)/a(t) imply that
e -- - 1/2.
Thus, it remains to find condition on 3 such that ()= 2 Ba(t)/4. To this end, recall that by dcfinition 1/ (8) = min L r- log π (A))) Taking
a(L)/8L in the right-hand expression above gives v/ S Bo(t)/8 log x (Ba(t//8 (A0))88((A)))))))))))))))))))( (A*)). It is then enough to have
B 2 8 loog = ((Batt/so((
a(t)
Remark 6.2 (Sharpness of bound). We note here that our bound on the inverse temperature required is in a sense sharp. To this, suppose for simplicity that we are interested in high-dimensional inference lask where seek to infer an unknown vector the unit sphere &, gd-1, Suppose that our loss satisfies {(0, X) I 1 and that æ is the uniform mcasure on gd-1. This sct-up captures,c.g. the PCA and logistic regression settings above, and our arguments show that the sampling approach works provided / S d. This
is sharp: By an elementary bound, (2( S e2 (AA) for any A C gd-1. Taking A = {0 (0, 60) > f}, a standard concentration bound yields (A) S e -c(t)d for some c(t) > so that my(A) S 22)-c(t)d Thus if
3 o(d), vA( 0, which would contradict the performance of the sampling- based estimator
Acknowledgments
The authors acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC). Cette recherche a été financée par le Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG), OGEECR-2023-0331 DGECR-2000-00199).
References
Pierre Alquier et al. User-friendly introduction pac-bayes bounds. Foundations and TrendsB in Machine Learning, 17(2):174-303, 2024.
Gholamali Aminian, Yuheng Bu, Laura Toni, Miguel Rodrigues, and Gregory Wornell, An exact charac- terization of the generalization error for the gibbs algorithm. Advances in Neural Information Processing Systems, 34:8106-8118, 2021.
Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M Kakade, and Matus Telgarsky. Tensor decompo- sitions for learning latent variable models. Journal of machine learning research, 15:2773 2832, 2014.
Robert Ash. Information Theory. Dover Books on Mathematics. Dover Publications, Mincola, NY, November 1990.
Benjamin Aubin, Antoine Maillard, Florent Krzakala, Nicolas Macris, Lenka Zdeborová, et al. The com- mittoe machine: Computational to statistical gaps in learning a two-layers neural network. Advances in Newral Information Processing Systems, 31, 2018.
Jinho Baik, Gérard Ben Arous, and Sandrine Péché. Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. The Annals of Probability,, 33(5):1643 1697, 2005. doi: 10.1214/ 0091179055000000233. URL https:///oi.org// /111011//////9111900000000000000
Jean Barbier, Florent Krzakala, Nicolas Macris, Téo Miolane, and Lenka Zdeborová. Optimal errors and phase transitions in high-dimensional generalized linear models. Proceedings of the National Academy of Scéences, 116(12):5451-546) 2019.
Gérard Ben Arous, Reza Ghcissari, and Aukosh Jagannath. Bounding flows for spherical spin glass dy- namics. Communications in Mathematical Physics, 373(3):1011 1048, December 2019. doi: 10.1007/ 400220-01--03619- URL httpt//s///ooo.oo//////000000000
Gérard Ben Arous, Alexander Wein, and Ilas Zadik. Free energy wells and overlap gap property in sparse pca. In Conference on Learning Theory, pp. 479 4822. PMLRR 2020.
10

---

Subhashis Ghosal, Jayanta K. Ghosh, and Aad W. van der Vaart. Convergence rates of posterior dis- tributions. The Annals of Statistics, 28(2):500 - 531, 2000. doi: 10.211/aass1010218222 URL attps://doi 2ttp///..211/////0112222222 Published in Transactions on Machine Learning Research (02/2025)
Florent Benryeh-Georges and Raj Rao Nadakuditi. The cigenvalues and cigenvectors of finite, low rank pertarbations of large random matrices. Advances in Mathemalics, 227(1):4444-55 521, 2011.
Indrabati Bhattacharya and Ryan Martin. Gibbs posterior inference on multivariate quantiles. Journal of Statistical Planning and Inference, 218:106-121, 2022. ISSN 0378-3758. doi: https://dbl.org//1.000///
jspi.2021.10.003. URL
Natalia Bochkina. Bernstein von Mises theorem and misspecified models: a review, 2022. URL https:
//arxiv. wwt.:/oggg/bb//////eeee abs//202s.././////////////////// 13614
Yuheng Bu. Towards optimal inverse temperature in the gibbs algorithm. In 2024 IEEE International
Symposium on Information Theory (ISIT), pp. 2257-2262. IEEE, 2024.
Xiang Cheng, Dong Yin, Peter Bartlett, and Michael Jordan. Stochastic gradient and langevin processes. In International Conference on Machine Learning, pp. 1810-1819. PMLR, 2020.
Victor Chernozhukov and Han Hong. An MCMC approach classical estimation. Journal of Econometrics. 115(2):293 346, 2003. ISSN 0304-4076. doi: http:://oo.ooor///...o/o//0/0000
URL https:
Amin Coja-Oghlan, Florent Krzakala, Will Perkins, and Lenka Zdeborová. Information-theorrtie thresholds from the cavity method. Advances in Mathemalics, 333:694-795, 2018.
Ahmed El Alaoui, Florent Krzakala, and Michael Jordan. Fundamental limits of detection in the spiked Wigner model. The Anmals of Statistics, 48(2):863 885, 2020. doi: 10.1214/19-A0S1826 URL https:
//doi.org// 10. 11044/999AS1822
David Gamarnik, Aukosh Jagannath, and Subhabrata Sen. The overlap gap property in principal submatrix recovery. Probability Theory and Related Fields, 181:757-814, 2021.
Peter J. Green, Krzysztof Latuszyíski, Marcelo Pereyra, and Christian P. Robert. Bayesian computation: a perspective on the current state, and sampling backwards and forwards. Stat. Comput, 25(4):835 862, 2015.
A.M. Gross, I.M. Gross, J.W. Tukey, and Princeton University. Department of Statisties. The Estimalors of the Princeton Robustness Study, Technical report, series 2. Department of Statistics, Univ., 1973. URL https://books. http://bbooos.gggeeeeee wttp//.bosss...............
Peter D. Grünwald and Nishant A. Mehta. Fast rates for general unbounded loss functions: from erm to generalized bayes, 2016. URL https:///axtiii http:://aaxxv.or//bbbbb. wtgg///////0aaa//////////// 000111055000020222
Steve Hanneke. The optimal sample complexity of PAC learning. Journal of Machine Leurning Research, 17(38):1-14 15, 2016. URL
.html
Aukosh Jagannath, Patrick Lopatto, and Léo Miolane. Statistical thresholds for tensor PCA. The Annals of Applied Probability, 30(4):1910 1933, 2020. doi:
URL https://doi.org org/10.
1114//9-AAP1554
Mark Jerrum. Large cliques elude the metropolis process. Random Structures & Algorithms, 3(4):347-32) 3359, 1992.
Tain M. Johnstone. On the distribution of the largest cigenvalue principal components analysis. The Annals of Statistics, 29(2):295 327, 2001. doi: 10. 10.1214/20s/100921000 URL https://dol: org/10.
1214/a08/10092100
11

---

Published in Transactions on Machine Learning Research (02/2025)
Karen Kafadar. The efficiency of the biweight robust estimator of location. Journal of Research of the National Bureau of Standards, 88(2):105, 1983.
Scott. Kirkpatrick, C Daniel Gelatt Jr, and Mario P Vecchi. Optimization by simulated annealing. science, 220(4598):671 680, 1983.
Michael R Kosorok. Introduction to empirical processes and semiparametric inference. Springer, 2008.
Marc Lelarge and Léo Miolane. Fundamental limits of symmetric low-rank matrix estimation. In Conference on Learning Theory, pp. 1297-1301. PMLR, 2017.
Stephan Mandt, Matthew D Hoffman, and David M Blei. Stochastic gradient descent as approximate bayesian inference. arXiv preprint N0o:7704004280 2017.
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual TEEE Symposium on Foundations of Computer Science, pp. 94 103. IEEE, 10 2007. doi: 10.1109 WW.1109/FOCS2007. 4389483.
Samir M Perlaza, Gactan Bisson, Iñaki Esnaola, Alain Jean-Marie, and Stefano Rini. Empirical risk mini- mization with relative entropy regularization. TEEE Transactions on Information Theory, 2024.
Amelia Perry, Alexander S Wein, Afonso S Bandeira, and Ankur Moitra. Optimality and sub-optimality of pea i: Spiked random matrix models. The Annals of Statistics, 46(5):2416 2451, 2018.
Amelia Perry, Alexander S. Wein, and Afonso S. Bandeira. Statistical limits of spiked tensor models. Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, 56(1):230 - 264, 2020. doi: URL /
11214/19-AIHP9R-
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky, Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis. In Conference on Learning Theory, pp. 1674-1703. PMLR,
2017.
Kelly Ramsay, Aukosh Jagannath, and Shoja'ed eddin Chenouri. Differentially private multivariate medians. arXiv e-prints, art. arXiv:2210.06459, March 2024. doi: 10.48550/ar 2ttp550//XXvvv220..00. 2210.0694..
Emile Richard and Andrea Montanari. A statistical model for tensor pea. Advances in neural information processing systems, 27, 2014.
Bodhisattva Sen. A gentle introduction to empirical process theory and applications. Lecture Notes, Columbia Universily, 2018.
Xiaotong Shen and Larry Wasserman. Rates of convergence of posterior distributions. The Annals of Statistics, 2983)6687-7 2001. ISSN 00905364. URL
Nicholas Syring and Ryan Martin. Gibbs posterior concentration rates under sub- sub-exponential type losses. arXiv e-prints, art. arXiv:2012.04505, December 2020. doi: 2.48500/aXXiv.2212.45500
M. Talagrand. Sharper bounds for gaussian and empirical processes. The Annals of Probability, 22(1):28-76, 28-)6 1994. ISSN 00911798.
Max Welling and Yee W Teh. Bayesian learning via stochastic gradient langevin dynamies. In Proceedings of the 28th international conference on machine learning (ICMI--11), pp. 681-688, 2011.
Lu Yu, Krishnakumar Balasubramanian, Stanislav Volgushev, and Murat A Erdogdu. An analysis of constant step size sgd in the non-convex regime: Asymptotic normality and bias. Advances in Neurol Information Processing Systems, 34:4234-4244 2021.
Yuchen Zhang, Percy Liang, and Moses Charikar. hitting time analysis of stochastic gradient langevin dynamics. In Conference on Learning Theory, pp. 1980-2022 PMLR, 2017.
12

---

Published in Transactions on Machine Learning Research (02/2025)
Xinying Zou, Samir M Perlaza, Iñaki Esnaola, and Eitan Altman. Generalization analysis of machine learning algorithms via the worst-case data-generating probability measure. In Proceedings of the AA Conference on Artificial Intelligence, volume 38, pp. 17271 17279,, 2024.
13


Reviews:
[{"review_id": "PmxpBpbcln", "reviewer": "Reviewer_qCrq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n(1) At an initial reading, all of the statements and proofs appear to be sound.\n\n(2) The authors demonstrate the applicability of the proposed bounds on three learning problems.\n\nWeakness:\nMajor:\n(1) The authors claim that this work relaxed the conditions in Ramsey, et al., 2024, which is part of the main contribution, however, it is not clear whether or not this is true. There is no introduction/discussion on Ramsey, et al., 2024 and no comparison of the conditions between these two. One should not be required to read another paper to understand this work. Moreover, Condition 3 requires sub-Gaussian property on the unknown distribution $\\mu$ and I am not entirely convinced this is a very relaxed condition.\n\n(2)This paper seeks to explore the relationship between the performance of a Gibbs sampler and the choice of sample size, prior, and inverse temperature. If the goal is to provide deeper understanding, further analysis of the right-hand side of equation (2.3) would be valuable. For instance, how should the assumption $\\alpha(t) \\vee I(t) \\ge 2t_0$ be interpreted beyond its mathematical convenience for the proof? Additionally, what practical insights does equation (2.3) offer for What insights does (2.3) bring for choosing $\\beta$? There are many studies on selecting the inverse temperature for the Gibb measure, such as “Towards Optimal Inverse Temperature in the Gibbs Algorithm” by Yuheng Bu. A comprehensive study of the properties of the Gibbs algorithms can be also found in ‘‘Empirical Risk Minimization with Relative Entropy Regularization’’ by Samir Perlaza, et al. More discussion on the insights should be provided.\n\n(3)The main result of this paper—Theorem 2.1—presents a PAC-Bayes bound specifically for the Gibbs measure, an area of active research. Notably, “User-friendly Introduction to PAC-Bayes Bounds” by Pierre Alquier and other related references offer important context. However, this paper does not mention prior work on PAC-Bayes bounds, which weakens its positioning within the literature. Also, analysis/discussion on the tightness of this bound would be appreciated. \n\n(4) The paper is missing a Conclusion section at the end.\n\nMinor:\n(1)The mathematical notations in this paper lack clarity. For example, in Condition (3) and Equation (2.3), the sub-Gaussian inequality does not explicitly specify which random variables it pertains to, making the statements ambiguous and harder to interpret. Providing precise definitions and clear references to the random variables involved would greatly enhance the readability and rigor of the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a concentration bound for the Gibbs measure, which can be applied in the setting of statistical learning under certain conditions. From a technical perspective, this result is an extension of a previous result in a different setting. The authors also demonstrated this result in three learning problems.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See Weakness for details.\n\nThe Major Weaknesses are critical for the acceptance of this work. \nIf these are addressed/cleared, I can bear with the rest minor weaknesses.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ECbHpE3see", "reviewer": "Reviewer_CfUN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\nStudying sample complexity bounds and bounds on the inverse temperature to ensure that small population risk is a fundamental problem in learning theory. Additionally, since the Gibbs algorithm can be viewed as the asymptotic limit of SGLD, it has practical applications for guiding hyperparameter selection.\n\nWeaknesses: \n\nA more detailed characterization of the minimum excess risk function $\\alpha(t)$ is needed. Currently, it is not immediately clear how the gap in the population risk depends on the number of samples and the inverse temperature. While I understand that $\\alpha(t)$ is problem-dependent, could you either work out Equation (3.1) or provide some figures to help the reader better understand this dependence?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper utilizes the recently developed concentration bound by Ramsay et al. (2024) to address the following question: How large should the inverse temperature $\\beta$, and the sample size n, be to ensure that a sample from the Gibbs measure is within a distance t of a minimizer of the population risk? Additionally, three canonical examples are provided, focusing on the classification of two-component mixture models, robust regression, and spiked matrix and tensor models.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Recent advancements in the information-theoretic characterizations of the Gibbs algorithm should be noted:\n\nAminian, Gholamali, Yuheng Bu, Laura Toni, Miguel Rodrigues, and Gregory Wornell. \"An exact characterization of the generalization error for the Gibbs algorithm.\" Advances in Neural Information Processing Systems 34 (2021): 8106-8118.\n\nBu, Yuheng. \"Towards Optimal Inverse Temperature in the Gibbs Algorithm.\" In 2024 IEEE International Symposium on Information Theory (ISIT), pp. 2257-2262. IEEE, 2024.\n\nZou, Xinying, Samir M. Perlaza, Iñaki Esnaola, and Eitan Altman. \"Generalization analysis of machine learning algorithms via the worst-case data-generating probability measure.\" In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 38, no. 15, pp. 17271-17279. 2024.\n\n2. Can the proposed method be applied to understand ERM by letting $\\beta$ approach infinity? Including such a discussion after theorem 2.1 would certainly enhance the quality of the paper.\n\nMinor comments:\n\n1.\tThe metric d() in the parameter space should be introduced when defining the Lipschitz condition. More generally, can the proof technique be extended to other metrics, provided they satisfy the Lipschitz condition?\n\n2.\tWhat is the prior distribution used in Section 3? Also, there is no Lemma A.1 in the paper, referring to (Lemma 6.1)?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "rsl3FMv6wv", "reviewer": "Reviewer_cku6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**\n\n1. The concentration result in the paper is established under relative mild conditions, which makes the method easy to be applied to varies risk minimization tasks.\n\n**Weaknesses**\n\n1. Although the authors mentioned the improvement of the concentration result from the one in [1], how this improvement is achieved methodologically is not explained. In my opinion, it will make the paper more insightful if a discussion on the methodology of proving the concentration bound can be added.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "**Summary Of Contributions**\n\n1. This paper derives a concentration bound for the Gibbs measure whose log-likelihood is the product of the empirical risk and the inverse temperature. The concentration upper bound depends on the calibration function $\\psi_{\\pi}$, the minimal excess risk $\\alpha$ and the rate function $I$, which further depend on the number of samples $n$, the inverse temperature $\\beta$ and the prior $\\pi$. By quantifying the dependency of $\\psi_{\\pi},\\alpha,I$ on $n,\\beta,\\pi$, the concentration bound can be applied to determine how large the inverse temperature and the number of samples should be to guarantee that a sample from the Gibbs measure is within a distance t of a minimizer of the population risk.\n\n2. The paper applies the aforementioned approach to analyze three canonical risk minimization examples: classification for a two component mixture model, robust regression and spiked matrix/tensor models.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. As the author mentioned in the paper, the concentration bound is general and may not imply a sharp bound in specific problems. In the three examples, it might be good to also introduce what the state of the art bounds on $n$ and $\\beta$ look like. That would help to understand how good this concentration method actual is when applied to different problems. \n\n2. In Condition 3, it might be good to also emphasize $c_1,c_2$ can depend on $d,n$.\n\n3. The prior $\\pi$ is chosen to be the uniform distribution in example 1. This should be stated explicitly in the main paper.\n\n4. In examples 2 and 3, it might be better to also introduce how the rate function $I$ is estimated, just like what's done in example 1.", "broader_impact_concerns": "No ethical concerns for this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a concentration bound for Gibbs-type measures, extending previous work by Ramsay et al. The work generalizes the previous results, using weaker conditions, and offers a broadening of scope of applicability. 

The technical claims and proofs appear to be correct, as verified by the reviews based on the revision and discussion with the authors. The original version lacked some technical details, but these have been provided in the updated manuscript and the reviewers are happy with the updates. In private discussion, one reviewer suggested that the comparison with Ramsay et al. (2024) in the introduction could be presented in a way that is more accessible to a general audience - I encourage you to do so in the final version.
Decision: Accept (poster)