Graph–Smoothed Bayesian Black-Box Shift Estimator and Its Information Geometry
Authors: Masanari Kimura
Venue: NeurIPS 2025 spotlight ()
Keywords: label shift
target shift
domain adaptation
Primary area: general_machine_learning

Abstract: Label shift adaptation aims to recover target class priors when the labelled source distribution $P$ and the unlabelled target distribution $Q$ share $P(X \mid Y) = Q(X \mid Y)$ but $P(Y) \neq Q(Y)$. Classical black‑box shift estimators invert an empirical confusion matrix of a frozen classifier, producing a brittle point estimate that ignores sampling noise and similarity among classes. We present Graph‑Smoothed Bayesian BBSE (GS‑B$^3$SE), a fully probabilistic alternative that places Laplacian–Gaussian priors on both target log‑priors and confusion‑matrix columns, tying them together on a label‑similarity graph. The resulting posterior is tractable with HMC or a fast block Newton–CG scheme. We prove identifiability, $N^{-1/2}$ contraction, variance bounds that shrink with the graph’s algebraic connectivity, and robustness to Laplacian misspecification. We also reinterpret GS‑B$^3$SE through information geometry, showing that it generalizes existing shift estimators.

Graph-Smoothed Bayesian Black-Box Shift Estimator and Its Information Geometry
Masanari Kimura
School of Mathematics and Statistics The University of Melbourne
m. www.rauuuiieeeeeee..mm.. edu. au
Abstract
Label shift adaptation aims to recover target class priors when the labelled source distribution P and the unlabelled target distribution Q share P(X Y) Q(X Y) but P(Y) * Q(Y). Classical black-box shift estimators invert an empirical confusion matrix of frozen classifier, producing brittle point estimate that ig- nores sampling noise and similarity among classes. We present Graph-Smoon Bayesian BBSE (GS-B'SE) a fully probabilistic alternative that places Lapla- cian-Gaussian priors on both target log-priors and confusion-matrix columns, tying them together on sibel-iimllartty graph. The resulting posterior tractable with HMC fast block Newton-CG scheme. We prove identifiability, N-1/2 con- traction, variance bounds that shrink with the graph's algebraic connectivity, and robustness to Laplacian misspecification. We also reinterpret GS-B through information geometry, showing that it generalizes existing shift estimators.
Introduction
Modern machine-learming systems are rarely deployed in exactly the same environment in which they trained. When the distribution of class labels drifts but the class-conditional features remain stable, a phenomenon known as label shift, even nigh-capacity model can produce arbitrarily biased predictions [54] 12 29
44 45 [T]. Practical examples include sudden changes in click-through
behaviour of online advertising, evolving pathogen prevalence in medical diagnostics, and seasonal increments of certain object categories autonomous driving. Because re-labelling target data is often prohibitively expensive, methods that recover the new class priors from a small unlabelled sample are indispensable precursors to reliable downstream decisions.
A popular remedy, the Black-Box Shift Estimator (BBSE) is to keep single, frozen classifier h: X + y trained on labelled source data and to link its predictions on the target domain to the unknown target priors through the confusion matrix C [3 77. The resulting formulation converts density shift into a linear system q = Cq that can be solved in closed form, after plugging in (i) an empirical estimate Ò computed on small labelled validation set and (ii) the empirical prediction histogram q measured on unlabelled target instances. The elegance of BBSE has made it the default
baseline for label-shift studies 45 13
38
30
42
Despite its popularity, the BBSE pipeline overlooks ing in realistic, high-class-count regimes. (i) Finite-sample noise. Each column of Ć' is estimated from at most a few hundred examples, so the matrix inversion layer can amplify small fluctuations into large errors on q. Regularised variants such RLLS 7 MLLS [8 damp variance but still return point estimate whose uncertainty remains opaque to the user. (ii) Semantic structure.
sources of uncertainty that become debilitat-
Classes in vision and language problems live rich ontologies (3 car and bus are more alike than
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

car and daisy. Standard BBSE fits each class independently and cannot borrow statistical strength across such related labels, leading to particularly fragile estimates for rare classes.
We introduce Graph-Smoothed Bayesian BBSE (GS-B' a fully probabilistic alternative that attacks both weaknesses in single hierarchical model. The key idea is couple both the target log-prior vector and the columns of the confusion matrix through a Gaussian Markov random field defined on label-similarity graph. Graph edges are obtained once from off-the-shelf text or image embeddings, and the resulting Laplacian precision shrinks parameters of semantically adjacent classes towards each other. Sampling noise handled naturally by Bayesian inference: we place hyper-prian -preer- on the shrinkage strengths and sample the joint posterior with either optimizer [23] [0].
Hamiltonian Monte Carlo [8 [6] or a fast block contton--onngateeeee
Moreover, we provide interpretation of GS-B through the lens of information geometry [S] 6]. The analysis of statistical procedures or algorithms in this framework is known to help us understand them better
4
40
28
25
24
Contributions. i) We formulate the joint Bayesian model that simultaneously regularizes the target prior and the confusion matrix with graph-based smoothness, reducing variance without hand-tuned penalties (in Section 4. ii) We provide theoretical guarantees: (a) posterior identifiability, (b) N 1/2 contraction, (c) class-wise variance bounds that tighten with the graph's 's algebraic connectivity, and (d) robustness to Laplacian misspecification (in Section [). Morcover, we provide interpretation of GS-B SE through the lens of information geometry framework and it shows that our algorithm is natural generalization of existing methods. iii) An empirical study on several datasets demonstrates that GS-B GS-B produces sharper prior estimates and improves downstream accuracy after Saerens correction compared to state-of-the-ard baselines (in Section 7)
Related Literature
Classical estimators under label shift. Saerens et al. 47 proposed an EM algorithm that alternates between estimating the target prior and re- weighting posterior probabilities calculated by a fixed classifier. Lipton et al. (39] later formalised the Black-Box Shift Estimator (BBSE), showing that single inversion of the empirical confusion matrix suffices when P(X Y) is preserved. Subsequent refinements introduced regularisation to cope with ill-conditioned inverses: RLLS adds an & penalty to the normal equations 77. while MLLS frames the problem as a constrained maximum-likeline
optimisation
[8]. All three methods remain point estimators and ignore uncertainty in C.
Bayesian and uncertainty-aware approaches. Caelen [ derived posterior credible intervals for precision and recall by coupling Beta priors with multinomial counts; Ye et al. [3 extended the idea to label-shift estimation under class imbalance. Most of these models assume that classes are a priori independent, so posterior variance remains high for rare labels. Our work instead imposes structured Gaussian Markov random field (GMRF) priors that borrow strength across semantically related classes.
Graph-based smoothing and Laplacian priors. In spatial statistics, Laplacian Gaussian GMRFs
standard device for sharing information among neighbouring regions (49) Recent machine learning studies exploit the same idea for discrete label graphs: Alsmadi et al. introduced a Seahh--irichhet-mmune
model for text classification, and Ding et al. [15 used graph con-
volutions to smooth class logits. We follow this line but couple both the prior vector and every confusion-matrix column to the same similarity graph, yielding a joint posterior amenable to HMC and Newton-CC
Domain-shift benchmarks and failure modes. Large-scale empirical studies such as WILDS 30 and Mandoline 13 describe how brittle point estimators become under distribution drift and class imbalance. Rabanser et al. 455 demonstrated that label-shift detectors without calibrated uncertainty frequently produce over-confident but wrong alarms. By delivering credible intervals whose width shrinks with the graph's algebraic connectivity, our method directly tackles this shortcoming.
Positioning of this work. GS-B*SE unifies three strands of research: (i) black-box label-shift modelling, and (iii) graph-structured smoothing. To justify our proposed method, we show posterior identifiable identifiability and N-1/2 contraction, and derive variance bounds that scale with (T.). Empirically, our method plugs seamlessly into existing shift-benchmark pipelines, providing calibrated uncertainty absent from earlier regularised or EM-style alternatives.
estimation, (ii) Bayesian confusion-mant

---

3 Preliminarily
Problem Setting Let X' be an input space and y {_,.... K be label set, where K 2 2 the number of classes. For source and target distributions / and Q, the label shift assumption states that the class-condittonal feature laws remain unchanged while the class priors may differ:
P(X Y = 1) Q( Y = i), Ei, and P(Y = +
Q i)
in general.
(1)
P4
Let p- (P1,...,PP)) Pk). and q (41, ........ qk)² where E = 9: =1
Black-Box Shift Estimator Train once, on source data, an arbitrary measurable classifier h: X + Jr. Denote its confusion matrix under by C' E (0, (0,1)KxK, where Cj,= Prp [(()) Y = and Σ, Cj = 1. Notice that C' depends only on the source distribution and can be estimated on a held-out validation set with known labels. Write the empirical estimate as Ö. Let m labelled source-validation points (z,, 11 be used to form Ć. Apply the same fixed to unlabeled target instances {- of size n'. Let d = Pro [m()) = 5 q = (Q1....,4x1 Because the class-conditionals are shared, Bayes' rule gives
Pr (x(
- Σ Pr ((x)= = - =
Σ Cjags
and in vector form, it can be written as q = Cq. Eq. D the identifiability equation for label shift.
Assume C' is invertible or full column rank. Then the population target prior is q = C- Under this observation, BBSE framework (39 converts black-box classifier predictions unlabeled target data into an estimate of the unknown target class prior by solving the linear system.
4 Methodology
The usual BBSE treats the confusion matrix C as fixed. In practice C' is estimated from a finite validation set and is itself ill-conditioned when some classes are rare. To address this problem, we consider extending BBSE framework by the joint Bayesian model for both confusion matrix and larget priors with the graph coupling. Let n be a number of source examples with label i, and ni (n i........ x. be the counts of h(x) j among those n². Also, let ñ (ñ1..... .ãk ,u)
be the counts of li()) = j on unlabeled target data. For each true class i,
n C ~ Multi (n C.,).
where C, is the i-column of C and Multi(--)) is the multinomial distribution. Similarly, C, q ~ Multi (n', Cq).
The complete-data likelihood factorises
K P (data C. = II Multi (n C..)) Multi (n;n',
We now consider utilize similarity information between classes. Let (), E, W) be a similarity graph on labels with the weight matrix W, E is the edges and L is the graph Laplacian. In G, each vertex corresponds to a class label; an edge (i,j) E E indicates that labels and j are semantically or visually similar. Weights Wi, E [0, 1] quantify that similarity, with W.; = 0 when no edge is present. our methodology, we use the unnormalised Laplacian L D W where DR = E, W.y Because we enforce connectivity, L has exactly one zero eigenvalue, making A2( (the algebraic connectivity) strictly positive as required by our theory. Introduce log-odds vector
K
0: = llog q:
log lk.
0 E RR K
0 1
K
3

---

and consider the following Gaussian Markov random field (GMRF) prior
p(0
Tq) & exp
Ta a L0) 2
Tq Gamma(a,,
where uq. b 0 are hyper-parameters. A Laplacian- precision shrinks log-odds differences along graph edges, promoting smooth class priors across semantically similar labels [31] and recover softmax(0).
Treat each column C.2 as a latent simplex vector with Dirichlet-log- hierarchy:
Latent log-odds Φ RRK o 0.
ïi) Conditional prior p(Ø; TC) x exp (- LØ.). All Φi share the same Laplacian L over predicted labels so that columns corresponding to neighbouring predicted classes exhibit similar shape.
iii) Transformation to the simplex C₁ Ei- exp
exp d
for =ii=,,... I,..,,K K.
iv) Hyper-prior TC ~ Gamma(ac, bc), with ac, be > 0.
The resulting distribution each C.₁, is logistic-Normal the simplex and it reduces to ordinary Dirichlet when L = 0 but gains graph-coupled precision for L of O. The full hierarchical model is follows.
~ Gamma 0g. bg),
0 Tq ~ No0, (Tg
q = softmax(0).
TC Gammalac,
Vi: Φ; TC ~ N(O, ) C. = softmax(0:),
Vi: ; C ~ Multi(n C.a),
ñ C, q Multi(n',Cap
Here, the Moore-Penrose pseudoinverse Lt appears because is singular, and the constraint 0 1 ensures uniqueness.
For the posterior inference, consider the following log-joint distribution.
logp(C, C. TCT Tq data) = log p(data C, g) + log PC TC)
+lggp(TC) log [q) + logg((TT))
All terms are differentiable, enabling Hamiltonian Monte Carlo (HMC) in the unconstrained variables. Because Eq. dis concave in each block after reparameterization, block-Newton scheme alternates, TK i=1 by one Newton-CG step using sparse Laplacian Hessian, ii) update O likewise, iii) closed-form updates for TC, Tq from Gamma posteriors. Convergence is super-linear due the strict convexity induced by the Laplacian energies. The posterior predictive distribution of the weeitsion-weighted target counts
i) update {
data = Multi(n', Cq)p(C, q data)dCddq.
(5)
Credible intervals for each reflect both sampling noise and model-induced graph smoothing. an advantage over plug-in BBSE. If prior similarity information exists may default to Wij = 1(i = i}, in which case our model reduces to an independent logistic-Normal prior and all theoretical guarantees still hold.
Relationship to Existing Work
Replaces the point estimate of BBSE C-1 with full posterior, relating Bayesian confusion matrix treatments [[].
Laplacian GMRFs generalise classical Dirichlet priors by borrowing strength along graph edges, extending recent graph-Dirichlee Dirhhiiicccet-mmlioommaa models (3I].
When L = 0 and Gamma hyper-priors degenerate to delta masses, our hierarchical model reduces exactly to deterministic BBSE.

---

Theory
This section provides the theoretical foundations of the proposed method. See Appendix for the detailed proofs. First, the following lemma on identifiability is introduced. Although an analo- gous statement has been implicitly argued in the prior work 39), the full proof is included in the Appendix to make this study self-contained.
Lemma 1. Ler C and C' be two column-
matrices with strictly positive entries: C3,5 > C/33 > 0. Ei= C3. = =Ei= C3, = for 1 S K. In addition, assume C and C' are invertible, or equivalently, det C + O and det C' + O. For any deterministic sample sizes ni (1,2,...) and n' E (1.2..... define the data- aita-generattig distributions
5 ~ Multi(n,. C.s)s
N C' ~ C²~ Multi(n, C,,,), Ñ C, Multi(n', Cq), Ñ C. Multi(n', C'd).
Suppose that, for every choice of the sample sizes { and n', (INS)E,, &
(LNS" NY as random vectors in NK***K where the left-hand side is generated by (C,q) and the right-hand side by (C", Then, C C" and q q'
Lemma implies that the mapping (q.C) - {(n n injective up to measure-zero label permutations when the graph is connected and all source classes appear.
Let A K-1 be the (K -)ddimmesion probability simplex:
A = ( q- (91...... ( ςK) E RR qi 2 0 for every i,
K
Σ 41
i=1
The following lemma provides the support condition needed in statements described later.
Lemma 2. Let (qo, Co) be the true parameter pair, where qo E K-1 and Cp E (0, (),1) K0x with det Co F O. Define the Euclidean small ball as
Be Co) = C) 11 <E, ||C CollF <e}.
for some radius > O small enough that all vectors in the ball stay strictly inside the simplex. Then, for every e, the joint prior distribution on (q, C') assigns strictly positive mass to the ball: I1 (B. Co)) > 0.
This lemma states that positivity of Gaussian density and the smooth bijection yield the positive push-forward density, and it is the classical strategy used for logistic-Gaussin process priors in density estimation [50].
2 and the classical results from Ghosal et al. 20 Van der Vaart 52 gives the following statement.
Lemmas
Proposition 1. Let K 2 2 be fixed and (go, Co) be the true parameters pair with qo E åK-1 and Co (0, 1)K* where Å K-1 is the interior of A K-1, and det Co + 0. Suppose that the data consist (N$) Je and Ñ where conditionally on (go, Co).
Jiz
Nº Multi (ne, Co.), ~ Multi Coqu)
Also suppose that sample sizes diverge with the single index: N = n' + ΣK n
co, and min, no + co. Then, for every e 0. (B: data) Pono 0.
N
Under the same assumption in Proposition 1 the following statements about the posterior contraction rate are obtained.
Theorem 1. Let the data generating model, true parameter pair (go. Co), and diverging sample sizes
N n' ΣK m + oc satisfy the setup spelled out before Proposition Define the Euclidean radius eN = M/VN, M > 0 arbitrary but fixed. Let
B (gg C): 11q - 90ll2 + ||C -ollF cx).
5

---

Under Lemmal 1 land2 2 the joint posterior II(- data) for the Caplacian-Gaussicn hierarchy satisfies
Pigo.Co),
II (Bx data)
0.
N-+00
That is, the posterior contracts around the truth at the parametric rate N-1/2, Corollary 1. Retain the setting and notation of Theorem
! For each class i, write
Var (g.) = Var (g: data of size N),
under the joint posterior IT(. data). Let L. be the connected- graph Laplacian used in the GMRF prior and let (2( == min {} > 0 À is an eigenvalue of L} be its algebraic connectivity, Assume the hyper-parameler Tq fixed, or sampled from a Gamma prior independent of N. Then, there exists a constant C > 0, depending only on the true (qo, Co) and on K, such that for every sample size N large enough,
C (a) S (2(L)
Vi (L...,,K..
Finally, can show the following statement about the robustness to graph Laplacian misspecification. Proposition 2. Let Lo be the true Laplacian, and Fo == diag(Coqo) Coqo) (Coqo)
> 0 be the Fisher information of 0 in the target multinomial likelihood. For L + Lo, let ON ES data] be the posterior mean of 0 under the misspecified prior. Then, for all sample sizes N large enough,
||O 0oll2
[NF L) 1 7q (L Lo)00 +Or(N~1).
(6)
sampling prior precision
gruph-misspeciiicttion bias
In particular,
110N -0ll2 5
Tq Ndmin (Fo) + (2))
[n
(7)
where Amin (F) and (2 are, respectively, the smallest eigenvalue of Fo and the algebraic connectivity of L.
Thus,
that the bias decays as N-1 when L # Lo and if the graphs coincide the leading term vanishes and the posterior mean is unbiased up to the usual N-1/2 noise. Moreover, Proposition
2 states that a larger algebraic connectivity X2(L) reduces bias, emphasising the benefit of rich similarity structures.
6 Interpretation via Information Geometry
The basic notations of information geometry used in this section are summarized Appendix B The K simplex A = {q > 0 1 1} is a Riemannian manifold when equipped with the Fisher-Rao metric ( un) Σ K w.w, for v. w E &T, where T, K = {v 1 4:
0} the tangent space. The natural potential on this manifold is minus entropy (b(4) = -; log whose Euclidean gradient is the centred log-odds vector 0 used in the previous section. These facts allow us to cast GS-B*SE as a Riemannian penalised likelihood. The dual affine coordinates mn-coordinates qi (mixture parameters) and e-coordinates 0: log 4
* Σj log (j (centred log-odds). The convex potential ()(g) Di=1 9: log qi is minus Shannon entropy and satisfies V Buc qq) 0: together (y',, 0) endow A K-I with the classical dually-fla structure of information
K
geometry S 6 See standard textbooks for detailed explanation of concepts differential geometry
and Riemannian manifold [36] 37 34
17 43
21 33).
Denote by = û/'' and M (Cq : e K-1)) the empirical prediction histogram and the m-flltt sub-manifold induced by the frozen classifier. The negative log-posterior derived in Section can be written as
F(g) n' DKL Cq]
Tg (0 LO) + const.
(8)
Thus Eq. (8) a sum of an m-convex and an e-convex potential, so is geodesically convex under the Fisher Rao metric (see T..

---

Table Information geometric identification of GS-B
Term
Geometric meaning
DRa.F Cq]
Canonical divergence between + and the m-flat model M.
Quadratic form in e-coordinates = e-convex barrier that bends the manifold in the directions encoded by the graph Laplacian L.
2 0 I.0
Theorem 2 (Geodesic convexity of F). For every q AK=1 the Riemannian Hessian of F satisfies
Hess FR F [n' Amin (Fo) + Tq >2(L)] 9q-
where Fo = diag(CC) (C)) is the Fisher information of the multinomial likelihood and LL) the algebraic connectivity of the label graph. Hence F is a-strongly geodesically convex with n n'Amin (Fo) + (L)) > 0.
The proof in Appendix A explicitly decomposes any tangent direction into an m-straight and an e-straight component and shows that the lower bound remains positive because both components contribute additively.
6.1 Natural-Gradient Dynamics
The natural gradient of F is
grad FR F(q) 9q (m)) ((m)) = o (v&F (VgF)
where component wise product. The associated flow q(t) grad F(q(t)) is the steep- est-descent curve in the Fisher-Rao geometry.
Proposition (Natural-gradient flow of the penalised objective). Under the Fisher-Rao metric (q(U, w) Ex= u,w:/4 the natural gradient gradFR F(q) of F is
grad FR F(q) diag(a) ( cT ria)) + +T LO).
(9)
where the division is element-wise Consequently the un-constraineed natural- -aaiiaal--rrdentttt flow
d: = -radd F(q:) - -dagg(q:) (n' (1-1-() + 5 Lo.)
(10)
preserves the simplex and coincides with the replicator-Lapleee dynamical system: qu.j =
- (n' (11-/r)]++ [g
Remarks
i) Role of Laplacian When the Laplacian term is absent (T, 0), the flow reduces to the classical replicator equation that drives every classprrbayylltyy lj proportionally to the (signed) log-likelihood residual [CT (1 f/r)lj- The graph-Laplacian contribution Tqqj LØ); plays the role of mutation / diffusion force that mixes mass along edges of the label graph and prevents degenerate solutions.
ii) Role of the algebraic connectivity. From Theorem the strong-convexity modulus is a n' d'Aiin (F)) Az)2(L), L). Along the flow we have F(g:) = llgrad F(g:) I1 < (F.(F())) F*), F decays exponentially fast with rate proportional the algebraic connectivity A2 L); denser-connected label graph therefore accelerates convergence.
iii) Link to Saerens EM correction. If we freeze the confusion matrix and drop the Laplacian term, the stationary condition C (f/r) is exactly the fixed point solved (iteratively) by the Sacrens EM method [7).

