V Schellekens

A Chatalic

F Houssiau

Y.-A De Montjoye

L Jacques

R Gribonval

DIFFERENTIALLY PRIVATE COMPRESSIVE K-MEANS

Keywords: Differential Privacy, Sketching, Sketched Learning, Compressive Learning, Clustering

This work addresses the problem of learning from large collections of data with privacy guarantees. The sketched learning framework proposes to deal with the large scale of datasets by compressing them into a single vector of generalized random moments, from which the learning task is then performed. We modify the standard sketching mechanism to provide differential privacy, using addition of Laplace noise combined with a subsampling mechanism (each moment is computed from a subset of the dataset). The data can be divided between several sensors, each applying the privacy-preserving mechanism locally, yielding a differentially-private sketch of the whole dataset when reunited. We apply this framework to the k-means clustering problem, for which a measure of utility of the mechanism in terms of a signal-to-noise ratio is provided, and discuss the obtained privacy-utility tradeoff.

INTRODUCTION

In the last few decades, the size and availability of datasets has increased exponentially. While this data promises serious advances, its sheer size represents a challenge and calls for new machine learning methods able to process large datasets efficiently, both in time and memory. In addition to tractability issues, using and publishing this data raises serious privacy concerns, and there is a need for machine learning algorithms that guarantee the privacy of users.

In the compressive learning framework [START_REF] Gribonval | Compressive statistical learning with random feature moments[END_REF], the dataset is compressed into a vector of generalized random moments (sometimes referred to as the sketch), from which the learning phase can then be performed with greatly reduced computational resources. In this paper, we propose a mechanism based on this approach to learn from compressed datasets with provable privacy guarantees, by computing noisy moments from dataset subsamples. This mechanism is shown to provide differential privacy [START_REF] Dwork | Differential privacy: A survey of results[END_REF], a popular privacy definition introduced by Dwork et al. Informally, it ensures that the output of a machine learning algorithm does not depend on the presence of one individual in the dataset.

Our method operates in a distributed context, where the dataset is shared across multiple devices, each producing and releasing publicly, once and for all, a scrambled sketch from the data it has access to. This can be done on the fly, and with low memory consumption. The sketches from each device are then averaged into one global scrambled sketch by a central analyst, who uses it later for a machine learning task. The learning task is formulated as an inverse problem as in traditional compressive learning. While this paper focuses on k-means clustering, our method is general and can easily be applied to other learning tasks such as Gaussian mixture modeling or principal component analysis. In the case of clustering, we show that the utility of a noisy sketch, i.e. its quality for subsequent learning, can be measured by a signal-to-noise ratio; we use this quantity to explain the tradeoff existing between privacy and utility and motivate our choice of parameters.

We give some background on k-means clustering, compressive learning and differential privacy in Section 2, and introduce in Section 3 our attack model and data release mechanism. Privacy guarantees and utility measures are provided respectively in Sections 4 and 5, the tradeoff between the two is discussed in Section 6 and related works are presented in Section 7.

NOTATIONS AND BACKGROUND

The general goal of (unsupervised) machine learning tasks is to infer parameters of a mathematical model from a dataset X {xi ∈ R d } n i=1 of n learning examples. In this paper, we focus on one such task to illustrate our method's capabilities: the k-means problem, that seeks, for a dataset X , to find

k cluster centroids C {cj ∈ R d } k
j=1 minimizing the sum of squared errors (SSE):

C * = arg min C SSE(X , C) arg min C x i ∈X min c j ∈C xi -cj 2 2 . (1)
As solving (1) exactly is NP-hard [START_REF] Daniel Aloise | NP-hardness of Euclidean sum-of-squares clustering[END_REF], a variety of heuristics have been proposed [START_REF] Anil | Data clustering: 50 years beyond K-means[END_REF], the most widely used being Lloyds' k-means algorithm [START_REF] Lloyd | Least squares quantization in PCM[END_REF]. These methods typically require multiple passes on the entire dataset X , which becomes prohibitive in time and memory when n is large. Compressive learning [START_REF] Gribonval | Compressive statistical learning with random feature moments[END_REF] bypasses this shortcoming by first compressing X into a single vector zX ∈ C m (called the sketch) before performing the learning task. The sketch is defined as the sample average of random Fourier features [START_REF] Rahimi | Random features for largescale kernel machines[END_REF], i.e.

zX = 1 n x i ∈X zx i with zx 1 √ m exp iΩ T x ∈ C m , ( 2
)
where m is the sketch dimension and Ω = [ω1, . . . , ωm] is a matrix composed of m frequency vectors ωj ∈ R d , generated randomly according to a specific distribution (see [START_REF] Keriven | Sketching for large-scale learning of mixture models[END_REF] for details). The most promising advantage of compressive learning is that the sketch size m required to learn models from zX does not depend on the dataset size n. For instance, it was shown that the compressive k-means method [START_REF] Keriven | Compressive K-means[END_REF] achieves an SSE close to the one obtained with Lloyd's k-means provided m = Ω(dk), i.e. provided that m is of the order of the number of parameters to learn. Moreover, the sketch can be computed in one pass, in parallel, and is easy to update when additional data is available. Finally, when n is large, the impact of one single sample xi on zX is small, due to the aggregation, leading us to believe that sketching methods are good candidates to build privacy-preserving methods. Differential Privacy (DP) is a powerful privacy definition, introduced by Dwork et al. [START_REF] Dwork | Differential privacy: A survey of results[END_REF], that is widely recognized as a standard and robust definition. Intuitively, differential privacy ensures that the result of an algorithm running on private data does not depend significantly on the contribution of one specific person or record in . . .

sX

A v e r a g e ( D e f . 4 )

