Controlling Federated Learning for Covertness
Authors: Adit Jain
Vikram Krishnamurthy
Venue: Accepted by TMLR ()

Abstract: A learner aims to minimize a function $f$ by repeatedly querying a distributed oracle that provides noisy gradient evaluations. At the same time, the learner seeks to hide  $\arg\min f$ from a malicious eavesdropper that observes the learner's queries. This paper considers the problem of \textit{covert} or \textit{learner-private} optimization, where the learner has to dynamically choose between learning and obfuscation by exploiting the stochasticity. The problem of controlling the stochastic gradient algorithm for covert optimization is modeled as a Markov decision process, and we show that the dynamic programming operator has a supermodular structure implying that the optimal policy has a monotone threshold structure. A computationally efficient policy gradient algorithm is proposed to search for the optimal querying policy without knowledge of the transition probabilities. As a practical application, our methods are demonstrated on a hate speech classification task in a federated setting where an eavesdropper can use the optimal weights to generate toxic content, which is more easily misclassified. Numerical results show that when the learner uses the optimal policy, an eavesdropper can only achieve a validation accuracy of $52\%$ with no information and $69\%$ when it has a public dataset with $10\%$ positive samples compared to $83\%$ when the learner employs a greedy policy.

Published in Transactions on Machine Learning Research (01/2023)
Controlling Federated Learning for Covertness
Adit Jain
aj457@
Department of Electrical and Computer Engineering, Cornell University
Vikram Krishnamurthy
vikramk cornelledde
Department of Electrical and Computer Engineering, Cornell University
Reviewed on OpenReview:
Abstract
learner aims to minimize a function f by repeatedly querying a distributed oracle that provides noisy gradient evaluations. At the same time, the learner seeks to hide arg min from a malicious eavesdropper that observes the learner's queries. This paper considers the problem of covert or learner-private optimization, where the learner has dynamically choose between learning and obfuscation by exploiting the stochasticity. The problem of controlling the stochastic gradient algorithm for covert optimization is modeled as Markov decision process, and we show that the dynamic programming operator has a supermodular structure implying that the optimal policy has a monotone threshold structure. A computationally efficient policy gradient algorithm is proposed to search for the optimal querying policy without knowledge of the transition probabilities. As a practical application, our methods are demonstrated on hate speech classification task in federated setting where eavesdropper can the optimal weights generate toxic content, which more easily misclassified. Numerical results show that when the learner uses the optimal policy, eavesdropper can only achieve a validation accuracy of 32% with no information and 69% when it has public dataset with 10% positive samples compared to 83% when the learner employs greedy policy.
1 Introduction
1.1 Main Results
A learner aims to minimize a function f by querying an oracle repeatedly. At times k 1,..., the learner sends query qe to the oracle, and the oracle responds with noisy gradient evaluation rk. Idcally, the learner would use this noisy gradient in stochastic gradient algorithm to update its estimate of the minimizer, 4g as: ax+1 4₂ Me where μ* is the step size and pose the next query as (j+1 = 2s+1- However, the learner seeks to hide the arg min f from an eavesdropper. The cavesdropper observes the sequence queries (qx) but does not observe the responses from the oracle. The eavesdropper is passive and does not directly affect the queries or the responses. How can the learner perform stochastic gradient descent to learn arg min f but hide it from the eavesdropper? This problem arises in federated learning (FL), where the central learner (e.g. an application) optimizes the loss function of neural network by communicating with distributed set of devices. The learner communicates the weights to the devices and receives noisy gradients of the loss function evaluated on local data which the learner uses to update the weights.
Our proposed approach to control the stochastic gradient descent (SGD) using another stochastic gradient algorithm, namely a structured policy gradient algorithm (SPGA) that solves a resource allocation Markov decision process. The following two-step cross-coupled stochastic gradient algorithm summarizes our approach:
Stochastic Gradient Descent: 6 = dx un GurG Mes qk);
(1)
Query using Policy from SPGA: 4k+1 P(v(y)+1), #x41)
Here & the time index, μ4 is the step size, q is the query and yı the system state. The function is designed by the learner to update the estimate based the noisy response rn (for example, G can be 0 when obfuscating and the

---

Published in Transactions on Machine Learning Research (01/2023)
noisy gradient ry otherwise). P is the probability distribution of the query based the transition probability kernel of the stationary policy, which decides whether to learn or obfuscate. The first equation in ① updates the learner's arg min estimate, &R. and the second equation computes the next query [h+1 using a policy v.
Contributions:
This paper proposes a framework for the learner to dynamically query the oracle for robust learning and covert optimization. We formulate a Markov decision process (MDP) to solve the decision problem of the learner by exploiting the inherent stochasticity of the oracle. Structural results which show that the optimal policy has a threshold structure (Fig. aa)) are proven in Theorem 2 and Theorem B] The structural results enable the of efficient policy search methods to search for the optimal policy. This framework can be extended to meta-learning problems like controlling learning for energy efficiency and quality control.
Action
(a) Threshold structure of the opti- mal policy with two actions.
C queries O and runs SGD
A policy gradient algorithm is proposed which estimates the optimal stationary policy for the MDP. The optimal stationary policy controls the primary stochastic gradient descent of the learner as described by (T) and shown in Fig. [b). The policy gradient algorithm has linear time complexity due to the threshold nature of the optimal policy and does not need knowledge of the transition probabilities. The policy gradient algorithm runs on a slower time scale and can adapt to changes in the system.
System State
Action uL leacn or cbEuscate
Structured policy gradient to obtain optimal policy
(b) Coupled interaction of the two gradient algorithms.
The proposed methods are demonstrated on a novel application, covert federated learning (FL) on text classification task using large language model embeddings. Our key numerical results summarized in Ta- b It is shown that compared to greedy policy when the learner is using the optimal policy, the the eavesdropper's 's estimate of the optimal weights do not generalize well, even if the eavesdropper uses a public dataset to validate the queries]
Figure 1: To achieve covert opti- mization, we propose controlling the SGD by a policy gradient algo- rithm that exploits the policy struc- ture.
This paper considers two pragmatic aspects of empirical distributed learning environments: stochastic oracle and optimization queue. A stochastic oracle with different noise levels can model non-i.i.d. client distribution in FL., and an optimization queue can model repeated optimization tasks like machine unlearning and distribution shifts. The- orem D characterizes the number of successful updates required for convergence, and Lemma I
Jnaalyzss the stability of the queue.
1.2 Motivation and Related Works
The main application of covert stochastic optimization is in distributed optimization where the central learner queries distributed oracle and receives gradient evaluations using which it optimizes f. Such a distributed oracle is part of federated learning where deep learning models are optimized on mobile devices with distributed datasets (McMahan et al. 2017) and pricing optimization where customers are surveyed (Delahaye et al. 2017). In distributed optimization, the eavesdropper can pretend as a local worker of the distributed oracle and obtain the queries posed (but not the aggregated responses). The eavesdropper can infer the local minima by observing the queries. These estimates can be used for malicious intent competitive advantage since obtaining reliable, balanced, labeled datasets is expensive. As example, in hate speech classification in a federated setting (Meskys et al. 2019 Narayan et al. 2022) a hate
A greedy policy poses learning queries until all required successful updates are done the model and then starts posing obfuscating queries.
2

---