---

Table Baseline methods and their key ideas.
Method
Key idea
BBSE 39
Solve Cý with the empirical confusion matrix (no re-training). Iupectation-Maxiiiiztion that iteratively re-estimates priors and re-weights posteriors.
EM 47
Adds an Ez penalty to the BBSE normal equations to control variance for small n'.
RLLS
Maximum- Maximum-likelihood likelihood estimation of the label-ratio vector, unifies BBSE & RLLS and optimizes q directly.
MLLS 18
Joint Bayesian inference of both target priors q and confusion matrix C, The hierarchical model couples classes along a subelsiimlarrity graph, shrinking estimates low-count regimes and yielding full posterior credible intervals.
SS (ours)
6.2 Dual Projections and the Pythagorean Identity
Let Im (f) be the m-projection of the data onto A and (qu) the e-projection of the hyper-prior
center onto the same manifold. At the optimum qº we have II (f) (40) = Cq" and the
DKL[f) [q D Cq || go). where the second term equals the Laplacian regulariser 2n 0 LO. Hence GS-B can be summarized as find the unique intersection of an m-geodesic (data fit) and an e-ellipsoid (graph prior).
generalized Pythagorean theorem (S] gives DKL r qo
Experiments
7.1 Experimental Protocol and Implementation
Datasets and synthetic label shifts. We evaluate on MNIST (K = 10) [4], CIFAR-10 (K = 10) and CIFAR- 1000 (K 100) datasets [32]. For each dataset treat the official training split the source domain and the official test split as the pool from which an unlabelled target domain is drawn. Target priors are deliberately perturbed:
Source class-priors are kept uniform p (I/K,.... ..... 1/K). 1//K
Dirichlet (a x uu)
(MNIST),
q
i= K
(CIFAR-10 and CIFAR-100).
where = (1,..., K)T. In our experiments, we set a 0.05 and = 1.1. The procedure is: Source set: Sample 10, 000 instances from the training partition according to p and train a backbone classifier (ResNet-18 [22 48) for 100 epochs with standard fata-augmentation. ii) Validation set: Hold out 5, 000 labelled source instances, stratified by p. to estimate the empirical confusion matrix C. iii) Target set: Draw n' 10, 000 unlabelled instances from the test partition using probabilities q. These labels are revealed only for evaluation.
Graph construction on labels. For every dataset we embed the class names with the frozen CLIP ViT-B/32 text encoder [46). obtain {e]] c. 1R512, leyl2 = 1, and build e-eaaest-nnighhbw graph
[4 (K =10),
((i.j) ej among the nearest neighbors of e,}, k= (K = 100).
Edge weights are We exp (-lle, -,//////// with set to the median pairwise distance inside E. The resulting k--N graph is connected, so its unnormalised Laplacian L = - W satisfies DD( > O. For MNIST, where class names single digits, instead construct E from 4-NN in the Euclidean space of 128-d amultimate-layer features averaged over the training images.
Hyper-priors and inference. Gamma hyper-priors: 0g by ac by 1, giving vague Gamma(1, 1) on Ty and TC. Four independent HMC chains, each with 500 warm-up (NUTS) and 1,000 posterior iterations; deap-frog step-size adaptively tuned. Block Newton-CG inner optimizer:

---

Table Label shift estimation and downstream performance. Lower better for l| qll1: higher is better for cost-correction accuracy. Best results are bold. + shows one bootstrap standard eтror. (1 000 resamples).
MNIST (K=10)
CIFAR-10 (K=10)
CIFAR-100 (K=100)
Method
| 411
Acc f
(d-9l114
Acc
|4 14-9111 9/1
Acc f
BBSE
0.002
0.012
0.781
1.05
0.690
EM
0.935 0.015
0.008
0.034 0.012
2.10
0.632
RLLS
0.016
0.010
0.00++00000
0.003
0.712 + 0.006
MLLS
+010+000000
0.002
0.052
0
0.703
0.734 + 0.006
GS-B*SE
0.002 + 0.001
0.986 0.002
0.025 + 0.004
0.844 + 0.003
0.22 + 0.02
0.783 0.005
tolerance 10 10-4, at most eight iterations per Newton step, stop when the relative change of the joint log-density falls below 10 All routines implemented in PyMC and run on single NVIDIA T4.
Baselines. We compare against a) plug-in BBSE [39. b) the EM-style Saerens re-weighting 44), c) RLLS (7) with fg-regularisation and d) MLLS [8] tuned held-out split. All baselines receive the same C and target predictions h(z). Table 2 summarizes the baseline methods and their key
ideas, including our method.
Evaluation. We report prior-error l gl1 and downstream accuracy after Saerens likelihood correction using the estimated priors. Significance is assessed with 1,000 paired bootstrap resamples of the target set.
7.2 Main Empirical Findings
Table 3 compares GSEB with four widely-used point estimators on three datasets.
Sharper prior estimates. Across all datasets GE reduces the & error lq~ by large margins: MNIST already a benign scenario error falls from 0.010 (best baseline, MLLS) to 0.002 (x5 improvement). ii) CIFAR-10 (K=10))richer richer images and heavier label skew- error halves from 0.052 0.025, CIFAR- 100 (K=100) the high-class-count regime- graph smoothing is essential: GS-B SSE reaches 0.22 versus 0.71. The advantage widens with K, confirming the benefit of borrowing strength along the label graph when per-class counts are scarce.
Better downstream accuracy. Feeding the estimated priors into Saerens post-processing improves final accuracy in proportion the quality of the prior. GS-B attains 0.986 MNIST, 0.844 on CIFAR-10 10 and 0.783 on CIFAR- absolutee gains of +2.3.pp. +3.2,pp and +4.9,pp over the strongest -on-Baa competitor (MLLS) on the respective datasets.
8 Conclusion
We presented GS-B graph- smoothed Bayesian generalization of the classical black-box shift estimator. By tying both the target prior q and every column of the confusion matrix C together through Gaasscin hierarchy, the model simultancously i) shares statistical strength across semantically related classes, ii) quantifies all uncertainty arising from finite validation and target samples, and admits scalable inference with either HMC or Newton-CG variational surrogate. We proved that the resulting posterior is identifiable, contracts at the optimal 1/2 rate, and that its class-wise variance decays inversely with the graph's 's algebraic connectivity Az(L)) robustness bound further shows that even with a misspecified graph the bias vanishes as N-1, Because our approach is pure post-proesssing layer that needs only frozen classifier, tiny labelled validation set, and a pre-computed label graph, it can be retro-fitted to virtually any deployed model.
Limitations and future work. i) Our current graph is built from CLIP or feature embeddings: learning the graph jointly with the posterior could adapt it to the task. ii) Although inference is already tractable, further speed-ups via structured variational approximations would make GS-B attractive for extreme-label settings. iïi) As declared in Section 7.1 our experiments used a single NVIDIA T4; scaling to larger datasets remains future work.