A v e r a g e ( D e f . 4 )

C *

Learned Model

Compressive Learning Adversary Fig. 1. Our attack model: L devices should protect the privacy of their local datasets (X l ) 1≤l≤L while allowing an algorithm to learn a model from it (in our case, the centroids C * ). The (public) matrix of frequencies Ω is used for both "private sketching" and "compressive learning". All devices publish their scrambled sketches sX l , which are combined into the global sketch sX .

the dataset. The definition of differential privacy involves a class of datasets and a neighboring relation over datasets. We denote D the set of all datasets in R d , and we define two datasets as neighbors if they differ by at most one record, i.e. X ∼ X ⇔

(|X | = |X | and |(X ∪ X ) \ (X ∩ X )| ≤ 2).
Definition 1 (Differential Privacy). Given a neighboring relation ∼ between datasets in D, a randomized algorithm f is said to achieve differential privacy with privacy parameter (noted -DP) if for any measurable set S of the co-domain of f :

∀X , X ∈ D s.t. X ∼ X : P [f (X ) ∈ S] ≤ e P f (X ) ∈ S . (3)
Differential privacy is widely recognized as a strong and particularly conservative definition of privacy. By definition, it protects the privacy of a record even against an adversary who knows all other records in the dataset. Furthermore, it has been shown to be resistant to many classes of attacks [START_REF] Shiva | On the'semantics' of differential privacy: A bayesian formulation[END_REF]. Formally, our definition provides event-level DP [START_REF] Dwork | Differential privacy under continual observation[END_REF], which is equivalent to user-level if each person has only one record in the dataset. However, implementing differentially private mechanisms for general purpose analytics is still an open challenge [START_REF] Johnson | Practical differential privacy for sql queries using elastic sensitivity[END_REF]. Although some statistics cannot be computed anymore from the (scrambled) sketch, our mechanism still allows to solve multiple learning tasks [START_REF] Gribonval | Compressive statistical learning with random feature moments[END_REF].

ATTACK MODEL AND PRIVACY MECHANISMS

In our setup, represented in Figure 1, the dataset X is distributed across L devices (e.g. a personal computer or smartphone, a server, or a sensor). Each device l locally stores a dataset X l (disjoint of all others), assumed to contain |X l | = n0 learning examples each, for a total number of records of n |X | = L n0. Each of these devices is trusted, in that it holds data in clear. Each device compresses its data, and publishes its scrambled sketch to a central agent, that will compute the total sketch and perform computations on it. Once the local sketch has been computed, the device can delete the data used. In our attack model, an attacker is able to observe all scrambled sketches, but cannot interact further with the devices. Additionally, the sketching mechanism is not kept secret, i.e. the adversary knows the random matrix of frequencies Ω, the sketching parameters (αr and σ ξ , introduced in Definition 3), and the dataset shape (d and n0). For simplicity, in our analysis we assume that all datasets have the same size, but in practice each device can actually use the mechanism with a different value of n0, corresponding to the size of its local dataset. Our method also works if the dataset is not distributed, i.e. if L = 1 (in which case the data holder can also be the analyst, who only publishes the result of the computation C * ).

Compressing the local dataset X l to the sketch zX l reduces the transmission costs and computational resources required during learning, but cannot guarantee differential privacy as such (consider for instance the extreme case n0 = 1). Instead, the devices thus publish a distorted, scrambled sketch sX l , formally described hereafter. Our construction of sX l relies on the Laplace mechanism (a strategy to make an algorithm differentially private by adding Laplacian noise on its output [START_REF] Dwork | Calibrating noise to sensitivity in private data analysis[END_REF]), that we combine with random subsampling. The sketch being complex, we first introduce a complex Laplace distribution from which the noise will be drawn. Definition 2. A random variable z follows a complex Laplace distribution of parameter β (denoted z ∼ L C (β)) iff its real and imaginary parts follow independently a real Laplace distribution of parameter β/ √ 2. In that case, z admits a density pz(z) ∝ exp(-(| z|+| z|) √ 2/β) and σ 2 z = 2β 2 . We now define, for a standard deviation σ ξ ∈ R + and a number of measurements r, the local and global scrambled sketches. Definition 3 (Local sketching mechanism). The scrambled sketch sX l of a dataset X l = {xi} n 0 i=1 located on one device, using r ∈ 1, m {1, • • • , m} measurements per record and a noise standard deviation σ ξ , is defined as

sX l 1 αr n 0 n 0 i=1 (zx i bx i ) + ξ √ αr mn 0 , (4)
where bx i iid ∼ U(Br) for all i ∈ 1, n0 , ξj iid ∼ L C σ ξ / √ 2 for all j ∈ 1, m , Br {b ∈ {0, 1} m | m
j=1 bj = r} is the set of binary masks b selecting exactly r coefficients, αr r/m is called the subsampling parameter, and is the pointwise multiplication.

Normalizing by αrn0 is needed to ensure E b,ξ [sX l ] = zX l . The noise is therefore normalized by √ αrn0 for coherence, and also by √ m to be consistent with the individual sketches defined in [START_REF] Dwork | Differential privacy: A survey of results[END_REF].

Intuitively, masking records improves the privacy of the mechanism given that each record contributes to only r components instead of m. This is however not sufficient to ensure differential privacy: knowing all but one record still allows an attacker to isolate a record's contribution, which justifies the addition of noise in (4). In practice, masking also helps to drastically reduce the sketching computational time. We now explain how to merge the different sketches to compute the global scrambled sketch, which is used for learning.

Definition 4 (Global sketching mechanism). If X1, . . . , XL are L local datasets of n0 samples each, stored on different devices, the global scrambled sketch of X = ∪ L l=1 X l is defined as follows:

sX 1 L L l=1 sX l . (5)
Note that if the local datasets have different sizes, each device can additionally release its dataset size, so that we can compute the mean sketch with the correct ponderations. Releasing the size does not affect differential privacy (if X ∼ X , then X and X have the same size). For the rest of the paper, we stick to our simplified scenario for easier readability, i.e. all datasets have n0 samples.

Note that if the devices can communicate privately (e.g., using cryptography), we can also consider making Ω private. In this setting, sketches could be sent privately and noise added after averaging, which would reduce the amount of noise needed for privacy.

ACHIEVING DIFFERENTIAL PRIVACY

We now show formally that the proposed local and global mechanisms to compute scrambled sketches are differentially private. Proof. Let X and X be two datasets such that X ∼ X , that we rewrite as X = {xi} n 0 -1 i=1 ∪ {x} and X = {xi} n 0 -1 i=1 ∪ {x }. The scrambled sketch sX of X can be written

sX = 1 αr n 0 n 0 -1 i=1 (zx i bx i ) + 1 αr n 0 (zx bx) + ξ ,
where ξ (αrmn0) -1/2 ξ is the rescaled noise. When conditioning on B {bx i } n 0 -1 i=1 ∪ {bx}, the sketch sX admits the density:

ps X (s|B) = p ξ s-1 αr n 0 n 0 -1 i=1 (zx i bx i ) -1 αr n 0 (zx bx) ∝ exp -2 σ ξ sB -zx bx αr n 0 1 + sB -zx bx αr n 0 1 .
where sB s -1

αr n 0 n 0 -1 i=1 (zx i bx i ). Now for a set of masks B, we denote B = b x i n 0 -1 i=1 ∪ {b x }
the equivalent set of masks for X , i.e. such that b x i = bx i for all samples xi appearing in both datasets, and b x = bx. We get ps X (s|B) ps

X (s|B ) = exp 2 σ ξ sB - z x bx αr n 0 1 - sB -zx bx αr n 0 1 + sB - z x bx αr n 0 1 - sB -zx bx αr n 0 1 (i) ≤ exp 2 αr n 0 σ ξ (z x -zx) bx 1 + (z x -zx) bx 1 (ii) ≤ exp 2 αr n 0 σ ξ • r • 2 √ 2 √ m (iii) = exp 1 σ ξ 4 √ 2αr m √ n 0 = exp( ),
where (i) comes from the triangle inequality, (ii) from m i=1 bi = r, the normalization of the sketches by 1/ √ m and max θ,θ cos(θ)cos(θ ) + sin(θ) -sin(θ ) = 2 √ 2, and (iii) results from the fact that σ ξ = (αrmn0) -1/2 σ ξ by definition of ξ .

The binary masks being drawn with uniform probability, we get ps X (s) = B∈(Br ) n 0 |Br| -n 0 ps X (s|B)

≤ B ∈(Br ) n 0 |Br| -n 0 exp( ) ps X (s|B ) = exp( )• ps X (s).
Integrating this density yields the desired result.

Note that the n -1/2 0 factor in the noise standard deviation comes from the fact that the local mechanism itself is adaptive to n0 in its definition. Our mechanism only uses the size of the dataset (as opposed to other approaches relying on local and smooth sensitivities [START_REF] Nissim | Smooth sensitivity and sampling in private data analysis[END_REF]), which under our definition of neighbouring datasets can be published without breaking differential privacy.

Masking impacts the parameter αr, which helps to reduce the amount of noise required to get differential privacy, but will also impact the utility as we show in Section 6.

When the dataset is distributed across multiple devices, the composition properties of differential privacy can be used to get a result on the global mechanism, as shown in the following proposition. Proof. The devices operate on disjoint subsets of the global (distributed) dataset, so this is a direct consequence of the parallel composition property of differential privacy [14, Section 2.4.2].

EXPERIMENTAL MEASURE OF UTILITY

Having defined our mechanism, and shown that it achieves differential privacy, we now show how the noise and masking impact utility, defined for k-means as the SSE. For this, we define the signal-tonoise ratio (SNR) of the mean sketch and show experimentally that the SSE is directly driven by this SNR and the sketch size m. These results are formulated for an arbitrary noise variance σ 2 ξ and masking parameter r. In section 6, we will use the theoretical values found in Section 4 to study how -DP affects utility.

Definition of the SNR. We first compute the variance of one value of the noisy global sketch of a distributed dataset X , computed using Definition 4 (i.e., using L devices with n0 samples each) and Definition 3 with r measurements per input sample. We make the assumption that the samples of X have been drawn according to a distribution π, and denote z = Ex∼πzx. From (5) we get Var((sX

)j) = 1 L Var X ,(b i ) n 0 i=1 ,ξ 1 αr n 0 n 0 i=1 (zx i bi)j + ξ j √ αr mn 0 = 1 L 1 (αr n 0 ) 2 n0Var x∼π,b∼Bern(αr ) [(zx)jb] + σ 2 ξ αr mn 0 = 1 αr n 0 L 1 αr αr m -|αrzj| 2 + σ 2 ξ m = 1 m -αr |z j | 2 + σ 2 ξ m αr n 0 L .
Hence, the SNR is defined as follows:

SNR z 2 m j=1 Var((sX )j) = αrn0L z 2 1 -αr z 2 + σ 2 ξ . (6)
Of these parameters, n0 and L are fixed by the context (data format and application), and αr, σ ξ and m are free parameters of the mechanism. Provided that σ ξ is independent of αr, the SNR is therefore maximized when σ ξ is as small as possible, and when αr = 1.