Published in Transactions on Machine Learning Research (01/2023)
Symbol
Description
k:
Time index for the stochastic gradient descent (SGD) Index for stochastic policy gradient algorithm (SPGA) Learner's estimate of the minima
Eavesdropper's 's estimate of the minima
y
State variable for the oracle state, learner state and arrival state Query posed to the oracle by the learner Action of the learner (Learning or Obfuscation)
q
Noisy gradient evaluation by oracle of function at query point Bound on the variance of the noise added time & Tolerance parameter of learner for bound noise variance O
True threshold parameter of the optimal policy
Threshold parameter of the SPGA tracking the true threshold parameter
14, K
Step size of the SGD and SPGA respectively
Table Summary of mathematical notations used in this paper.
speech peddler can pretend as a client and observe the trajectory of the learner to obtain the optimal weights minimizing the loss function. Using these optimal weights for discrimination, the eavesdropper can train generator network to generate hate speech which will not be detected (Hartvigsen et al.
2022 Wang al. 2018).
Leavner-private or covert optimization:
The problem of protecting the optimization process from eavesdropping
adversaries is examined in recent literature (Xu et al. 2021a Tsitsiklis et al.) 2021] Xu 2018 Xu et al.) 2021b).
Tsitsiklis et al. (021) Xu et al. 2222bba a) to obtain (T., -tytye privacy bounds on the number of queries required to
achieve a given level of learner- learner-privacy and optimize with and without noise. The current state art (Xu et al. 202
in covert optimization dealt with convex functions in noisy setting. Although there is extensive work in deriving the theoretical proportion of queries needed for covert optimization, practically implementing covert optimization has not been dealt with. In contrast, queries given desired level of privacy. We want to schedule M model updates in N queries and obfuscate otherwise, ideally learning when the noise of the oracle is expected to be less. Theoretical bounds are difficult to derive for a non-convex case, but we empirically show our formulation achieves covertness. The approach of this work aligns with hiding optimal policies in reinforcement learning when actions are visible (Liu et al. 2021: Pan et al. 2019 Dethise et 2019), information theory (Bloch, 2016), and preserving privacy while traversing graphs (Erturk Xu 2020
work considers non-convex noisy setting with the problem of posing learning
Motivation for stochastic oracle and optimization queue:
An important application of covert optimization is in federated learning, which is deployed in various machine learning tasks improve the privacy of dataset owners and communication efficiency (Heusel et al.
2022a). FL involves non-i.i.d. data distribution across clients and time-varying client participation and data contribution which motivate a dynamic stochastic oracle (Karimireddy
2017 Chen et al.
et al. 2020 Jhunjhunwala et al.) 2022 Doan et al. 2020
Chen et al.) 2022b). Similar to recent work in a setup with
Distinction from differential privacy: Differential privacy Lee et al. 2021 Dimitrov al. 2002 Asi al. 22021 is concerned with the
problem of preserving the privacy of the local client's data hy mechanisms like adding noise and clipping gradients, whereas learner-private or cnvert optimization is used when the central learner is trying prevent eavesdropper from freeriding the optimization process (siissiks et 202T
Scenario 1
Scenario
Favesdropper has toxic samples
Eavesdropper has toxic samples
Type of Policy Greedy
Eavesdropper accuracy
Learner accuracy
Eavesdropper accuracy
Learner accuracy
0.83
0.84
0.83
0.82
Optimal
0.52
0.81
0.69
0.81
Table 2: The optimal policy to our MDP formulation achieves covertness: The eavesdropper's accuracy is reduced significantly in comparison to greedy policy (-31%) 3) even when the eavesdropper has samples to validate the queries (-14%). The leamner's accuracy remains comparable in both the scenarios with a maximum difference of 3%.
3

---

Published in Transactions on Machine Learning Research (01/2023)
Markovian noise in FL (Sun et al.] 2018 Rodio al.) 2023), we model the bounds on the variance of the oracle noise to vary discrete Markov chain, and exploit the Markovian nature of the oracle's s stochasticity to query dynamically. An optimization queue for training tasks is motivated by active learning where the learner waits for training data to be annotated and performs optimization once there is enough annotated data (Bachman et al., 2017 Wu et al.) 2020). Optimization tasks can also be due to purging client's data, training new contexts, distributional shifts, or by design of
the learning algorithm (Tripp et al. 2020: Cai et al. 2021 Mallick et 2022 Ginart et al. 2019 Sekhari et al. 2021
1.3 Organization
In Section 2 the problem of minimizing a function while hiding the arg min is modeled as a controlled SGD. In Section B a finite horizon MDP is first formulated where the learner has to perform M successful gradient updates of the SGD in N total queries to stochastic oracle. The formulation is extended to an infinite horizon constrained MDP (CMDP) for cases when the learner performs optimization multiple times, and policy gradient algorithm is proposed to search for the optimal policy. Numerical results are demonstrated classification task in Section 4 A discussion of the stochastic oracle, dataset description, additional experimental results and proof', are presented in the Appendix. Notations are summarized in Table
Limitations: The assumption of unbiased responses and the independence of the eavesdropper and oracle might not hold, especially if the eavesdropper can deploy multiple devices. Due to the lack of data on device participation in FL., it is difficult to verify the assumption of a Markovian oracle. The assumption on an equal cavesdropper prior for both the obfuscating and learning SGD has not been theoretically verified. The assumption that the learner knows about the eavesdropper's s dataset distribution might only hold if it is public dataset or if there are obvious costly classes.
2 Controlled Stochastic Gradient Descent for Covert Optimization
This section discusses the oracle, the learner, and the cavesdropper and states the assumptions which are essential in modeling the problem as a Markov decision process in the next section. The following is assumed about the oracle O:
(A1): (Bounded from below and Lipschitz continous) The oracle is function f R - IR. f is continous and is bounded from below, f 2 f". f' is continously differentiable and its derivative is p-Lipschitz continous, i.e. [[V - fx))l Vf(e))~V((())) S 7/1= æ|| Vx, E Rd, where Vff indicates the gradient of f and || || is the 1 22-norm.
At time k, for a query Qu E Rdd the oracle returns a noisy evaluation ra of V at qa with added noise 7ik
ru( = V f(i)) m-s-
(2)
(A2): (Assumption on Noise) The noise 7)s is such that rx(ga) ) is an unbiased estimator of V ((x)). E[(x (nx) v f(g)). The noise has a bounded variance E [[lT> < (ax)². of is constant that the oracle returns along the response, F4 (.)).
Assumptions (A1) and (A2) are regularity assumptions for analyzing query complexity results of the stochastic gradient
descent, and are found in standard first-order gradient descent analysis (Ghadimi & Lan 2013; Ajallocian & Stich
202T). There assumption on the noise terms is slightly weaker than independence (Ghadimi & Lan 2013). Our analysis can be extended to algorithms with better convergence rates like momentum based Adam (Kingma & Ba 2017). Besides simplicity in exposition, SGD is shown to have better generalizability [Zhou et al. (2020); Wilson et al. (2017). f can be an empirical loss function for a training dataset D, far; D) = Ex, eD (x;; d.). D = [d.} where ((:--) loss function. In FL., the oracle is collection of clients acting as distributed dataset and compute.
The objective of the learner C is to query the oracle and obtain a e-close estimate & such that,
E f()))²) <e.
(3)
given an initial estimate, 20 Rdd The expectation E[|1 here is with respect to the noise sequence and the external random measure (if any) used to compute the estimate. The learner has knowledge of the Lipschitz constant y from (A 1). At time & for query oe the learner receives (rk, at) from the oracle (the response rx (qx) is denoted as rı).. The
4

---

Published in Transactions on Machine Learning Research (01/2023)
learner iteratively queries the oracle with sequence of queries q1, ...... and correspondingly updates its estimate 02....... for estimating è such that it achieves its objective
In classical SGD, the learner iteratively updates its estimate based on the gradient evaluations at the previous estimate. Now, since the queries are visible and the learner has to obfuscate the eavesdropper, the learner can either query using its true previous estimate or obfuscate the eavesdropper as described later. The learner updates its estimates L1, f2,,.. based on whether the posed query qu is for learning or not and the received noise statistic σke A learning query is denoted by action U, and obfuscating query by action u2 = 0. The learner chooses noise constant and performs controlled SGD with step size μll for m1th successful update) such that it updates its estimate only if of o² and if learning query was posed, i.e., UA = 1 (1 denotes the indicator function),
8x - parkll (o S <o) (ux 1). क
(4)
For formulating the MDP in the next section, we need the following definition and theorem, which characterizes the finite nature of the optimization objective of (3) The proof of the theorem follows by applying the gradient lemma and
standard convergence results the update step (Bottou 2004 given in the Appendix B.I.
Ghadimi & Lan 2013 Ajalloeian & Stich 202T) and is
Definition Successful Update: At time k an iteration of 4 is a successfiu update if (o S oo) (ux = 1) = 1.
Theorem 1. (Required number of successful updates) Learner L querying an oracle O which satisfies assumptions (AI-2) using controlled stochastic gradient descent with updates of the form (4) with a constant step size ps = μ = 11 needs to perform M successful updates (Def. 1b get c-close critical point (3 where
min 2702. 7
( o²
M =
+-=+0
2
Let the M successful updates happen at time indices .i...., KM then the learner's ' estimate of the critical point, a is Pi, which is a uniform distribution for a constant step size.
chosen as 3x. with probability
Σ PR.
Theorem I heepp characterize the order of the number of successful gradient updates that need to be done in the total communication slots available to achieve the learning objective of 33. If the optimization is not one-off, the learner maintains a queue of optimization tasks where each optimization task requires up order M successful updates.
The obfuscation strategy used by the learner builds upon the strategy suggested in existing literature (Xu et al. 2021a Xu 2018). The learner queries either using the correct estimates from ( or queries elsewhere in the domain to obfuscate the eavesdropper. In order to compute the obfuscating query, we propose that the learner runs parallel SGD, which also ensures that the eavesdropper does not gain information from the shape of two trajectories. The obfuscating queries are generated using suitably constructed function, H, and running parallel SGD with estimate, 2x.
2 = E. - H (rk, (E, uk).
(5)
At time k an eavesdropper & has access to the query sequence, (q),..., (k) which the eavesdropper uses to obtain an estimate, & for the arg min f. We make the following assumption on the cavesdropper:
(E1) The eavesdropper is assumed to be passive, omnipresent, independent of the oracle, and unaware of the chosen c.
(E2) Given sequence of N queries (q1, -2,-.. .NN) which the eavesdropper observes, we assume that the eavesdropper can partition query sequence into two disjoint SGD trajectory sequences I and J
(E3) In the absence of any additional information, the eavesdropper uses proportional sampling estimator similar to Xu (2018) and is defined below.
"The noise constant ø helps characterize the number of queries required and decide if received response will be used for learning or not, this is in principle similar the controlling communication done in [Chn al. (2022a), (Sun et al. (202). The probability of o 5 depends on the oracle state (defined in the next section). Using such construction
framework enables characterizing a oracle which has varying noise levels. "The parameter space is high dimensional, and it is assumed that SGD trajectories do intersect. The final weights used in production can he transmitted in secure fashion (using much costlier, less efficient communication et.. 2023 Kaimuz
2021)
5

---

Published in Transactions on Machine Learning Research (01/2023)
Assumption (EI) is generally not true, especially if the eavesdropper is part of the oracle (for example, in FL), but we take this approximation assuming since the number of clients is much greater than the single eavesdropper and hence the oracle is still approximately Markovian. Given an equal prior over disjoint intervals, an eavesdropper using a proportional sampling estimator calculates the posterior probability of the minima lying in an interval proportional to the number of queries observed in the interval. Since this work considers two disjoint SGD trajectories, the eavesdropper's posterior probability of the minima belonging to one of the SGD trajectories given equal priors is proportional to the number of queries in the trajectories,
Definition 2. Proportional sampling estimator: If the eavesdropper (with assumptions E1-2) observes queries belonging to two SGD trajectory sequences I and J and has equal prior over both of them, then the eavesdropper's
posterior belief of the learner's true estimate à belonging to I is given by, Pt - P( E [[ (2, ................................ .2N))...))) |/+
12|
Let K* be defined as K arg max Px and B[-1] retrieve the last item of the sequence B. After N observed queries, KE[I,J}
the eavesdropper's maximum a posteriori estimate, 2 of the learner's true estimate, é, is given by,
= (qulqk E K
[-].
(6)
An eavesdropper using a proportional sampling estimator with an estimate of the form (6) can be obfuscated by ensuring a) that the eavesdropper has equal priors over the two trajectory and b) that the majority of the queries posed are obfuscating | Rather than posing the learning queries randomly, formulate MDP in the next section, which exploits the stochasticity of the oracle for optimally scheduling the queries.
3 Controlling the Stochastic Gradient Descent using a Markov decision process
This section formulates Markov decision process that the learner L solves to obtain policy to dynamically choose between posing a learning an obfuscating query. The MDP is formulated for finite horizon and infinite horizon case, and we prove structural results characterizing the monotone threshold structure of the optimal policy.
3.1 Finite Horizon Markov Decision Process
In the finite horizon where the learner wants optimize once and needs M successful updates (obtained from Theorem[or chosen suitably) to achieve 3 with N(> M) queries. Such formulation helps model covert optimization of the current literature for one-off FI. task or a series of training tasks carried out one after the other.
The state space is an augmented state space of the oracle state space So and the learner state space Sr.- The oracle is modeled to have W oracle states, So = 21. W}. The learner state space has M states, Sy = {1, 2,.,,..... M} which denote the number of successful updates left to be evaluated by the learner. The augmented state space is S So St. The state space variables with n queries remaining (out of N) is denoted by 3n, (4.. w²) As described in the obfuscation strategy, the learner can query either lear using (4) or to obfuscate using 5 the action space is U {0- obfuscate,
learn). uh denotes the action when n queries are remaining.
Y So x u + [0, 1] denotes the probability of a successful update of (4) and is dependent on y and action uns T(u
0 vn.) = P (o? < o² :n) 1 (u,, = 1). Hence, the bounds on the noise variance in (A2) of the SGD are dynamic and modeled as a finite state Markov chain. The learner state reduces by one if there is a successful update of (4) hence the transition probability between two states of the state space given by,
P(y-- u,,) P(0h-110)) (T(yn Un 1 D/ - 1) +(1 +(1-T(yi un = -
With n queries left, for action, u, the learner incurs privacy cost, c(u,: y which accounts for the increase in the useful information known the cavesdropper. At the end of N queries, the learner incurs terminal learning cost (1)6) which penalizes the remaining number of successful updates v/- The following assumptions are made about the MDP:
(M1) The rows of the probability transition matrix between two states of the oracle are assumed to be first-order stochastic dominance orderable (Eq. (1) of Ngo & Krishnamurthy (2009), i.c., Σxz P(y kly = j) <
This can he extended obfuscating with multiple intervals hy using auxiliary trajectories and ohfuscating by choosing uniformly between those.

---

Published in Transactions on Machine Learning Research (01/2023)
E kly? = 1= 1...., W. This is restatement of the assumption that oracle in better state is more likely to stay in better state, which is found to be empirically true for most computer networks.
(M2) cluns yn ) is chosen to decrease in Un and also decrease in oracle cost yn to incentivize learning when the oracle is in a good state. The learner does not incur privacy cost when it does not learn, i.c., c(0, yo) = 0.
(M3) 1(y6)) is increasing in yd' integer convex, 1y96 + 2) 1yb6 + 1) 1yb6 + 1) 1(v6) and I(0) =
(M4) With queries remaining, the learner has information on Yn. and eavesdropper does not have any information.
For a Fl. setting, (M1) assumes that if the client participation is high, it is less likely to drop suddenly. (M2-M3) ensure that the optimal policy prioritizes learning in a better oracle state, i.e., when the variance is more likely to be bounded. Integer convexity from (M3) in prove the structural results and ensures that the learning is prioritized more when the learner queue state is larger. The asymmetry in information in (M4) can be explained by (EI) since the eavesdropper is assumed to be a part of much larger oracle. The objective for the finite horizon MDP can be formulated as minimizing the state action cost function Qu (y: u).
(v) min Qu(y, u), VyES, wEll
where, (v, u) = c(un, + P(v'lv v and Vn (v) is the value function with n queries remaining and Vo())= = U(y6). ). The optimal decision rule is given by. (1) = arg win Qn u). The optimal policy 1² is the sequence of optimal decision rules, V v²())= = (u) - (1).)).......
3.2 Infinite Horizon Constrained Markov Decision Process
This subsection formulates the infinite horizon constrained MDP (CMDP), highlights the key differences from the finite horizon case, introduces the optimization queue, and proves its stability. The CMDP formulation minimizes the average privacy cost while satisfying a constraint on the average learning cost. An optimization queue helps model the learner performing optimization repeatedly, which is needed for purging specific data, distributional shifts, and active learning.
Optimization Queue: The learner maintains a queue with the number of successful updates it needs to make, vy at time n. In contrast to the finite horizon case, the learner receives new requests and appends the optimization tasks to its queue. At time 71, y new successful updates required are added to the queue. y is an i.i.d. random variable with PEEE- = M) = 5, (EE,, = 0) = - - and (E,) = dM 5 In order to ensure the queue is stable, we pose conditions on the success function Y, the learning cost 1, and the learning constraint in Lemma
The state space for the new arrivals to the queue is Sy {0, M). Also, the learner state is denumerable, Sr. 1.. J. The oracle state space, So is the same before. The state space is now, S = So X St x Sg. The state variables at time (n denotes the time index for deciding this section) are given by yn. = (v v....))
v..).
The transition probability now has to incorporate the queue arrival, with the same as before and can be written as,
P( 13h, un) = ((vetilu, (( PP (I(2n un u.) vh + - - 1)
(8)
+(1 T u,,)) ( 2t +y)))
The learning cost in the infinite horizon case is redefined as I(u,, vi) and is decreasing in u, and increasing in U which contrasts with c. The learning cost does not depend on y except when : = 0, [u,, vn = 0 Vu,, E L vh E So. The privacy cost c(u,, yn ), assumptions (M1-2), and the action space I are the same as the finite horizon case.
In the infinite horizon case, a stationary policy a map from the state space the action space, v S - U. Hence the policy generates actions, V (u1, .2....). Let T denote the space of all stationary policies. The average privacy cost and the average learning cost, respectively, are,
N c(un, vi0 yo ===1
N Σ ==
Cyp (v) = lim E,
Σ
Lyg (v) = lim sup E,
Uuun
yo
No000 N
No0 N
Thhe construction of 8 and the i.i.d. condition convenience and we only require that 5 is independent of the learner and the oracle state.
7

---

Published in Transactions on Machine Learning Research (01/2023)
The constrained MDP can then be formulated as,
C (v) s.t. (D) S Ayo E S, VET
inf
where A is the constraint on the average learning cost and accounts for delays in learning. Since the optimization queue can potentially be infinite, to ensure that new optimization tasks at the end get evaluated, we state the following lemma, Lemma 1. (Queue stability) Let the smallest success probability be min ming T(u 1, If.
6M
A
T min
I(0, W)'
then every policy satisfying the constraint in 9 induces stable queue and recurrent Markov chain.
Lemmal T Tensures that the optimization queue is stable. Since the policy of always transmitting satisfies the constraint, the space of policies that induce a recurrent Markov chain is non-empty.
3.3 Structural Results
This subsection proves structural results for the optimal policy solving the MDP and the CMDP. The threshold structure of the optimal policy substantially reduces the search space and is used devising the structured policy gradient algorithm. The following theorem proves that the optimal policy, v* solving the finite horizon MDP of (7) has threshold structure with respect the learner state, vh-
Theorem 2. (Nature of optimal policy v") The optimal policy for the finite horizon MDP of with assumptions (M1-3) is deterministic and monotonically increasing in the learner state, vh
Since the action space consists actions, a monotonically increasing policy is a threshold policy (Fig. Ta)).
0 obfuscate, y < x
(y(n
1 learn,
otherwise
where x(v2) is oracle state dependent threshold and parametrizes the policy. The proof of Theorem 2 is in the Appendix and follows from Lemma supermodularity, and assumptions on the cost and transition probability matrix.
In order to characterize the structure of the optimal policy for the CMDP, we first study an unconstrained Lagrangian average cost MDP with the instantaneous cost, w(u, 90 A) = y + Al(u, y where À the Lagrange multiplier. The average Lagrangian cost for a policy is then given by.
(n A) = lim sup
1 Ey N
Σ wo w O. ;) yo
yo E S.
No0
The corresponding average Lagrangian cost MDP and optimal stationary policy are.
J (A)
inf Joo (v, A). DET
(10)
vx ing (v, X).
WET
Further, we treat the average Lagrangian cost MDP of 100 as a limiting case of the following discounted Lagrangian cost MDP when the discounting factor, 33 goes to 1,
J (v. B, A)
lim sup E, N0000
Σ
3" Un. Un O, A) yo
(11)
Theorem 2 can then be extended to show that the optimal policy of (11 has a threshold structure in terms of the learner
state, - The average Lagrangian cost MDP of (10) is limit of the discounted Lagrangian cost MDPs (11 with an appropriate sequence of discount factors (3,) converging to 1, and therefore has a threshold policy. The existence stationary policy for (TO) is shown in previous work Ngo & Krishnamurthy (2010): [Sennott (1989) and discussed in Appendix B.4, Hence we directly state corollary from Sennott (1989) as a theorem, which shows that the stationary queuing policy for the CMDP in 9 is randomized mixture of optimal policies for two average Lagrangian cost MDPs.
8

---

Published in Transactions on Machine Learning Research (01/2023)
Theorem 3. (Existence of randomized stationary policy) (Sennotti 1993) There exists optimal stationary policy for the CMDP of ( which is randomized mixture of optimal policies of two average Lagrangian cost MDPs,
V = ===pp + + (1-p)
(12)
where Vx, and V2, are optimal policies for average Lagrangian cost MDPs of the form (10) and is the probability with which Vx, is chosen.
Because of Theorem 3 the optimal policy for the CMDP is randomized mixture of two threshold policies and will also have a threshold structure. A threshold policy of the form of (12) has two threshold levels (denoted by Φ for transition from action to randomized action and @ for randomized action to action 1) can be written as,
0,
y < Φ1 Φ S y < 02 Φ y²
v" vv)
with prob. p:
(13)
1,
We next propose efficient reinforcement learning algorithm that exploits this structure to learn the optimal stationary policy for the CMDP.
3.4 Structured Policy Gradient Algorithm
The optimal policies for both the finite horizon MDP and infinite horizon MDP using existing techniques of either value iteration linear programming, but these methods require knowledge of the transition probabilities. Hence search for the optimal policy without the knowledge of the transition probabilities, we propose policy gradient algorithm which has a linear time complexity in the learner state space.
In order to efficiently find the optimal policy of the form of constructed as follows,
13 we use an approximate sigmoidal policy D(y, θ)
h
1 h
byy, θ)
(14)
exp +0
cxp +0
where 0, and O2 are a parameter which approximates the thresholds and the randomization factor p, Φi and d2. h approximates the mixing probability Parameter 7 controls how close the sigmoidal policy follows a discrete threshold policy. It can shown that as - 0, h p. 0, -> di and 0g - dh. the approximate policy converges to the true policy (yy )) + v" (Ngo & Krishnamurthy 2010 Kushner Yin 2003).
Algorithm Structured Policy Gradient Algorithm
Input: Initial Policy Parameters Oo. Perturbation Parameter w, K Iterations, Step Size n, Scale Parameter Learning cost I, Privacy Cost c Output: Policy Parameters θк
procedure COMPUTESIATOONARPOLCCY../ K, for +- 1...K K do
r + Bernoulli())
b3 x |So[|Se| i.i.d. Bernoulli random variables 0 +- θ, +I w. 0 - - AVGCOST(.e))
Ál + (AvGCOST((,, θ#) AVGCOST(I, 0,)) Ac t (AvaCosT((c, + AvaCosT(c,0,)
O, and S. using 15
end for end procedure procedure AvGCoST(J, θ)
i - POLICYTRROMPAAMMEERSSSS j- J((m)) end procedure

---

Published in Transactions on Machine Learning Research (01/2023)
C
Central Learner
Distributed Oracle
Training Queue
Clients
leazn obEuscaLe
Task 1
9
Task 2
weight update
E
Training data size, of clients
Lavesdropper
Retraining requests
(t) purging client data (b) training on new context
Figure 2: Learner L either learns from the oracle O (distributed clients) or obfuscates the eavesdropper & based on the oracle state (number of clients) and the queue state (number of successful training rounds). Learner (central aggregator in FL) updates its queue state based on the response (size of the training data) and the action taken.
A policy gradient algorithm that finds an optimal policy of the form (12) for solving the CMDP of (9) is now proposed. For each oracle state, the parameters for the approximate policy of (14) is given by (0,, 02 h). The complete set of policy parameters (total of 3 SSo parameters) is referred to as, O The procedure is summarized in Algorithm I
13 by taking an approximate gradient of the average costs, the constraint in ( and &, which updates using [5) The parameters which are updated are chosen randomly using a vector r, the components of which have an i.i.d. Bernoulli distribution. These chosen parameters are perturbed by +w and -w and the approximate gradient of the privacy and learning cost denoted by Ac and Al, respectively. The approximate gradients of these costs are computed using finite difference method on the approximate costs. The approximate average costs computed by interacting with the Markovian oracle for T timesteps. The approximate average learning cost is denoted by i. and p are suitably chosen step and scale parameters
Our policy gradient algorithm updates the parameter estimates O, using
On+1 = O (Ac+ + Ál x max
0, ((-)))
(15)
En+1 max
(11
"En p
fi .n + (i-
The SPGA algorithm can run on faster time scale by interacting with the system paraliel to the SGD and updating the stationary policy parameters, O. The stationary policy controls the query posed and updates the SGD estimate in T The computational complexity for the SPGA algorithm described here O(SS), i.e., the algorithm linear the state space and hence significantly more scalable than standard policy gradient methods (Kushner & Yin 2003).
3.5 Alternative discrete optimization formulation for threshold identification
Since the SPGA algorithm is not amenable to finite time complexity analysis, an alternative approach to solve for the threshold levels by formulating the problem multi-armed bandits (MAB). Considering each possible configuration of Y [Sol|Sel thresholds (each of which can take values) for the Lagrange constrained problem of [1] arms
in a MAB problem, the minimum achievable regret is of the order O (u log (Lai & Robbins
1985 The value
of the Lagrange parameter can then be iterated over similar to the value iteration of Ngo & Krishnamurthy 2010) to
obtain the two Lagrange multipliers and the randomization probability which form the optimal policy of (13). The main
disadvantages of MAB approach compared to the SPGA is that there are strong assumptions on the noise structure, it is unable track changes in the underlying system and the time complexity exponential in the state space.
"The step size constant if the SPGA track change in the underlying system and decreasing otherwise.
10

---

Published in Transactions on Machine Learning Research (01/2023)
4 Hate speech classification in a federated setting
We now present a novel application of the covert optimization framework in designing robust hate speech classifier illustrated in Figure 2 The task of the learner L is to minimize classification loss function (fx)) and simultaneously hide the optimal classifier (neural network) parameters (arg min ((x)) from an eavesdropper (E).
State Space: In our federated setting, the oracle state, yo denotes the number of clients participating in each communication round, and more clients indicate a better state. Client participation is assumed be Markovian since it more general than i.i.d. participation and is closer Although the stochastic aspect of the oracle is modeled on client participation and the quantity of the training data, it can also be modeled with respect to the quality. For example, in hate speech detection and similar applications, unintended bias based on characteristics like race, gender, etc. often occurs (Dixon et al.) 2018). If the oracle is based on how diverse the training data is, we can train when the available data is good enough and obfuscate otherwise using costs related to biased classification Viswanath et al. 2022). The learner state, y², denotes the number of remaining successful gradient updates. The learner decides the total number of required successful gradient updates based on convergence criteria, like the one in Theorem | A successful gradient update is done if the number of available training data is above threshold, similar to communication skipping using system parameters in [Sun al. (2022): )
real-world scenario (Sun et al. 2018 Rodio al.) 2023)
Mishchenko et al. (2022). This is proxy for the threshold of in (A2) since an exact noise bound is difficult to obtain in practice. The optimization queue receives new arrivals, yf for model retraining due to client requests for unlearning their data, data distribution shifts, and active learning (Bachman et al. 2017 Sekkari et al.) 2021 Cai et al., 2021). The timescale for practical federated training ranges from a few hours to a few days (Hard et al. 2019). In the hate speech classification, model retraining requests due to a shift context is on a slower time scale, but purging requests for a client's data can be made every few hours. All devices, including the ones not participating in the training round can make such a request ensuring 5 is independent of yo (E1).
Action Space: Using labeled datasets, GANs can be trained to generate hate speech (Lin et al. 2017 de Masson d' Autume et al. 2019). But since access to labeled data is difficult, an eavesdropper & can use the optimal weights as discriminator weights to train a generator (Wang et al. 2018). The action space, 24 is to either send the correct learning neural network parameters or the obfuscating parameters. We discuss in the next section how to generate obfuscating parameters under two different eavesdroppers' information scenarios.
Costs: Although for this paper, only a majority of queries need to be obfuscating, in general, the more learning queries eavesdropper knows, the higher probability of the eavesdropper figuring out the optimal weights. Hence the eavesdropper can generate hate speech and misinformation which are semantically more coherent (measured by metrics of readability and perplexity (Carrasco-Faart) 2022] Mimno et al. 2) and can be spread easily (Viswanath et al.] 2022). Hence the privacy cost in the MDP can be associated with metrics of the spread of malicious content, including prevalance (Wang et al., 202I), and contagion spread rates (Davani et al. 2021 Lawson ct al. 2023). Analogously, the learning cost can be associated with the same set of costs since malicious content will go unclassified if the classifier does not achieve the desired accuracy. For delays in forgetting client's information, the learning cost is analogous to the value of private information, measured by metrics like Shapeley value [Kleinberg] 2001] |Wang al. 2020). Also, clients might want to remove their data because they incorrectly annotated it earlier, and keeping the retraining task in the queue can worsen the real-time accuracy (Davani et al., 2021 Klie et al., (023). The privacy and learning cost and the learning constraint, A of (9) can be chosen appropriately depending on the maximum ratio of the queries the learner can afford to expose, which for the proportional sampling estimator is 0.5.
4.1 Numerical Results
For the first experiment, the MDP formulation and structural results are demonstrated hate speech classification task under federated setting described above. The convergence of the threshold parameters in SPGA is investigated in the second experiment. It is empirically shown that the optimal policy solving 9 is threshold in the oracle state, demonstrating that the optimal policy makes the learner learns more when the oracle is good. Additional benchmark experiments on the MNIST data, dataset preprocessing, the architecture, and assumptions are listed in the Appendix. Before discussing the numerical study, we explain two scenarios with respect to the information that the eavesdropper has and the information the learner has about the eavesdropper. The results of the study are then presented under both scenarios.
11

---

Published in Transactions on Machine Learning Research (01/2023)
0.8
0.8
Accuracy Score
Accuracy Score
0.6
0.6
0.4
0.4
2 acc. under Optimal Policy
acc. under Optimal Palicy
0.2
acc. under Optimal Policy
0.2
C acc. under Optimal Policy
acc. under Greedy Policy
acc. under Greedy Policy
C acc. under Greedy Palicy
C. acc. under Greedy Policy
0.0
0.0
10
30
10
20
30
40
Communication Round
Communication Round
(a) Eavesdropper with public dataset having no positive samples.
(b) Eavesdrupper with dataset having 10% positive samples.
Figure 3: Convergence of validation accuracies for Learner L and Eavesdropper & under greedy and optimal policy. The optimal policy helps dynamically learn and hide the optimal weights compared a greedy policy of always learning.
Scenario 1: Eavesdropper does not have enough data: When the eavesdropper does not have enough data to choose between the two SGDs, the obfuscating queries can be posed in various ways, for example, by posing noisy queries sampled randomly from domain I or by doing a mirrored gradient descent using the true queries in ( Since the eavesdropper has no information, the prior over the two SGDs the same. An extension of this scenario is when the learner is trying to obfuscate hyperparameters which are essential training neural network (Probst al. 2019) from the eavesdropper. The learner switch between the intended hyperparameter and suitably chosen obfuscating hyperparameter.
Scenario 2: Eavesdropper has subset of data, but the learner has information about the subset: In case the eavesdropper has access to subset of the data, it can test out both the trajectories on its dataset to see which one has a smaller empirical loss. Let the dataset of the eavesdropper be Do E D. If the learner knows Do, then it can simulate an oracle with function f'(x: = (ar Do) = DDo EdED, 9(x, d) to obtain noisy gradients, r/c = V (qx) + 7/e where G is the loss function and 1/4 is suitably simulated noise. The obfuscating queries can be obtained using the following SGD trajectory: & = - / 1 (ux = 0). For example, when the eavesdropper is using public dataset, accessing a reliable and balanced datasct is otherwise costly. The case where learner has incomplete information about the eavesdropper's 's dataset left for future research. The case when the eavesdropper has access to all data is not relevant since then the cavesdropper can carry out the optimization on its own. The weights obtained using the parallel SGD do not generalize well since the empirical loss being minimized is for subset of the data. This makes the prior over both the SGDs more balanced since the eavesdropper can no longer take advantage of its dataset. And because the parallel SGD is observed the majority of the time, then the eavesdropper's estimate (6) corresponds to the parallel SGD.
4.2 Demonstration of MDP framework on Covert Optimization in Hate Speech classification
A hate speech classification task is considered where extended version of pre-trained BERT (Devlin et al.) 2019 Ture al. 2019) model is fine-tre trained labeled dataset to classify textual data as toxic not [ A federated setting with 20 clients whose data is non-overlapping is considered. Each client has 5443 training samples and 1443 validation samples. For the experimental results, we consider N = 45 communication rounds (or queries) and M = 16 successful model updates (which is around ~ 34% of the total queries). To demonstrate the versatility our formulation, we use the FedAvg algorithm, where the learner aggregates the weights of the individual clients rather than the weight updates (MeMahan et al. (017). The experiment is done with random seeds to obtain error bounds. We use size of the training data proxy for aı since exact 0 is difficult estimate, A threshold on the noise bound (a) is approximated with the threshold on the number of data points, i.c., the learner discards any communication round when
'The dataset used was made public by Jigsaw and found here Hate speech classification is still open problem and achieved accuracy harely satisfactory but our aim was show the application of formulation. source code can found this anonymized link
12

---

Published in Transactions on Machine Learning Research (01/2023)
less than 1/4 of the entire dataset is available for training The underlying Markov chain of the device participation has three states, i.e. either Wi = 1/4, W2 = 1/2 or W3 1/1 of the devices participating in any communication round. Each device can contribute any number of data points out of the available datapoints, and for the chosen criteria, the success function empirically comes out to be Tyy 1) = [0.1. 0.43, 0.95]. The transition probabilities between the oracle states given by po = [0.8 0.2 0; 0.3 0.5 0.2; 0 0.2 0.8). The privacy cost, e is taken to be 0.3, 0.8, 1.8 for the respective oracle states and the learning cost, I to be 0.6. The choice of the cost done by interacting with the system and seeing the average proportion of queries obfuscated using the stationary policy as shown in Appendix A.4.3 This cost can also be tuned in online fashion based on the number of slots available, the learner's 's preference, and the percentage of queries the learner can afford to expose hence enabling practical realizability of previous work on covert optimization (Xu et al. 202la). Since this is finite horizon MDP, the learner can use linear programming or value iteration to find an optimal policy using empirical estimates of the transition probabilities using past data or can use the SPGA algorithm and interact with the system to find a stationary sub-optimal policy. We show our results using a stationary policy obtained by using the SPGA algorithm, hence the learner does not know P(yn+1 11 una)
Figure 3 a) shows the convergence of the aggregated validation accuracies for the learner and the eavesdropper under Scenario under a greedy and stationary policy. The loss function considered is the binary cross entropy loss function, and the accuracy is the validation accuracy score. The eavesdropper accuracy is calculated using a balanced validation dataset of size 2886. It can be seen that although the learner's accuracy. on average goes up to 0.85, the eavesdropper's accuracy goes up to 0.52. Figure 3b) is for Scenario 2 with an eavesdropper with an imbalanced dataset of 10% toxic (one of the two classes) examples. This dataset is assumed to be public, and the learner has complete access to it, which it uses to obfuscate the eavesdropper. In Figure b). it is evident that the obfuscation achieved is lesser than when the eavesdropper had no toxic samples since the eavesdropper is able achieve accuracy of around 0.69, explained by the fact that the obfuscating parameters are trained sample of the entire dataset. Although, in both cases, when the learner uses greedy policy, the eavesdropper's accuracy is at par with the learner's 's accuracy. This demonstrates how using the optimal policy, the learner can prevent an eavesdropper from learning the optimal weights of the classifier.
4.2.1 Convergence of SPGA algorithm and numerical structural result
The convergence of Algorithm to the true threshold pa- rameters is investigated next. In addition to the previously defined parameters, a learning constraint A = 0.2 is im- posed on the average learning rates, setting up CMDP whose objective is given by (Q). The arrival probability For calculating the
8: 0
8, 0-002
0 0= 3
c 0= 1
for M- 4 queries is 5 0.1 10
Parameters
c 0=
approximate average cost, we take a sample path of 100
4: 0-3
timesteps. The results are averaged over 100 runs. The
convergence of the threshold parameter Φ2 for different oracle states with arrival state E = 0 is plotted in Figure along with the true threshold parameters found by linear programming.
The approximate thresholds, 02 of the sigmoidal policy of [4] converge close to the true threshold parameters, db without the knowledge of the transition probabilities. The threshold for the oracle state converges to negative value which when plugged into the sigmoidal policy of (4) resemble a threshold policy with threshold 0 since the learner state can not be negative. It can be numerically seen that the threshold of optimal policy decreases with increasing oracle state; that is, the optimal policy is non- increasing in the oracle state hence the learner poses learning query more often when the oracle is in good state.
1000
2000
4000
5000
Iterations
Figure 4: Convergence of threshold parameters 0 to true threshold parameters é in Alg. 1 for different oracle states. The optimal policy incentivizes learning more when the oracle is in a better state.
Recent work in federated learning has proposed skipping training rounds when the distributed oracle is not good enough leading to less communication rounds and better convergence rates (Chen et al. [2018] (Sun al. [222 Mishchenko | 2002).
1hhis slightly different from the theoretical model since it not possible simulate infinite butter, consider length 40 queue, and to prevent queue overflow high leamingg cost of 100 imposed case the queue full. This consideration similar to previous work network
queueing using CMDP approach and does change the threshold and monotone nature of the policy (Djonin & Krishnamurhy 2007
13

---

Published in Transactions on Machine Learning Research (01/2023)
The parameters for the SPGA algorithm along with an additional experiment with constant step size is given in Appendix A.6
5
Conclusion
The problem of covert optimization is studied from dynamic perspective when the oracle is stochastic, and the learner receives new optimization requests. The problem is modeled as Markov decision process, and structural results are established for the optimal policy. A linear time policy gradient algorithm is proposed, and the application of our framework is demonstrated in a hate speech classification context. Future work can look at inverse RL techniques for the eavesdropper to infer the optimal learner policy, and more robust obfuscating gradient trajectories can studied. The problem of covert optimization can be investigated in a decentralized setting where the problem is modeled switching control game with participants switching between learning and obfuscating others. Our suggested methodology dynamically control learning in distributed settings for objectives like energy efficiency, client privacy, and client selection. An eavesdropper with finite memory and objective of minimizing average learning cost with constraint on average privacy cost can be considered. This work's s main broader ethical concerns are a) an increase in energy consumption to achieve covertness and b) it could help a learner covertly train a classifier for questionable reasons, e.g., censorship.
References
A. Ajallocian and S. U. Stich. On the Convergence of SGD with Biased Gradients, May 2021. //axxlv.org/abb//0000 00050 arXiv:2008.0000 [cs, math, stat].
URL http:
H. Asi, V. Feldman, T. Koren, and K. Talwar. Private Stochastic Convex Optimization: Optimal Rates in LI Geometry. In Proceedings of the 38th International Conference Machine Learning, pp. 393-403. PMLR, July 2021. URL
http:///ooeeeeenoooooo..eeeeee/s mlr wtt..ppeess//11/ss22222 html
ISSN: 2640-3498.
P. Bachman, A. Sordoni, and A. Trischler. Learning Algorithms for Active Learning. In Proceedings of the 34th International Conference Machine Learning, pp. 301-310. PMLR, July 2017.
http::s//proceeeiing ngs
mlr. wttpppsss/////aaaaaaaaaaa aa html
ISSN: 2640-3498.
M. R. Bloch. Covert Communication Over Noisy Channels: Resolvability Perspective. IEEE Transactions on Information Theory, 62(5):2334-2354, May 2016. ISSN 1557-9654. doi: 10.11099 Conference
Name: IEEE Transactions on Information Theory.
L. Bottou. Stochastic Learning. O. Bousquet, von Luxburg, and G. Rätsch (eds.), Advanced Lectures on Machine Learning: ML Summer Schools 2003, Canberra, Australia, February 14, 2003, Tübingen, Germany, August 4 16, 2003, Revised Lectures, Lecture Notes in Computer Science, pp. 146-168. Springer, Berlin, Heidelberg, 2004. ISBN 978- 978-3-540-28650-99
doi: 10.10077978-3-540-2288
URL httpt::t//// /tte::///ooooooo http:///ooooo//11.0000.00000
978 3 3-8---400286--99
T. Cai, R. Gao, J. Lee, and Q. Lei. Theory of Label Propagation Subpopulation Shift. In Proceedings of the 38th International Conference on Machine Learning, pp. 1170-1182. PMLR, July 2021. URL https: //prccediing ngs. www.mmmrr... /ttea/////nn......r.ee/s//////// callb////////.b....../.b..b html ISSN: 2640-3498.
C. Carrasco-Faréé... The fingerprints misinformation: how deceptive content differs from reliable sources in terms of cognitive effort and appeal to emotions. Humanities and Social Sciences Communications, 9(1):1-18, May 2022. ISSN 2662-9992 doi: 10.
URLhttps. wwww./ www.:naauue.cmm www.nattuze.comartt..ee wtt.ccoomaarr.e.....
641599-022-01174- Number: Publisher: Palgrave.
T. Chen, G. Giannakis, Sun, and W. Yin. LAG: Lazily Aggregated Gradient for Coammunication-Efficci Distributed Learning. In Advances in Neural Information Processing Systems, volume 31. Curran Asso- ciates, Inc., 2018. URL httplatt///cccceinnnngeo wwwp:eeedddeeeeeeeiee.e..e..e cwtpppppp.cpppppp..ppppm hwteaaaper_iee/ppaaaaaeee fwt.ss/ppper//18///aaaa
html
14

---

Published in Transactions on Machine Learning Research (01/2023)
T. Chen, K. Zhang, G. B. Giannakis, and T. Başar. Communication--fiee Policy Gradient Methods for Distributed Reinforcement Learning. IEEE Transactions on Control of Network Systems, 9(2):917-929, June 2022a. ISSN 2325-5870. doi:
Z. Chen, S. Zhang, T. Doan, J.-P. Clarke, and S. Maguluri. Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning, January 2022b. URL http://azxiv.on
1905. 11 1425 arXiv: 1425 [es, math].
A. M. Davani, M. Atari, B. Kennedy, and M. Dehghami. Hate Speech Classifiers Learn Human-Lise Social Stereotypes, October 2021. URL http::t:t/aiii.../ot wttp:/iioooooooooooe.. abs /2100. 14839 1eXiv:2110.1444 [cs].
C. de Masson d' Autume, Mohamed, M. Rosca, and J. Rae. Training Language GANs from Scratch, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL httpstttttssssceeeeeeeeeo
neur
htt.raaccccccccccccccccceaaaaaaa Abstract.html
T. Delahaye, R. Acuna-Agost, N. Bondoux, A.-Q. Nguyen, and M. Boudia. Data-driven models for itinerary preferences of air travelers and application for dynamic pricing optimization. Journal of Revenue and Pricing Management, 16 (6):621-639) December 2017. ISSN 1477-657X. doi: 10. 00.1057/s41222-017-005555
[RLptst::////o1
10. 10.1057/s4127/ 01 0095-2
A. Dethise, M. Canini, and S. Kandula. Cracking Open the Black Box: What Observations Can Tell Us About Reinforcement Learning Agents. In Proceedings of the 2019 Workshop on Nenwork Meets Al & ML. NetAI' 19, pp. 29-36, New York, NY, USA, August 2019. Association for Computing Machinery. ISBN 978-1-4503-6872-88 10. 10.11433441211.3322211 URL BRLLhttps://ddi acm. http://aaa....goo/o//11.1.0 /tt////oo111111/333342222223
doi:
3342210
J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding, May 2019,
04805
[es].
D. Dimitrov, M. Balunovic, N. Konstantinov, and M. Vechev. Data Leakage in Federated Averaging. Transactions on Machine Learning Research, November 2022. ISSN 2835-8856. UR//ttppe///peeneeree...ttt formm
id=e www.0999eennnotteeeeeeeeeee
L. Dixon, J. Li, J. Sorensen, N. Thain, and L. Vasserman. Measuring and Mitigating Unintended Bias in Text Classification. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, AIES '18, pp. 67-73, New York, NY, USA, December 2018. Association for Computing Machinery. ISBN 978-1-4503-601224 10. 10.1145/3278211322777777
doi:
acm. htt.://s........ooorr./////////. 327777
D. Djonin and V. Krishnamurthy. MIMO Transmission Control in Fading Channels- Constrained Markov Decision Process Formulation With Monotone Randomized Policies. IEEE Transactions on Signal Processing. 55(10):5069-508) October 2007. ISSN 1941-0476. doi: 10.11099/TSP22007.877555 Conference Name: IEEE Transactions on Signal Processing.
T. T. Doan, L. M. Nguyen, N. H. Pham, and Romberg, Convergence Rates of Accelerated Markov Gradient Descent with Applications in Reinforcement Learning, October 2020. URL http::t/axiiv..o/ wwg. httpg////////.....o/g 02873 arXiv:2002.02873 [math].
M. S. Erturk and K. Xu. Anonymous Stochastic Routing. December 2020. URL http::/aaxvv..orgaa///saeea 08875 arXiv: 191.08978 [cs, math].
S. Ghadimi and G. Lan. Stochastic First- and Zeroth-Ordas Methods for Nonconvex Stochastic Programming. SIAM Journal on Optimization, 23(4):2341 January 2013. ISSN 1052-6234. doi: 10.1137/120880111 URL https::/ s am. wttp:///00//111111/11233...53..0 Mathematics.
Publisher: Society for Industrial and Applied
A. Ginart, M. Guan, G. Valiant, and Y. Zou. Making AI Forget You: Data Deletion in Machine Learning. In Advances in Neural Information Processing Systems, volume 32. Cur- ran Associates, Inc., 2019. URL cb cb79FFfas8b91dda hrt.s//cchaaaaaaacccccccccoooee. Abseddda-bbatrtt.ccc.mm html
15

---

Published in Transactions on Machine Learning Research (01/2023)
A. Hard, K. Rao, R. Mathews, S. Ramaswamy, F. Beaufays, S. Augenstein, H. Eichner, C. Kiddon, and D. Ramage. Federated Learning for Mobile Keyboard Prediction, February 2019. 2XXv:1811.00660 [cs].
03604
T. Hartvigsen, S. Gabriel, H. Palangi, M. Sap, D. Ray, and E. Kamar. ToxiGen: A Large- Scale--Sallaaa
Dataset for Adversarial and Implicit Hate Speech Detection. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 3309-3326, Dublin, Ireland, May 2022. Association for Computational Linguistics. doi: 10. wow.://..o.......oooo..o..o URL WtRLhttp::/// /ttLtpp:///alaaahoooog
org/ 202220022..0 aci- acl-lonng--........o 234
M. Heusel, H. Ramsauer, T. Unterthiner, B. Nessler, and S. Hochreiter. GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL https::/prooeeeingg..... http://00//////16600000066111110
wwwppppr.ppppppeeeeeeeeeeeeeeeee files// html
D. Jhunjbunwala, P. Sharma, A. Nagarkatti, and G. Joshi. Fedvarp: Tackling the variance due to partial client participa- tion in federated learning. In Proceedings of the Eighth-Eighth Conference on Uncertainty Artificial Intelligence, pp. 906-91 906 PMLR, August 2022. URL https: wwtpt::t////eeeeee httsss///coceeeings.ooo mlr wrw.ppressssv.... jaan jhuraahaaaaaa222 atml
ISSN: 2640-3498.
P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode,
R. Cummings, R. G. L. D'Oliveira, H. Eichner, S. Rouayheb, D. Evans, J. Gardner, Z. Garrett, A. Gascón, B. Ghazi, P. B. Gibbons, M. Gruteser, Z. Harchaoui, C. He, L. He, Z. Huo, B. Hutchinson, J. Hsu, M. Jaggi, T. Javidi, G. Joshi, M. Khodak, J. Konečný, A. Korolova, F. Koushanfar, S. Koyejo, T. Lepoint, Y. Liu, P. Mittal, M. Mohri, R. Nock, A. Özgür, R. Pagh, M. Raykova, H. Qi, D. Ramage, R. Raskar, D. Song, W. Song, S. U. Stich, Z. Sun, A. T. Suresh, F. Tramèr, P. Vepakomma, J. Wang, L.. Xiong, Z. Xu, Q. Yang, F. X. Yu, H. Yu, and S. Zhao Advances and Open Problems in Federated Learning, March 2021. URL arXiv:1912.04977 [cs, stat].
S. P. Karimireddy, S. Kale, M. Mohri, S. Reddi, Stich, and A. T. Suresh. SCAFFOLD: Stochastic Controlled Averaging for Federated Learning. In Proceedings of the 37th International Conference on Machine Learming, pp. 5132-5143. PMLR, November 2020. URL htttp:: http://ppeeeaailo..o.rppp/a///es ISSN: 2640-3498.
mllr http://eee//111///airrreeee////e
D. P. Kingma and J. Ba. Adam: Method for Stochastic Optimization, January 2017. URL httPhttt:///axiv.orrr abs/14122 6980 arXiv:1412.6980 [es].
J. Kleinberg. On the Value of Private Information. TARK '01: Proceedings of the 8th conference on Theoretical aspects of rationality and knowledge, July 2001.
J.-C. Klie, B. Webber, and I. Gurevych. Annotation Error Detection: Analyzing the Past and Present for More Coherent Future. Computational Linguistics, 195 March 2023. ISSN 0891-2017. doi: 10.1162/coli_a_000 URL
attps:///oi http://od...rr/1111111//////////
00444
H. Kushner and G. G. Yin. Stochastic Approxiatton and Recursive Algorithms and Applications. Springer Science & Business Media, July 2003. ISBN 978-0-387-00894-3, Google-Books-ID: EC2W1SaP67YC
T. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4222 March 1985. ISSN 01968858. doi: 10. 10.1016/0196-88552 00800009966--5588999000--- URU/tttps://Linking elw.eeee lsevier com/ coon//aarrieeee/////1666688
M. A. Lawson, S. Anand, and H. Kakkar. Tribalism and tribulations: The social costs of not sharing fake news.
Journal of Experimental Psychology: General, 152(3)661 1-331, March 2023. ISSN 1939-2223 2222, 0096-3445. doi: 10. 10.10377xge00001374 URL/attp://doi.ce www.:/p...ggg.......oo..
org gww.oi.tdii..ooooo wttp::iiffmcmmmm000mm0mm 1037 1000////////333444444
H. Lee, J. Kim, S. Ahn, R. Hussain, S. Cho, and J. Son. Digestive neural networks: A novel defense strategy against inference attacks in federated learning. Computers & Security, 109:102378, October 2021. ISSN 0167-4048.
doi: co.ee1/j..osee.02211 htt.0//..............//.../.../. http://wwww.ceeeeeeeeeeeeeeeeeee 501 01167704221000 002029
URL htLLhttps//www.sieecceee
16

---

Published in Transactions on Machine Learning Research (01/2023)
K. Lin, D. Li, X. He, Z. Zhang, and M.-t. Sun. Adversarial Ranking for Language Genera- tion. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
URL https:/pproceeiingg nwwripuurricmoo wwwpriips.cpppppr....eepe FiLes//pper/2217/naa BEZD:5507250011555cc3333777776-2
html
Z. Liu, Y. Yang, T. Miller, and P. Masters. Deceptive Reinforcement Learning for Prreecy- Planning, February 2021. URL Bothttp:/// http:///rxiyy http:/gggg/a/aoaee http://www...g//a////222..222220
arXiv:2102.03022 [cs].
A. Mallick, K. Hsich, B. Arzani, and G. Joshi. Matchmaker: Data Drift Mitigation Machine Learning for Large-Scale
Systems. Proceedings of Machine Learning and Systems, 4:77 94, April 2022. URL httL/tttpp////reeed.noo
-tw.e:/abbbbbbatttttttooo m http:////ww../2/22ccccccccc322.2
R. Mattila, C. R. Rojas, V. Krishnamurthy, and B. Wahlherg. Computing monotone molocone for Markov decision processes: nearly-isotonic penalty approach, April 2017. URL http:://arx....orr/ab///76..... arXiv:1004.00621 [es].
B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y. Arcas. Communicatonn-ffiiieen Learning of Deep Networks from Decentralized Data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pp. 1273-1282. PMLR, April 2017. URL ISSN: 2640-3498.
v54 1044/mmmhaa111 7a..mml.. html
E. Meskys, J. Kalpokiene, P. Jurcys, and A. Liaudanskas. Regulating Deep Fakes: Legal and Ethical Considerations, December 2019. URL htttht:sp//ppppet
ssrn. com/ httm//bbtraat=39144444.
D. Mimno, H. Wallach, E. Talley, M. Leenders, and McCallum. Optimizing Semantic Coherence in Topic Models. EMNLP '11 Proceedings of the Conference Empirical Methods in Natural Language Processing, July 201 1.
K. Mishchenko, G. Malinovsky, S. Stich, and P. Richtarík. ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally! In Proceedings the 39th International Conference Machine Learning. pp. 15750-15769. PMLR, June 2022. htt.t:ttp///// / http///pcccenng..c/oe///oo ml r.... press/vl 62 mimmmiiii sichhnn222222
html
ISSN: 2640-3498.
K. Narayan, H. Agarwal, S. Mittal, K. Thakral, S. Kundu, M. Vatsa, and R. Singh. DeSI: Deepfake Source Identifier for Social Media. pp. 2858-2867, 2022. URL
com. comm/conent// CVPR2022W/ TCV/ht/l /Narayan DeSI Deepfaaeeeeeeeeeeee Source Identifier for for_Sociall Media media__VPRV,
2a1222paperrht_.c html
M. H. Ngo and V. Krishnamurthy. Optimality of threshold policies for transmission scheduling in correlated fading channels. IEEE Transactions on Communications, 57(8):2474-2483, August 2009, ISSN 1558-0857. doi: 10.1 ICCOMM2200.08.0705555
M. H. Ngo and V. Krishnamurthy. Monotonicity of Constrained Optimal Transmission Policies in Correlated Fading Channels With ARQ. IEEE Transactions Signal Processing, 58(1):438-451, January 2010. ISSN 1941-0476. doi: 10. 10.11099T9P:20092222773
X. Pan, W. Wang. X. Zhang, B. J. Yi, and D. Song. How You Act Tells Lot: Privacy-Leaking Attack on Deep Reinforcement Learning. Reinforcement Learning, 2019.
P. Probst, A.-L. Boulesteix, and B. Bischl. Tunability: Importance of Hyperparameters of Machine Learning Algorithms. Journal of Machine Learning Research, 20(53):1-32, 2019. ISSN 1533-7928. URL http: /mrr. /
papers/ Papers/v20/22 8- 444.
A. Rodio, F. Faticanti, O. Marfoq, G. Neglia, and E. Leonardi. Federated Learning under Heterogeneous and Correlated Client Availability, January 2023. URL
04632 arXiv:2301.04632 [cs].
S. M. Ross. Introduction Stochastic Dynamic Programming. Academic Press, July 2014. ISBN 978- 1-4832-6909-2. Google-Books-ID: BBIJBBQAAQBAI
17

---

Published in Transactions on Machine Learning Research (01/2023)
A. Sekhari, J. Acharya, G. Kamath, and A. T. Suresh. Remember What You Want to Forget: Algorithms for Machine Unlearning. In Advances in Neural Information Processing Systems, volume 34, pp. 18075-18086. Curran As- sociates, Inc., 2021. URL t
wweeurps..c/ppapee. files Files//paper2222//nss html
L. I. Sennott. Average Cost Optimal Stationary Policies in Infinite State Markov Decision Processes with Unbounded Costs. Operations Research, 37(4):226-633, 1989. ISSN 0030-364X. URL https: ptttps://wwwrr jstor. .oritorrrr/goooooooooo..
org/
stable/171262 Publisher: INFORMS.
L. Sennott. gineering and Informational Sciences, 7(1):69-83) 83, January 1993. 9648. doi: 10.1007/500699644000077755
Constrained Average Cost Markov Decision Chains.
Probability in the En-
ISSN 1469-8951, 0269-
URL
http:///woolltttaaaaaaaaaaaaaaaa 541 04440663311311117773333333333333
art ort.:///5.....c.cttaaaaaaaaaaar0
Publisher: Cambridge University Press.
J. Sun, T. Chen, G. B. Giannakis, Q Yang, and Z. Yang. Lazily Aggregated Quantized Gradient Innovation for Communication-E-fiiiee Federated Learning. IEEE Transactions Pattern Analysis and Machine Intelligence, 44 (4):2031-2044, April 2022. ISSN 1939-3539. doi: (0.1100/PAAM2220000333333
T. Sun, Sun, and W. Yin. On Markov Chain Gradient Descent, September 2018. URL httt:t://///xt..oo abs abs/1809.044 04216
04216 mTXiv:180.042116 [math, stat].
A. Tripp, E. Daxberger, and M. Hemández-Lobato. Sample-Efficient Optimization in the Latent Space of Deep Generative Models via Weighted Retraining. In Advances in Neural Information Processing Systems, volume 33, pp. 11259-11272. Curran Associates, Inc., 2020. URL
ngs. nee.rieursspp weeuripps.ccppppe////000 html
N. Tsitsiklis, K. Xu, and Z. Xu. Private Sequential Learning. Operations Research, 6965 September 2021. ISSN 0030-364X, 1526-5463. doi: 10. 10.1287/0pre:2220.22111 URL http::ttpppp/o// ine. inw.iin.............. informs
2021
I. Ture, M.-W. Chang, K. Lee, and K. Toutanova. Well-Read Students Learn Better: On the Importance of Pre-training Compact Models, September 2019, URL
wttp://.w.rraaaab1......0 08962 arXiv:1908.08962 [cs].
H. Viswanath, A. Shor, and Y. Kitaguchi. Quantifying Human Bias and Knowledge to guide ML models during Training, November 2022.
10796 arXiv:2211.107%6 [cs].
S. Wang, H. Fang, M. Khabsa, H. Mao, and H. Ma. Entailment as Few-Shot Learner, April 2021. URL http:
2244bb///224444 14690 arXiv:2104.1 144.999044. [cs].
T. Wang, J. Rausch, C. Zhang, R. Jia, and D. Song. A Principled Approach to Data Valuation for Federated Learning. In Q. Yang, L. Fan, and H. Yu (eds.), Federated Learning: Privacy and Incentive, Lecture Notes in Computer Science, pp. 153-167. Springer International Publishing, Cham, 2020. ISBN 978-3-030-63376-4 doi: 10.1007/
978-3-030-63076-8 11. URL
3- 030 63076-8
Y. Wang, C. Wu, L. Herranz, J. Van De Weijer, A. Gonzalez-Garcia, and B. Raducanu. Transferring GANs: Generating Images from Limited Data. In V. Ferrari, M. Hebert, C. Sminchisescu, and Y. Weiss (eds.), Computer Vision ECCV 20/8, volume 1 11210, pp. 220-236. Springer International Publishing, Cham, 2018. ISBN 978-3-030-00120-44 978-3-030-01231-L. doi: 10. 1001007797883-00011133---
BtLlhttts:///iit springer. com ctt.:t..ccom000/0/ Series Title: Lecture Notes in Computer Science.
978-3-030-01231- 14
A. C. Wilson, R. Roclofs, M. Stern, N. Srebro, and B. Recht. The Marginal Value of Adaptive Gradient Meth- ods in Machine Learning. In Advances Neural Information Processing Systems, volume 30. Curran Asso- ciates, Inc., 2017. URL https/ttpprccceeeinniiee htwp://www..uuui....ee./ooo httpeeeeeeeeeaaeee/////aaaaae F1333335555435555474444450333333
html
18

---

Published in Transactions on Machine Learning Research (01/2023)
Y. Wu, E. Dobriban, and S. Davidson. DeltaGrad: Rapid retraining of machine learning models. In Proceedings of the 37th International Conference on Machine Learning, pp. 10355-10366. PMLR, November 2020. URI https: https://proceeddggs.. wttpp/ppwwww....e//eeeeeeeeeeee. html ISSN: 2640-3498.
J. Xu, K. Xu, and D. Yang. Learner-rrivate Convex Optimization, October 2021a. URL http:httpp/attt 1IXiv:2102.11976 [cs, math, stat].
abs/ /2s/2210
J. Xu, K. Xu, and D. Yang. Optimal query complexity for private sequential learning against eavesdropping. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, pp. 2296-2304. PMLR, March 2021b. URLhttpa httt:p:://proceediinge www.
http:///ppppedddnggg........eeee ptw.sssss/.pp..00000 //200/xclfff....f/lll html ISSN: 2640-3498.
J. Xu, K. Xu, and D. Yang. Leamer--rivass Convex Optimization. IEEE Transactions on Information Theory, 69(1): 528-547, January 2023. ISSN 1557-9654. doi: 10.1009/1T122002.220999. Conference Name: IEEE Transactions
on Information Theory.
K. Xu. Query Complexity of Bayesian Private Learning. In Advances in Neural Information Processing Systems, volume 31. Curan Associates, Inc., 2018. URL pttps::/prooceddnggs.. wtwp:ss..e.i.ss..ceeeeeeeeeeeeee hash/ hash:/ooctee/LaalbbbffffCC 752.cccaaa52c111
752c1 -Asstratt. oat.raaettttttcccaaaaaaaaaaaaaaa
P. Zhou, J. Feng, C. Ma, C. Xiong, S. C. H. Hoi, and W. E. Towards Theoretically Understanding Why Sgd Generalizes Better Than Adam in Deep Learning. In Advances in Neural Information Processing Systems, volume 33, pp. 21285-21290 Curran Associates, Inc., 2020. URL https::/pprocee...ngg/////// wwtp:/eeuriiico.oeee neuriigs.ccc/pppp///22000
html
A Appendix A: Experimental Parameters and Methodology
A.1 Dataset and Preprocessing
We use Jigsaw's Unintended Bias in Toxicity Classification dataset for our experimental results. The dataset has ~ 1.8 million public comments from the Civil Comments platform. The dataset was annotated by human raters for toxic conversational attributes, mainly rating the toxicity of each text on a scale of 0 to and sub-categorizing for severe toxicity, obscene, threat, insult, identity attacks, and sexually explicit content. More information about the annotation process can be found on the Kaggle website for this dataset [here] We consider the much simpler task of classifying the text toxic or not. The toxicity is scored by human volunteers on a scale of 0 to 1, and consider a comment toxic if the toxicity score is greater than 0.5. The original dataset is imbalanced with 1660540 non-toxic samples and 144334 toxic samples, and for each experimental run, we take a random balanced subset with 144334 toxic and non-toxic samples. The reason we do this is twofold, a) to reduce the time it takes to train our model and make it feasible to run the clients concurrently on our machine, and b) to study the accuracy that the cavesdropper achieves on the positive samples more profoundly. To achieve b), we could also have taken a weighted accuracy function. We preprocess the data by removing special characters and contracting the word space (for example, replacing "can" 't" and "cant" with the same word).
A.2 Architecuture, training hyperparameters, and loss functions
Our architecture used for training involves the following layer sequence: A pre-trained BERT layer which outputs 128-length embedding, fully connected 128 neurons wide linear layer with ReLU activation, dropout layer with rate of 10-1 and finally, linear layer classifying the text as hate speech or not. The motivating reason for choosing this architecture was that this was the standard template in many of the submissions received in the competition. However, as highlighted before, our approach is both architecture and convergence algorithm-agnostic.. We consider the logit loss function. We use the following hyperparameters for training: learning rate: 10 3, training batch size of 40, and validation batch size of 20. To demonstrate the versatility of our methods, we optimize our neural network using Adam Kingmaa Ba 2017) and run FedAvg (McMahan al., (017)) instead of FedSGD. Using the preprocessed training data, fine-train our model to minimize the binary cross entropy loss (BCE).
19

---

Published in Transactions on Machine Learning Research (01/2023)
A.3 Markov decision process parameters
We consider 20 clients and client participation is simulated using Markov chain with the states being 5 clients, 10 clients, and 20 clients. In each training round, each participating client chooses between 0 to Nuatches batches. We perform N = 45 training rounds with M = 20 successful updates. The accuracies are accuracy scores evaluated on the validation dataset averaged across clients. At any given communication round, we assume that the eavesdropper takes whatever weight trajectory occupies the majority number of communication rounds up till that round.
A.4 Additional benchmark experiments on MNIST dataset
We further conduct experiments on an image recognition task on the MNIST data in a federated setting to a) benchmark our methods on a standard dataset and b) study the effect varying eavesdropper and Markov chain parameters on the effectiveness our approach. Also, the image recognition task is more computationally efficient than the hate speech classification task. We can perform a lot more runs of the experiment (20 runs of the Hate Speech Classification task took around 23 hours, whereas, within the same time frame, could do 1040 runs of the image classification task).
A.4.1 Varying eavesdropper parameters
We use a Markov chain which identical to Experiment We set M 30 successful gradient updates out of 120 communication rounds for this task. We report our results for 20 and 50 clients.
Our experimental results reported in Table and Table and summarize our key findings below:
We vary the size of the training data the eavesdropper has compared to the size of a participating client. We consider three cases: the size of the cavesdropper's training set is 10%, 40%, 100% of the size of the participating client's 's size. We observe that as the training size even with the obfuscated weights, the eavesdropper's accuracy improves since the eavesdropper can learn on its own just well enough.
We also vary the number of classes the eavesdropper has classes to other classes. We consider three cases: 2, 5, and 8 "good" classes that the eavesdropper composes 99% or 90% of the data. The case when all classes are evenly distributed is also benchmarked against. We observe that both the number of good classes and a more balanced dataset improve the eavesdropper accuracy.
samples of and the proportion of data for these
We conclude that for the case of a limited information eavesdropper, the optimal policy performs much better than a greedy policy with the eavesdropper accuracy having difference of as much as 51% (for the case with 2 good classes which form 99% of the training data with 40% of the size.).
A.4.2 Results on FedSGD
For completeness, we demonstrate our results on FedSGD as well with successful updates in 240 communication queries. We summarize our results in Table averaged for 20 experiment runs. The eavesdropper is assumed to have 4 good classes composing 90% of the data and 10% of the training data size. We see that the pattern is similar to the FedAvg case but with slower convergence, with the average learner accuracy going up to 88% while the eavesdropper is stalled up to 56% while the learner uses the optimal policy.
A.4.3 Varying Markov chain parameters
FedSGD
7 oracle states
Type of Policy
Eavesdropper accuracy
Learner accuracy
Eavesdropper accuracy
Learner accuracy
Greedy Optimal
0.89
0.89
0.93
0.88
0.56
0.88
0.34
0.88
Table 3: Additional results on MNIST dataset using a) FedSGD and b) oracle states demonstrate versatality of our framework and robustness to the choice of system parameters respectively.
20

---

Published in Transactions on Machine Learning Research (01/2023)
We consider setup similar to experiment 1 with 100 clients and fix the eavesdropper parameters to have 2 good classes composing 99% of the data and 100% of the training data size. The number of ora- cle states increased to with the device counts as (36, 41, 45, 50, 55, 58, 100] and the threshold is set to
0.35
Average proportion of
0.50
1/8th of the dataset. The emperical success probabilities are found to be [0.01, 0.12, 0.41, 0.75, 0.94, 0.96, 1]. The probability transition matrix has a structure similar to the previous one and can be found in the code.
0.45
0.40
0.35
The results are summarized in Table Table avverged over 30 runs, and we see trends similar to the case with oracle states (the eavesdropper accuracy is much less since the training data is now distributed over 100 clients so the
0:30
Cost of learning
cavesdropper data is not big enough) The possible rea- son for the eavesdropper having better accuracy in greedy scheme could be that the weights that the eaves- dropper estimates are optimal and the eavesdropper has more time slots to train.
Figure 5: Empirical results the effect of the cost of learning on the average proportion of learning queries.
We also investigate the effect of learning cost, L, on the average number of times action u 1 (lear) is taken when using the stationary policy in Fig. [ This helps illustrate how our learning cost can be chosen achieve desired level of leamer-prrivacy (percentage of queries that should be obfuscated), which are set based theoretical results (Xu et al. 2021b). The average cost is calculated over 1000 for different simulation runs. The graph seems piecewise linear with jumps which could be explained by the nature of the solution of the occupation measure for the MDP, which is a vertex of a polytope defined by the corresponding linear program and jumps to next vertex with an increase in the instantenous cost.
A.5 Discussion on a policy without any stochastic considerations and possible limitations of the optimal policy
In the controlled SGD setting presented in this paper, the learner discards certain queries which are evaluated unsuccess- fully according to chosen noise constant. Controlling for stochasticity helps filter out communication rounds that will perform poorly due to insufficient clients and training data. When there is an appreciable disparity between the good and bad states, such filtering leads to significant performance difference. Additionally, our assumption is more general than a single noise constant. The learner can control the noise threshold constant, a, which enables the characterization of the finite number of updates to optimize f.
An approach without such considerations is different, it will be equivalent using a random policy in placing M learning queries in N total queries. Our approach solve this task by modifying the SGD update step and updating the learner state regardless of σg. For practical setting, such scheme would still perform better than the random policy since the obfuscation would be the same, but the learning would be done when the practical parameters, like the number of clients and data points, are better. In our numerical experiments with the MNIST data, using random policy of placing 30 learning queries in 120 communication rounds, the learner obtained a average accuracy of 80.5% against an accuracy 92.5% obtained using the optimal policy.
The learning performance of the proposed optimal policy is the same as the greedy policy since the greedy policy also uses the same thresholding (Øx <) policy. However, since the greedy method does not schedule the queries optimally, it poses a lot more learning queries and cannot achieve obfuscation as illustrated in the numerical experiments. On the other hand, a random policy without thresholding, which poses M learning queries in N communication slots, achieves obfuscation but suffers in learning performance. Hence, the optimal policy can be seen as achieving a tradeoff between both of them. The significant limitations of using the proposed method are:
The gain from the optimal policy will not be significantly high if the ratio M/N is much higher than the average occupancy of the oracle in the good oracle states.
21

---

Published in Transactions on Machine Learning Research (01/2023)
2.
The stochastic nature of the optimal policy implies that there is probability that enough queries not obfuscated.
A.6 SPGA algorithm parameters and additional experiment
For analysing the convergence of the SPGA algorithm, we choose the step size Kr. and the initial constraint parameter oracle is state y 3 when interacting with the system.
0.5 the scale parameter as p 20 10. The initial condition for the learner state is set be y 40 and the
In Fig. 7 we also demonstrate how with a constant step size the SPGA algorithm is able to track changes in the underlying policy parameters. Before iteration 2000 the underlying Markov chain has parameters same as the previous SPGA experiment except the arrival rate which 3% for M = 10 updates. After the 2000 iteration, this changes to MM updates, with an arrival rate of 10%. The success probabilities and the oracle state transition is taken to be, T [0.1, 0.6, 0.9] and po [0.7 0.2 0.1; 0.3 0.1 0.7; 0.2 0.2 0.7]. The results are averaged over 100 runs. It can be from the figure that even though the convergence is not close the decreasing step size, the SPGA algorithm tracks changes in the system. This effect is more prominently visible for oracle state y = since the change in the true parameters is significant.
Note on convergence: Proving convergence for the SPGA algorithm difficult since policy search not a convex problem and it's difficult to make regularity assumptions for the average cost function of the CMDP with respect to the policy (which is on a discrete space). Efficient linear programs can be derived for solving the CMDP which have finite sample results but these methods require knowledge of the transition probabilities (Mattila al. 2017). Hence we use the structural results on the optimal policy to reduce the search space from |So||S to 3 S Seg. Where |8t] is the finite approximation for the countably infinite queue length. This reduction at least makes it computationally possible to minimize the cost function.
22

---

Published in Transactions on Machine Learning Research (01/2023)
A.7 Tradeoff between convergence and obfuscation
log For finite-horizon case, the learners convergence varies as O naa where m is the number of successful updates already made. The obfuscation with respect to an eavesdropper using proportional sam- pling and MAP estimator is step function as shown in Figure [ As reminder this simple model of eavesdropper works in our setting because the eavesdropper is assumed to be have equal priors both the trajectories in absence of any additional information.
Otéssstion
No OMaacatoon
Existing theoretical results in learner- leamer-private optimization give more general probability bounds but till now have been extended to the convex optimization case only (using a Dirichlet process prior) (Xul et al. 2023). Without going into the technical details, the key idea of the bound that in order ensure that the eavesdropper has less than 1/2 probability of estimating the arg min, the learner must pose at least & times the standard number of learning queries, where @ E N. Although tight upper and lower bounds are difficult to obtain for non- convex functions even with regularity assumptions, the lower bounds for the convex case serve as loose lower bound for the non-convex case too, making the obfuscation probability staircase function.
of queries learning
leans's
% of queries used in learning
Figure 6: Pictorial representation of the tradeoff between the learning objective and the obfusca- tion objective. (a) shows obfuscation is a step function for the proportional sampling estimator based eavesdropper. (b) shows the change in closeness critical point of f.
For the infinite horizon case the obfuscation has similar structure but look at it with respect the average number of learning queries and obfuscation on average. And if the conditions of Lemmal 1 are satisfied, the optimization remains stable and the set of optimization tasks converge and the learning objective is satisfied. Note that for the infinite horizon case the underlying true emperical function f changes with a change context or removal which the asymptotic convergence rate becomes slower as the average number of queries decreases although an exact characterization is tough.
data point. Our methods could also be extended to an SGD which has a constant step size
20.0
0g
8,
8,
0
Parameters
12.5
4 =
10.0
2.5
500
1000
1500
2000
2500
3000
350D
4000
Iterations
Figure 7: Convergence of threshold parameters in Alg. for different oracle states with constant step sizes. This trajectory for the parameter estimates is more erroncous, has only weak convergence results but can track changes the underlying true parameters.
A.8 Note on Arrival State Space
The arrival state space taken in the paper is a specific case for illustrative purposes. could be a more general set, for ex. F {M, 2M, 3M, 4M} with suitable probability distribution. Lemma can be suitably adjusted to ensure stable queue as long the expected arrival rate is finite. We can then quantize the actual arrivals to the nearest arrival
23

---

Published in Transactions on Machine Learning Research (01/2023)
Datuset Parameters Training Data
Accuracy
Accuracy
No. of Good Classes
Prop.
Prop. of Good Classes
Greedy Policy
Optimal Policy
Greedy Policy
Optimal Policy
2
0.1
0.99
0.857
0.336
0.925
0.832
2
0.1
0.9
0.857
0.725
0.925
0.832
2
0.1
0.2
0.857
0,927
0.925
0,832
2
0.4
0.99
0,859
0,445
0.924
0.815
2
0.4
0.9
0.859
0,907
0.924
0.815
0.4
0.2
0,859
0.973
0,924
0.815
0.99
0,850
0.632
0.930
0.822
0.916
0,930
0.968
0,930
5
0.1
0.99
0.843
0.784
0.924
0.817
5
0.1
0.9
0.843
0.900
0.924
0.817
5
0.1
0.5
0.843
0.932
0.924
0.817
5
0.4
0.99
0.834
0,707
0.922
0.819
5
0.4
0.9
0.834
0,920
0.922
0.819
5
0.4
0.5
0.834
0.970
0.922
0.819
0.99
0,848
0.820
0,926
0.815
0.9
0,926
0.815
0.977
0,926
0.1
0.99
0.898
0,926
0.819
8
0.1
0.9
0.830
0.957
0,926
0.819
8
0.1
0.8
0.830
0.943
0.926
0.819
8
0.4
0.99
0.868
0.898
0.926
0.809
8
0.4
0.9
0.868
0,936
0.926
0.809
0.4
0.8
0.868
0.955
0.926
0.809
0.99
0.864
0.943
0.931
0.831
0.9
0.864
0.975
0.931
0.831
0,975
0.931
Table 4: Additional experiments on the MNIST data with 20 clients showcase how varying different eavesdropper parameter changes the accuracy the eavesdropper is able achieve.
state. In most practical implementations of a stochastic gradient algorithm, apart from an epsilon-basee based convergence criteria, there is also a parameter for the maximum number of iterations, which can be thought of as Additionally. the implementation for our particular arrival state space {0, .M} can be done by considering two states (an arrival or no arrival), and the structured policy gradient algorithm does not need the exact value of to update state parameters. The SPGA also adapts to changes in the underlying arrival probability.
B Appendix B: Proofs
B.1 Proof of Theorem 1
Proof. Let the learner successfully update the minima estimate at time indices, ki,..-,ki Using quadratic bound associated with the Lipschitz condition of Al (the descent lemma) the following can be derived. We use constant step size but similar results can be derived for a decreasing step size.
Lemma 2. (Modified Descent Lemma) For an oracle function f which satisfies assumptions AI, the following can be shown for the successful updates (Def. 7 performed at time ki..... KkM-
1
11 2
[ 21 f( - -
Σ
M
(Vf(H Thm..
2
M
| 11
(16)
We introduce the following expression to bound the expected gradient norm and obtain the desired result,
M
MM
E
M
m=
The expectation with respect to the noise terms Tk. T7p ....... Mars Vas is equal to the expected gradient norm uniformly at random selected iterate, V M [
2 for & Euar. ( Tkg. ). The expectation is w.r.t.
24

---

Published in Transactions on Machine Learning Research (01/2023)
Dataset Parameters
Accuracy
C Accuracy
No. of Good Classes
Prop. Training Data
Prop. of Good Classes
Greedy Policy
Optimal Policy
Greedy Policy
Optimal Policy
2
0.1
0.99
0.861
0.320
0.860
0.840
0.1
0.9
0,861
0,611
0,860
0,840
0.1
0.2
0.861
0.852
0,860
0.840
0.4
0,99
0,884
0.318
0,862
0,830
0.4
0.9
0.884
0.734
0.862
0.830
0.895
0,862
0.99
0.852
0.393
0.859
0.843
0.9
0.852
0.864
0.859
0.843
2
1
0.2
0.852
0.955
0,859
0.843
5
0.1
0,99
0.875
0,461
0.638
0.838
0.1
0.9
0,875
0,655
0.638
0.838
0.1
0.5
0.875
0.807
0.638
0.838
0.4
0.99
0,843
0.595
0,854
0.833
0.4
0.9
0,843
0.795
0.854
0,833
0.4
0.5
0.843
0.916
0.854
0.833
0,99
0.864
0.710
0.857
0.9
0.864
0.810
0.857
0.840
1
0.5
0.864
0.892
0.857
0.840
8
0.1
0.99
0.868
0.408
0.856
0.839
0.1
0.9
0.868
0,714
0.856
0.839
0.1
0.8
0.868
0,870
0.856
0.839
0.4
0.99
0.841
0.805
0.862
0.832
0.4
0.9
0,841
0.916
0,862
0.832
0.4
0.8
0.841
0.914
0,862
0.832
0,99
0.861
0.820
0,853
0.840
0.9
0.861
0.860
0.853
0,840
0.8
0.861
0.881
0.853
0.840
Table 5: Additional experiments on the MNIST data with 50 clients showcase how varying different eavesdropper parameter changes the accuracy the cavesdropper is able to achieve and how our framework can be extended to more number of clients.
both the random iterate and the noise terms. The bound on V is presented in the following corollary and is obtained by algebraic manipulation of Lemma 2 taking expectation on both sides and using assumption (A1, A2),
Corollary 1. After M successful updates of the SGD (Def. 1. for any step size μ S under assumptions (AI, A2) the following holds,
((E - P*) + uzy0
T
<
(17)
Mμ
What remains to be shown is that for appropriate step size μ and number of successful updates M, VM Oce) and the learning objective is achieved. To achieve this, we obtain the following conditions on the two summands of (17) by bounding them individually by c/2 and setting F = (ES()))) - -
< Mμ 2o170 < 2 2
2F
6
6
250 7 Putting 11.
The second equations bounds the step size, μ S zzz., which along with p S gives, / = min
the step size in the first equation makes objective VM S e for any M 2 max {
This implies
M O ) and completes the proof.
7
25

---

Published in Transactions on Machine Learning Research (01/2023)
B.1.1 Proof of Lemma 2
Proof. We can use the quadratric upper bound from the Lipschitz condition, the response in and the successful gradient update step of (4) to obtain the following bound,
1º (1|Tk..l) 11²)
(( (f(k)m))
pa. fark ): Fkm.
2
(IV (I(kk... + (kmm))) }) + 1 (I( + 1mmm (2m.113)
( Ss (Tikk))
2
-(--- ik- (n- n²²
(( (f(kk.)))
V V )| 1112 (1- 1-²)) (VI(on..) ). m....) +
(11 113)
2
2
Summing over the inequalities till m M.
1 [
M
1r²g
V )1 f( f(kke)))) (n- p²2) Σ
(I ) mkm
Σ
| 11?
2
M
22y
M
$ f((k)) - - - pP7)
Σ
(V ). Thm) +
1 112.
2
m=1
m==1
The last step is due the function being lower bounded by f". This concludes the proof.
B.1.2
Proof of Corollary 1
Proof.
Taking expectation on 16 from Lemma w.r.t. the noise terms Toko M78
M
M
2.2y M
E
V
12 S E [f f (μ x2-) (Vf(k... Mem.)) +
[[] |13]
2
m=1
Now using assumption A2, ( ). mkm Too.........................1T.. 7mm-1 and by (A2) and definition successful gradient step, E [I17
||]
< kmm < 0².
The above equation therefore reduces to,
M
> & B[ 8r M²yMo²
E V
Denoting Fo = Ef((k..)) f", and using jyy < we obtain,
#
(2
m7)
M
[ 11 < Fo
Mo2
M
E
V (( (1. S Fo
uºyMo²
2
2
2 m=1
2
T=
Multiplying by 9/μM on both sides we obtain the desired result,
V M S 2Fo
+ H
Mμ
E
B.2 Proof of Lemmali
Proof. Let be querying policy satisfying the constraint of (9. then
1
A lim sup N
E
Σ
1(0. a Wo) = 0. 0) y0
N
26

---

Published in Transactions on Machine Learning Research (01/2023)
If lim supN oo N E
Em=
102 = 0)]30] > 0 then the queue stable since the queue returns to the state y
infinitely often and hence the Markov chain is also recurrent.
Otherwise if lim sup E Σ n= (1 0) [o = 0 the stability of the queue can be shown by proving that the average successful transmissions (denoted by rv. (v)) under the policy v is greater than the average arrival rate oM,
N 1 (un * 0)/30
Tyo (v) lim inf Ev No
1 N
(un: un 1 + 0)lvo
2 lim inf N N
En
Σr
Tmmi
===1
))
2 Tmin
1- lim lim N-oo
En
Σ 1uu, -0,y 0)|10
T min
(1- (1- 1(0, 100, y===)w) W]) 2 8M.
A
N
Since the average successful learning rate is greater than the average query arrival rate, this induces stable buffer, and due to Foster's Theorem, this induces recurrent Markov chain.
]
B.3 Proof of Theorem 2
We state the following lemma which key to prove Theorem
Lemma 3. (Monotonicy of value function V) The value function (y) is decreasing in number of queries left, n and oracle state, y and increasing in learner state, yL.
Proof. The strategy for proving the monotonicity of the value function with respect to the state space variables will to use induction and assumptions about the cost function and the probability transition matrix.
The recursion for Va+1 (1v0, ,1) from is,
Vu+1 (y = 11) = min cuu, + E nell
P(u 11 (T(,,,))) uuV,, (w0 .y -ul) + (1 - T(y,,))VV (bo, ,v4))
ESO
where Vo (100'10)) 1(x²).
Monotonicity ni The first step the induction, 112 (Iv 941 s Vo (wO .14) can be shown as,
Vi (1v0, = min c(u, y + well
Σ
Ply (T(y w)(("²+) - +(1- w))l((()))
y ESO
$ 2Qi (100 =((yt) = Vo (10. -4).
Now let Vn (I0",, w44) S Vn- (wO', , then using the recursion and the monotonicity of cost it is straightforward to show that it holds true for n + since,
Va+1 (lv0 11 = min c(u, y + +
Σ
P(u P(o0'199) (T uVVn- (u(o- (Do --0- + +(1 -1-T - (00' 040)
well
n eso
= Vvn (10 114
Monotonicity in yt: We use inductive reasoning again to prove that the value function is increasing in ,² Note that Vo (iy I h( is increasing in yr. Let V, (Iv", (1) be increasing in y². From the definition of I1 it follows that Vn+1 is sum of increasing functions of y hence it should also be increasing in y².
Vo+i (lv (100,*1)
Monotonicity in yo: Using the assumption of first order stochastic dominance on P1y") we prove that V, (lv", "I is non-increasing in v. Vo (1)))" I(y²) is non-increasing in S Assume V,, (lv .1 is non-increasing.
27

---

Published in Transactions on Machine Learning Research (01/2023)
Then, for y > 1, by monotonicity of y(u,89) I cdu,go - -1). -1).And And by the first-order stochastic dominance assump- tion and induction assumption, E coo P(y Vv (100' v(1) = E ESO P(y"Iv" -, (Iv", v7)).
Then for y0 > 1,
Vn+ (y = 110.1²)) = min cu, y
Σ 129) (T(V, (112 ,2 - ul) + (1 - -(V u))V (wo (2/1))
nell
50 ESD
I min c(u, 4 - +)} Σ
P -1) (2()).u)V, (10' 36 - ul) + (1 - , (10², -)')))
well
ESO
= Vat1 - - 1, ))
Proof for the infinite horizon discounted MDP: Since instantaneous cost w is bounded. Hence the value function sequence,
V n+1 (Iv . .15)
min well
w(u, y;
B
Σ
(T(P. (wo" -vt + - u. 51) +
-
yo' ESo v ESE
(1 (1-T (1 , (Wo +N - wyr"))
converges for any initial Vid (4v v4, Hence we choose a Vg 24 which is increasing in yt, ye and decreasing in vº. Note that by assumptions Therefore by induction V (Iv ")) is increasing in y² and y.. And by assumption of first order stochastic dominance on P())'119)
and w(u, y; A) is decreasing in yº and nondecreasing in y²:
) it is easy to see that V (1v0 (1 ()) is decreasing yO. Therefore 8 (Wv y (f,l))) =
V& (Iv2, y y 1) is increasing in yd and y and decreasing in y0
We use this result on 1 (lvo, ,,,,~)) in the discussion of structural results on the infinite horizon average cost MDP.
We now prove Theorem
Proof. To show that the optimal discounted cost policy is monotonically increasing in learner state y², we will prove inductively that QN (Iv", yy",, u) is submodular in (y" u) for all 8² 2 1. In other words, we prove that,
Qu+1 (I0 (10,01H, 111 Quti 109.0*1,0 c(1, -0,,0)0000))))
c(0,v))+
Σ
P(y 100'009100011
yo' ESO
x Vn 110,v"-10 - 11) - Va .f))].
is monotonically decreasing in the learner state F for y 2 1 for all n 2 0 for suitable initialization. This is a sufficient condition for a monotone threshold policy since if the state action (Q) decreases monotonically. will change its sign over the learner state space St only once, and the action will be optimal until a certain value of y² and the action will be optimal otherwise.
For illustration, in finite horizon case, we assume the oracle state is fixed, and with abuse of notation, write the Q function only in terms of the learner state Supermodularity of the Q function in (v² u) is satisfied when Supermodularity implies increasing differences in with increasing.. The optimal action with queries remaining can be written as Therefore, if at some, the optimal action is O, then for the optimal action has to be since the difference between the Q function only decreases. Hence, inductively, in can be shown that for the optimal action will be O. Similarly, it can be shown that if at some the optimal action is 1, then for all the optimal action would have to be 1. This gives rise to the threshold structure of the policy. This was an illustrative explanation of the concept of supermodularity, which has been used show threshold policy results in previous work Ngo & Krishnamurthy (2000)
28

---

Published in Transactions on Machine Learning Research (01/2023)
and can be extended to the discounted Lagrangian cost MDP case. Applying a policy trained by the policy gradient method to stochastic gradient method can be difficult, due to the changing environment.
Qu+1 (Iv v 1) QQ++1 (Iv2: 1))0 has increasing differences in 3 if, Vn (br .v4") has increasing difference in vt. We prove this inductively. By assumption of integer convexity, Vo v41) = -Vy"). has increasing differences in y². Assume Vn (Iv =) has increasing differences in y² then Qu+1 (Lv v0,, 11 u) is submodular in (y", u). We
will now show that Vn+1 (1g) 1 has increasing differences in yr. i.e.
Vn+1 (LV 1 + +1] Vn+i (WV wy')) (Vo+1 (1v v/1lv - Vn+1
2 0.
(18)
Now let 2a+1 (400, y = Va+1 (Ivo, yh + II). Qut1 (nr y²), I. Uz)
Vn+1 (100,/ v41) and Uut1 (Iv 1411 us) Vn+ "u0 - -1]) for some actions u1, and ug Now 18 can be written as,
Qn+1 (40 + 1]. u1) - Qn+1 (6x 10..11, () 21) - (Qn-1 (Iv ".',, - Un+1 (10 .0 1.0--1,1 11. u1. 2
(Qn+1 (10 .v' + u1) Qutz (10 .y vz)) - (Qn+1 (10 . 2u+1 ,00, v2))
By optimality20
-(19u+1 (Iv "1 u2) Uu+1 (I (,),)s))))) ((2zz1 (1 vy 11 us) Qut1 (w 11/h 11, (s))) 2 0.
By optimality 20
B
Now rearranging the terms for A,
A= Σ
1(10)0) x ((v,,s>)) (v, (40' .04) - Vo (b0r,zt-11)
30' ESO
+(1 - +1- ,2)) (vr (w", ,
+ +11) - Vn (bvo, ,y/")) 2
Σ D0 ESO
PpyO1 1 x Vi (I0' x2)) Vn (Ivo /o6 --4 11]] 2 B.
The second last inequality is due to induction on Vn, (Iv", (1) and the last inequality follows from similar expansion on B and induction hypothesis. This theorem can be straightforwardly extended to infinite horizon discounted MDP. j
B.4 On threshold structure of average Lagrangian cost optimal policy
To show that the optimal policy of the unconstrained average cost MDP has threshold structure, we first state the following lemma (Sennott [989).
Lemma 4. Let (Bx) be any increasing sequence of discount factors, s.t., lim Bx = 1. Let (V%, be the associated sequence of discounted optimal stationary policies. There exist a subsequence (ax) of (Bx) and a stationary policy v that is the limit of (Var)-
An optimal policy given by Lemma 4 is an average cost optimal policy under suitable assumptions (Sennott) 1989). We verify these assumptions and characterize the average cost optimal policy in the following theorem:
Theorem 4. Any stationary deterministic policy v given by Lemma 4 is an average cost optimal policy, In particular there exists a constant vb lim -3) (y) (y) for every y, and function (gy with -N s (Vyy) S My, such that,
2 + (yy) = min
w w(u () + Σ Ply ly, u)
wel
y'es
Furthermore, the stationary policy is average cost optimal with an average cost sb.
Proof. For any stationary policy v to be average cost optimal, the following assumptions need be satisfied (Sennoti 1989):
29

---

Published in Transactions on Machine Learning Research (01/2023)
Assumption 1: For every state y and discount factor B, the optimal discounted cost V (y() is finite.
Assumption 2: There exists N 2 such that, -N = (y) - (0) where 0 a reference state.
Assumption 3: There exists My 2 O, such that, ()) I My for every and B. For every y there exists, u such that Eyes P(y ly, u) < co.
Assumption 3': Assumption holds and Eyes es Ply ly, My < co.
For reference state 0 [0, W. OJ. the policy of always transmitting induces stable buffer, and the expected time and cost for the first passage to state are finite. Therefore by Proposition Si) and 4ii) of Sennott (1989) and from Ross (2014) Assumption and 3 are satisfied. Assumption 3' is satisfied by the probability transition given in 8 Assumption is satisfied because V is increasing in y", y and decreasing in y and therefore ( 2 V² Vy as shown in Lemma
Due to the above lemma and theorem and using the discussion the proof of Lemma the average cost optimal policy inherits the monotone threshold structure of the discounted optimal policy.
30


Reviews:
[{"review_id": "CBfXn0kZVr", "reviewer": "Reviewer_Ai6d", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n- The authors provided a proper motivation for such problem in the paper. Especially, the description on the problematic scenario when the eavesdropper behave maliciously based on the revealed information on the hate speech classification model\n- This paper provides some theoretical and empirical results on the optimal policy", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers covert FL, where the learner have two goals simultaneously: (1) learn the minimizer of a function $f$ based on the noisy gradients from distributed oracles by sending a query $q$, and (2) hiding the minimizer of $f$ from a malicious eavesdropper.\n\nThe authors considered this problem as controlling the SGD by a policy gradient algorithm that exploits the policy structure. The authors showed that the optimal policy has a monotone threshold structure. This paper also proposes an efficient policy gradient algorithm, which well balances between accuracy and robustness (against eavesdropper) in practical scenarios including the hate speech classification task.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Probably it is better to improve the readability of the paper. Making a table summarizing important notations would be helpful. In the caption of figure/table, it is better to what each mathematical notations is (e.g., \\phi, \\theta in Fig.4)", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "88yGCQ1gy9", "reviewer": "Reviewer_N6BD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The authors apply the classical Markov decision process (MDP) to model the query of stochastic gradient oracle. This provides a general framework to study the eavesdropper issue in federated learning. \n\n- The authors show that the optimal policies of proposed MDPs have a threshold structure that can be used to reduce the policy search space. By approximating the policy using sigmoid functions, the authors propose a structured policy gradient to learn an optimal query policy. This is a useful application of policy gradient methods in federated learning.\n\n- The authors also provide experiments to show the performance of the proposed methods. The hate speech classification seems to be a new application of covert optimization. \n\nWeaknesses:\n\n- Modeling the stochastic gradient with controlled oracles as a MDP problem is intuitive. Can the authors provide more rigorous statements? Any simple examples of stochastic gradient methods?\n\n- Assumptions made about the proposed MDPs can impose the limitations. It is important to illustrate why the stochastic gradient method is the case. \n\n- The non-asymptotic convergence of stochastic gradient method is quite standard in theory. However, non-asymptotic convergence is absent for the proposed policy gradient method. It is also less discussed the computational complexities of the algorithm. \n\n- Performance of the proposed policy is similar as greedy policy. Pros and cons of the propopsed method needs to be clarified.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the covert optimization problem in federated learning in which a learner dynamically decides to query a stochastic gradient oracle. The authors model the decision-making problem of choosing stochastic gradients as a (constrained) Markov decision process and present several structural properties of the underlying optimal policies. To find an optimal policy, the authors propose a policy gradient method and demonstrate the performance of proposed methods in experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Here are some other questions:\n\n- What is the definition of $P$ in Equation (1)?\n\n- It seems difficult to determine $M$ in MDPs. How this can be handled in policy gradient algorithms and experiments.\n\n- It is useful to illustrate the super modular structure more and its implications for the optimal policy?\n\n- Applying a policy trained by the policy gradient method to a stochastic gradient method can be difficult, due to the changing environment. How does the policy trained by the policy gradient method generalize?", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "oU5sE308FI", "reviewer": "Reviewer_TFyX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The formulation and questions asked in this paper seem to be interesting and meaningful. The experimental evaluation is useful. The derivation of a Markov decision process as a means to control the stochastic gradient descent algorithm is also fairly novel.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, a learner seeks to minimize a function f via gradient descent by querying a distributed oracle that provides noisy gradient evaluation. However, the learner seeks to hide the argmin of f from a malicious eavesdropper. \n\nLet me mention that I am not an expert in federated learning but I do know a bit about covertness in the context of information theory.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The reviewer, however, has the following major concerns about the submission. \n\n1) There does not seem to be a theoretical guarantee for the Structured Policy Gradient algorithm in Section 3.4.  \n\n2) When researchers in information theory use the word \"covert\", it usually means something different. Please search \"covert communications\" and look at this paper.\nhttps://ieeexplore.ieee.org/document/7407378/\nHerein a major consideration is to quantify the **tradeoff** between the level of covertness and throughput. In the authors' investigations, they should also quantify the tradeoff between the convergence rate and the level of covertness (e.g., how well the argmin f is actually hidden). This is not done in the present submission.", "broader_impact_concerns": "NIL", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: ## Summary and strengths
All reviewers were positive about the paper and pointed out that the problem is well-motivated, reasonably studied from the theoretical point of view, and given a sufficient experimental evaluation. 

## Weaknesses
In short, the theory is somewhat limited, and only one problem is studied numerically. 

**Extra details**. One weakness pointed out by Reviewer N6BD is that the paper's guarantees are asymptotic. The authors explained the difficulty of getting non-asymptotic guarantees in their response and Appendix A.6. While I understand the technical difficulty, it is, nevertheless, of higher interest to the TMLR community to have non-asymptotic guarantees. 

Reviewer N6BD also pointed out that the assumptions are a bit limiting, which I also agree with. The assumptions made about the optimization aspects (compact domain, bounded stochastic gradients) are not what the modern theory of SGD uses.
Decision: Accept (poster)