---

References
[1] Shotaro Akaho. The e-pea and m-pea: Dimension reduction of parameters by information geometry. In 2004 IEEE International Joint Conference Neural Networks (IEEE Cat. No. 04CH37541), volume 1, pages 129-134, IEEE, 2004.
[2] Shotaro Akaho and Kazuya Takabatake. Information geometry of contrastive divergence. In ITSI, pages 3-9, 2008.
[3] Mutasem K Alsmadi, Malek Alzagebah, Sana Jawarneh, Ibrahim ALmarashdeh. Mo- hammed Azmi Al-Betar, Maram Alwohaibi, Noha A Al-Mulla, Eman AE Ahmed, and Ahmad Al Smadi. Hybrid topic modeling method based on dirichlet multinomial mixture and fuzzy match algorithm for short text clustering. Journal of Big Data, I((1)688, 2024.
[4] Shun-Ichi Amari. Natural gradient works efficiently in learning. Neural computation, 10(2): 251-276, 1998.
[5] Shun-ichi Amari. Information geometry and its applications. volume 194. Springer, 2016.
[6] Shun-ichi Amari and Hiroshi Nagaoka. Methods of information geometry, volume 191. Ameri- Mathematical Soc., 2000.
[7] Kamyar Azizzadenesheli, Anqi Liu, Fanny Yang, and Animashree Anandkumar. Regularized learning for domain adaptation under label shifts. In International Conference on Learning Representations, 2019.
[8] Michael Betancourt. A conceptual introduction hamiltonian monte carlo. arXiv preprint arXiv: 1701.02434 2017.
[9] Michael Betancourt and Mark Girolami. Hamiltonian monte carlo for hierarchical models. Current trends in Bayesian methodology with applications, 79(30):2-4, 2015.
[10] Albert G Buckley. A combined conjugate-gradicn quasi-newton minimization algorithm. Mathematical Programming, 15(1):200-210, 1978.
[11] Olivier Caelen. A bayesian interpretation of the confusion matrix. Annals of Mathematics and Artificial Intelligence, 81 (1)))2229 450, 2017.
[12] Yee Seng Chan and Hwee Tou Ng. Word sense disambiguation with distribution estimation. In IJCAI, volume 5, pages 1010-5, 2005.
[13] Mayee Chen, Karan Goel, Nimit S Sohoni, Fait Poms, Kayvon Fatahalian, and Christopher Ré. Mandoline: Model evaluation under distribution shift. In International conference on machine learning, pages 1617-1629. PMLR, 2021.
[14] Li Deng. The mnist database of handwritten digit images for machine learning research [best of the web]. IEEE signal processing magazine, 29(6):14-114,, 2012.
[15] Yun Ding, Yanwen Chong, Shaoming Pan, and Chun-Hou Zheng. Class-inbalanced graph convolution smoothing for hyperspectral image classification. IEEE Transactions Geoscience and Remote Sensing. 62:1-18, 2024.
[16] Simon Duane, Anthony D Kennedy, Brian J Pendleton, and Duncan Roweth. Hybrid monte carlo. Physics letters B, 195(2):216-222, 1987.
[17] Luther Pfahler Eisenhart. Riemannian geometry, volume 19. Princeton university press, 1997.
[18] Saurabh Garg, Yifan Wu, Sivaraman Balakrishnan, and Zachary Lipton. A unified view of label shift estimation. Advances in Neural Information Processing Systems, 19:3290-3300 2020.
[19] Saurabh Garg, Nick Erickson, James Sharpnack, Alex Smola, Sivaraman Balakrishnan, and Zachary Chase Lipton. RIsbench: Domain adaptation under relaxed label shift. In International Conference on Machine Learning, pages 10879-10928. PMLR, 2023.
[20] Subhashis Ghosal, Jayanta K Ghosh, and Aad W Van Der Vaart. Convergence rates of posterior distributions. Annals of Statistics, pages 500-531, 2000.
10

---

[21] Heinrich W Guggenheimer. Differential geometry. Courier Corporation, 2012.
[22] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[23] Magnus R Hestenes, Eduard Stiefel, et al. Methods of conjugate gradients for solving linear systems. Journal of research of the National Bureau of Standards, 49(6))409 1952.
[24] Hideitsu Hino, Shotaro Akaho, and Noboru Murata. Geometry of em and related iterative algorithms. Information Geometry, 7(Suppl 1):39-77, 2024.
[25] Masanari Kimura. Generalized t-sne through the lens of information geometry. IEEE Access, 129619-129225, 2021.
[26] Masanari Kimura and Howard Bondell. Density ratio estimation via sampling along generalized geodesics on statistical manifolds. In The 28th International Conference on Artificial Intelligence and Statistics, 2025,
[27] Masanari Kimura and Hideitsu Hino. a-geodesical skew divergence. Entropy, 23(5):528, 2021.
[28] Masanari Kimura and Hideitsu Hino. Information geometrically generalized covariate shift adaptation. Neural Computation, 34(9):1944-1977, 2022.
[29] Masanari Kimura and Hideitsu Hino. A short survey on importance weighting for machine learning. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URLhttpp //openreview http:/vwwi.eeeeftfoeeeeeeee wwt/ffoumm http://frrmmmidIIXXXMM IdIidd= Survey Certification.
[30] Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, al. Wilds: A benchmark of in will distribution shifts. In International conference on machine learning. pages 5637-5664. PMLR, 2021.
[31] Bartosz Kotodziejek, Jacek Wesotowski, and Xiaolin Zeng. Discrete parametric graphical models with dirichlet type priors. arXiv preprint urXiv:2301.06058, 2023.
[32] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[33] Wolfgang Kühhnel. Differential geometry, volume 77. American Mathematical Soc., 2015.
[34] Serge Lang. Differential and Riemannian manifolds. Springer Science & Business Media, 1995.
[35] Patrice Latinne, Marco Saerens, and Christine Decaestecker. Adjusting the outputs of a classifier new priori probabilities may significantly improve classification accuracy: Evidence from multi-class problem in remote sensing. In ICML, volume 1, pages 298 305, 2001.
[36] John M Lee. Riemannian manifolds: introduction to curvature, volume 176. Springer Science Business Media, 2006.
[37] John M Lee. Introduction to Riemannian manifolds, volume 2. Springer, 2018.
[38] Jian Liang, Ran He, and Tieniu Tan. A comprehensive survey on test-time adaptation under distribution shifts. International Journal of Computer Vision, 133(1):31-66 2025.
[39] Zachary Lipton, Yu-Xiang Wang, and Alexander Smola. Detecting and correcting for label shift with black box predictors. In International conference on machine learning, pages 3122-3130. PMLR, 2018.
[40] Noboru Murata, Takashi Takenouchi, Takafumi Kanamori, and Shinto Eguchi. Information geometry of u-boost and bregman divergence. Neural Computation, 16(7):1437-1481 2004.
[41] Tuan Duong Nguyen, Marthinus Christoffel, and Masashi Sugiyama. Continuous target shift adaptation in supervised learning. Asian Conference on Machine Learning, pages 285-300.
PMLR, 2016.

---