Measuring utility with the SNR. We now provide experimental simulations to exhibit the relation between the SNR and the SSE. All experiments are run in Matlab and based on the SketchMLbox toolbox, and learning is performed using the CL-OMPR algorithm [START_REF] Keriven | Compressive K-means[END_REF]. For all experiments in this paper, data is drawn in 6) of the SNR, the quantity z 2 is always smaller than 1 because the features (2) are scaled by m -1/2 , and depend on the data and frequencies distribution. Experiments performed on data drawn according to mixtures of k > 1 Gaussians showed that we always obtain z 2 ≈ δ 0.35 for the chosen distribution of the frequencies [START_REF] Keriven | Sketching for large-scale learning of mixture models[END_REF], independently of the mixture's parameters. In our experiments, we use this numerical approximation to generate values of αr or σ ξ for a given SNR. The correlation observed between the two quantities underscores the soundness of using the SNR as a measure of utility for a given sketch size.

R d ac- cording to a mixture of k Gaussians π = 1 k k i=1 N (µi, I d ), where (µi) 1≤i≤k ∼ N (0, (1.5k 1/d ) 2 I d ).
Role of the sketch size. In Figure 2 (right), we plot the relative SSE (i.e. the ratio between the SSE obtained with our method and the SSE obtained with Lloyd's algorithm), for n = 10 5 using different sketch sizes and SNRs, computed using additive noise and without subsampling (r = m). The red dashed line corresponds to m = kd, and as expected [START_REF] Keriven | Compressive K-means[END_REF] the reconstruction fails below this line. From this plot, we derive that when m is greater than 10kd, one can consider that the reconstruction is successful provided that SNR × m/(kd) ≥ 100 (which corresponds to the yellow area, i.e. a relative SSE below 1.2).

PRIVACY-UTILITY TRADEOFF

In this section, we study the tradeoff existing between privacy guarantees and utility measures proposed respectively in Sections 4 and 5. When plugging the value of σ ξ required to obtain -DP (Proposition 1) into the SNR [START_REF] Rahimi | Random features for largescale kernel machines[END_REF], we obtain an expression of the latter parameterized by and other parameters of the mechanism:

SNR( ; n0, L, αr, m) = αr n0 L δ 1 -αrδ + 32αr m 2 n 0 2 . ( 7
)
We show in Figure 3 the privacy-utility curves, i.e. the relative SSE as a function of , obtained for different values of n0, L, αr and m, and we use this expression of the SNR [START_REF] Keriven | Sketching for large-scale learning of mixture models[END_REF] to explain the results.

We also compare our method with DPLloyd [START_REF] Blum | Practical privacy: the SuLQ framework[END_REF], a noisy variant of Lloyd's iterative algorithm, and EUGkM [START_REF] Su | Differentially private k-means clustering[END_REF], which builds a noisy histogram of the data. DPLloyd was implemented in matlab according to [START_REF] Li | Differential privacy: From theory to practice[END_REF], using 5 iterations as suggested by the authors. Initialization is performed either uniformly, or using the method proposed in [START_REF] Su | Differentially private k-means clustering[END_REF]. We used the python EUGkM implementation 1 of the authors, with the suggested initialization.

When using L = 1 devices (centralized dataset), we obtain good clustering results, i.e. a relative SSE below 1.2, provided that > 10 -2 . The parameter αr does not change much the results, as the variance term induced by the subsampling operation (i.e. using αr < 1) is small compared to the one induced by the additive noise in [START_REF] Keriven | Sketching for large-scale learning of mixture models[END_REF]. Therefore we are free to use αr < 1 to reduce the computational cost, without degrading utility. Standard DPLloyd seems to perform poorly compared to our method, but using the improved initialization [START_REF] Su | Differentially private k-means clustering[END_REF] does help significantly. For EUGkM, only points corresponding to lower values of could be calculated due to the histogram-based nature of the algorithm, the number of bins becoming substantial; such methods are mostly suited for low-dimensional datasets of moderate size. We thus conclude that our method performs at least as well as previously developed ones, while requiring less computations, having a controlled memory usage, and being usable in a distributed setting.

RELATED WORK

Differentially private k-means has already received attention in the literature. Addition of Laplacian noise has for instance been used in the SuLQ framework [START_REF] Blum | Practical privacy: the SuLQ framework[END_REF] that proposes a noisy version of Lloyd's iterative algorithm (DPLloyd), or in non-interactive approaches, such as EUGkM, that release noisy histograms of the data [START_REF] Qardaji | Differentially private grids for geospatial data[END_REF][START_REF] Su | Differentially private k-means clustering[END_REF]. The noise level is sometimes adapted to the instance on which the algorithm is performed, such as in the sample and aggregate approach [START_REF] Nissim | Smooth sensitivity and sampling in private data analysis[END_REF]. The exponential mechanism, another standard approach choosing the output probability w.r.t. a user-defined utility measure, has also been used with genetic algorithms [START_REF] Zhang | PrivGene: differentially private model fitting using genetic algorithms[END_REF]. Private coresets have been investigated by Feldman et al. [START_REF] Feldman | Private coresets[END_REF][START_REF] Feldman | Coresets for differentially private k-means clustering and applications to privacy in mobile sensor networks[END_REF]. The popular k-means++ seeding method has also been generalized to a private framework [START_REF] Nock | k-variates++: more pluses in the k-means++[END_REF]. Balcan et al. investigated the large-scale high-dimensional setting with an approach based on Johnson-Lindenstrauss dimensionality reduction [START_REF] Balcan | Differentially private clustering in high-dimensional euclidean spaces[END_REF]. Many other embeddings based on random projections have been proposed as privacy-preserving encoding of data, see e.g. [START_REF] Kenthapadi | Privacy via the Johnson-Lindenstrauss Transform[END_REF], often assuming that the projection matrix is unknown to the adversary.

Closer to our work, Balog et al. recently proposed to release kernel mean embeddings [START_REF] Balog | Differentially private database release via kernel mean embeddings[END_REF], either as sets of synthetic data points in the input space or using feature maps (as we do). Their work rely on the Gaussian mechanism, resulting in a weaker definition of differential privacy with an additive term δ > 0. Studying the utility of a mechanism based on mean embeddings is, to the best of our knowledge, something new in the literature.

CONCLUSION

Compressing a dataset not only reduces the resources required for learning, but also intrinsically helps to build private algorithms. We propose a sketching method based on the addition of Laplacian noise, coupled to a subsampling mechanism for efficiency, which is proven to be differentially private.

Although we focused on k-means clustering, other learning tasks can be solved in a compressive manner and should be investigated, such as Gaussian mixtures fitting or principal components analysis. We leave for future work the idea of using quantized sketches [START_REF] Schellekens | Quantized compressive k-means[END_REF] (quantization for privacy has already been considered [START_REF] Boufounos | Secure binary embeddings for privacy preserving nearest neighbors[END_REF][START_REF] Rane | Privacy-preserving nearest neighbor methods: Comparing signals without revealing them[END_REF]), and leveraging fast transforms to speed-up the process [START_REF] Chatalic | Large-scale high-dimensional clustering with fast sketching[END_REF]. Using additive noise on the data samples themselves is also a possibility that should be investigated.

Proposition 1 .

 1 The local sketching mechanism given in Definition 3 with r measurements per input sample and noise standard deviationσ ξ = 4 √ 2αr m √ n 0, where αr r/m, achieves -DP (Definition 1).

Proposition 2 .

 2 The global sketching mechanism given in Definition 4, combining the sketches obtained from the different devices with the local mechanism (Definition 3) with r measurements per input sample and noise standard deviation σ ξ = 4 √ 2αr m √ n 0 on each device, achieves -DP (Definition 1).

Fig. 2 .

 2 Fig. 2. (Left) Correlation between relative (w.r.t. k-means with 3 replicates) SSE and SNR for different values of αr and σ ξ , using m = 10kd. Medians of 40 trials, blue area shows the standard deviation. (Right) SSE as a function of SNR and m/kd, using n = 10 5 , interpolated from a 12x12 grid, means of 40 trials, k = d = 10.

Figure 2 (

 2 left) depicts the correlation between relative (w.r.t. Lloyd's k-means) SSE and SNR for

Fig. 3 .

 3 Fig. 3. Relative SSE (utility) vs. (privacy), for different values of L, αr and m. Variances are similar for all methods. CKM stands for "Compressive k-means", and in that case the dashed lines correspond to αr = 1. Medians over 20 trials (less for EUGkM). Synthetic data, d = k = 10, n = 10 7 . Best viewed in colors.

https://github.com/DongSuIBM/PrivKmeans


Rabab Boyaala

Rachid Touzani

Thierry Roisnel

Vincent Dorcet

Elsa Caytan

Denis Jacquemin

Julien Boixel

Véronique Guerchais

Henri Doucet

Jean-François Soulé

Catalyst-Controlled Regiodivergent C-H Arylation Site of Fluorinated 2-Arylpyridine Derivatives: Application to Luminescent Iridium(III) Complexes

Keywords: Catalysis, Palladium, Ruthenium, C-H Bond Functionalization, Luminescence, Iridium, TD-DFT

Regiodivergent C-H bond arylation of fluorinated 2-aryl-pyridines and -quinolines has been developed. The use of Pd catalyst allows to functionalize the C-H bond of the aryl flanked by two fluorine atoms (most acidic position); while using Ru catalyst, the arylation takes place at the ortho heterocycle position. Both reaction conditions exhibit a good functional group tolerance. The synthetically useful selectivity observed with Pd catalyst was applied to design novel C^N ligands for the preparation of luminescent cationic iridium(III) complexes. The influence of the incorporated aryl group onto the fluorinated phenyl unit and the fluorine position patterns on the photophysical properties is described.

INTRODUCTION

Fluoroarene molecules represent one of the most prevalent entities within both pharmaceutical compounds, [START_REF] Wang | Fluorine in Pharmaceutical Industry: Fluorine-Containing Drugs Introduced to the Market in the Last Decade (2001-2011)[END_REF] and material sciences. [START_REF] Babudri | Fluorinated Organic Materials for Electronic and Optoelectronic Applications: the Role of the Fluorine Atom[END_REF] Among them, fluorinated 2-arylpyridines have been successfully used as building blocks in the preparation of medicine, e.g., VX-702 is employed for the transient suppression of biomarkers of inflammation in ongoing rheumatoid arthritis. [START_REF] Damjanov | Efficacy, Pharmacodynamics, and Safety of VX-702, a Novel p38 MAPK Inhibitor, in Rheumatoid Arthritis: Results of Two Randomized, Double-Blind, Placebo-Controlled Clinical Studies[END_REF] In addition, fluorinated 2-arylpyridines are precursors of iridium complexes, (4) e.g., [Ir(dFppy) 2 (dmbpy)]PF 6 (Figure 1, left). (4f) Such biscyclometalated complexes exhibit highly efficient optoelectronic properties, with widespread applications as photoredox catalysts, (5) biological staining agents, (6) or medicinal drugs. [START_REF] Ouyang | Fluorinated Cyclometalated Iridium(III) Complexes as Mitochondria-Targeted Theranostic Anticancer Agents[END_REF] The introduction of fluorine atoms often results in the modification of both HOMO and LUMO energy levels, enabling optimizing the carrier injection and tuning the electroluminescent color. (8) However, the access to welldecorated fluorinated 2-arylpyridines remains quite challenging and often involves multi-sept synthesis. Therefore, there is a high demand toward the discovery of user-friendly synthetic methods to modify such fluorinated ligands in order to adjust their photophysical properties and/or to develop more stable cyclometalated iridium(III) complexes. (9) Over the past decades, transition metal catalyzed C-H bond functionalizations have emerged as a straightforward synthetic strategy to avoid additional steps related to the pre-activation of the substrates. (10) However, one of the major issues in this field remains the control and the switch of the regioselectivity to obtain diversely decorated structures in one-step. (11) In order to achieve C-H bond functionalization at the desired position, substrates bearing a directing/coordinating group for the ortho C-H bond cleavage were employed; (12) or specific templates to functionalize remote C-H bond were designed. (13) An alternative approach is to distinguish the C-H bonds by their electronic properties and to tailor the reaction conditions in function of the targeted position. This strategy has been widely applied for the regiodivergent C-H bond functionalization of 5membered ring heteroarenes, (14) but scarcely studied in the case of benzene derivatives. (15) Fluoroarenes are ideal candidates for developing regioselective C-H bond functionalizations, as fluorine atoms often enhance the reactivity of the adjacent C-H bond owing its electronically properties. (16) To the best of our knowledge, the reactivity of fluorinated 2-arylpyridine derivatives in C-H bond arylation with enhancing site selectivity by fluorine atom was not developed yet, although the discovery of a catalyst-dependent method to control the site of the arylation of fluorinated 2-arylpyridine derivatives would allow a simple access to diversely decorated ligands, applicable in the preparation of new iridium(III) complexes. In the present work, we report (i) regiodivergent C-H bond arylation of fluorinated 2-aryl-pyridines and -quinolines via the choice of metal (Figure 1, right), (ii) the use of arylated ligands in the preparation of novel cyclometalated iridium(III) complexes, (iii) the characterization of the photoluminescent properties of these iridium(III) complexes with theoretical correlation by TD-DFT calculations.

RESULTS AND DISCUSSION

Optimization of the regiodivergent C-H bond arylation

To determine the regioselectivity of C-H bond functionalization with 2-arylpyridine derivatives bearing two fluorine atoms onto the aryl unit, we firstly examined the arylation of 2-(2,4-difluorophenyl)pyridine (1a) with 4bromobenzonitrile (2a) in the presence of 2 equivalents of KOAc as base in DMA at 150 ºC using various Pd catalyst precursors (Table 1, entries 1-3). In all cases, we were pleased to find that the reaction mainly occurred at the most acidic C-H bond (the one flanked by the two ortho-fluorine atoms). Indeed, a 76:24 mixture of 3aa/4aa was obtained in the presence of 2 mol% of phosphine-free Pd catalyst Pd(OAc) 2 (Table 1, entry 1). A similar ratio was observed using 2 mol% of PdCl 2 catalyst (Table1, entry 2). We reasoned that the use of diphosphine palladium catalyst PdCl(C 3 H 5 )(dppb), could inhibit the formation of the regioisomer 4aa by preventing the coordination of the pyridine unit to Pd. Under these conditions, the regioselectivity (3aa/4aa) was greatly improved to 92:8 ratio (Table 1, entry 3). It is known that the base plays a critical role in concerted metalation-deprotonation mechanism, therefore using more soluble base, KOPiv, the 3aa/4aa ratio was raised up to 95:5 (Table 1, entry 4). Full conversion of 2a can be reached with a higher Pd loading of 5 mol%, and the regioisomer 3aa was isolated in 76% yield (Table 1, entry 5). It is important to note that the previous protocols to prepare such arylated fluorinated 2-aryl-pyridines required the use of stochiometric amounts of organometallic reagents (magnesium and zinc) and multi-step synthesis. [START_REF] Davin | Ligand-Induced Reactivity of β-Diketiminate Magnesium Complexes for Regioselective Functionalization of Fluoroarenes via C-H or C-F Bond Activations[END_REF] It was also reported that ortho-C-H bond arylation of 2-phenylpyridine derivatives could be performed using Ru(II) catalyst through coordinating effect . (18) On the other hand, Ru(II) is also able to promote the C-H bond arylation of polyfluorobenzene derivatives at orthoposition, through electronic factors. (19) To the best of our knowledge, there is no study on the regioselectivity of the arylation of fluorinated 2-aryl-pyridines in the presence of Ru(II) catalysts. Interestingly, using 5 mol% of [Ru(pcymeme)Cl 2 ] 2 associated to KOAc in DMA, we were pleased to find that arylation of 1a exclusively occurred at the C6 position leading the formation of the product 4aa, i.e., the proximal position to the pyridine unit, in > 95:5 selectivity, albeit with a poor conversion (Table 1, entry 6). Changing the solvent to NMP, 4aa was also obtained in 95% regioselectivity, but was isolated in 70% yield (Table 1 entry 8). Notably, for both sets of reaction conditions, we never observed the formation of side-products derived from the activation of C-F bonds. (20) [c] [a] Determined by GC-analysis using n-dodecane as internal standard, conv = conversion based on the consumption of 2a. [b] Isolated yield in 3aa. [c] Isolated yield in 4aa.

Pd-catalyzed C-H bond arylation under Electronic Control

Having discovered two sets of conditions leading to highly regioselective C-H bond arylations: i) Pd catalysis for the arylation under electronic control; and ii) Ru catalysis for the arylation using coordination control, we turned our attention to the scope of these transformations (Schemes 1 and2

Ru-catalyzed C-H bond arylation under Coordination Control

Next, we investigated the scope of the reaction using Ru(II) catalyst in order to prepare C2-arylated products 4 via pyridine or quinoline direct ortho-arylations (Scheme 2). Electron-poor and electron-rich aryl bromides have been successfully coupled with 1a to afford 2-(6-aryl-2,4-difluorophenyl)pyridines in good to excellent yields (4aa and 4ai-4ak, 59-84% yields).

Preparation and characterization of cyclometalated Ir(III) complexes

Then, we anticipated that the new arylateddifluorophenylpyridine (dFppy) 3ac, arylateddifluorophenylquinoline (dFqui) pro-ligands 3bc, 3cc, 3dc, and arylated-trifluorophenylquinoline (tFqui) 3ec -prepared in a single step thanks to the unique regioselectivity observed with Pd catalyst-can be used as cyclometalated C^N ligands to obtain heteroleptic bis-cyclometalated iridium(III) complexes. The corresponding cationic [Ir(C^N) 2 (N^N)]PF 6 (N^N = dmbpy) complexes were prepared and isolated in 58-81% yields as yellow (5b) and orange (6-9) air-stable solids via a reported two-step procedure (Scheme 3). [START_REF] Matsuo | Synthesis of a Few Derivatives of Cycloiridated 2-(2-Thienyl)pyridine[END_REF] The unsubstituted complex 5a was also synthesized and used as the reference for comparative studies. (4f) This set of new complexes can be divided into two series. The first which includes complexes 5a and 5b allows assessing the impact of the incorporation of an aryl group (p-CF 3 -phenyl) onto the dFppy ligand, on the electrochemical and photophysical properties. The second encompasses complexes 6-9 where the pyridine ring has been replaced by a quinoline (dFqui or tFqui), the p-CF 3 -phenyl ring and two or three fluorine substituents diversely located onto the C^N ligand. The crystal structures of complexes 5b, 6 and 8 are presented in Scheme 3. The pendant p-CF 3 -phenyl is not coplanar with the C^N ligand; the torsion angles between the plane of the incorporated aryl group and that of cyclometalated phenyl ring of the two C^N ligands in 5b vary among 48.2° and 84.7°. (23) These values, larger than those reported in the corresponding fluorine-free related complexes, breaks the conjugation within the ligand. Similarly, the pendant phenyl groups of 6 and 8 are twisted, the respective dihedral angles being 51.6° and 62.4°. This feature has been previously observed for the related 4-phenylsubstituted ppy complex. (23a) A c c e p t e d M a n u s c r i p t Scheme 3. Synthesis of cationic iridium(III) complexes and X-ray structures of 5b, 6, and 8 thermal ellipsoids are drawn at the 50 % probability level, hydrogen atoms, PF 6 counterion and solvent molecules are omitted for clarity Electrochemical measurements were carried out in MeCN solution (see the SI for details), each complex exhibits a reversible or quasi-reversible metal-centered oxidation. The oxidation potentials of 5a, 5b and 6 are very similar, despite the incorporation of the aryl group and/or substitution of the pyridine by a quinoline ring. Upon addition of an extra fluorine atom in 9 at the 6'-phenyl position with respect to 8, expectedly the oxidation wave is anodically shifted (0.18 V). The UVvisible absorption data and emission spectral data (MeCN and in EPA at 77 K) of 5a, 5b and 6-9 are summarized in Figure 2b and Figures S1-S3. These spectra have been interpreted with the help of TD-DFT calculations (see Table S2 and SI for details and Figure 3 for the key MOs). Complexes 5a and 5b show intense absorption bands in the UV with maxima at about 300 nm, which are ascribed to spin-allowed π → π* transitions of the (C^N and N^N) ligands. Lower energy bands between 350 and 400 nm correspond to spin-allowed metal-to-ligand ( 1 MLCT), ligand-to-ligand charge transfer ( 1 LL'CT, π N^C → π* N^N ) and intra-ligand charge transfer ( 1 LLCT, π N^C → π* N^C ) transitions whereas the low intensity tails up to 450 nm arise from triplet transitions of mixed 3 MLCT/ 3 LL'CT character and very weakly allowed singlet transitions of the same character. Indeed, the S 1 state computed at 426 nm in both 5a and 5b present an oscillator strength of ca. 5 x 10 -4 . Comparing the spectra of these two compounds, one notes very small differences (Figure S1) in accordance with the topology of the frontier orbitals that show no contribution from the p-CF 3 -Ph moieties in 5b (Figure 3 andS3). Note that in 5a and 5b the LUMO is exclusively located on the ancillary N^N ligand (Figure 3). The absorption profile of complexes 6-9 are similar, the replacement of dFppy ligand by dFpq or tFpq in the C^N ligands lead to a more intense and broad absorption π → π* intraligand bands at 350-360 nm, more interestingly a now more marked absorption in the 400-450 nm domain (Figure S1). This trend is well restored by theory with a significant absorption in that region, absent in 5a and 5b (Table S2). This new band presents a mixed 1 MLCT and 1 LLCT (π N^C → π* N^C ) character and its emergence can be explained by the fact that the LUMO of 6-9 are now centered on the C^N rather than N^N ligand (Figure 3). Upon excitation at 380 nm, complex 5b shows similar spectral feature than the reference complex 5a, with a broad emission band at  em = 525 nm presenting a lifetime in the μs regime, indicative of an emission with charge-transfer character (Figure 2a left). The fact that 5b bearing a p-trifluoromethylphenyl group shows similar emission energy than 5a is consistent with previous studies. (23) As mentioned above, the twist between the aryl group and the 4,6-difluorophenyl ring disrupts the conjugation between these two aryl groups, minimizing the impact of the substituent on the emission wavelength. Interestingly, this site selective arylation on the difluoroaryl unit of 5a leads to an enhancement of the photoluminescence quantum yield, a feature not observed when the arylation occurred on the pyridine ring. (23d) This analysis is corroborated by the computed spin densities of the lowest triplet states that are mainly located on the metal and ancillary ligand in both 5a and 5b (Figure S4). The computed emission wavelength of 528 and 532 nm for 5a and 5b, respectively, also agree well with the measurements at both RT and 77K. The second family of complexes 6-9 containing a quinoline exhibit intense luminescence in the yellow-orange domain (Figure 2a right). For instance, the emission maxima of 6 was found at 552 nm and 579 nm with a long lifetime of 8 s. In all cases, the presence of quinoline gives rise to a red-shifted and structured emission band, characteristic of a significant contribution of 3 LC excited state localized on the C^N ligand. Interestingly, position isomers allow a fine-tuning of the emission energy without significantly affecting the photoluminescence quantum yields. This analysis is again supported by theoretical calculation that show that the lowest triplet state of 6 and 9 locates principally on one of the two C^N ligands (Figure S4). For those two compounds, the computed phosphorescence energies are 634 and 654 nm, respectively, strongly redshifted compared to 5a and 5b, and again nicely fitting the low temperature measurements.

