REVIEW 5 major objections 5 minor 40 references
The Safety-Privacy Tradeoff in Linear Bandits
T0 review · 5 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash
Pith's one-line read This paper shows that when private agent responses are learned under a shared safety constraint with a simplex-shaped safe set, any fixed regret budget admits a privacy-allocation vector that no agent can individually improve upon.
desk verdict A useful and mostly sound extension of safe linear bandits to heterogeneous LDP, but the main unimprovability theorem is not well-defined for small constraint coefficients and the printed regret bound has a dimensional typo. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery has three parts. First, the sharpness of the safe set, $\mathrm{Sharp}^{\infty}_{S'}(\Delta)$, defined as the maximal Euclidean distance from a point in the safe set to the $\Delta$-shrunk safe set; for a transformed simplex it evaluates exactly to $\Delta\sqrt{(M-1) + (2q'\tilde{\rho} - 1)^2}$, with $\rho_m = c_m/\beta_{T,m}$ the ratio of the constraint width to that agent's confidence radius. Second, the limiting regret constant $r(a) = \lim_{T\to\infty} r(T,a)/(T^2 \log T)^{1/3}$, which after substitution takes the form $2LK\bigl(d(R^2 + \tilde{\alpha}^2\sigma^2)\bigr)^{1/3}\left(\frac{2S\sqrt{M}}{\check{\lambda}} + \sqrt{(M-1) + (2f(a)-1)^2}\right)$, where $f(a) = \max_m \sum_{m'} \frac{c_m\sqrt{R^2 + \alpha_{m'}^2\sigma^2}}{c_{m'}\sqrt{R^2 + \alpha_m^2\sigma^2}}$. Third, the ratio-symmetry fact that $f(a) \ge M$ with equality exactly when the scaled radii $h_m(\alpha_m) = c_m\sqrt{R^2 + \alpha_m^2\sigma^2}$ are all equal; this identity is what certifies that perturbing $a^*$ in any single coordinate strictly increases $r(a)$.
What would settle it
Evaluate Lemma 13's formula at $a^* + v$ for a concrete simplex and a single positive coordinate of $v$: the unimprovability claim reduces to the arithmetic fact that $f(a) > M$ whenever the scaled radii $h_m(\alpha_m)$ are not all equal, so a single evaluation that gave $r(a^* + v) \le U$ would refute it. Separately, compose the per-round Gaussian mechanism over $T$ rounds under the algorithm's adaptive action rule (for instance by standard advanced composition) and compare the composed privacy parameter with the $\varepsilon_m$ used in the confidence radii; a gap would show that the regret budget $U$ was calibrated with the wrong privacy parameter.
Extended reading notes
Core claim
The paper claims that the privacy vector $a^*$ with components $\alpha^*_m = \sqrt{\left(R^2/\sigma^2 + \tilde{r}^2\right)\frac{c_m^2}{\tilde{c}^2} - \frac{R^2}{\sigma^2}}$, where $\tilde{c} = \max_m c_m$ and $\tilde{r}$ is chosen so that the limiting regret constant equals the budget $U$, belongs to the set $A^*$ of unilaterally unimprovable privacy levels (Theorem 3). Concretely, this means $r(a^* + v) > U$ for every nonzero $v \in \mathbb{R}_+^M$: any strictly stronger privacy for one agent, with all other agents' privacy levels unchanged, pushes the limiting regret bound past the allowed budget. In the noiseless case $R = 0$ the formula reduces to $\alpha^*_m = \tilde{r}\, c_m/\tilde{c}$, so each agent's privacy level is proportional to the tightness $c_m$ of the safety constraint in that agent's direction, and agents whose responses are more tightly constrained receive weaker privacy. The proof relies on an exact expression for the sharpness of a transformed simplex, which is minimized when the scaled constraint widths $\rho_m = c_m/\beta_{T,m}$ are equal across agents.
Load-bearing premise
The paper proves the local differential privacy guarantee only for a single round of responses at a time, and never shows that the full $T$-round interaction, in which the coordinator's actions depend on all past private responses, satisfies the same $(\varepsilon_m,\delta)$-LDP; the confidence radii that drive the regret bound would change if full-sequence privacy were the intended guarantee.
Editorial extensions
If this is right
- For a fixed regret budget $U$, the vector $a^*$ satisfies $r(a^*) = U$ exactly, and any unilateral increase in one agent's privacy level makes $r(a) > U$, so each agent's privacy is individually maxed out within the budget.
- In the noiseless setting $R = 0$, privacy levels are allocated in proportion to the constraint-tightness parameters $c_m$: agents whose responses sit under tighter safety constraints get weaker privacy (Corollary 1).
- For simplex safe sets the regret of the algorithm grows as $O(T^{2/3}(\log T)^{1/3})$, with the leading constant set by the privacy noise variance and by the sharpness of the scaled safe set.
- The sharpness of the transformed simplex is smallest when all scaled constraint widths $\rho_m$ are equal (Lemma 11), making a symmetric simplex the most favorable geometry for regret.
- For any polytopic safe set, Theorem 2 splits regret into a safety term (sharpness times the shrinkage of the safe set) and an optimism term, with privacy entering only through the confidence radii $\beta_{T,m}$.
Reading between the lines
- The paper's privacy guarantee (Fact 1) is proved per time step and never composed over the $T$ rounds; if the full adaptively-chosen transcript is the real privacy object, the effective $(\varepsilon,\delta)$ is weaker and the confidence radii $\beta_{t,m}$, hence the whole tradeoff curve, would have to be recomputed. The unimprovability result is stated for the per-step guarantee as given.
- The proportionality rule of Corollary 1 suggests a transferable design heuristic: allocate privacy-loss budget inversely to an agent's marginal contribution to feasibility, a principle that could apply to other safety-critical data-sharing settings beyond bandits.
- The proof's ratio-symmetry structure ($f(a) \ge M$ with equality at equal scaled radii) hints at a broader principle: any safety-and-privacy objective whose regret constant depends on such a ratio will have its unimprovable point at the symmetric allocation, so analogous vectors should exist for other noise mechanisms and other constraint geometries.
- A testable extension would rerun the same unimprovability program with Laplace or truncated noise per agent; the sharpness machinery survives, but the Gaussian structure that makes $h_m(\alpha_m)$ depend on $\alpha_m^2$ must be replaced.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper considers M linear stochastic bandit problems coupled by a global safety constraint of the form Θ_* X_t ∈ Y. Each agent adds Gaussian noise to its observed response before sharing it with a central coordinator, giving an (ε_m, δ)-LDP guarantee per released response. The coordinator runs a two-phase Safe-LUCB-style algorithm consisting of a pure-exploration phase and an optimism-based exploration-exploitation phase, with confidence radii inflated by the privacy noise. For polytopic safe sets, the paper gives a regret bound in terms of the sharpness of the transformed safe set Y′. It then specializes to simplex safe sets, derives a closed-form expression for the sharpness, and proposes a privacy vector a* that is claimed to be unilaterally unimprovable for a given asymptotic regret budget U, i.e. a* ∈ A*. Numerical experiments on a three-agent simplex compare regret for different privacy allocations.
Significance. If the results were fully correct, the paper would be a useful contribution: it formalizes a safety-privacy tradeoff in safe linear bandits, extends the sharpness framework of [5] to local differential privacy, and provides a concrete Pareto-style recommendation for allocating privacy levels across agents. The derivation of the sharpness of a simplex in Lemma 8 is self-contained, and the formulation of unilateral unimprovability in A* is a clear and meaningful notion. The paper also clearly identifies privacy noise as an additional contribution to the confidence radii β_{t,m}, which is the right structural mechanism. However, several load-bearing technical points are currently not supported as written: the printed regret bound in Theorem 2 has a scaling inconsistency, the constructive claim in Theorem 3 can fail to define a real privacy vector, and the proof of Theorem 3 contains an algebraic assertion that is false for the stated formula. These issues need to be resolved before the central claim can be accepted.
major comments (5)
- [Section IV, Theorem 2 and Lemma 5] As printed, Theorem 2 evaluates Sharp∞_Y′ at 2√2K√(2ν + T′λ̌), whereas Lemma 5 defines the shrinkage parameter as l′ = 2√2K / √(2ν + T′λ̌) and uses it in that reciprocal form in Eq. (27) and Eq. (31). The printed form is dimensionally inconsistent and would make the second regret term grow like T′ instead of contributing the intended T^(2/3)-type rate. The theorem and the lemma must be reconciled, and the constants in the stated regret bound should be re-derived after the correction.
- [Section V, Theorem 3] The vector a* defined in Theorem 3 need not exist in R_+^M. With α*_m = sqrt((R^2/σ^2 + r̃^2)c_m^2/c̃^2 - R^2/σ^2), the radicand can be negative whenever c_m is small relative to c̃. For example, take R = σ = 1, M = 2, c_1 = 1, c_2 = 0.1, c̃ = 1, and choose the budget U so that r̃^2 = 10; then (α*_2)^2 = 1.1·0.01 - 1 = -0.89, so α*_2 is not real. The theorem needs an explicit feasibility condition on U, or on r̃, relative to min_m c_m/c̃, or a modified construction.
- [Appendix D6, proof of Theorem 3] The proof of Theorem 3 claims that there exists a positive real B′ such that h_m(α*_m) = B′ for all m, where h_m(α_m) = c_m√(R^2 + α_m^2 σ^2). For the printed definition of α*, direct substitution gives h_m(α*_m) = c_m√(R^2 + r̃^2σ^2) c_m/c̃ = (c_m^2/c̃)√(R^2 + r̃^2σ^2), which depends on m unless all c_m are equal. Since both case arguments in the unimprovability proof rely on this property, the proof that r(a) > U for every a = a* + v with v ∈ R_+^M \ {0} is not established.
- [Section III-A, Fact 1 and Appendix A] The paper states the LDP guarantee only for a single response at a single time step: Fact 1 says that at any single time t ∈ [T], Algorithm 1 is (ε_m, δ)-LDP. However, Algorithm 1 releases T perturbed responses per agent, and the coordinator's actions depend on the entire transcript. No composition bound is given for the full sequence. If the intended privacy guarantee is full-sequence LDP, the effective privacy parameter after T-fold composition would be different and would enter the confidence radii β_{t,m}, changing the tradeoff; if the intended guarantee is only per-round LDP, this limitation should be stated explicitly in the abstract and conclusion.
- [Appendix C, Lemma 6] The proof of Lemma 6 switches between H∞_Y and H∞_Y′ without justification. In Eq. (35) the bound is written as β_{T,m} H∞_Y, while Eq. (36) and the lemma statement use β_{T,m} max(H∞_Y′, 2). Since Y′ = BY with B = diag(1/β_{T,m}), the maximum shrinkages of Y and Y′ generally differ. This inconsistency affects the constant in the Term II bound and should be corrected.
minor comments (5)
- [Appendix D6] The appendix labels a statement as 'Theorem 4 (Duplicate of Theorem 3)'; this duplicate numbering should be removed or the statement should be presented once.
- [Section I-B] The notation x_{1:t} is defined but never used; the definition can be removed.
- [Section VI and Appendix E] Figure 1 and Figure 3 appear to have essentially the same caption, although they are described differently in the text; the captions and the experimental protocol should be aligned.
- [Algorithm 1 and Eq. (66)] Algorithm 1 takes T′ as an input, while the later analysis sets T′ = max(t_h′, t_δ′, (2/λ̌)(β̃_T T)^(2/3)); the recommended choice of T′ should be stated before or within the algorithm description.
- [Overall] There are scattered typographical issues in the displayed equations, including missing square-root bars and inconsistent use of p and √; a careful proofreading pass is needed.
Circularity Check
No circular derivation found: a* is calibrated to the regret budget, but the unimprovability claim is proved by an independent monotonicity argument.
full rationale
Theorem 3's construction is a calibration step: the formula for alpha*_m is obtained by inverting Lemma 13's expression for r(a) under f(a*)=M and max_m alpha*_m = r-tilde, so that r(a*)=U. That alone does not establish a* in A*; the substantive content is the second half of the proof, which shows that for any v in R_+^M \ {0}, r(a*+v)>U using Lemma 12 and the monotonicity of r(a) in max_m alpha_m and f(a). This argument is self-contained and does not assume the conclusion. The sharpness lemmas for the simplex (Lemmas 8-11) are derived from the definition of S' and the confidence ellipsoid, and Lemma 13 is derived from Theorem 2; none of these steps presuppose Theorem 3. The only imported ingredients are the confidence bound of Abbasi-Yadkori et al. [22], the Safe-LUCB exploration lemma [4], and the sharpness definition [5]; these are prior building blocks, and the target privacy-tradeoff result is not assumed in any of them. The paper's self-citations are therefore not load-bearing circularity. A separate, non-circular correctness concern is that Theorem 3 states no feasibility condition ensuring the radicand in alpha*_m is nonnegative; for agents with sufficiently small c_m the vector may not lie in R_+^M. That is a well-definedness gap, not a circular reduction.
Assumptions & free parameters
free parameters (3)
- Regret budget U
- Regularizer ν =
0.1 (experiments)
- Pure exploration length T' =
max(t'_h, t_δ', (2/λ̌)(β̃_T T)^(2/3))
assumptions (8)
- domain assumption Assumption 1: noise η_{t,m} is conditionally zero-mean R-sub-Gaussian
- domain assumption Assumption 2: f is L-Lipschitz on Y
- domain assumption Assumption 3: bounded θ, actions, and responses y∈[-1,1]
- domain assumption Assumption 4: D_s ⊆ D (decision set not restrictive)
- domain assumption Assumption 5: D0 has nonempty interior with a ball of radius r
- ad hoc to paper The radicand in α*_m is nonnegative for all m
- standard math Confidence ellipsoid theorem of Abbasi-Yadkori et al. (Theorem 2 of [22])
- standard math Gaussian mechanism LDP guarantee (Lemma 1, from [8],[24])
Cite this review
Pith. "Pith review of The Safety-Privacy Tradeoff in Linear Bandits." pith.science (2026). https://pith.science/paper/LUYF4VTL
@misc{pith2026250416371,
author = {Pith},
title = {Pith review of: The Safety-Privacy Tradeoff in Linear Bandits},
year = {2026},
howpublished = {\url{https://pith.science/paper/LUYF4VTL}},
note = {Machine review of arXiv:2504.16371}
}
read the original abstract
We consider a collection of linear stochastic bandit problems, each modeling the random response of different agents to proposed interventions, coupled together by a global safety constraint. We assume a central coordinator must choose actions to play on each bandit with the objective of regret minimization, while also ensuring that the expected response of all agents satisfies the global safety constraints at each round, in spite of uncertainty about the bandits' parameters. The agents consider their observed responses to be private and in order to protect their sensitive information, the data sharing with the central coordinator is performed under local differential privacy (LDP). However, providing higher level of privacy to different agents would have consequences in terms of safety and regret. We formalize these tradeoffs by building on the notion of the sharpness of the safety set - a measure of how the geometric properties of the safe set affects the growth of regret - and propose a unilaterally unimprovable vector of privacy levels for different agents given a maximum regret budget.
Figures
Reference graph
Works this paper leans on
-
[5]
S. Hutchinson, B. Turan, and M. Alizadeh, “The impact of the geo- metric properties of the constraint set in safe optimization with bandit feedback,” in Proceedings of The 5th Annual Learning for Dynamics and Control Conference. PMLR, 2023, pp. 497–508
work page 2023
-
[1]
Correlational dueling bandits with application to clinical treatment in large decision spaces,
Y . Sui and J. W. Burdick, “Correlational dueling bandits with application to clinical treatment in large decision spaces,” in Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, 2017, pp. 2793–2799
work page 2017
-
[2]
Safe pricing mechanisms for distributed resource allocation with bandit feedback,
S. Hutchinson, B. Turan, and M. Alizadeh, “Safe pricing mechanisms for distributed resource allocation with bandit feedback,” IEEE Transactions on Control of Network Systems , pp. 1–12, 2024
work page 2024
-
[3]
Safe online convex optimization with unknown linear safety constraints,
S. Chaudhary and D. Kalathil, “Safe online convex optimization with unknown linear safety constraints,” in Proceedings of the AAAI Confer- ence, vol. 36, no. 6, 2022, pp. 6175–6182
work page 2022
-
[4]
Linear stochastic bandits under safety constraints,
S. Amani, M. Alizadeh, and C. Thrampoulidis, “Linear stochastic bandits under safety constraints,” Advances in Neural Information Pro- cessing Systems, vol. 32, 2019
2019
-
[6]
Stochastic bandits with linear constraints,
A. Pacchiano, M. Ghavamzadeh, P. Bartlett, and H. Jiang, “Stochastic bandits with linear constraints,” in International Conference on Artificial Intelligence and Statistics . PMLR, 2021, pp. 2827–2835
work page 2021
-
[7]
Differential privacy,
C. Dwork, “Differential privacy,” in International colloquium on au- tomata, languages, and programming . Springer, 2006, pp. 1–12
2006
-
[8]
The algorithmic foundations of differential privacy,
C. Dwork, A. Roth et al. , “The algorithmic foundations of differential privacy,” Foundations and Trends® in Theoretical Computer Science , vol. 9, no. 3–4, pp. 211–407, 2014
2014
Show all 40 references
-
[9]
Local differential privacy: Tools, challenges, and opportunities,
Q. Ye and H. Hu, “Local differential privacy: Tools, challenges, and opportunities,” in International conference on web information systems engineering. Springer, 2020, pp. 13–23
2020
-
[10]
Local differential privacy for data collection and analysis,
T. Wang, J. Zhao, Z. Hu, X. Yang, X. Ren, and K.-Y . Lam, “Local differential privacy for data collection and analysis,” Neurocomputing, vol. 426, pp. 114–133, 2021
2021
-
[11]
Differentially private contextual linear bandits,
R. Shariff and O. Sheffet, “Differentially private contextual linear bandits,” Advances in Neural Information Processing Systems , 2018
2018
-
[12]
(nearly) optimal differentially private stochastic multi-arm bandits,
N. Mishra and A. Thakurta, “(nearly) optimal differentially private stochastic multi-arm bandits,” in Proceedings of the Thirty-First Con- ference on Uncertainty in Artificial Intelligence , 2015, pp. 592–601
2015
-
[13]
Algorithms for differentially private multi-armed bandits,
A. Tossou and C. Dimitrakakis, “Algorithms for differentially private multi-armed bandits,” in Proceedings of the AAAI Conference on Artifi- cial Intelligence, vol. 30, no. 1, 2016
2016
-
[14]
Differentially private stochastic linear bandits:(almost) for free,
O. Hanna, A. M. Girgis, C. Fragouli, and S. Diggavi, “Differentially private stochastic linear bandits:(almost) for free,” IEEE Journal on Selected Areas in Information Theory , 2024
2024
-
[15]
Generalized linear bandits with local differential privacy,
Y . Han, Z. Liang, Y . Wang, and J. Zhang, “Generalized linear bandits with local differential privacy,” Advances in Neural Information Pro- cessing Systems, vol. 34, pp. 26 511–26 522, 2021
2021
-
[16]
Optimal rates of (locally) differentially private heavy-tailed multi-armed bandits,
Y . Tao, Y . Wu, P. Zhao, and D. Wang, “Optimal rates of (locally) differentially private heavy-tailed multi-armed bandits,” in International Conference on Artificial Intelligence and Statistics . PMLR, 2022, pp. 1546–1574
2022
-
[17]
Locally differentially private (contextual) bandits learning,
K. Zheng, T. Cai, W. Huang, Z. Li, and L. Wang, “Locally differentially private (contextual) bandits learning,” Advances in Neural Information Processing Systems, vol. 33, pp. 12 300–12 310, 2020
2020
-
[18]
(lo- cally) differentially private combinatorial semi-bandits,
X. Chen, K. Zheng, Z. Zhou, Y . Yang, W. Chen, and L. Wang, “(lo- cally) differentially private combinatorial semi-bandits,” in International Conference on Machine Learning , 2020, pp. 1757–1767
2020
-
[19]
Safe linear stochastic bandits,
K. Khezeli and E. Bitar, “Safe linear stochastic bandits,” Proceedings of the AAAI Conference on Artificial Intelligence , vol. 34, no. 06, pp. 10 202–10 209, Apr. 2020. [Online]. Available: https://ojs.aaai.org/ index.php/AAAI/article/view/6581
2020
-
[20]
Differentially-private federated linear ban- dits,
A. Dubey and A. Pentland, “Differentially-private federated linear ban- dits,” NeurIPS, vol. 33, pp. 6003–6014, 2020
2020
-
[21]
Distributed linear bandits with differential privacy,
F. Li, X. Zhou, and B. Ji, “Distributed linear bandits with differential privacy,” IEEE Trans. on Network Science and Eng. , pp. 1–13, 2024
2024
-
[22]
Improved algorithms for linear stochastic bandits,
Y . Abbasi-Yadkori, D. Pál, and C. Szepesvári, “Improved algorithms for linear stochastic bandits,” Advances in neural information processing systems, vol. 24, 2011
2011
-
[23]
R. T. Rockafellar and R. J.-B. Wets, Variational analysis. Springer Science & Business Media, 2009, vol. 317
2009
-
[24]
Reviewing and improving the gaussian mechanism for differential privacy,
J. Zhao, T. Wang, T. Bai, K.-Y . Lam, Z. Xu, S. Shi, X. Ren, X. Yang, Y . Liu, and H. Yu, “Reviewing and improving the gaussian mechanism for differential privacy,” arXiv preprint arXiv:1911.12060 , 2019
1911 arXiv
-
[25]
V . Dani, T. P. Hayes, and S. M. Kakade, Stochastic linear optimization under bandit feedback , 2008
2008
-
[26]
Rate-optimal online convex optimization in adaptive linear control,
A. B. Cassel, A. Peled-Cohen, and T. Koren, “Rate-optimal online convex optimization in adaptive linear control,” Advances in Neural Information Processing Systems , vol. 35, pp. 7410–7422, 2022. APPENDIX A. Privacy Guarantee Lemma 2. (post-processing property, proposition 2.1...
2022
-
[27]
To do so, we first explant the process of action selection during the pure exploration phase
Random Action Selection for Pure Exploration Phase: We start by bounding Term I. To do so, we first explant the process of action selection during the pure exploration phase. During this phase the central coordinator chooses actions for each user uniformly at random from a sub...
-
[28]
To sample from this set, define a vector u uniformly sampled from a unit sphere i.i.d, with, E[uuT ] = 1 MdI
is a subset of D0 as well. To sample from this set, define a vector u uniformly sampled from a unit sphere i.i.d, with, E[uuT ] = 1 MdI. The central coordinator chooses Xt as follow: Xt = v + r 2 u. (21) Since Xt = [ xT t,1, xT t,2,··· , xT t,M]T is a stacked vector of all age...
-
[29]
For the remainder of the proof, we will condition on this holding without further reference
Therefore, for δ′ = δ 2, when δ′ ∈ (0, 1/2), they jointly hold with probability 1−δ. For the remainder of the proof, we will condition on this holding without further reference. Now, we bound Term I directly in the following. Lemma 5. Let Assumptions 1-5 hold. Then for t>T ′, ...
-
[30]
Proof of Lemma 8: First, we will give an exact form of the shrunk version of the transformed simplex S′ = S(A′, b), where A′ = βT ,1 c1 βT ,2 c2 ··· βT ,M cM −βT,1 0 ··· 0 0 −βT,2 ··· ... ... ... 0 0 ··· 0 −βT,M , (43) given Equation (16) and the fact that ...
-
[31]
wm≥ 1 2q′− 1 2qβT ,m ∀m∈ [M],
-
[32]
First, 1) holds by definition as wm = 1 2q′− 1 2qβT,m ≥ 1 2q′− 1 2qβT,m , (50) for all m∈ [M]
PM m=1 βT ,m cm xm≤ 1 2− 1 2q′q′. First, 1) holds by definition as wm = 1 2q′− 1 2qβT,m ≥ 1 2q′− 1 2qβT,m , (50) for all m∈ [M]. Then, we show that 2) holds, MX m=1 βT,m cm wm≤ 1 2− 1 2q′q′ ⇐⇒ MX m=1 βT,m cm 1 2q′− 1 2qβT,m ≤ 1 2− 1 2q′q′ ⇐⇒ MX m=1 βT,m cm 1 2q′− MX m=1 1 cm 1...
-
[33]
Lemma 12
Proof of Lemma 11: To prove Lemma 11, let us use the following lemma. Lemma 12. Consider the function g : RM ++→ R defined as g(b) = max m∈[M] bm MX m=1 1 bm . Then, for any b∈ RM ++, it holds thatg(b)≥M. Furthermore, g(b) =M if and only if b =B1 for some B∈ R++. Proof: First,...
-
[34]
(42)), we can rewrite it as follows: Sharp∞ S′(∆) = ∆ p (M− 1) + (2q′ ˜ρ− 1)2 = ∆ p (M− 1) + (2f(ρ)− 1)2, (64) where f(ρ) = maxm∈[M]ρm PM m=1 1 ρm
Completing the proof of Lemma 11: Proof: Given sharpness of the transformed safe set S′ from Lemma 8 (Eq. (42)), we can rewrite it as follows: Sharp∞ S′(∆) = ∆ p (M− 1) + (2q′ ˜ρ− 1)2 = ∆ p (M− 1) + (2f(ρ)− 1)2, (64) where f(ρ) = maxm∈[M]ρm PM m=1 1 ρm . Then the follow- ing i...
-
[35]
Then, using Theorem 2 and Lemma 8, the regret upper bound for Safe-Private Lin-UCB with a simplex safe set S can be written as a function of privacy vector a
Regret Bound, a function of privacy levels: Sinceβt,m is a function of αm (12), we define vector a = [α1,α 2,...,α M], called privacy vector which is a vector of allM agents’ privacy level parameters (defined in (8)). Then, using Theorem 2 and Lemma 8, the regret upper bound f...
-
[36]
Proof of Lemma 13: Proof: Given Equation (66), r(T, a) = 2LKS √ MT′ +L(T−T′) 2 √ 2K ˜βTp 2ν + ˇλT′ p (M− 1) + (2q′ ˜ρ− 1)2 +L max( 1 2q′, 2) × vuut2d log(1 +TK 2 dν )(T−T′) X m∈[M] β2 T,m , (69) where T′ = max(t′ h,tδ′, 2 ˇλ( ˜βTT ) 2 3 ) and ˜βT = max βT,m m∈[M] . Also, note ...
-
[37]
Completing the proof: Theorem 4 (Duplicate of Theorem 3). Consider the pri- vacy vector a∗∈ RM , for which the mth element is defined as α∗ m = s R2 σ2 + ˜r2 c2m ˜c2 − R2 σ2, where ˜c = maxm∈[M]cm and ˜r = 1 σ vuut U3 8L3K3dM 3 2 2S ˆλ + √ 4M− 3 3−R2. It holds that a∗∈A∗. Proo...
-
[38]
First, we show 1)
r(a∗ +v)>U for any v∈ R+\{ 0}. First, we show 1). To do so, note that f(a∗) = max m∈[M] MX m′=1 cm p R2 + (α∗ m′)2σ2 cm′ p R2 + (α∗m)2σ2 = MX m′=1 ˜c √ R2 + ˜r2σ2 ˜c √ R2 + ˜r2σ2 =M. Also, it holds that ˜α∗ = max m∈[M] α∗ m = max m∈[M] r (R2 σ2 + ˜r2)(cm ˜c )2− R2 σ2 = s (R2 σ...
-
[39]
If there exists a positive real B such that hm(αm) =B for all m∈ [M], then it holds that B = hm(αm) < hm(α∗ m) = B′ since there exists at least one ¯m∈ [M] such that α ¯m > α∗ ¯m and hm is strictly decreasing for allm. Therefore, we can use the fact that the inverse of a stric...
-
[40]
Also, by definition, maxm∈[M]αm ≥ maxm∈[M]α∗ m
If there does not exist a positive real B such that hm(αm) = B for all m ∈ [M], then Lemma 12 tells us that f(a) = g(h(a)) > M = f(a∗). Also, by definition, maxm∈[M]αm ≥ maxm∈[M]α∗ m. Then, sincer(a) is strictly-increasing with respect to f(a) and maxm∈[M]αm, it follows that r...
Reviewed August 16, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.