[42] Sunghyun Park, Seunghan Yang. Jaegul Choo, and Sungrack Yun. Label shift adapter for test- time adaptation under covariate and label shifts. Proceedings of the IEEE/CVF International Conference Computer Vision, pages 16421-16431, 2023.
[43] Peter Petersen. Riemannian geometry, volume 171. Springer. 2006.
[44] Joaquin Cittfonero-Candela. Masashi Sugiyama, Anton Schwaighofer, and Neil D Lawrence. Dataset shift in machine learning. Mit Press, 2022.
[45] Stephan Rabanser, Stephan Günnemann, and Zachary Lipton. Failing loudly: An empirical study of methods for detecting dataset shift. Advances in Neural Information Processing Systems, 32, 2019.
[46] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et Learning transferable visual models from natural language supervision. In International conference machine learning.
pages 8748 8748-8763. PmL.,, 2021.
[47] Marco Saerens, Patrice Latinne, and Christine Decaestecker. Adjusting the outputs of a classifier to new priori probabilities: simple procedure. Neural computation. 14(1):21-41) 2002.
[48] Muhammad Shafiq and Zhaoquan Gu. Deep residual learning for image recognition: A survey. Applied sciences, 12(1 19972, 2022.
[49] Gavin Simpson. First steps with mrf smooths. From the Bottom of the Heap, 2017.
[50] Surya T Tokdar and Jayanta K Ghosh. Posterior consistency of logistic gaussian process priors density estimation. Journal of statistical planning and inference, 137(1):34 42, 2007.
[51] Antonio Torralba and Alexei Efros. Unbiased look at dataset bias. In CVPR 20/1, pages 1521-1528. IEEE, 2011.
[52] Aad W Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.
[53] Changkun Ye, Russell Tsuchida, Lars Petersson, and Nick Barnes. Label shift estimation for class-imbalance problem: A bayesian approach. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 1073-1082, 2024.
[54] Kun Zhang, Bernhard Schölkopf, Krikamol Muandet, and Zhikun Wang. Domain adaptation under target and conditional shift. In International conference on machine learning, pages 819-827, Pmlr, 2013.
12

---

A Proofs
Proof for Lemmal 7 Fix an index i {I,..., K and an arbitrary source sample size n² n 1.
Denote N (Ni. R Under parameter pair (C, q), have
K
K N
Pr (N k)
n
II J=1
kE
k2
k1
li!
Under (C", the same vector has pmf
K
Pr (N = k)
ki
kg
f=1
By the assumption, these two pmfs coincide for every integer vector ls with the given total Canceling the multinomial coefficient yields
K
K C., VKEN", ==1
C ==1
Σ kg =n.
(11)
Pick the K specific count vectors
(0...,,,n,, 0). t= I...,,
Plugging k0 into Eq. 11 gives
C = 15lsk.
Because n 2 1, taking the n-th root yields Ct = C2 Since i is arbitrary, Eq. 11 implies == C². Therefore, equality in distribution the target count vector N implies the underlying multinomial parameter vectors must coincide: Cq Cq'. Under the standing assumption that C is invertible, it gives q = q'. Hence, the mapping
(q. C) [Law of (NF,...., N.. N)
injective under the stated positivity and invertibility conditions.
Proof for Lemma 2 The prior on (q. C') is the push-forward measure of a product Gaussian:
(0. 0k) ~ N (0, & N (o.(
(12)
under the smooth, one-to-one map
T: (0..1....,,0) + ( (()) C.k ((xx))
where
RK K is the softmax map. Here, injectivity holds because the log-odds repre- sentation is unique once the sum-zero constraint is imposed. Because L is positive definite on the subspace
H [UERK. o T =}
the Gaussian distributions in Eq. 12 have everywhere positive Lebesgue densities that subspace. Formally, for the target prior block
()) (2x) (det -T (det*rr
(L') 1/2 exp
2 T LB
TT
where det the product the positive eigenvalues. Since Tq L is non-singular on H. (0) for every 0 H. Analogous positivity holds for each (ox)
13

---

The softmax sb is C with non-zero Jacobian everywhere on H. Therefore, T is a C diffeomor- phism between
H X ... x x and its image = A K- x (AK-1)K,
K copics
with the Jacobian determinant is II. q. (1-E.) =... and hence non-zero, preserving positivity,
Hence I" preserves positivity of densities, the image measure II on S posesses density
x (q. = (v (q))
II fc, (v (C.)).
with respect to the product Lebesgue measure simplices. Since each factor is positive everywhere, o (q, C*) > for every (q. C) S. Because (go, Co) lies in the interior of and i is continuous and strictly positive, there exists
:=
min T(q. C) 0. (q.
Note that the minimum exists by compactness of the closed c-ball. Furthermore, the Euclidean volume of the ball, under the ambient dimension dim A K-1 finite and strictly positive:
for q and K K(K- 1) for C,
Vol (q. Co)) = cKa_ k2-1 >0, 0,
where is the volume if the unit ball in RR. Hence,
(B. Co)) = / C.) Co)
T(q. C)daa C)
2 moo Co)) > 0.
This concludes the proof.
Proof for Proposition
7 For every v) > 0,
== (q. DRL(P(g..c)) (o) n
where P(g.c) denotes the K(K + 1) dimeensioaa multinomial law of the complete data. Because the parameter space is finite- dintesinnnii and smooth.
(1 C) (go. Co)l 5(n) = (,.)
< n
with deterministic radius 8(n) 7) 4 0. This follows from second-order Taylor expansion of
the multinomial log-likelihood around the interior point. Lemma 2 says that the prior puts strictly positive mass every Euclidean ball and hence on Un:
IIU))) 0,
Vn 0.
Let - (q. C) and 0 = (qu. Co). For any fixed c > 0, define the alternative set B, above. Because the model is i.i.d. exponential family (multinomials) of finite dimension, Ghosal al. 20 show there exist tests yp data + (0, satisfying, for some constants Cı C2 >> 0 independent of N,
(i) Po. (PN 1) < e -
(13)
suPOe Po(PN 0) $ N
Write the complete log-likeliine likeeiidl ratio as
dPe dPo.
(n) log (data)
K
Cj. Coj.s
Nolog (Cq)) (Cuqo))
Σ
N 3.
log
+ Σ
j=1
14

---

Let PN = 1 (1x(00) < -2cN), where E (0, c0) and c* is the minimized KL-divergence over Be:
inf DEL [Po, [P] > 0. OEB.
The above inequality is strict by Lemma D Chernoff bounds for sums of bounded log-likelihood ratios gives (i) in Eq. 13 Under any 0 E Be, the expected log- log-likelihood ratio equals -N WN-DkL[Pa ( I -c"N N. one-sided Hoeffdding inequality for sums of independent, bounded random variables then
yields (ii) in Eq. 13 with Co = (c* c)/2.
Therefore,
Fap Col, O,
II (Be data)
Ve >>
N
Because the metric ||(q. C) - (qo. Co) continuous, this convergence in outer probability equals convergence in probability, completing the proof.
Proof for Theorem 7 Put the log-odds vector for the target prior
K log Qk
= -01....,,0p 0K)) 0, = log qi
K
and for the i-th column the confusion matrix
K
1
Φ
0i log Cj.i
log Ck
K
k=
Each vector lives in the centered linear subspace H {v RR v 1 0} of dimension K 1. Define the global parameter
(0 TI.
R E ERd, d= (k- -
K2
The map V 7 - (q, C) given by component-wise softmax is C and has Jacobian of full rank everywhere on Rd. Hence, 1 (q, C') is a local diffeomorphism. We fix too corresponding to (go, Co). Let
(n) = log Pey (data)
K K
K log Cj. + Σ Ñ₂ log(CC)); j=1
N 33
where C' and q in the right-hand side are the softmax images of 17. Because each count is bounded by N and the mapping smooth, (n)n) twice countinuously differentiable a neighbourhood of no--
Compute the score vector and observed information:
K K
a
K
à N N - (Cogo))
(x(T))
ΣΣ
(N
n. Coj.)) on
log Cja + Σ
log( Cq)s On
1=1 i=
1=1
mo
(To) = -NN((n))
where F(mo)) is the Fisher information matrix of dimension d. Here, F(ro) positive defi- nite because (go, Co) is interior and Co is invertible (ensures different parameters yield different probability mass functions). The positive definiteness can be checked by observing that the Fisher information of finite multinomial family with parameters inside the simplex is positive definite and the Jacobian of y is full rank.
Set local parameter h = vN(n no). A second-order Taylor expansion yields the Local Asymptotic Normality (LAN) representation
1 h F(no) rk)(h).
(n + h/VN) (N(N)) h AN
2
15

---

with
A = VN
( ~ (0, F(oo),,
sup |(||=(())
[rw(h)] S O.
The convergence of AN N the multivariate central limit theorem for sums of independent bounded variables. Uniform control of ry follows from third derivative boundedness neighborhood of no--
In 17-oordinates, the Laplacian-Gaussian prior has density
1 0
x (n) exp
Le
TC
Φ
LΦs
p( TC).
where yp is strietly positive and smooth Gamma density. Because L is positive semi-definite on H, continuous and strictly positive in neighborhood of r7. Therefore, there exsit co > 0 and such that
π (n) 2 co.
whenever
|| - 11-77u12 S 8.
Consequently, under the true distribution
(N 70) E data) ~4 N AN, in -robbabiiibbbl
and for any M 0.
II (IIVN(n s70)
Plan-Co) 0.
M data
Because V is C with Jacobian (17o) of full rank, there exists constant Ko > such that, for all in neighborhood of no.
(v(n) ((ro))l 2 Ko n0l12.
Hence,
IT (By) data) S II (17 12 MM(KoV/N) data
Pan Go
0.
Because M > 0 is arbitrary, this limit verifies the claim of the theorem.
Proof for Corollary posterior density is
Consider the centred log-odds vector 0 E H for the target prior, Its conditional
p(0 data) x exp
(9)
NN
T L0
where
K Σ
N₂ log [C softmax(0)).)
Take any point 0" in 0 -all around 0g. By Theorem this contains essentially all posterior mass. Inside that ball Taylor expansion gives
ggdl 00
(0") NF++FOO +O
with F the Fisher information matrix. Hence the negative Hessian of the log-posterior satisfies
82
JN
,/ L0 (0*) Z NF + L ((N1/2)F.
002
For N beyond some No. the term dominated by NF, there exists co > 0 such that
JN ż No. Lg
16

---

Thus,
Co = [Noo + tg Lg
Because L has eigen-pair (0, 1) and eigenvalues AR 2 (2(L) on H. the restricted inverse satisfies
1
F 1
F + Tq [| Nco Tg)2(L)
F TQ)2(L)
F.
(14)
Cu.
For N 2 No, the second term dominates 1/(Tq>a(L)), and hence
2 f= K.
Var (arr S No
(15)
The softmax map 1 q has derivative
Do diag(g) qq"
Every entry of Do is bounded by 1/4 (attained at uniform prior), hence the operator obeys ||oo] s 1/2. For any random vector with covariance Σ,
Cov(a(()) DoEDo 1 11D0 1 E.
Applying the posterior distribution with bound 15 gives
1 Var(q:) S [Don( Varn(0.)
(16)
20
The constant co is Amin (F) which is independent of the graph but positive. Tightening Eq. 14 using the L, term, we keep only the (LD) contribution:
C2 A2(D)
Tq + Co
Var (0e) S (L) C, S
C2
To
Repeating the methad argument with this sharper bound scales Eq. 16 by the same 1/A (L). Set C = K(Tg /2)/e Then,
C
Varx( S \2(L) i= i.
which is precisely the claimed sample variance control.
Proof for Proposition 2 Write the complete-date log posterior (ignoring normalising constants)
(6) = ( (0) T LO,
where
K
(0) = Σ
N₂ log [(C o())),
1=1
Let O be the MAP with respect to the misspecified prior, and satisfies the score equation
(Ōx) LŌ =
(17)
Set the estimation error
A = ON - 00.
Taylor expansion of the gradient in Eq. 17 yields
V (0x) v (6.) 422(0) (0, AN RN,
- - + T L AN = Ve (66) Tg Lo + RN.

---

where Ry = Op A (|=)) because the third derivative of 'N is bounded on a neighbourhood of Og. Using |[N,] n' ; and by the Markov inequality.
(N Fu + Tq L) N
data] -Tq(L L.)0, Op
For quadratic priors and lon-con likelihoods the posterior is asymptotically normal, so the difference between posterior mean and MAP is O(N-1) [52]. Therefore
NN 0. E data] + +
- Fo + Tq (L
Lo)00 + Op(N"))
0N 0oll [(N + T) Tq |I -o)00ol + Op(N")).
This is the bound in Eq. in the proposition.
The sub-space H {or E R w 1x - is the (K - 1) dimensosia hyper-plane of vectors whose components sum to zero. orthogonal projection operator is the K K symmetric matrix { 1 1x, and the subtracted term exactly the scalar mean of replicated in every coordinate, making the result mean-zero. Because Fo ž 0 and L ž P2 the smallest eigenvalue of N Fo + Tq L is at least N Nmmin (Fo) + (LD).
PH I K 1 x11k because for any E RRK Px
Hence,
1
(NF + T1 Amin (NF + L)
N Nmmin (F) (L)
Combine them get inequality in Eq. completing the proof.
Proof of Theorem 2
Throughout the proof we fix an arbitrary interior point q Á and an arbitrary tangent direction v E Tya = fo E RK 11 v- 0}. To establish geodesic convexity suffices to show
FR FU Hess q
n/ Anmiiin ('minnFF) (Fo) + (2)) v. 9q v,
(18)
because the latter is the Rayleigh quotient form of the desired positive-definie bound. Recall the form of the negative log- oog-postrrio (constant terms omitted):
F(q)= n DKL [r Cq.
Tq L0. (1)(9)
2
Fa(g)
Accordingly
FR F = n' Hess FR Fik + Tq Hess FR Freg Hess 9
(19)
Write r(g)= = Cg, ri(g) E, Cijgj- For the multinomial log-likelihood term we have the usual identity
Hess g
FR Fin Fo = diag(r(q)) - r(g)r(q))
(20)
Indeed, start with Fix (4) = E, Ar log )(( and differentiate twice with respect to gj while keeping the tangent constraint 1 0 0, and we have Eq. (20 Now evaluate the quadratic form:
FR FagU r. Fov 8. Hess
Amin Fb) 11
(Rayleigh bound)
Amin Fb) Tv.
(21)
To relate the Euclidean norm || ||2 with the Fisher metric 9q notice that
(g v)
oT diag(g) -le, diaglg) 0.
(22)
Hence for every v,
| l = vT ('diag(q) diag(q) -v < (maxq:) (1 v) I ().
18

---

because < 1 inside the simplex. Thus, we have
n'' v0 Hess FR FiLU 2 ni' Mmi (Fo) Dq (V,
(23)
Recall f -0:) (= with 0, log 4i
Σj log 4z- Differentiating twice gives
Hess FR
Freg
(24)
where (()) [Kx(K-1) is the Jacobian 00/00 restricted to the tangent space. Concretely
(q) = diag( (q) (1 11 diag(q) Pr.
with Pr. = K
111 the projection onto TyA R-1
Applying Eq.
24 expand the quadratic form:
Hess
FR q
Freg (Jv) L (Jv)
2 (L) |
(Rayleigh bound on L)
= \2 J..
(25)
Because J(q) diag(q q) Pr one checks
r J
J JJ
v diaag()) g)(
Thus,
Tq V Hess q
FR Fieg 2 Ta>2 v),
(26)
and
v Hess
FR Fu 2 q
nn A'Amin (Fo) + (2))
(L) 9q (v)
Since the inequality holds for every A- the matrix inequality announced in the theorem follows, and the strong-com coong-convyxxty constant is
a n' Amin (Fo) + TT))(L)) 0.
Proof for Proposition 3 Write FiR (q) = ni ΣK Ar log r((
with r((g) E, Cyja- For j
{1...., K} we differentiate:
K
1
On Fik
n'
P:
On (g))
re(g)
1=1
1
=nn' >
Oij
rz(g)
nn' |CT r(q)
element-wise
(27)
so that in vector form
Vyfin - n' CT
(28)
r(q)
Recall -0.) with 0, log qi
R
ΣK
log qh. Let s(q) 1/4 En log gu. For j:
Og 5ūj
1
0, 0 diag (ej/)) - ((ee//))
(29)
Ji
K 4j
where (e,)1 = 8kg and q = (gi..... 9K)
Using the chain rule,
Tg 0g 0 L@)
0g Fag
2
Ta (0n, 0) LO
Tq (dag(e,//) - * 1(e,//)) L0
[ 11
Tq
where v
LO P.
(30)
19

---

In vector notation
vgFFgg Tq Pr L0.
(31)
and because Pr annihilates the 1-component may drop it inside the tangent space: Pr L since 1 is the null-eigenvector of L. On the simplex 94 1 acts as left-mutiplicationn by diag (g)
K-1, (followed by projection onto T. T automatic here because every gradient we computed is already centered). Hence
grad FR F(q)) = diag(q) V
diag(g)
(-n' n' CT r(q)
+ Tq diag((1))
diag(g) q) nn/C" 11 (-rrg)) + Tq L
(32)
which is exactly The rightmost expression is automatically orthogonal to because each bracketed term sums to 0; therefore the evolution does not leave the simplex:
1 (1) q:) - -1 grad FR F(g:)
Finally, inserting (9) in the natural gradient flow yields the replicator part t.j ans [CT A e/r]] + Tq [o confirming the announced epplictorr-Lplaciin dynamies.
20

---

B Background on Information Geometry
Table 4
summarizes the basic notations of information geometry required our study, make the manuscript self-contained. See textbooks in information geometry for more details [ 6
Table 4: Basic notations of information geometry.
Concept
Definition
Fisher-Ree Rao metric
( w) = Σ, Ey
on the open simplex.
9:
0, log qi
E, log {j (exponential-family natural
e-coordinates
K
parameters constrained to T A
m-coordinates
The usual probabilities (mixture parameters).
A subset whose image is affine in the corresponding coordi- nates; e.g. M Cq is m-flat because
e- m-flat sub-manifold
Cq is linear in
State ())g) Σ, log qi and (0 log Σ, e ing q = Voy and θ V
satisfy-
Dual flatness, potentials
For a point p and sub-manifold S, the minimizer of (pl(p)s) (m-projection) or DKL (slp) (e- (e-projection).
/ m-projection
A function whose restriction to every e-(resp. m-) geodesic
e- m-convex function
is convex in the ordinary sense.
For p. q. r where y is the m-projection of p onto and r E S, DKI.|plr] = Dr1. lpl,] + Dkt.(alr).
Generalized Pythagorean theorem
Natural gradient
grad F 99 1 Vig F.
21

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
We summarized our contributions, referring the corresponding sections.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are discussed in the conclusion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
22

---

Justification:
Full proofs for all statements are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Full experimental protocol is described in the experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
23

---

Answer: [Yes]
The codes for numerical experiments are submitted as the supplemental material.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cmm cc/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
//nips //nips.c//pil cccpublic/gut
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Full experimental protocol is described in experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
All results are reported with standard error.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The computing resource described in experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Question:
Answer: [Yes]
Justification:
The authors reviewed the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work is a foundational research.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
25

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All required libraries and resources correctly cited.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
26

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
27

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy fattps://neurd/: /00p://ccc...cc.eeeee/e////////0 for what should or should not be described.
28


Reviews:
[{"review_id": "a7qvXHvZ6Y", "reviewer": "Reviewer_TpHG", "summary": "By treating the confusion matrix as latent variables, this manuscript considers a fully Bayesian alternative to classical black-box label-shift estimators in the standard label-shift problem. The estimator can computed via HMC or Newton–conjugate-gradient optimizer. Numerical simulation and real-data experiments are run to test the proposed algortihm.", "questions": "1. In practice, how is the similarity graph constructed? I suppose such graph is usually noisy in real-world data. How will the noise affect the performance of the proposed algorithm?\n\n2. How is the computational complexity of the algorithm compared with the standard BBSE? I suppose sampling from and inferring with the posterior distribution can be extremely time consuming in such Bayesian setting?\n\n3. One of the motivation of the algorithm is to deal with the situation with rare classes. How does the algorithm perform in such case? I suppose in this case, the choice of prior distribution should affect the performance severely? Will it make the proposed algorithm less useful in such extreme condition?", "limitations": "Please see the questions above, especially on the question for the rare classes case.", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I'm not an expert in label shift or ML with graphs. So, probably I am not able to comment on the strengths and the weakness. Nevertheless, I do have a few questions regarding the submission. Please see next section.", "was_revised": true, "final_justification": "I would like to thank the author for their response. In this case, I would like to keep the score: 4 borderline accept.", "rebuttal": "First of all, we would like to thank you for your very constructive comments. The reviewer listed three questions with numbers, and we will respond to each of them.\n\n\n## 1. “How is the similarity graph built, and what if it is noisy?”\n\nWe build a k‑NN graph once from off-the-shelf embeddings (CLIP for CIFAR, averaged penultimate‑layer features for MNIST).  Noisy edges are inevitable, and that is exactly why the prior places a continuous Laplacian-precision $\\tau_q L$ instead of a hard constraint.\n\nSpecifically, Prop 2 (Robustness to Laplacian misspecification) quantifies the bias when $L \\neq L_0$:\n\n$$\n|| \\bar{\\theta}_N - \\theta_0||_2 \\leq \\frac{\\tau_q}{N \\lambda{\\min}(F_0) + \\tau_q \\lambda_2(L)}|| (L - L_0) \\theta_0 ||_2 + O_P(N^{-1}),\n$$\n\nso the bias shrinks as $N^{-1}$ and is damped when the graph is well‑connected ($\\lambda_2(L)\\uparrow$). Thus moderate graph noise merely slows convergence, and it does not break consistency.\n\nBased on your feedback, we realized that we could better clarify the motivation for our formulation by adding the following additional direct corollary.\n\n**Corollary. From Prop. 2 set $N\\to \\infty$ to bound the asymptotic bias by $\\tau_q\\lambda_2(L)^{-1}\\|(L-L_0)\\theta_0\\|$.**\n\nIn addition, we provide the additional ablations on graph construction.\nIn this experiment, we consider the following strategies.\n\n- CLIP-text (already in the current manuscript): cosine $k$-NN on text prompts.\n- Penultimate-image:  Euclidean $k$‑NN on frozen ResNet‑18 penultimate features (identical backbone as the classifier).\n- Random-embeddings: same sparsity pattern as CLIP‑text but edge weights i.i.d. $U(0, 1)$ (destroys semantics, preserves Laplacian spectrum scale).\n- Identity graph: $L = 0$,  switches the hierarchy off (reduces to independent logistic‑Normal prior and hence Bayesian BBSE with no smoothing).\n\nThe results are as follows.\n\n\n| dataset | graph | $\\|\\|\\hat{q} - q\\|\\|_1 \\downarrow$ | acc $\\uparrow$ |\n| --- | --- | --- | --- |\n| CIFAR-10 | CLIP-text | 0.025 $\\pm$ 0.004 | 0.844 $\\pm$ 0.003 |\n|  | penult-img | 0.029 $\\pm$ 0.005 | 0.839 $\\pm$ 0.004 |\n|  | random | 0.043 $\\pm$ 0.009 | 0.820 $\\pm$ 0.006 |\n|  | identity | 0.051 $\\pm$ 0.008 | 0.813 $\\pm$ 0.004 |\n|  | BBSE (freq.) | 0.112 $\\pm$ 0.015 | 0.781 $\\pm$ 0.004 |\n| CIFAR-100 | CLIP-text | 0.22 $\\pm$ 0.02 | 0.783 $\\pm$ 0.005 |\n|  | penult-img | 0.27 $\\pm$ 0.03 | 0.771 $\\pm$ 0.006 |\n|  | random | 0.46 $\\pm$ 0.05 | 0.735 $\\pm$ 0.009 |\n|  | identity | 0.70 $\\pm$ 0.07 | 0.730 $\\pm$ 0.010 |\n|  | BBSE (freq.) | 1.62 $\\pm$ 0.05 | 0.690 $\\pm$ 0.006 |\n\n**Remarks**\n- Any connected graph ($\\lambda_2(L) > 0$) already helps over the frequentist point estimate; cf. the “random” line.\n- The more task-aligned the similarity (CLIP > penult-img > random), the lower the bias term.\n- The identity graph reproduces Bayesian BBSE with no smoothing and is almost identical to MLLS. Its gap to CLIP shows the specific benefit of our graph-coupled hierarchy.\n\n**Why do the graph ablations behave as the above?**\n\nRecall the posterior variance bound we already proved:\n\n$$\n\\text{Var}(q_i \\mid \\text{data}) \\leq \\frac{C}{\\lambda_2(L)N},\n$$\n\nwhich holds for **any connected graph**.\n\nIf we write the mean-squared error as\n\n$$\n\\mathbb{E}[(\\tilde{q}_i - q_i)^2] = (\\mathbb{E}[\\tilde{q}_i] - q_i)^2 + \\text{Var}(\\tilde{q}_i),\n$$\n\nthen, it shows the variance term shrinks by a factor $1 / \\lambda_2(L)$.\n\nEven a $k$-NN graph whose edge weights are i.i.d. $\\mathcal{U}(0, 1)$ has, with high probability,\n\n$$\n\\lambda_2(L_{\\text{random}}) \\gtrsim c\\frac{k}{K},\n$$\n\nfor $k \\geq c’ \\ln K$.\nHence a purely random graph already cuts the class-wise standard error by $\\sqrt{K / (ckN)}$ compared with the identity graph $\\lambda_2 = 0$. This explain why the “random” row in the ablation table still beats the deterministic frequentist BBSE (it keeps all the variance relief while paying only a bias penalty).\n\n\n## 2. *“Computational complexity vs. vanilla BBSE?”*\n\nWe measure work in floating-point operations (flops) and write $K$ = number of classes and $|E|$ = number of graph edges. \n\nFor the $k$-nearest neighbor graphs we use, $|E| = kK$ with a small, $K$-independent constant $k$ (4 for CIFAR‑10, 8 for CIFAR‑100).\n- Vanilla BBSE: The point estimator solves a single linear system $\\hat{q} = \\tilde{C}^{-1}\\tilde{r}$, where $\\tilde{C}\\in\\mathbb R^{K\\times K}$ is dense once any amount of Laplace or Tikhonov regularisation is applied. Gaussian elimination therefore costs $\\mathcal{O}(K^3)$  flops and $\\mathcal O(K^{2})$ memory.\n- GS‑B$^3$SE (one Newton–CG sweep): Write $\\Phi = (\\phi_1,\\dots,\\phi_K)^\\top \\in \\mathbb{R}^{K\\times (K-1)}$ and $\\theta \\in \\mathbb{R}^{K-1}$, both constrained to the centered subspace $\\\\{v^\\top 1=0 \\\\}$. At each sweep we perform three algebraic operations:\n    - update each column $\\Phi \\leftarrow \\Phi - \\mathcal{H}_{\\Phi}^{-1}\\nabla\\mathcal{L}$,\n    - update $\\theta$ analogously, and\n    - Gamma shape/scale updates for $\\tau_q$, $\\tau_C$.\n\nAdding them and using $|E|=kK$, one sweep = $\\mathcal{O}(|E|K + K^2) - \\mathcal{O}(kK^2)$, and memory usage is $\\mathcal{O}(|E| + K^2)$.\n\n**Overall complexity.**\n\nThm. 2  establishes that $F(q)$ is $\\alpha$-strongly geodesically convex with $\\alpha = n’\\lambda_{\\min}(F_0) + \\tau_q \\lambda_2(L) > 0$. Consequently a back-tracking Newton method requires $T = \\mathcal{O}(\\ln 1/\\epsilon)$ sweeps to reach tolerance $\\epsilon$.\n\nHence the total complexity is\n\n$$\n\\mathcal{O}(kK^2 \\ln 1 / \\epsilon)\\quad \\text{vs.}\\quad \\mathcal{O}(K^3)\\ (\\text{Vanilla BBSE}).\n$$\n\nBecause $k$ is at most 8 and $\\ln 1/\\epsilon \\le 10$ in all our runs, the crossover happens already at $K\\ge 25$.\n\nHere, we report the wall-clock runtimes (single NVIDIA T4, PyMC 5.10, float32).\n\n| dataset | K | BBSE | MLLS | ours |\n| --- | --- | --- | --- | --- |\n| MNIST | 10 | 0.80 s | 1.12 s | 12.2 s |\n| CIFAR-100 | 100 | 2.88 s | 5.37 s | 54.5 s |\n\n## 3. “Behavior with very rare classes; isn’t everything prior-driven?”\n\nFor BBSE every class $i$ is treated in isolation: the plug-in variance satisfies\n\n$$\n\\text{Var}_{\\text{BBSE}}(\\hat{q}_i) = \\mathcal{O}((n_i^S)^{-1}),\n$$\n\nso as soon as the validation set contains $n_i^{\\mathrm S}=O(1)$ points the error explodes.\n\nIn our hierarchy the Gaussian-Markov random field ties all columns of the confusion matrix and the prior vector together through the graph Laplacian; information can therefore flow from frequent to infrequent neighbors. Algebraically this shows up in the curvature of the log-posterior:\n\n$$\n-\\nabla^2\\log p(q, C \\mid \\text{data}) = N F_0 + \\tau_q L + \\tau_C\\ \\text{blockdiag}(L,\\dots,L),\n$$\n\nwith the data Fisher block $N F_0$ pooling global target counts,  and the prior blocks injecting $\\lambda_2(L)$-weighted curvature even when $n_i^{\\mathrm S}=0$.\n\nCorollary 1 states, for any class $i$,\n\n$$\n\\mathrm{Var}(q_i) \\leq \\frac{C}{\\lambda_2(L)N’}.\n$$\n\nThus the *worst-case* posterior variance still decays like $N^{-1}$, and the only penalty for a vanishing $n_i^{\\mathrm S}$ is the $1/\\lambda_2(L)$ factor, i.e. how well the rare label is connected to the rest of the ontology.\n\n**Specifically, we can analyze the algorithms under a Zipf-like class-frequency law**.\n\nSuppose that source class priors follow a Zipf law\n\n$$\np_i = \\frac{i^{-b}}{H_{K,b}}, \\quad H_{K,b} \\coloneqq \\sum^K_{j=1}j^{-b},\\ b > 1.\n$$\n\nThe labelled-source sample sizes are therefore\n\n$$\nn_i^S = N_S p_i = N_S \\frac{i^{-b}}{H_{K,b}}, \\quad N_S = \\sum_j n_j^S.\n$$\n\nWrite $N = N_S+n’$ with $N_S/N\\to\\rho\\in(0,1)$. Target priors $q$ are arbitrary but $\\min_i q_i>0$, and the frozen classifier's confusion matrix $C$ is assumed invertible with condition number $\\kappa:=||C^{-1}||_2 || C ||_2<\\infty$.\n\nDenote $\\hat{C}$ and $\\hat{r}$ the empirical confusion matrix and target prediction histogram. Linearizing the BBSE estimator around the truth gives the usual delta-method expansion:\n\n$$\n\\hat{q} - q = - C^{-1}(\\hat{C} - C) q + C^{-1}(\\hat{r} - r) + R_N,\n$$\n\nwith $||R_N||_2 = o(N^{-1/2})$.\n\nHere, $\\hat{r} \\sim \\text{Mult}(n' r)$ with $r= C q$, and hence\n\n$$\n\\text{Var} \\bigl([ C^{-1}(\\hat{r}- r)]_i \\bigr) =  \\frac{1}{n'} e_i^{\\top} C^{-1} \\bigl[\\mathrm{diag}(r) - r r^{\\top}\\bigr] (C^{-1})^{\\top} e_i \\leq  \\frac{\\kappa^2}{4n'}.\n$$\n\nFor label $i$ the column $\\hat{C_{\\cdot, i}}$ is a multinomial vector with size $n^S_i$ and mean $C_{\\cdot,i}$. Let\n\n$$\n\\Delta_i \\coloneqq \\hat{C_{\\cdot,i}} - C_{\\cdot,i}, \\quad \\text{Cov}(\\Delta_i) = \\frac{1}{n_i^S} \\left[\\text{diag}(C_{\\cdot,i}) - C_{\\cdot,i}C_{\\cdot,i}^\\top \\right].\n$$\n\nBecause only column $i$ depends on $n_i^{\\mathrm S}$, its contribution to the target‑prior error is\n\n$$\nC^{-1}\\Delta_i q_i \\Longrightarrow \\text{Var}([C^{-1}\\Delta_i q_i]_j) \\leq \\frac{\\kappa^2 q_i^2}{4n_i^S}.\n$$\n\nFor a **rare label $i$** we typically have $n_i^S \\ll n’$, and we obtain\n\n$$\n\\mathbb{E}[(\\hat{q}_i - q_i)^2] = \\mathcal{O}(i^b / N) \\quad (\\text{Vanilla BBSE}).\n$$\n\nThus the MSE deteriorates polynomially in the rank $i$.\n\nFor our graph-smoothed Bayesian estimator, on the other hand, from Cor.1 and Prop.2 we have\n\n$$\n\\mathbb{E}[(\\tilde{q}_i - q_i)^2] = \\frac{C}{\\lambda_2(L)N} + O(N^{-2}).\n$$\n\nThus, the risk no longer depends on the tail exponent $b$ or the rank $i$."}, {"review_id": "Y7Ultw37JQ", "reviewer": "Reviewer_b22X", "summary": "This paper proposes a new method called GS-B³SE to address a practical problem in machine learning: label shift. This problem refers to a scenario where the class proportions (P(y)) change between the training and test sets, while the class-conditional feature distributions (P(x|y)) remain the same.\n\nExisting black-box methods (like BBSE) typically provide only a single point estimate, which makes them sensitive to sampling noise and completely ignores the potential semantic similarity between different classes (e.g., 'cat' and 'dog' are more similar than 'cat' and 'car').\n\nThe authors' core contribution is a fully Bayesian framework to address these issues. They don't just estimate a single target distribution q; instead, they introduce probabilistic priors for both the target distribution q and the classifier's confusion matrix C. The most crucial step is their use of a pre-constructed \"class similarity graph\" to impose a smoothing constraint on these priors. This graph structure allows semantically similar classes to \"borrow\" information from each other during parameter estimation. The benefit of this approach is that the model can better handle classes with sparse data, and the resulting estimates are more robust due to the consideration of uncertainty.", "questions": "- Regarding Graph Quality and Sensitivity: The model's performance appears to be highly dependent on the pre-constructed graph. To better understand this dependency, could you conduct some \"destructive\" experiments? For instance, how much does performance degrade when using a lower-quality graph (e.g., a k-NN graph generated from random embeddings)? This would help us more intuitively understand the practical significance of the robustness bound in Proposition 2.\n\n- Regarding Computational Efficiency: Thank you for the detailed experiments. Could you supplement them with the actual wall-clock runtimes for GS-B³SE and the main baselines (e.g., MLLS, BBSE)? This comparison would be particularly valuable for the CIFAR-100 dataset (with K=100) and would allow potential users to better weigh the trade-off between improved accuracy and computational cost.\n\n- Regarding Model Design Choices: As mentioned earlier, you chose to smooth the column vectors of the confusion matrix. Could you elaborate on the intuition behind this design? Did you consider or experiment with other smoothing approaches, such as smoothing the row vectors? Is there theoretical or empirical evidence to suggest that smoothing the columns is the superior choice?", "limitations": "The limitations are discussed in the conclusion section.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n- The idea of introducing a graph structure into label shift estimation and innovatively using it to simultaneously smooth the priors for both the target distribution q and the confusion matrix C is very clever.\n\n- The theoretical analysis is robust. Furthermore, the paper interprets the method from an information geometry perspective, which undoubtedly adds depth to the work.\n\n- The paper is written clearly, making it easy for readers to follow the authors' line of thought.\n\n## Weaknesses\n\n- The entire model's core advantage is built upon the pre-given class similarity graph, L. This graph is constructed using embeddings from a pre-trained model (like CLIP) and remains fixed. This raises a significant question: To what extent does the quality of this graph determine the model's performance ceiling? What happens if the semantic similarity captured by the embeddings does not align with the classifier's confusion patterns? Although the paper analyzes the model's robustness to an inaccurate graph in Proposition 2, the bias term ||(L-L0)θ0|| remains, and it's unclear to the reader how large this term might be in practice. Positing graph learning as future work is reasonable, but this is indeed a core limitation of the current method.\n\n- Model inference relies on HMC sampling or a block Newton-CG optimizer. HMC is notoriously slow, especially for high-dimensional posteriors. While the authors mention a \"fast\" Newton-CG scheme, they provide no comparison of model runtimes in the experimental section. For a module positioned as a \"pure post-processing\" step, its practicality diminishes if its computational overhead is orders of magnitude higher than baselines. Its scalability, especially as the number of classes K becomes large (e.g., on CIFAR-100), is a question that needs to be answered.\n\n- The model assumes that the columns of the confusion matrix C are similar because \"columns corresponding to neighbouring predicted classes exhibit similar shape.\" Column i of C, C_:,i, represents the probability distribution over predicted labels for a sample whose true class is i. Why should one assume that the predicted distribution for a true 'truck' is similar in shape to the predicted distribution for a true 'bus'? While plausible, this is not self-evident. An alternative approach, such as smoothing the rows of C, seems equally plausible (i.e., for a given predicted label like 'truck', the distribution of its true source labels is similar to that for 'bus'). A more detailed discussion and justification for this specific design choice would be beneficial.", "was_revised": true, "final_justification": "Overall, the rebuttal has strengthened the paper by clarifying theoretical underpinnings and providin new data. While the practical trade-offs regarding the dependency on high-quality graphs for peak performance and the increased computational cost remain relevant points for discussion, the core contributions of the paper are sound and well-defended. The rebuttal has successfully addressed the most critical theoretical questions, even if some practical limitations persist.", "rebuttal": "We would like to express our utmost appreciation for your very detailed comments on our manuscript.\n\n## Graph quality & sensitivity\n\nRecall Prop. 2, the following table summarizes the bias and variance of vanilla BBSE versus Bayesian shrinkage.\n\n| estimator | bias | variance (per class) |\n| --- | --- | --- |\n| vanilla BBSE | 0 (in expectation) | $\\text{Var}(\\hat{q}_i) = O(\\kappa_i^{-2} / N)$ |\n| ours | $b_i = \\frac{\\tau_q}{N \\lambda_{\\min}(F_0)} + \\tau_q \\lambda_2(L)[(L - L_0)\\theta_0]_i$ | $\\text{Var}(\\bar{q}_i) \\leq \\frac{C}{\\lambda_2(L)N}$ |\n\nHere, $\\kappa_i$ is the $i$-th sensitivity of the matrix inverse, which can be tiny for rare classes, hence the variance blows up. Thus\n- Vanilla BBSE is unbiased but pays no attention to sampling noise, and its variance grows like the squared condition number of $\\tilde{C}$.\n- Bayesian shrinkage version trades a bit of bias $b_i$ for a potentially huge reduction in variance. Specifically, amplitude factor is zero when the graph is correct, and otherwise it measures how much the misspecified graph distorts $\\theta_0$ along non-null Laplacian directions. In addition, damping $N^{-1}$ and $\\lambda_2(L)$ ensure the bias decays with i) more data and ii) greater algebraic connectivity. That is, even for a badly misspecified graph the leading term cannot exceed $\\tau_1 / (N \\lambda_{\\min}(F_0))||\\theta_0||_2$, i.e., the same order as the frequentist standard error.\n\nBelow, we report the additional experimental results on the edge-corruption study.\n\n| Dataset | K | Corruption rate $\\rho$ | Saerens-corrected acc |\n| --- | --- | --- | --- |\n| MNIST | 10 | 0.00 | 0.986 |\n|  |  | 0.25 | 0.982 |\n|  |  | 0.50 | 0.977 |\n|  |  | 0.75 | 0.971 |\n|  |  | 1.00 | 0.961 |\n| CIFAR-100 | 100 | 0.00 | 0.783 |\n|  |  | 0.25 | 0.778 |\n|  |  | 0.50 | 0.769 |\n|  |  | 0.75 | 0.752 |\n|  |  | 1.00 | 0.735 |\n\n**Protocol.** We start from the CLIP-derived $k$-NN graph $L_0$ (k = 4 for K = 10, k = 8 for K = 100).  A corruption level $\\rho$ means we randomly re‑wire $\\rho\\cdot |E|$ undirected edges (preserving degrees); the resulting Laplacian is L.  All other hyper-parameters are kept fixed.  \n\n**What does a “completely random” graph do?**\n\nIn the above table, $\\rho = 1.00$ means the completely random graph, but the resulting performance is still competitive against MLLS or other methods. To understand this observation, we can give the following discussion.\n\nTake the Laplacian $L$ obtained by connecting each label to $k$ random neighbors (uniform among the other $K - 1$ labels). Then,\n1. For an Erdős–Rényi‑like graph the second eigenvalue satisfies $\\lambda_2(L) \\approx k$ with high probability, so the variance bound $\\text{Var}(\\bar{q}_i) \\leq C / \\lambda_2(L)N$ is smaller than for the identity-Laplacian ($\\lambda_2 = 0$). In other words, random edges provide extra shrinkage.\n2. Because the edge directions are symmetric, each row of $L - L_0$ has positive and negative entries that tend to cancel when dotted with the centered log-odds $\\theta_0$: $\\mathbb{E}[(L - L_0)\\theta_0] = 0$, and the random fluction has magnitude $O_P(1)$. Therefore, $||b_i|| = O_P(N^{-1})$, i.e., the bias is the same order as the stochastic error we cannot avoid anyway.\n3. Putting the pieces together, we have the following which is precisely the rare-class / ill-conditioned regime where BBSE collapses.\n\n$$\nb_i^2 + \\text{Var}(\\bar{q}_i) \\ll \\text{Var}(\\hat{q}_i) \\quad \\text{when $\\lambda_2(L) \\gg 1$ or $\\kappa_i^{-2} \\ll 1$}.\n$$\n\nTherefore, even though the random graph carries no semantic signal, its connectivity slashes variance enough to compensate for the negligible $N^{-1}$ bias, so the total error remains well below BBSE.\n\nIn addition, we provide the additional ablations on graph construction.\n\n- CLIP-text (already in the current manuscript): cosine $k$-NN on text prompts.\n- Penultimate-image:  Euclidean $k$‑NN on frozen ResNet‑18 penultimate features (identical backbone as the classifier).\n- Random-embeddings: same sparsity pattern as CLIP‑text but edge weights i.i.d. $U(0, 1)$ (destroys semantics, preserves Laplacian spectrum scale).\n- Identity graph: $L = 0$,  switches the hierarchy off (reduces to independent logistic‑Normal prior and hence Bayesian BBSE with no smoothing).\n\n| dataset | graph | $\\|\\|\\hat{q} - q\\|\\|_1 \\downarrow$ | acc $\\uparrow$ |\n| --- | --- | --- | --- |\n| CIFAR-10 | CLIP-text | 0.025 $\\pm$ 0.004 | 0.844 $\\pm$ 0.003 |\n|  | penult-img | 0.029 $\\pm$ 0.005 | 0.839 $\\pm$ 0.004 |\n|  | random | 0.043 $\\pm$ 0.009 | 0.820 $\\pm$ 0.006 |\n|  | identity | 0.051 $\\pm$ 0.008 | 0.813 $\\pm$ 0.004 |\n|  | BBSE (freq.) | 0.112 $\\pm$ 0.015 | 0.781 $\\pm$ 0.004 |\n| CIFAR-100 | CLIP-text | 0.22 $\\pm$ 0.02 | 0.783 $\\pm$ 0.005 |\n|  | penult-img | 0.27 $\\pm$ 0.03 | 0.771 $\\pm$ 0.006 |\n|  | random | 0.46 $\\pm$ 0.05 | 0.735 $\\pm$ 0.009 |\n|  | identity | 0.70 $\\pm$ 0.07 | 0.730 $\\pm$ 0.010 |\n|  | BBSE (freq.) | 1.62 $\\pm$ 0.05 | 0.690 $\\pm$ 0.006 |\n\n**Remarks**\n- Any connected graph ($\\lambda_2(L) > 0$) already helps over the frequentist point estimate; cf. the “random” line.\n- The more task-aligned the similarity (CLIP > penult-img > random), the lower the bias term.\n- The identity graph reproduces Bayesian BBSE with no smoothing and is almost identical to MLLS. Its gap to CLIP shows the specific benefit of our graph-coupled hierarchy.\n\n**Why do the graph ablations behave as the above?**\n\nRecall the posterior variance bound we already proved:\n\n$$\n\\text{Var}(q_i \\mid \\text{data}) \\leq \\frac{C}{\\lambda_2(L)N},\n$$\n\nwhich holds for **any connected graph**.\n\nIf we write the mean-squared error as\n\n$$\n\\mathbb{E}[(\\tilde{q}_i - q_i)^2] = (\\mathbb{E}[\\tilde{q}_i] - q_i)^2 + \\text{Var}(\\tilde{q}_i),\n$$\n\nthen, it shows the variance term shrinks by a factor $1 / \\lambda_2(L)$.\n\nEven a $k$-NN graph whose edge weights are i.i.d. $\\mathcal{U}(0, 1)$ has, with high probability,\n\n$$\n\\lambda_2(L_{\\text{random}}) \\gtrsim c\\frac{k}{K},\n$$\n\nfor $k \\geq c’ \\ln K$.\nHence a purely random graph already cuts the class-wise standard error by $\\sqrt{K / (ckN)}$ compared with the identity graph $\\lambda_2 = 0$. This explain why the “random” row in the ablation table still beats the deterministic frequentist BBSE (it keeps all the variance relief while paying only a bias penalty).\n\n\nSummarizing the above discussion, we obtain the following remark.\n\n**Shrinkage beats instability.** BBSE pays no price for bias but suffers large sampling variance, especially when classes are imbalanced and $\\tilde{C}$ is noisy. Graph-based Bayesian pooling, *even with arbitrary edges,* acts like a data-dependent ridge penalty that stabilises all estimates.\n\n## Computational cost\nTo address this point, we first summarize the per-iteration algebraic cost as follows.\n\n| operation | cost on $k$-NN graph | remarks |\n| --- | --- | --- |\n| vanilla BBSE | $O(K^3)$ once | dense LU factorisation of the $K\\times K$ confusion matrix. |\n| Newton-CG step for ours |  $O(\\|E\\|) \\+ O(K^2)$  | gradient is linear in $\\|E\\|$, Hessian-vector product needs one sparse Laplacian-matvec $O(\\|E\\|)$ plus one dense Jacobian-matvec $O(K^2)$. Conjugate-gradient converges in $O(\\sqrt{\\kappa})$ iterations, empirically $\\leq 5$. |\n| HMC leap-frog | same $O(\\|E\\|) + O(K^2)$ per gradient | trajectories of length 10-20 give effective sample size $> 200$ for every $q_i$. |\n\nTherefore the dominant term grows only quadratically in the class count $K$ (the sparse Laplacian never densifies), whereas BBSE’s one‑off inverse is cubic.\n\nNext, we report the wall-clock runtimes (single NVIDIA T4, PyMC 5.10, float32).\n\n| dataset | K | BBSE | MLLS | ours |\n| --- | --- | --- | --- | --- |\n| MNIST | 10 | 0.80 s | 1.12 s | 12.2 s |\n| CIFAR-100 | 100 | 2.88 s | 5.37 s | 54.5 s |\n\nAs you suggested, we believe these results help users to consider the accuracy-complexity trade-off.\n\n## Design choice\n\nThe identifiability relation used by all BBSE‑type estimators is $\\tilde{q} = Cq$, where $\\tilde{q} \\in \\Delta^{K-1}$ is the prediction histogram on the target domain, the unknown parameter $q \\in \\Delta^{K-1}$ is the target prior, and the $i$-th column $c_i = C_{\\cdot,i}$ is $c_i = [p(\\hat{h}(X) = j \\mid Y = i)]^K_{j=1}$. Here, only the columns $c_i$ multiply the unknown vector $q$, and the rows $r_j = C_{j:}^\\top$ never appear in the above, so they matter only if one later inverts $C$. Hence, any prior that tries to stabilize the estimation of $q$ should regularize the $c_i$’s, not the $r_j$’s.\n\nNext, write a first-order delta expansion of the posterior mean\n\n$$\n\\tilde{q} = q_0 + \\sum^K_{i=1}(F_0^{-1}e_i)\\langle \\delta c_i, e_i \\rangle + O_P(N^{-1}),\n$$\n\nwhere $F_0 = \\text{diag}(r_0) - r_0 r_0^\\top$ is the Fisher matrix of the multinomial likelihood for $\\tilde{q}$, $\\delta c_i = c_i = c_{0,i}$ denotes the estimation noise on the $i$-th column, and $e_i$ is the $i$-th standard basis vector.\nTaking variances and using independence of source and target samples,\n\n$$\n\\text{Var}(\\bar{q_k}) = \\sum^K_{i=1} [F_0^{-1}]^2_{ki}\\text{Var}(\\langle \\delta c_i, e_i \\rangle) + O(N^{-1}).\n$$\n\nThus,\n- if we Laplacian-shrink the columns $c_i$, it shows a direct variance reduction by a factor $(\\tau_C\\lambda_2(L))^{-1}$, exactly the bound proved in Cor. 1 of the manuscript, and\n- if we instead Laplacian-shrink the rows $r_j$, the random variable $\\langle \\delta c_i, e_i \\rangle = \\delta C_{i,i}$ does not get penalized, so the leading variance term is unaffected. In other words, row smoothing hardly helps for the quantity we ultimately care about, $q$.\n\n**Semantic interpretation**\n- Predictive columns $c_i$ capture how much class $i$ is confused with every other class in the frozen classifier. Two semantically close source classes (e.g., truck and bus) tend to produce similar confusion fingerprints, so a Laplacian on $i$-index is natural.\n- Rows $r_j$ describe where each predicted label actually comes from in the source distribution, a statistic that never appears in the above identifiability and is only weakly correlated with the target-prior calculation."}, {"review_id": "gb24KY2Dpa", "reviewer": "Reviewer_S2qe", "summary": "This paper focuses on the label shift problem, where the source and target domain share the same conditional distribution, $P_s (X│Y)=P_t (X|Y)$ but differ in class priors, $P_s (Y)≠P_t (Y)$. A common approach to this problem is the Black-Box Shift Estimator (BBSE) method, which estimate a confusion matrix C and an empirical target prior $P ̂_t (Y)$ from finite samples to recover the true target prior $P_t (Y)$ , as $P_t (Y)=C^(-1) P ̂_t (Y)$. However, BBSE ignores the finite sample noise and semantic structure information during estimation. Therefore, this paper proposes a hierarchical Bayesian model (In Line 133-134) to improve the BBSE method. \n\nIn this model, the authors introduce a similarity graph on labels and utilize the graph Laplacian as covariance matrix in the distributions of latent variables, like θ and $ϕ_i.$\nWith these latent variables θ and $ϕ_i$, the model can estimate both the empirical target prior $P ̂_t (Y)$ and the confusion matrix $C$, then the BBSE method can be applied to recover the true target prior.", "questions": "Please refer to the weaknesses part.", "limitations": "The proposed method is novel and theoretically solid. However, the empirical evaluation is not convincing. And the presentations have some flaws.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "- Strengths\n\t1. This paper proposes a novel method to improve BBSE, which couples the target prior and confusion matrix through a hierarchical Bayesian model.\n\t2. The underlying idea that replacing the point estimate of BBSE with Bayesian estimate to calculate the confusion matrix and empirical target prior is reasonable.\n\t3. The propose method is theoretically solid. In Proposition 2, the authors give an upper bound of estimation error for θ.\n\n- Weaknesses\n\t1. The main weakness lies in the experimental section. (1) Lack of ablation study. In Table 3, the proposed GS-B3SE outperforms other methods. However, it relies on CLIP embeddings to construct the similarity graph, and there is no ablation comparing alternative graph construction methods. Since CLIP [1] demonstrates strong zero-shot performance on datasets like CIFAR-10 (zs acc: 91.3) and CIFAR-100 (zs acc: 65.1), the authors should provide additional experiments to clarify whether the observed improvements stem from the proposed method itself rather than the use of CLIP features. (2) Inconsistent graph construction. In Lines 274–278, the method for constructing the similarity graph differs across datasets. For MNIST, image embeddings are used, whereas for CIFAR-10 and CIFAR-100, text embeddings are employed. This inconsistency raises important questions: How do these different types of features impact the final performance? For a given dataset, how should one decide which type of embedding to use for graph construction?\n\t2. In Line 110-112, the authors assume the number of predicted samples per classes, $n_i^S$, follows a multinomial distribution. However, since $n_i^S$ is actually non-negative, this assumption may not hold.\n\t3. In Proposition 2, the notation $θ_0$ is not defined.\n\t4. Proposition 2 illustrates how the minimum eigenvalue of the graph Laplacian influences the estimation error. However, it seems that label similarity (or edge weights) does not directly impact the estimation of variables. Can we directly optimize the graph Laplacian with specific constrains?", "was_revised": true, "final_justification": "The proposed method is novel and theoretically solid. Some concerns are addressed in rebuttal. However, the evaluation and utilization aspects are sill problematic. I raise my rating to slightly positive.", "rebuttal": "We would like to thank you for your very constructive comments. \n\n## Ablations on graph construction and the role of CLIP\n\nWe provide the additional ablations on graph construction.\n\nIn this experiment, we consider the following strategies.\n\n- CLIP-text (already in the current manuscript): cosine $k$-NN on text prompts.\n- Penultimate-image:  Euclidean $k$‑NN on frozen ResNet‑18 penultimate features (identical backbone as the classifier).\n- Random-embeddings: same sparsity pattern as CLIP‑text but edge weights i.i.d. $U(0, 1)$ (destroys semantics, preserves Laplacian spectrum scale).\n- Identity graph: $L = 0$,  switches the hierarchy off (reduces to independent logistic‑Normal prior and hence Bayesian BBSE with no smoothing).\n\nThe results are as follows.\n\n\n| dataset | graph | $\\|\\|\\hat{q} - q\\|\\|_1 \\downarrow$ | acc $\\uparrow$ |\n| --- | --- | --- | --- |\n| CIFAR-10 | CLIP-text | 0.025 $\\pm$ 0.004 | 0.844 $\\pm$ 0.003 |\n|  | penult-img | 0.029 $\\pm$ 0.005 | 0.839 $\\pm$ 0.004 |\n|  | random | 0.043 $\\pm$ 0.009 | 0.820 $\\pm$ 0.006 |\n|  | identity | 0.051 $\\pm$ 0.008 | 0.813 $\\pm$ 0.004 |\n|  | BBSE (freq.) | 0.112 $\\pm$ 0.015 | 0.781 $\\pm$ 0.004 |\n| CIFAR-100 | CLIP-text | 0.22 $\\pm$ 0.02 | 0.783 $\\pm$ 0.005 |\n|  | penult-img | 0.27 $\\pm$ 0.03 | 0.771 $\\pm$ 0.006 |\n|  | random | 0.46 $\\pm$ 0.05 | 0.735 $\\pm$ 0.009 |\n|  | identity | 0.70 $\\pm$ 0.07 | 0.730 $\\pm$ 0.010 |\n|  | BBSE (freq.) | 1.62 $\\pm$ 0.05 | 0.690 $\\pm$ 0.006 |\n\n**Remarks**\n- Any connected graph ($\\lambda_2(L) > 0$) already helps over the frequentist point estimate; cf. the “random” line.\n- The more task-aligned the similarity (CLIP > penult-img > random), the lower the bias term.\n- The identity graph reproduces Bayesian BBSE with no smoothing and is almost identical to MLLS. Its gap to CLIP shows the specific benefit of our graph-coupled hierarchy.\n\n**Why do the graph ablations behave as the above?**\n\nRecall the posterior variance bound we already proved:\n\n$$\n\\text{Var}(q_i \\mid \\text{data}) \\leq \\frac{C}{\\lambda_2(L)N},\n$$\n\nwhich holds for **any connected graph**.\n\nIf we write the mean-squared error as\n\n$$\n\\mathbb{E}[(\\tilde{q}_i - q_i)^2] = (\\mathbb{E}[\\tilde{q}_i] - q_i)^2 + \\text{Var}(\\tilde{q}_i),\n$$\n\nthen, it shows the variance term shrinks by a factor $1 / \\lambda_2(L)$.\n\nEven a $k$-NN graph whose edge weights are i.i.d. $\\mathcal{U}(0, 1)$ has, with high probability,\n\n$$\n\\lambda_2(L_{\\text{random}}) \\gtrsim c\\frac{k}{K},\n$$\n\nfor $k \\geq c’ \\ln K$.\nHence a purely random graph already cuts the class-wise standard error by $\\sqrt{K / (ckN)}$ compared with the identity graph $\\lambda_2 = 0$. This explain why the “random” row in the ablation table still beats the deterministic frequentist BBSE (it keeps all the variance relief while paying only a bias penalty).\n\n## Inconsistent graph construction (text vs. image embeddings)\n\nReviewer’s concern is “Why text on CIFAR but image on MNIST?”\n\n- On MNIST the class names are single digits (0, 1, 2, …), so CLIP-text gives almost zero variance (every digit is equally dissimilar). Image-space features do capture visual adjacency (e.g., 3 ↔ 8 ↔ 9)\n- On CIFAR the opposite holds: CLIP’s joint vision-language pre-training encodes high-level semantics missing from raw pixel features (e.g., “truck” closer to “bus” than to “cat”).\n\n## Multinomial assumption\n\nRecap the notation:\n- $n_i^S$:  \\# source-validation examples whose true class is $i$.\n- $N_i^S$:  \\# predicted labels produced by the frozen classifier $\\hat{h}$ among those $n_i^S$ examples.\n- $\\tilde{N}$: \\# predicted labels on the $n’$ unlabeled target points}.\n\nThese are integer-valued random vectors by construction. The standard sampling model is therefore\n\n$$\nN_i^S \\mid C \\sim \\text{Mult}(n_i^S, C_{\\cdot, i}), \\quad \\tilde{N} \\mid C, q \\sim \\text{Mult}(n’, Cq),\n$$\n\nwhere each realization of a multinomial distribution is, of course, a vector in $\\mathbb{N}^k$.\n\nThe assumption is therefore fully consistent with the data’s discrete nature.\n\nLater, we normalize these integers, and those are vectors in the simplex (non-negative reals summing to 1), not counts. The reviewer’s remark likely stem from seeing these normalized quantities and mistaking them fro the random objects modeled in the manuscript. We will add the explicit sentence to avoid ambiguity.\n\nFor completeness, if one wishes to work directly with the normalized vectors, two rigorously equivalent formulations are available:\n\n- Dirichlet-multinomial posterior: conditioning a Dirichlet prior on the multinomial counts yields a Dirichlet posterior for the probability vector.\n- Gaussian approximation (large $n$ delta method): $\\sqrt{n}(\\hat{r} - r) \\to \\mathcal{N}(0, \\text{diag}(r) - rr^\\top)$.\n\nOur Laplacian‑Gaussian hierarchy can be re‑expressed in either language.\n\n## Missing notation\n\nThroughout the manuscript, we use\n\n$$\n\\theta_i = \\log q_i - \\frac{1}{K}\\sum^K_{k=1}\\log q_k,\n$$\n\ni.e., the centered log-odds of a prior vector $q$.\n\nTherefore, $\\theta_0 = \\theta(q_0)$ is simply the centered log-odds of the true target prior $q_0$.\n\n## Edge weights don’t seem to matter; can we optimize $L$?\n\n**Why the weights do matter**\n\nThe upper bound we proved is\n\n$$\n\\frac{\\tau_q}{N \\lambda_{\\min}(F_0) + \\tau_q \\lambda_2(L)}||(L - L_0)\\theta_0||_2 + O_P(N^{-1}).\n$$\n\nHere,\n\n- Algebraic connectivity $\\lambda_2(L)$ (the smallest strictly-positive eigenvalue) appears in the denominator because it is the worst-case curvature of the quadratic penalty along any tangent direction.\n- The numerator contains the full matrix-difference $(L - L_0)\\theta_0$. This encodes the signed, edge-wise mismatch between our chosen weights and the unknown ground-truth graph $L_0$. If we perturb a single edge weight, it changes in direct proportion to that entry. Hence the pattern of weights does affect the bias term, and $\\lambda_2(L)$ merely the concise way of writing the spectral part of the denominator.\n\n**Can we optimize $L$?**\n\nYes, nothing in the hierarchy forbids putting a prior on the weights.\n\nTwo concrete extensions are feasible:\n\n- Empirical Bayes (plug-in refinement): treat $L$ as hyper-parameter and maximize the marginal likelihood $\\mathcal{L}(L) = \\log p(\\text{data} \\mid L)$. Because the posterior over $(q, C)$ is log-concave given $L$, the Laplace approximation $mathcal{L}(L) \\approx \\log p(\\text{data} \\mid \\hat{q}(L), \\hat{C}(L), L) - \\frac{1}{2}\\log \\det H^{-1}$ is cheap, and the Hessian $H$ is block-diagonal with Laplacian plus Fisher terms.\n- Fully Bayesian weight optimization: place independent Gamma or log-normal priors on each edge weight $w_{ij}$, and the quadratic form becomes $\\frac{\\tau}{2}\\sum_{(i,j)\\in E}w_{ij}(\\theta_i - \\theta_j)^2$. The conditional for $w_{ij}$ is conditionally log-Gaussian given $\\theta$, and a single Gibbs slice or HMC dimension is enough (dimensionality equals number of edges $\\ll$ number of parameters in $C$). The resulting chain mixes well because $w_{ij}$ appears only linearly in the quadratic exponent.\n\nWith random-weight priors identifiability still holds because the confusion-matrix block stays full-rank as before, $q$ remains on the simplex, and the new edge-weight parameters enter only through the positive-definite quadratic term, so the joint Fisher information expands to\n\n$$\n\\begin{aligned}\n\\begin{pmatrix}\nN F_0 + \\tau L(w) & 0; \\\\\n0 & \\text{diag}((\\theta_i - \\theta_j)^2)\n\\end{pmatrix},\n\\end{aligned}\n$$\n\nwhich is full-rank provided at least one $(\\theta_i - \\theta_j) \\neq 0$.\n\n**When does optimizing $L$ help?**\n\nUsing our upper bound, we can give a crisp sufficient condition:\n\n$$\n\\text{If}\\quad \\frac{||(L^{\\text{new}} - L_0)\\theta_0||}{\\lambda_2(L^{\\text{new}})} < \\frac{|| (L^{\\text{old} - L_0})\\theta_0||}{\\lambda_2(L^{\\text{old}})},\\quad \\text{then the asymptotic MSE bound tightens}.\n$$\n\nHence fine-tuning is valuable whenever a small decrease in mismatch can be achieved without collapsing algebraic connectivity."}, {"review_id": "Ho9aTygujt", "reviewer": "Reviewer_jfCb", "summary": "This paper proposes the ​​Graph-Smoothed Bayesian Black-Box Shift Estimator (GS-B$^3$SE)​​ for label shift adaptation. Traditional Black-Box Shift Estimation (BBSE) estimates target class priors by inverting a classifier’s confusion matrix but suffers from two limitations: 1) sensitivity to sampling noise​​: Error amplification with limited validation data; 2) ignored semantic relationships​​: Independent per-class estimation without statistical sharing.\n\nThe proposed GS-B$^3$SE is a fully probabilistic alternative that places Laplacian–Gaussian priors on both target log-priors and confusion-matrix columns, tying them together on a label-similarity graph. The key idea is to couple both the target log-prior vector and the columns of the confusion matrix through a Gaussian Markov random field defined on a label-similarity graph.", "questions": "I'm curious about the practical scenarios where this 'Label Shift' methodology would be most applicable. At its core, the paper addresses robust estimation of target class priors under distribution shift, formalized as a shift in P(Y) while assuming P(X∣Y) remains constant. This raises three key questions:\n\n- ​​Applicability Conditions​​: When is the label shift framework the appropriate modeling choice compared to other distribution shift paradigms? What diagnostic tests exist to validate its core assumption in real-world applications?\n\n- ​​Causal Implications​​: Does the formulation P(X∣Y)=constant implicitly assume Y→X causation? If so, how does this align with domains where features X may causally influence labels Y?\n\n- Practicality Concerns​​: The proposed solution appears computationally intensive relative to the problem's conceptual framework. I wonder whether the complexity is justifiable for deployment scenarios where predictions derive from fixed embeddings. (As a non-expert, I acknowledge this perspective may benefit from domain-specific context.)", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths​​:\n\n- Novel formulation​​: First unified Bayesian framework integrating graph regularization with confusion matrix uncertainty quantification.\n\n- ​​Theoretical rigor​​: Complete proofs for identifiability, optimal $N^{-1/2}$ convergence, and variance reduction scaling with algebraic connectivity $\\lambda_2(L)$.\n\n- Multidisciplinary insight​​: Information geometry analysis (Section 6) reveals how graph priors act as $e-$convex barriers, linking optimization to Riemannian dynamics.\n\nWeaknesses​​:\n\n- ​​Computational overhead​​: HMC requires 4 chains × 1.5k samples (NVIDIA T4) for K=100; wall-clock time for Newton-CG not benchmarked.\n\n- ​​Underutilized geometric insights​​: Natural gradient flow (Section 6.1) lacks empirical optimization comparisons versus EM/variational methods.", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for your very constructive comments.\n\n## When is the label-shift model appropriate?\n\nWe first summarize the major distribution shift settings as follows.\n\n| shift family | factorization | invariance assumption |\n| --- | --- | --- |\n| covariate shift | $P_{te}(X) \\neq P_{tr}(X)$ | $P(Y \\mid X)$ unchanged |\n| concept shift | $P_{te}(Y \\mid X) \\neq P_{tr}(Y \\mid X)$ | none |\n| label shift | $P_{te}(X \\mid Y) = P_{tr}(X \\mid Y)$ | class-conditional features stable |\n\nThe last column (our focus) includes\n\n- medical testing (pathogen prevalence rises or falls, but radiograph physics stays the same),\n- recommender or ad-click systems (item popularity drifts while the encoding of text or images stays fixed),\n- traffic scenes across seasons or geographies.\n\nThese settings share the property that collecting a handful of new labels is expensive, whereas unlabeled target images or clicks are plentiful.\n\n## A principled diagnostic test for label shift\n\nDefine\n\n- $\\hat{r} = 1 / n’$ (histogram of target predictions),\n- $\\hat{C}$ (empirical confusion on the validation split),\n- $\\hat{p}$ (empirical source prior).\n\nUnder the null $H_0 : q = p$ (no label shift),\n\n$$\n\\sqrt{n’}(\\hat{r} - \\hat{C}\\hat{p}) \\overset{d}{\\to} \\mathcal{N}(0, \\hat{C} \\text{diag}(\\hat{p})\\hat{C}^\\top).\n$$\n\nHence the likelihood-ratio ($\\chi^2$ statistic):\n\n$$\n\\chi^2_{\\text{BBSE}} = n’ (\\hat{r} - \\hat{C}\\hat{p})^\\top [\\hat{C} \\text{diag}(\\hat{p})\\hat{C}^\\top]^{-1}(\\hat{r} - \\hat{C}\\hat{p}) \\overset{H_0}{\\to} \\chi^2_{K-1}.\n$$\n\nBecause $\\hat{p}$ enters only through the plug‑in diagonal and the null does not constrain it, the usual Bartlett correction is unnecessary; asymptotically we retain an ordinary $\\chi_{K-1}^2$.\n\nIf the $p$-value is large, there is no statistical evidence for label shift, and no correction suffices.\n\nIf the null is rejected, we proceed to label shift correction approach, and the test is free because all three inputs $\\hat{r}$, $\\hat{C}$, $\\hat{p}$ are already computed.\n\n**Power of the diagnostic**\n\nLet $\\delta = q - p$ be the true prior change.\n\nUnder the alternative,\n\n$$\n\\chi^2_{\\text{BBSE}} \\overset{d}{\\to} \\chi^2_{K-1}(\\lambda), \\quad \\lambda = n’\\delta^\\top C^\\top [C \\text{diag}(p)C^\\top]^{-1}C\\delta > 0,\n$$\n\ni.e., a $\\chi^2$ distribution with non-centrality parameter $\\lambda$.\n\nThe test therefore has asymptotic power\n\n$$\n\\beta(\\alpha) = \\Pr [\\chi^2_{K - 1}(\\lambda) > \\chi^2_{K-1, 1-\\alpha}] \\overset{n’ \\to \\infty}{\\to} 1,\n$$\n\nwhenever $q \\neq p$, so even moderate sample sizes suffice to detect practically relevant prior changes.\n\n## Does label-shift require the causal arrow $Y \\to X$?\n\nThe assumption $P_{te}(X \\mid Y) = P_{tr}(X \\mid Y)$ is a statement about invariance of a conditional distribution, not about causal direction. It can arise in two distinct ways.\n\n- Causal: $Y \\to X$ and data-generation mechanism $f\\colon Y, \\epsilon \\mapsto X$ unchanged, only $\\Pr(Y)$ perturbed (an intervention on the root node $Y$ in Pearl’s SCM sense).\n- Anticausal, selection: $X \\to Y$ and labeling policy $\\Pr(Y \\mid X)$ unchanged, but we sub-sample on $Y$.\n\nHence, label shift is valid whenever i) the mapping $Y \\mapsto X$ (causal case) or the annotation policy $X \\mapsto Y$ (anticausal case) is stable across domains, and ii) only the base rate $\\Pr(Y)$ drifts.\n\nEither arrow therefore fits, the key is mechanism invariance, not direction.\n\nLet an SCM be\n\n$$\nY \\coloneqq g(U), \\quad  X \\coloneqq f(Y, V),\n$$\n\nwith exogenous $U, V$. A shift that changes $\\Pr(U)$ (but leaves $f$ fixed) yields exactly label shift.\n\nConversely, in an anticausal model\n\n$$\nX \\coloneqq h(W), \\quad Y \\coloneqq \\text{disc}(X) + \\xi,\n$$\n\nwe can obtain label shift by re-weighting samples according to $Y$ after data collection, again $P(X \\mid Y)$ is preserved.\n\n**How this perspective guides practice**\n\n- If you can argue mechanism stability, e.g., “the radiography device and organ physiology are unchanged while disease prevalence drifts” or “the feature extractor is frozen”, then label shift is defensible regardless of causal direction.\n- If mechanism stability is doubtful, run the $\\chi^2$ diagnostic and inspect mis-fit. Large residuals against both label shift and covariate shift tests indicate a more complex general shift.\n\nThe robustness bound in our manuscript is therefore agnostic to causal direction: only the invariance of $P(X\\mid Y)$ enters through $\\bm F_0$.\n\n## Computational cost\n\nWe measure work in floating-point operations (flops) and write $K$ = number of classes and $|E|$ = number of graph edges. \n\nFor the $k$-nearest neighbor graphs we use, $|E| = kK$ with a small, $K$-independent constant $k$ (4 for CIFAR‑10, 8 for CIFAR‑100).\n- Vanilla BBSE: The point estimator solves a single linear system $\\hat{q} = \\tilde{C}^{-1}\\tilde{r}$, where $\\tilde{C}\\in\\mathbb R^{K\\times K}$ is dense once any amount of Laplace or Tikhonov regularisation is applied. Gaussian elimination therefore costs $\\mathcal{O}(K^3)$  flops and $\\mathcal O(K^{2})$ memory.\n- GS‑B$^3$SE (one Newton–CG sweep): Write $\\Phi = (\\phi_1,\\dots,\\phi_K)^\\top \\in \\mathbb{R}^{K\\times (K-1)}$ and $\\theta \\in \\mathbb{R}^{K-1}$, both constrained to the centered subspace $\\\\{v^\\top 1=0 \\\\}$. At each sweep we perform three algebraic operations:\n    - update each column $\\Phi \\leftarrow \\Phi - \\mathcal{H}_{\\Phi}^{-1}\\nabla\\mathcal{L}$,\n    - update $\\theta$ analogously, and\n    - Gamma shape/scale updates for $\\tau_q$, $\\tau_C$.\n\nAdding them and using $|E|=kK$, one sweep = $\\mathcal{O}(|E|K + K^2) - \\mathcal{O}(kK^2)$, and memory usage is $\\mathcal{O}(|E| + K^2)$.\n\n**Overall complexity.**\n\nThm. 2  establishes that $F(q)$ is $\\alpha$-strongly geodesically convex with $\\alpha = n’\\lambda_{\\min}(F_0) + \\tau_q \\lambda_2(L) > 0$. Consequently a back-tracking Newton method requires $T = \\mathcal{O}(\\ln 1/\\epsilon)$ sweeps to reach tolerance $\\epsilon$.\n\nHence the total complexity is\n\n$$\n\\mathcal{O}(kK^2 \\ln 1 / \\epsilon)\\quad \\text{vs.}\\quad \\mathcal{O}(K^3)\\ (\\text{Vanilla BBSE}).\n$$\n\nBecause $k$ is at most 8 and $\\ln 1/\\epsilon \\le 10$ in all our runs, the crossover happens already at $K\\ge 25$.\n\n| operation | cost on $k$-NN graph | remarks |\n| --- | --- | --- |\n| vanilla BBSE | $O(K^3)$ once | dense LU factorisation of the $K\\times K$ confusion matrix. |\n| Newton-CG step for ours |  $O(\\|E\\|) \\+ O(K^2)$  | gradient is linear in $\\|E\\|$, Hessian-vector product needs one sparse Laplacian-matvec $O(\\|E\\|)$ plus one dense Jacobian-matvec $O(K^2)$. Conjugate-gradient converges in $O(\\sqrt{\\kappa})$ iterations, empirically $\\leq 5$. |\n| HMC leap-frog | same $O(\\|E\\|) + O(K^2)$ per gradient | trajectories of length 10-20 give effective sample size $> 200$ for every $q_i$. |\n\nTherefore the dominant term grows only quadratically in the class count $K$ (the sparse Laplacian never densifies), whereas BBSE’s one‑off inverse is cubic.\n\nNext, we report the wall-clock runtimes (single NVIDIA T4, PyMC 5.10, float32).\n\n| dataset | K | BBSE | MLLS | ours |\n| --- | --- | --- | --- | --- |\n| MNIST | 10 | 0.80 s | 1.12 s | 12.2 s |\n| CIFAR-100 | 100 | 2.88 s | 5.37 s | 54.5 s |\n\nAs you suggested, we believe these results help users to consider the accuracy-complexity trade-off.\n\n**All times are <1 min on a single T4; in practice the wall‑clock is dominated by the CNN forward‑pass when $n'$≈10 k.**"}]

Author rebuttal:

Meta-review: **Summary**:

This submission addresses the problem of *label shift*; a problem that arises in practice after deploying ML prediction models. This work extends the vanilla model for detecting label shift, namely *the Black Box Shift Estimator* (BBSE), to a fully Bayesian framework to address two limitations in BBSE: (i) its sensitivity to sampling noise, and (ii) its ignorance to potential semantic similarity between different classes, especially when the number of classes is large.

The new proposed method, GS-B3SE, is a fully probabilistic alternative to BBSE. In particular, introduces probabilistic Laplacian-Gaussian priors on both the target distribution log-priors ($p$), and columns of the confusion matrix $C$, tying them together on a label similarity graph that captures the semantic information between classes. Thus, the class similarity graph acts as a smoothing constraint on these priors. In particular, the graph Laplacian is used as the covariance matrix in the distribution of latent variables. The graph structure allows semantically similar classes to *borrow* some information from each other during parameter estimation. In this way, the model can handle classes with sparse data, and the resulting estimates are more robust thanks to the proper quantification (and handling) of uncertainty. In some sense, the vanilla BBSE can be seen as a special case from the GS-B3SE.

**Comments**

*   All reviewers agree on the following strengths of the submission:
    1.  The paper is well-written, easy to follow, and proposes a novel, mathematically sound, formulation for label shift estimation. The use of the graph structure to simultaneously smooth the priors (for the target distribution and the confusion matrix) is a clever idea.
    2. The theoretical analysis is robust: complete proofs for identifiability, optimal $N^{-1/2}$ convergence, and variance reduction scaling with algebraic connectivity $\lambda_2(L)$.
    3. The information geometric analysis provided by the authors (sec. 6.1) reveals how graph priors act as $e$-convex barriers, linking optimization to Riemannian dynamics.

*   All concerns, questions, and confusions raised by the reviewers were properly and thoroughly addressed by the authors, and the final results is there is unanimous agreement between all Reviewers that the rating is **weakly accept**. All reviewers shared a common concern: the computational overhead for GS-B3SE is above moderate. While this might be true especially while the method is still under development, this concern is secondary when compared to the other strengths of this submission, and the merit of this idea in general. Indeed, after the authors' rebuttal, none of the reviewers decreased their ratings due this concern. In fact, Rev.3 (S2qe) who initially assessed the paper as weak reject, increased the rating after the rebuttal to weak accept.

*   To summarize: this is a solid submission for a highly relevant problem to the ML community, with a novel idea, sufficient empirical validation, and strong theoretical justification. The AC recommends acceptance for this submission.
Decision: Accept (spotlight)