CONCLUSION

In summary, we have showed that depending on the choice of the transition metal catalyst, one can achieve regiodivergent C-H bond arylations of fluorinated 2-arylpyridines and 2arylquinolines. Highly ortho-to-fluorine-selectivity is obtained using palladium catalyst. Interestingly, the electronically enhanced site selectivity is not altered by the presence of heterocycle coordinating group and by the position pattern of the fluorine atoms. In contrast, the use of ruthenium enables pyridine or quinoline ortho-directed C-H bond arylations of the fluoroarenes. The regioselectivity of the Pd-catalyzed C-H arylation was applied to efficient synthesis of proligands for the preparation of Ir(III)-complexes displaying tunable photophysical properties. Incorporation of the CF3-aryl group at the C3-position of the dFppy C^N ligand (complex 5b) does not modify the emission energy but induces an enhanced photoluminescence quantum yield.

Moreover, a subtle modulation of the emission color can be readily achieved by changing the location of the incorporated aryl group at the cyclometalated phenyl ligand. These studies represent a unique example of late-stage modification of fluorinated 2arylpyridines opening a facile access to regioselectively substituted bis-cyclometalated complexes with tailoring photophysical properties. In the near future, this approach should contribute to the efficient tuning of photoredox catalysts and of luminescence properties of complexes useful for the fabrication of optoelectronic devices such as OLEDs and LEECs.

Figure 1 .

 1 Figure 1. Relevant Structures containing Fluorinated 2-Arylpyridines and their Site Reactive C-H Bonds in Transition-Metal-Catalyzed Functionalizations.

Scheme 1 .

 1 Scheme 1. Palladium-Catalyzed C-H Bond Arylation at Ortho-Positions of Fluorine Atoms: Electronic Control.

From 2 -Scheme 2 .

 22 Scheme 2. Ruthenium-Catalyzed C-H Bond Arylation at Ortho-position of Pyridine or Quinoline Units: Coordination Control

  in MeCN conc. ≈ 1.5 x 10 -5 M. [ii] in deaerated MeCN with : conc. ≈ 1.5 x 10 -5 M, � exc = 380 nm. [iii] ref = Ru(bpy) 3 Cl 2 (� = 0.04). [iv] � exc = 375 nm. [v] in EPA, � ex = 380 nm.

Figure 2

 2 Figure 2 a) Emission spectra of the Ir(III) complexes 5a, 5b, and 6-9 in degassed acetonitrile at 298 K b) Table with absorption and emission data of the Ir(III) complexes 5a, 5b, and 6-9

Figure 3 .

 3 Figure 3. Frontier MOs of the different compounds (contour threshold: 0.04 au)

Table 1 .

 1 Optimization of the Reaction Conditions

	Entry Cat. (x mol%)	Base	Solvent Conv. (%) [a] 3aa/4aa [a]
	1	Pd(OAc)2 (2)	KOAc	DMA	54	76:24
	2	PdCl2 (2)	KOAc	DMA	58	77:23
	3	PdCl(C3H5)(dppb) (2)	KOAc	DMA	65	92:8
	4	PdCl(C3H5)(dppb) (2)	KOPiv	DMA	68	>95:5
	5	PdCl(C3H5)(dppb) (5)	KOPiv	DMA	100	>95:5 (76%) [b]
	6	[Ru(p-cymeme)Cl2]2 (5)	KOAc	DMA	25	>5:95
	7	[Ru(p-cymeme)Cl2]2 (5)	KOAc	DMF	40	>5:95
	8	[Ru(p-cymeme)Cl2]2 (5)	KOAc	NMP	95	>5:95 (70%)

ACKNOWLEDGMENT

R.B. is grateful to ''Université Mohamed Premier, Oujda, Morocco" for providing financial support. We also thank CNRS for providing financial support. This work used computational resources of the CCIPL center installed in Nantes.

ASSOCIATED CONTENT Supporting Information

The Supporting Information is available free of charge on the ACS Publications website.

AUTHOR INFORMATION Corresponding Author

Denis Jacquemin: Denis.Jacquemin@univ-nantes.fr Veronique Guerchais: veronique.guerchais@univ-rennes1.fr Henri Doucet: henri.doucet@univ-rennes1.fr Jean-François Soulé: jean-francois.soule@univ-rennes1.fr