Battin-Leclerc

Y Song

L Marrodán

N Vin

Olivier Herbinet
email: olivier.herbinet@univ-lorraine.fr

E Assaf

C Fittschen

A Stagni

T Faravelli

M U Alzueta

F Battin-Leclerc

The sensitizing effects of NO2 and NO on methane low temperature oxidation in a jet-stirred reactor

Keywords: Jet-stirred reactor, NOx methane combustion, Low-temperature oxidation

The sensitizing effects of NO 2 and NO on methane low

temperature oxidation in a jet stirred reactor

Introduction

The limited fossil fuel resource and its harmful effects on the climate have increased the interest for environmentally friendly fuels. Biomass seems to be a promising fuel source due to its sustainability, secure supply and low threat to the environment. Produced from the biomass anaerobic digestion, the so-called "biogas", consists mainly of methane (CH4) and carbon dioxide (CO2) with trace amounts of nitrogen and sulfur compounds. Biogas plays an important role as potential renewable gas-phase fuel. The main nitrogen compound present in biogas is ammonia, which could easily convert to NO in the presence of oxygen even at low temperatures. The mutual effects of CH4/NOx or CH4/NH3 have attracted considerable attention in the past decade.

A large number of experimental reports concerning the hydrocarbon-NOx interactions in ideal reactors are available [1][2][3][4][START_REF] Dagaut | Proceedings of the Combustion Institute[END_REF][START_REF] Dagaut | [END_REF][7][8][9][10][11][12]. Most studies related to reburning technology were performed in tubular flow reactors (FR) for CH4 high-temperature oxidation. Over a relatively low-temperature range (800-1150 K), Dagaut and Nicolle [START_REF] Dagaut | [END_REF] demonstrated the effects of NO on methane oxidation at pressures of 1-10 atm in a jet stirred reactor. A simplified reaction path was proposed, in which the reaction NO + HO2= OH + NO2 followed by OH + CH4= CH3+ H2O were highlighted. In addition, the investigation of mutual effects of NO2 on CH4 oxidation is also of significant value. Bendtsen et al. [4] and Chan et al. [9] examined the impact of NO and NO2 as promoters to CH4 oxidation under fuel-lean conditions in a FR. The different key reactions at the onset for NO (CH3O2+ NO = CH3O + NO2) or NO2 (NO2+ CH4= CH3+ HONO) sensitization were identified. However, some minor reaction paths such as NO2+ CH2O = HONO + HCO, which could play a role in mutual effects on CH4 oxidation, have been ignored so far. Moreover, to the authors' knowledge, the sensitizing effects of NO2 on methane low-temperature oxidation in a jet-stirred reactor have not been investigated yet.

Despite the abundant kinetic studies for the CH4-NOx interactions, the knowledge of some notable intermediate nitrogen species (such as HONO) is not comprehensively understood. Chai and Goldsmith [13] calculated the rate coefficients for H2+ NO2 and CH4+ NO2 with the formation of HONO. The fate of these species is of importance to the hydrocarbon-NOx interactions during the biogas oxidation. However, until now, HONO has never been detected during fuel oxidation.

Therefore, the aim of this work is to investigate the hydrocarbon-NOx (NO and NO2) interactions in biogas oxidation at atmospheric pressure and temperatures ranging from 650 to 1200 K. A search for intermediate species HONO, CH3NO2 and HCN has been made with the aid of continuous wave Cavity Ring-Down Spectroscopy (cw-CRDS) and Fourier Transform Infrared (FTIR), respectively. A detailed kinetic mechanism, recently updated according to the latest available ab initio calculations, is used to interpret the experimental data.

Experimental setup

The experimental setup was a laboratory-scale spherical fused silica JSR (volume of 85 cm 3 ; detailed description provided elsewhere [14]). A more detailed description of the experimental setup is available in Supplementary material (SM1). The reactant gases were premixed in a preheating zone before entering the reactor center through four nozzles which create high turbulence resulting in homogeneity in composition and temperature of the gas phase. The residence time inside the preheater was only 1% with respect to the one in the reactor which was fixed at 1.5 s (±0.1 s) within all the experiments performed. Both the reactor and the preheater were heated using Thermocoax resistances. The reactor temperature was measured by a type-K thermocouple (±5 K) located at the center of the reactor. The pressure in the reactor was controlled by a needle valve (±0.2 kPa) positioned downstream of the reactor and kept at 107 kPa. Argon, oxygen, NO, NO2 and methane were provided by Messer (purities of 99.99%, respectively). The flow rates of the reactants were controlled by mass flow controllers (±0.05%). The gases leaving the reactor were analyzed on-line using two gas chromatographs (GCs), a NOx analyzer (Thermo Scientific Model 42i), a FTIR (Thermo Scientific Antaris) spectrometer and a cw-CRDS spectroscopy cell.

• The first GC equipped with a thermal conductivity detector was used to quantify O2. The second GC equipped with flame-ionization detector preceded by a methanizer and a PlotQ capillary column was used to quantify CH4, CO, CO2, C2H4, C2H6 and C2H2.

• The chemiluminescence NOx analyzer was adopted to measure NO and NO2. The quantitative range is 0-5000 ppm for NO and 0-500 ppm for NO2 with 0.1 ppm sensitivity, respectively. Two pumps are used for outlet and bypass channels, respectively. • The FTIR spectrometer was used to detect the CH3NO2 (if any) and HCN (calibrated using a HCN diluted (1000 ppm in N2) cylinder) species.

• cw-CRDS infrared spectroscopy was used to detect H2O, CH2O and HONO (if any) species, the description of this instrument is also provided in [15].

The uncertainty for the different diagnostic instruments is estimated to be ±5% except for the FTIR and CRDS measurements which is ±10-15%. All the experimental data presented hereafter are detailed in a spreadsheet in SM2.

Kinetic model

The kinetic mechanism used for chemistry description and analysis of experimental results was obtained by relying on the POLIMI kinetic framework, describing the pyrolysis and oxidation of hydrocarbon fuels [16]. Its core C0-C3 mechanism was recently revised by coupling the H2/O2 and C1/C2 subsets from Metcalfe et al. [17], C3 from Burke et al. [18], and heavier fuels from Ranzi et al. [19]. For the low temperature conditions of interest in this work, particular attention was devoted to updating the (equilibrated) reaction rates of peroxy radical formation from methyl radical [20], as well as the related thermodynamic properties. They were adopted, when available, from the database of Burcat and Ruscic [START_REF] Burcat | Third millenium ideal gas and condensed phase thermochemical database for combustion with updates from active thermochemical tables[END_REF].

Following the modularity principle behind the POLIMI mechanism, a NOx sub-mechanism was integrated into the main framework: a complete characterization of its basic structure is provided in [START_REF] Faravelli | [END_REF]23]. It describes the major paths leading to NOx formation. Apart from the three wellstudied reactions responsible of thermal NOx mechanism [24], the mechanism underwent a major update for the prompt path, especially in relation to the NCN-route: the kinetic laws of the reactions involving NCN were updated after the ab initio calculations by Harding et al. [25] and Faßheber et al. [26]. Moreover, the chemistry of HNC and HNCN was also updated according to the modifications proposed by Lamoureux et al. [27]. On the other side, the high-temperature reburning mechanism of methane implements the rates proposed by Dean and Bozzelli [START_REF] Dean | Combustion chemistry of nitrogen[END_REF] for the reactions of methyl with NO. The methoxy activation by NO (CH3O2+ NO = CH3O + NO2) was obtained from Atkinson et al. [START_REF] Atkinson | [END_REF], and validated in the 200-430 K temperature range, while its direct formation via NO2 (CH3+ NO2= CH3O + NO) was updated following Glarborg and Bendtsen [30], which is temperature independent over the range 295-1400 K. Rate coefficients of HONO and HNO2 formation from methane and NO2 were implemented following Chai and Goldsmith [13]. The complete mechanism (153 species and 2361 reactions) is provided as supplemental material of this paper in CHEMKIN format, along with thermodynamic and transport properties (SM3). The present mechanism is able to reproduce experimental data from literature [START_REF] Dagaut | [END_REF]7,9] as shown in SM1.

Results

Experiments for the oxidation of CH4 doped with NO and NO2 with argon as bath gas were performed under fuel-lean (𝜑 = 0.5) to fuel-rich (𝜑 = 2) conditions over the 650-1200 K temperature range. Equivalence ratios were calculated neglecting the amounts of added NOx compounds which were around 4-10% that of CH4. The experimental conditions investigated in this study are presented in Table 1. Numerical calculations were conducted with CHEMKIN-PRO software package [START_REF]CHEMKIN-PRO 15151[END_REF]. Transient solver was applied in the simulation tasks with sufficient time allowed to reach the steady state solution.

Profiles of carbon compound species and water

Figure 1 shows the evolution of major products with temperature for the oxidation of CH4 (left), methane doped with NO2 (middle) and NO (right) for the three studied equivalence ratios (𝜑 = 0.5, 1 and 2). With respect to the pure CH4 oxidation, the initial oxidation temperatures are 1025 K, 1075 K and 1175 K for 𝜑 = 0.5, 1 and 2, respectively. Dynamic behaviors (oscillations) occur under oxidizing and stoichiometric conditions when the temperature is above 1050 K and 1100 K, respectively. This is, too, an interesting topic of research in such systems, but beyond the goals of this specific study.

In the presence of NO2 (400 ppm) under fuel-lean conditions, the reaction is initiated at 825 K. The rise of consumption of CH4 is extremely fast with the increase of temperature. At 950 K, 98% of the inlet methane concentration was oxidized. Under stoichiometric conditions, the onset temperature for CH4 oxidation is around 825 K as well. However, CH4 consumption is slower than that under fuel-lean conditions: there is still 24% CH4 left in the reactor outlet at 1000 K. Similarly as under the above two conditions, the consumption of methane also starts at 825 K under fuelrich conditions, whereas the consumption of methane is even slower compared to that under stoichiometric conditions. Differing from what is observed under stoichiometric and oxidizing conditions, the mole fraction of methane reaches a minimum at 950 K under reducing conditions, and the mole fraction of methane increases at higher temperatures until 1050 K. After that, methane is consumed again. Compared to the oxidation of neat methane (left column), the enhancing effect for the addition of NO2 into the oxidizing environment system is quite obvious especially for reducing conditions. In the presence of NO (500 ppm), the evolution of methane profiles is quite similar to what is obtained in the presence of NO2. This indicates that the promoting effects of NO and NO2 on methane oxidation is almost the same although the amount of the addition of NO and NO2 is a little different.

Note that oscillations even occur under stoichiometric (T > 1000 K) and oxidizing conditions (T > 1100 K, with NO2 addition) in the presence of NO and NO2. The present model could reproduce the above mentioned dynamic behavior as shown in SM1.

The peak mole fraction of CH2O profile occurs at a temperature of 850 K, which is independent of equivalence ratios in the presence of both NO and NO2. Likewise, the mole fraction of CO reaches its utmost value at 850 K under fuel-lean conditions, which indicates that the methane oxidation is very fast at this specific temperature. Under fuel-rich conditions, the temperature for the peak CO mole fraction shifts to 900 K. C2 species (C2H4, C2H6) mainly appear under stoichiometric and reducing conditions at higher temperature (T > 900 K). Under oxidizing conditions, the mole fraction of C2 species are below the detection limit and this behavior is well captured by the model as is shown in SM1. The global carbon balance has been checked and the deviation is below 5% (SM2).

The agreement between the experimental data and simulated results is generally good within all the investigated conditions except for that the model underestimates the experimental profile of H2O under stoichiometric and fuel-lean conditions, which was also observed by Bugler et al. [START_REF] Bugler | [END_REF].

It might be ascribed to the uncertainty in cw-CRDS measurements derived from its significant concentrations. Also, the performance of different literature models against present experimental data is displayed in SM1. It is found that the current POLIMI model is better capturing the experimental data than the other models.

In order to evaluate the effect of the amount of added NO2 and NO on the methane oxidation, three more sets of experiments with addition of 100 ppm NO2 or NO and addition of 1000 ppm NO (sets 7, 11 and 12 in Table 1), respectively, were conducted. Figure 2 shows both the experimental and model results. It was found that the onset temperature for methane oxidation is independent of the added amount of NO2 and NO. Moreover, with the lower added amount of NO2 or NO, the methane conversion is slower. When 1000 ppm of NO is present, methane conversion shows a trend similar to that with 500 ppm NO addition. Furthermore, the consumption rate for methane also exhibits the similar trend in the presence of both NO2 (100 ppm) and NO (100 ppm) which differs from what was previously observed by Chan et al. [9] in a FR.

Profiles of nitrogen containing species

NO2 and NO

Figure 3 shows the evolution of NO2 and NO profiles as a function of temperature for methane oxidation in the presence of NO2 (left) and NO (right), respectively. In the presence of 400 ppm NO2, the consumption of NO2 is approximately similar for all investigated equivalence ratios. The increase of the NO mole fraction is quite sharp over the range 800-900 K, and is independent of equivalence ratio. After that, it attains a "plateau" level of 280 ppm in stoichiometric and oxidizing conditions and 300 ppm in reducing conditions, with the increase of temperature. Only under rich conditions the NO concentration drops from 300 to 100 ppm when the temperature increases from 1100 K to 1200 K. The model accurately predicts the onset for both the consumption of NO2 and production of NO. It overestimates the amount of NO when the temperature is above 800 K. In the presence of NO (500 ppm), the mole fraction of NO2 peaks at 850 K, which corresponds to the maximum consumption of NO with all equivalence ratios. The amount of NO2 drops gradually as the temperature is above 850 K, meanwhile, the mole fraction of NO increases to a stable value until the temperature is beyond 900 K. Under reducing conditions, the mole fraction of NO decreases dramatically over the temperature range 1100-1200 K. Although the model underestimates the formation of NO2, the initiation temperature for NO-NO2 conversion is well captured.

HCN

HCN has been quantified by FTIR at the highest temperatures (1175-1200 K) studied in this work for both NO2 and NO additions as shown in Figure 3. The measured HCN spectrum is displayed in SM1. At a same temperature, the amount of HCN is higher in the presence of NO than with NO2 addition. Moreover, the quantification of HCN could somewhat help to close the nitrogen balance at the highest temperatures. The model predicts the formation of HCN quite well in the presence of although it underestimates the amount of HCN in the presence of NO at 1200 K.

The mass balance of nitrogen deteriorates with the increase of temperature when temperature is above 850 K in the presence of NO2 condition. The reason could be ascribed to the detection failure for some nitrogenated species with the currently available diagnostic instruments. Also, the overprediction of NO in the presence of NO2 indicates that the NO2 conversion channel needs to be further investigated.

A search for HONO and CH3NO2 species

The absorption spectrum of HONO has been previously measured by Jain et al. [33]. This previous work indicates that HONO, if any, should be detected in the present study. In our study, the cw-CRDS product analyses were conducted in the near infrared at wavenumbers in the 6638.0-6643.5 cm -1 range. The absorption line at 6643.17 cm -1 was chosen as the most suitable for the quantification of HONO with an absorption cross-section of 4.2 ± 1.7 × 10 -21 cm 2 [33] due to the fact that there are no interferences at this specific absorption line. There were obvious signals at this absorption line in the spectrum around a temperature of 850 K. However, for some less intense absorption lines, such as 6642.45 cm -1 , no signals could be observed in our spectra. Therefore, the maximum produced HONO mole fraction is then below the estimated detection limit of 3 ppm. No obvious FTIR absorption lines for CH 3 NO 2 could be observed. The maximum produced CH 3 NO 2 mole fraction is then below the estimated detection limit of 5 ppm. The measured spectra of HONO and CH 3 NO 2 of this study can be found in SM1. Modeling calculations (see SM1) predict low mole fraction (1-2 ppm) of HONO, which is consistent with what is observed in these experimental data. Note that the discrepancy between experimental and modeling calculations found in the 800-1000 K range for NO2 (right upper in Figure 3), can be explained by the too high predicted formation of CH3NO2. However, no experimental detection of this species by FTIR was achieved although it could be done.

Discussion

Reaction rate and sensitivity analyses have been performed to identify the main reaction routes and the utmost sensitive reactions for CH4 consumption in the presence of NOx, respectively, as shown in Figure 4. The characteristic temperature of 850 K is selected because the consumption of methane is quite significant and the formation of carbon species peaks at this specific temperature.

In the case of neat CH4, the reaction path analysis is conducted at 1100 K, its consumption proceeds through methyl radicals (CH3) which can continue reacting following 4 different routes: The above mentioned reaction loop (1)-( 4) acts as a "catalytic" cycle and it can explain the fact that the addition of NO or NO2 seems to have similar effects on promoting methane oxidation. Note that NO/NO2 interchanging occurs via the reaction of NO and HO2 radicals giving NO2 and OH radicals and the reaction of NO2 with H radicals reforming NO and OH radicals. The OH radicals produced during the NO-NO2 interchanging cycle interact with CH4 promoting its conversion, whereas the H and HO2 radicals produced during the conversion of CH4 (i.e. mainly through CH3O(+ M) = CH2O(+ M) + H and HCO + O2= CO + HO2) promote the NONO2 conversion as described earlier. The role of the radicals in the mutual sensitization of the oxidation of CH4 and NOx has been highlighted in Figure 4.

Moreover, in the presence of NO or NO2, CH3 radical is consumed by an alternative route, leading to the formation of nitromethane, CH3NO2. This acts as an inhibitor of the whole system for two different reasons: (i) it traps both CH3 and NO2, slowing down their successive reactions and the formation of the very reactive methoxy radical (CH3O), and (ii) it also acts as an OH scavenger via OH + CH3NO2= H2O + NO + CH2O.

The main formation route for HONO is from NO2 by reactions NO2+ CH2O = HONO + HCO and NO2+ HNO = HONO + NO. It only represents 4% in the total NO2 consumption at 850 K and 𝜑 = 0.5, hence the expected HONO mole fraction is small, which agrees with the experimental data.

However, these reactions play an essential role for the consumption of methane because the unstable HONO can readily convert to OH radical. In turn this favors the abstraction reaction CH4+ OH = CH3+ H2O, which is the second most sensitive reaction for methane depletion in the conditions with NO2 addition. Note that the sensitivity analysis in Figure 4 shows a strong promoting effect of the reaction NO2+ CH2O = HONO + HCO.

At high temperatures, when HCN has been experimentally detected, NO reacts with HCCO and CH3 radicals to form HCNO and H2CN, respectively, and later HCN is obtained; thus, NO is reduced by means of well-known reburn type reactions [3].

Conclusions

In this work, the oxidation of neat methane and methane doped with NO2 or NO at 107 kPa and temperatures of 650-1200 K with a fixed residence time of 1.5 s has been investigated in a jet-stirred reactor under oxidizing to reducing conditions from both experimental and modeling points of view. In general, there is a good agreement between experimental results and modeling calculations. New experimental data and new species detection, along with the confirmation of a detailed kinetic model under these new conditions, have provided insights into understanding the mutual effect of CH4NOx interaction. The addition of NO2 or NO produces comparable results on methane oxidation, anticipating the onset temperature for CH4 consumption to lower temperatures (825 K) regardless of the equivalence ratio. Kinetic analysis showed that the parallel behavior of NO and NO2 is connected to their interchanging via NO2+ H/CH3= NO + OH/CH2O and NO + HO2/CH3O2= NO2+ OH/CH3O reactions. This allows relating both actions to a common, oxidation-sensitizing mechanism, activated by methoxy radical formation, whilst counteracted by the parallel formation of nitromethane. The mole fraction of HCN has been quantified with FTIR, and the agreement between the experimental data and model predication is generally good. Modeling calculations predict the formation of CH3NO2, which was not detected experimentally although it could be, partially explaining the discrepancy between experimental and modeling results in the NO2 profile at 800-1000 K. The contribution of HONO in the activation of the system was pointed out, too. The amount of HONO was under the detection limit, consistently with the modeling predictions.

Figure 1 .

 1 Figure 1. Species profile comparison between experimental data and model predictions. The left column is for the oxidation of neat methane; the middle column is for the oxidation of methane doped with NO2 (400 ppm); the right column is for the oxidation of methane doped with NO (500 ppm). Here and in further figures in this paper, symbols represent experiments and lines denote simulations. Experiments and simulations are not presented for conditions where oscillations were observed.

Figure 2 .

 2 Figure 2. Mole fractions of methane with various additions of NO2 (400 and 100 ppm) and NO (1000, 500 and 100 ppm) under stoichiometric condition.

Figure 3 .

 3 Figure 3. The comparison of NO2, NO and HCN profiles between experimental data and model predictions. Left: the oxidation of methane doped with NO2 (400 ppm). Right: the oxidation of methane doped with NO (500 ppm).

  (a) a self-reaction forming ethane; reactions with O2, (b) forming directly CH2O + OH radicals, (c) giving CH3O radicals which also lead to formaldehyde via reaction (1) CH3O(+ M) = CH2O + H(+ M) or (d) producing CH3O2 radical via reaction (2) CH3+ O2(+ M) = CH3O2(+ M), which is also a minor source of formaldehyde.At 850 K, in the presence of NOx, methoxy radical formation through reaction (3) CH3 + NO2 = CH3O + NO is the most sensitive as shown in sensitivity analysis except for the addition of NO under reducing condition, when reaction (3) is slightly less sensitive than chain branching reaction H + O2 = O + OH. In this case, CH3O radicals are also formed in large extent by the reaction of NO with CH3O2 radicals: reaction (4) CH3O2+ NO = CH3O + NO2. The whole reaction cycle (1)-(4) results in an overall balance: 2CH3+ O2= 2CH2O + 2H and produces a strong acceleration of methane oxidation, since 2 H atoms are obtained from 2 CH3 radicals and one O2 molecule. The reaction route involving C2 species becomes more relevant as the temperature is increased being almost negligible at 850 K.

Figure 4 .

 4 Figure 4. Left: Reaction path diagram for CH4 oxidation in presence of NOx (𝜑 = 1, 𝑇 = 850 K). Solid lines represent the main reaction routes occurring during the oxidation of neat CH4 (1100 K); dashed lines highlight the main changes due to the presence of NOx. The size of the arrow is proportional to the flow rate of the given reactions. Right: CH4 sensitivity coefficient at 850 K in the presence of NO2 (upper: 400 ppm) and NO (bottom: 500 ppm).

o

  Comparison of FTIR spectra for HCN with the spectra obtained during the oxidation of methane doped with NO. o Comparison of FTIR spectra for CH3NO2 with the spectra obtained during the oxidation of methane doped with NO2. o Comparison of cw-CRDS spectra for HONO with the spectra obtained during the o oxidation of methane doped with NO2. o Comparisons between the original POLIMI model and POLIMI model with CH3+NO2=CH2O+NO modified against the experimental data under different conditions.  Experimental results (excel spreadsheet)  Detailed kinetic model (reactions, thermodynamic properties, transport data)

Table 1 .

 1 Experimental conditions (Inlet composition volume basis; balanced Ar).

	Exp.	𝑿 𝑪𝑯 𝟒	𝑿 𝑵𝑶 ppm	𝑿 𝑵𝑶 𝟐 ppm	𝑿 𝑶 𝟐	𝝋
	1	0.01	-	-	0.04	0.5
	2	0.01	-	-	0.02	1
	3	0.01	-	-	0.01	2
	4	0.01	500	-	0.04	0.5
	5	0.01	500	-	0.02	1
	6	0.01	500	-	0.01	2
	7	0.01	100	-	0.02	1
	8	0.01	-	400	0.04	0.5
	9	0.01	-	400	0.02	1
	10	0.01	-	400	0.01	2
	11	0.01	-	100	0.02	1
	12	0.01	1000	-	0.02	1

Acknowledgments

This work has received funding from the European Union H2020 (H2020-SPIRE-04-2016) under Grant agreement no. 723706 and from the COST Action CM1404 "Chemistry of smart energy carriers and technologies". Ms. Marrodán acknowledges Aragón Government for the predoctoral grant awarded.


Aurélien Bellet

Rachid Guerraoui

Mahsa Taziki

Marc Tommasi

Personalized and Private Peer-to-Peer Machine Learning

The rise of connected personal devices together with privacy concerns call for machine learning algorithms capable of leveraging the data of a large number of agents to learn personalized models under strong privacy requirements. In this paper, we introduce an efficient algorithm to address the above problem in a fully decentralized (peer-topeer) and asynchronous fashion, with provable convergence rate. We show how to make the algorithm differentially private to protect against the disclosure of information about the personal datasets, and formally analyze the trade-off between utility and privacy. Our experiments show that our approach dramatically outperforms previous work in the non-private case, and that under privacy constraints, we can significantly improve over models learned in isolation.

Introduction

Connected personal devices are now widespread: they can collect and process increasingly large and sensitive user data. As a concrete example, consider the health domain. Smart watches can record cardiac activities, mobile apps encourage users to participate to studies (about depression, concussion, etc.), 1 and recent painless sensors can replace a finger prick for blood glucose testing [START_REF] Cappon | Wearable continuous glucose monitoring sensors: A revolution in diabetes treatment[END_REF]. Such information can be leveraged through machine learning to provide useful personalized services (e.g., personalized treatments) to the user/patient. A common practice is to centralize data from all devices on an external server for batch processing, sometimes without explicit consent from 1 See e.g., https://www.apple.com/researchkit/ Proceedings of the 21 st International Conference on Artificial Intelligence and Statistics (AISTATS) 2018, Lanzarote, Spain. PMLR: Volume 84. Copyright 2018 by the author(s).

users and with little oversight. While this data concentration is ideal for the utility of the learning process, it raises serious privacy concerns and opens the door to potential misuse (e.g., exploitation for the purpose of recruitment, insurance pricing or granting loans). Therefore, in applications where the data is considered too sensitive to be shared (due to legislation or because the user opts out), one has to learn on each device separately without taking advantage of the multiplicity of data sources (e.g., information from similar users). This preserves privacy but leads to poor accuracy, in particular for new or moderately active users who have not collected much data. Instead of the above two extreme approaches, our goal is to design a solution allowing a large number of users (agents) to collaborate so as to learn more accurate personalized models while ensuring that their data stay on their local device and that the algorithm does not leak sensitive information to others. We consider a fully decentralized solution where agents operate asynchronously and communicate over a network in a peer-to-peer fashion, without any central entity to maintain a global state of the system or even to coordinate the protocol. The network acts as a communication network but also models similarities between users. While a decentralized architecture may be the only available option in some applications (e.g., IoT), it also provides interesting benefits when a more traditional distributed (master/slave) architecture could be used. In particular, peer-to-peer algorithms provide scalability-by-design to large sets of devices thanks to the locality of their updates [START_REF] Kermarrec | Want to scale in centralized systems? Think P2P[END_REF]. For instance, it was recently shown that fully decentralized learning algorithms can perform better than their distributed counterparts because they avoid a communication bottleneck at the master node [START_REF] Lian | Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent[END_REF]. Finally, a decentralized architecture intrinsically provides some security guarantees as it becomes much more difficult for any party (or any external adversary) to observe the full state of the system.

The problem of decentralized collaborative learning of personal models has been recently considered by [START_REF] Vanhaesebrouck | Decentralized Collaborative Learning of Personalized Models over Networks[END_REF], but they did not consider any privacy constraints. In fact, while there has been a large body of work on privacy-preserving machine learning from centralized data, notably based on differential privacy (see [START_REF] Dwork | The Algorithmic Foundations of Differential Privacy[END_REF][START_REF] Chaudhuri | Differentially Private Empirical Risk Minimization[END_REF]Bassily et al., 2014, and references therein), the case where sensitive datasets are distributed across multiple data owners has been much less studied, let alone the fully decentralized setting. Existing approaches for privacy-preserving distributed learning (see e.g., [START_REF] Pathak | Multiparty Differential Privacy via Aggregation of Locally Trained Classifiers[END_REF][START_REF] Rajkumar | A Differentially Private Stochastic Gradient Descent Algorithm for Multiparty Classification[END_REF][START_REF] Shokri | Privacy-Preserving Deep Learning[END_REF][START_REF] Huang | Differentially Private Distributed Optimization[END_REF] rely on a central (sometimes trusted) server, assume the local data distribution is the same for all users and/or are designed to learn a single global model rather than a personal model for each user.

In this paper, we ask a challenging question: given the above decentralization and privacy constraints, can agents improve upon their purely local models through collaboration? Our contributions towards a positive answer to this question are three-fold. First, we propose a decentralized and asynchronous block coordinate descent algorithm to address the problem in the non-private setting. Taking advantage of the structure of the problem, this algorithm has simple updates and provable convergence rates, improving upon the previous work of [START_REF] Vanhaesebrouck | Decentralized Collaborative Learning of Personalized Models over Networks[END_REF]. Second, we design a differentially-private scheme based on randomly perturbing each update of our algorithm. This scheme guarantees that the messages sent by the users over the network during the execution of the algorithm do not reveal significant information about any data point of any local dataset. We provide a formal analysis of the utility loss due to privacy. Third, we conduct experiments on synthetic and real-world data to validate our approach. The empirical results show that the trade-off between utility and privacy is in line with our theoretical findings, and that under strong privacy constraints we can still outperform the purely local models in terms of accuracy.

The rest of the paper is organized as follows. In Section 2, we describe the problem setting and presents our decentralized algorithm for the non-private case. Section 3 introduces a differentially private version and analyzes the trade-off between utility and privacy. In Section 4, we discuss some related work on decentralized and private learning. Finally, Section 5 is dedicated to numerical experiments. Detailed proofs can be found in the supplementary material.

Peer-to-Peer Personalized Learning with Coordinate Descent

We start by formally describing the learning problem that we address in this paper.

Problem Setting

We consider a set of n agents. Each agent i has a local data distribution µ i over the space X × Y and has access to a set S i = {(x j i , y j i )} mi j=1 of m i ≥ 0 training examples drawn i.i.d. from µ i . The goal of agent i is to learn a model θ ∈ R p with small expected loss E (xi,yi)∼µi [ (θ; x i , y i )], where the loss function (θ; x i , y i ) is convex in θ and measures the performance of θ on data point (x i , y i ). In the setting where agent i must learn on its own, a standard approach is to select the model minimizing the local (potentially regularized) empirical loss:

θ loc i ∈ arg min θ∈R p 1 m i mi j=1 (θ; x j i , y j i ) + λ i θ 2 Li(θ;Si) , (1)
with λ i ≥ 0. In this paper, agents do not learn in isolation but rather participate in a decentralized peer-topeer network over which they can exchange information. Such collaboration gives them the opportunity to learn a better model than (1), for instance by allowing some agents to compensate for their lack of data. Formally, let n = {1, . . . , n} and G = ( n , E, W ) be a weighted connected graph over the set of agents where E ∈ n × n is the set of edges and W ∈ R n×n is a nonnegative weight matrix. W ij gives the weight of edge (i, j) ∈ E with the convention that W ij = 0 if (i, j) / ∈ E or i = j. Following previous work (see e.g., [START_REF] Evgeniou | Regularized multi-task learning[END_REF][START_REF] Vanhaesebrouck | Decentralized Collaborative Learning of Personalized Models over Networks[END_REF], we assume that the edge weights reflect a notion of "task relatedness": the weight W ij between agents i and j tends to be large if the models minimizing their respective expected loss are similar. These pairwise similarity weights may be derived from user profiles (e.g., in the health domain: weight, size, diabetes type, etc.) or directly from the local datasets, and can be computed in a private way (see e.g., [START_REF] Goethals | On Private Scalar Product Computation for Privacy-Preserving Data Mining[END_REF][START_REF] Alaggan | Private Similarity Computation in Distributed Systems: from Cryptography to Differential Privacy[END_REF].

In order to scale to large networks, our goal is to design fully decentralized algorithms: each agent i only communicates with its neighborhood N i = {j : W ij > 0} without global knowledge of the network, and operates without synchronizing with other agents. Overall, the problem can thus be seen as a multi-task learning problem over a large number of tasks (agents) with imbalanced training sets, and which must be solved in a fully decentralized way.

Objective Function

Our goal is to jointly learn the models of the agents by leveraging both their local datasets and the similarity information embedded in the network graph.

Following a well-established principle in the multi-task learning literature [START_REF] Evgeniou | Regularized multi-task learning[END_REF][START_REF] Maurer | The Rademacher Complexity of Linear Transformation Classes[END_REF][START_REF] Dhillon | Semi-supervised multi-task learning of structured prediction models for web information extraction[END_REF], we use graph regularization to favor models that vary smoothly on the graph. Specifically, representing the set of all models Θ i ∈ R p as a stacked vector Θ = [Θ 1 ; . . . ; Θ n ] ∈ R np , the objective function we wish to minimize is given by

Q L (Θ) = 1 2 n i<j W ij Θ i -Θ j 2 +µ n i=1 D ii c i L i (Θ i ; S i ),
(2) where µ > 0 is a trade-off parameter, D ii = n j=1 W ij is a normalization factor and c i ∈ (0, 1] ∝ m i is the "confidence" of agent i.2 Minimizing (2) implements a trade-off between having similar models for strongly connected agents and models that are accurate on their respective local datasets (the higher the confidence of an agent, the more importance given to the latter part). This allows agents to leverage relevant information from their neighbors -it is particularly salient for agents with less data which can gain useful knowledge from better-endowed neighbors without "polluting" others with their own inaccurate model. Note that the objective (2) includes the two extreme cases of learning purely local models as in (1) (when µ → ∞) and learning a single global model (for µ → 0).

We now discuss a few assumptions and properties of Q L . We assume that for any i ∈ n , the local loss function L i of agent i is convex in its first argument with L loc i -Lipschitz continuous gradient. This implies that Q L is convex in Θ. 3 If we further assume that each L i is σ loc i -strongly convex with σ loc i > 0 (this is the case for instance when the local loss is L2-regularized), then

Q L is σ-strongly convex with σ ≥ µ min 1≤i≤n [D ii c i σ loc i ] > 0. In other words, for any Θ, Θ ∈ R np we have Q L (Θ ) ≥ Q L (Θ) + ∇Q L (Θ) T (Θ -Θ)+ σ 2 Θ -Θ 2 2 . The partial derivative of Q L (Θ) w.r.t. the variables in Θ i is given by [∇Q L (Θ)] i = D ii (Θ i +µc i ∇L i (Θ i ; S i ))-j∈Ni W ij Θ j .
(3) We define the matrices

U i ∈ R np×p , i ∈ n , such that (U 1 , . . . , U n ) = I np . For i ∈ [n], the i-th block Lipschitz constant L i of ∇Q L (Θ) satisfies [∇Q L (Θ + U i d)] i - [∇Q L (Θ)] i ≤ L i d for any Θ ∈ R np and d ∈ R p . It is easy to see that L i = D ii (1 + µc i L loc i ).
We denote L min = min i L i and L max = max i L i .

Non-Private Decentralized Algorithm

For ease of presentation, we first present a non-private decentralized algorithm. Note that this is interesting in its own right as the proposed solution improves upon the algorithm previously proposed by [START_REF] Vanhaesebrouck | Decentralized Collaborative Learning of Personalized Models over Networks[END_REF], see Section 4 for a discussion.

Time and communication models. Our goal is to minimize the objective function (2) in a fully decentralized manner. Specifically, we operate in the asynchronous time model [START_REF] Boyd | Randomized gossip algorithms[END_REF]: each agent has a local clock ticking at the times of a rate 1 Poisson process, and wakes up when it ticks. This is in contrast to the synchronous model where agents wake up jointly according to a global clock (and thus need to wait for everyone to finish each round). As local clocks are i.i.d., we can equivalently consider a single clock which ticks when one of the local clocks ticks. This provides a more convenient way to state and analyze the algorithms in terms of a global clock counter t (which is unknown to the agents). For communication, we rely on a broadcast-based model [START_REF] Aysal | Broadcast Gossip Algorithms for Consensus[END_REF][START_REF] Nedic | Asynchronous Broadcast-Based Convex Optimization Over a Network[END_REF] where agents send messages to all their neighbors at once (without expecting a reply). This model is very appealing in wireless distributed systems, as sending a message to all neighbors has the same cost as sending to a single neighbor.

Algorithm. We propose a decentralized coordinate descent algorithm to minimize (2). We initialize the algorithm with an arbitrary set of local models Θ(0) = [Θ i (0); . . . ; Θ n (0)]. At time step t, an agent i wakes up. Two consecutive actions are then performed by i:

• Update step: agent i updates its local model based on the most recent information Θ j (t) received from its neighbors j ∈ N i :

Θ i (t + 1) = Θ i (t) -(1/L i )[∇Q L (Θ(t))] i (4) = (1 -α)Θ i (t) + α j∈Ni Wij Dii Θ j (t) -µc i ∇L i (Θ i (t); S i ) , where α = 1/(1 + µc i L loc i ) ∈ (0, 1].
• Broadcast step: agent i sends its updated model Θ i (t + 1) to its neighborhood N i .

The update step (4) consists in a block coordinate descent update with respect to Θ i and only requires agent i to know the models Θ j (t) previously broadcast by its neighbors j ∈ N i . Note that the agent does not need to know the global iteration counter t, hence no global clock is needed. The algorithm is thus fully decentralized and asynchronous. Interestingly, notice that this block coordinate descent update is adaptive to the confidence level of each agent in two respects: (i) globally, the more confidence, the more importance given to the gradient of the local loss compared to the neighbors' models, and (ii) locally, when Θ i (t) is close to a minimizer of the local loss L i (which is the case for instance if we initialize Θ i (0) to such a minimizer), agents with low confidence will trust their neighbors' models more aggressively than agents with high confidence (which will make more conservative updates).4 This is in line with the intuition that agents with low confidence should diverge more quickly from their local minimizer than those with high confidence.

Convergence analysis. Under our assumption that the local clocks of the agents are i.i.d., the above algorithm can be seen as a randomized block coordinate descent algorithm [START_REF] Wright | Coordinate descent algorithms[END_REF]. It enjoys a fast linear convergence rate when Q L is strongly convex, as shown in the following result.

Proposition 1 (Convergence rate). For T > 0, let (Θ(t)) T t=1 be the sequence of iterates generated by the proposed algorithm running for T iterations from an initial point

Θ(0) ∈ R np . Let Q L ∈ min Θ∈R np Q L (Θ). When Q L is σ-strongly convex, we have: E [Q L (Θ(T )) -Q L ] ≤ 1- σ nL max T (Q L (Θ(0)) -Q * L ) .
Proof. This follows from a slight adaptation of the proof of [START_REF] Wright | Coordinate descent algorithms[END_REF] (Theorem 1 therein) to the block coordinate descent case. Note that the result can also be obtained as a special case of our Theorem 2 (later introduced in Section 3.2) by setting the noise scale s i (t) = 0 for all t, i.

Remark 1. For general convex Q L , an O(1/t) rate can be obtained, see [START_REF] Wright | Coordinate descent algorithms[END_REF] for details.

Proposition 1 shows that each iteration shrinks the suboptimality gap by a constant factor. While this factor degrades linearly with the number of agents n, this is compensated by the fact that the number of iterations done in parallel also scales roughly linearly with n (because agents operate asynchronously and in parallel). We thus expect the algorithm to scale gracefully with the size of the network if the number of updates per agent remains constant. The value

σ Lmax ≥ µ min 1≤i≤n [Diiciσ loc i ] max 1≤i≤n [Dii(1+µciL loc i )]
> 0 is the ratio between the lower and upper bound on the curvature of Q L . Focusing on the relative differences between agents and assuming constant σ loc i 's and L loc i 's, it indicates that the algorithm converges faster when the degree-weighted confidence of agents is approximately the same. On the other hand, two types of agents can represent a bottleneck for the convergence rate: (i) a high-confidence and high-degree agent (the overall progress is then very dependent on the updates of that particular agent), and (ii) a low-confidence, poorly connected agent (hence converging slowly).

Differentially Private Algorithm

As described above, the algorithm introduced in the previous section has many interesting properties. However, while there is no direct exchange of data between agents, the sequence of iterates broadcast by an agent may reveal information about its private dataset through the gradient of the local loss. In this section, we define our privacy model and introduce an appropriate scheme to make our algorithm differentially private. We study its utility loss and the trade-off between utility and privacy.

Privacy Model

At a high level, our goal is to prevent eavesdropping attacks. We assume the existence of an adversary who observes all the information sent over the network during the execution of the algorithm, but cannot access the agents' internal memory. We want to ensure that such an adversary cannot learn much information about any individual data point of any agent's dataset. This is a very strong notion of privacy: each agent does not trust any other agent or any third-party to process its data, hence the privacy-preserving mechanism must be implemented at the agent level. Furthermore, note that our privacy model protects any agent against all other agents even if they collude (i.e., share the information they receive).5

To formally define this privacy model, we rely on the notion of Differential Privacy (DP) [START_REF] Dwork | Differential Privacy[END_REF], which has emerged as a powerful measure of how much information about any individual entry of a dataset is contained in the output of an algorithm. Formally, let M be a randomized mechanism taking a dataset as input, and let > 0, δ ≥ 0. We say that M is ( , δ)-differentially private if for all datasets S = {z 1 , . . . , z i , . . . , z m }, S = {z 1 , . . . , z i , . . . , z m } differing in a single data point and for all sets of possible outputs O ⊆ range(M), we have:

P r(M(S) ∈ O) ≤ e P r(M(S ) ∈ O) + δ, (5)
where the probability is over the randomness of the mechanism. At a high level, one can see (5) as ensuring that M(S) does not leak much information about any individual data point contained in S. DP has many attractive properties: in particular it provides strong robustness against background knowledge attacks and does not rely on computational assumptions.

The composition of several DP mechanisms remains DP, albeit a graceful degradation in the parameters (see [START_REF] Dwork | Boosting and Differential Privacy[END_REF]Kairouz et al., 2015, for strong composition results). We refer to [START_REF] Dwork | The Algorithmic Foundations of Differential Privacy[END_REF] for more details on DP.

In our setting, following the notations of ( 5), each agent i runs a mechanism M i (S i ) which takes its local dataset S i and outputs all the information sent by i over the network during the execution of the algorithm (i.e., the sequence of iterates broadcast by the agent).

Our goal is to make M i (S i ) ( , δ)-DP for all agents i simultaneously. Note that learning purely local models ( 1) is a perfectly private baseline according to the above definition as agents do not exchange any information. Below, we present a way to collaboratively learn better models while preserving privacy.

Privacy-Preserving Scheme

The privacy-preserving version of our algorithm consists in replacing the update step in (4) by the following one (assuming that at time t agent i wakes up):

Θ i (t + 1) = (1 -α) Θ i (t) + α j∈Ni Wij Dii Θ j (t) -µc i (∇L i ( Θ i (t); S i ) + η i (t)) , (6)
where η i (t) ∼ Laplace(0, s i (t)) p ∈ R p is a noise vector drawn from a Laplace distribution with finite scale s i (t) ≥ 0. 6 The difference with the non-private update is that agent i adds appropriately scaled Laplace noise to the gradient of its local loss L i . It then sends the resulting noisy iterate Θ i (t + 1), instead of Θ i (t + 1), to its neighbors. Note that for full generality, we allow the noise to potentially depend on the global iteration number t, as we will see towards the end of this section that it opens interesting perspectives.

Assume that update ( 6) is run T i times by agent i within the total T > 0 iterations across the network. Let T i = {t k i } Ti k=1 be the set of iterations at which agent i woke up and consider the mechanism

M i (S i ) = { Θ i (t i + 1) : t i ∈ T i }.
The following theorem shows how to scale the noise at each iteration, s i (t i ), so as to provide the desired overall differential privacy guarantees.

Theorem 1 (Differential privacy of M i ). Let i ∈ n and assume that L i (θ;

S i ) = 1 mi mi k=1 i (θ; x k i , y k i ) + λ i θ 2 where (•; x, y) is L 0 -Lipschitz with respect to the L 1 -norm for all (x, y) ∈ X ×Y. For any t i ∈ T i , let s i (t i ) = 2L0 i(ti)mi for some i (t i ) > 0.
For any δi ∈ [0, 1] and initial point Θ(0) ∈ R np independent of S i , the 6 We use the convention Laplace(0, 0) = 0 w.p. 1.

mechanism M i (S i ) is (¯ i , δi )-DP with ¯ i = min Ti ti=1 i (t i ), Ti ti=1 (e i (t i ) -1) i(ti) e i (t i ) +1 + Ti ti=1 2 i (t i ) 2 log e + Ti ti=1 i (t i ) 2 / δi , Ti ti=1 (e i (t i ) -1) i(ti) e i (t i ) +1 + Ti ti=1 2 i (t i ) 2 log(1/ δi ) .
Remark 2. We can obtain a similar result if we assume L 0 -Lipschitzness of w.r.t. L 2 -norm (instead of L 1 ) and use Gaussian noise (instead of Laplace). Details are in the supplementary material.

Theorem 1 shows that M i (S i ) is (¯ i , 0)-DP for ¯ i = Ti ti=1 i (t i ).
One can also achieve a better scaling for ¯ i at the cost of setting δi > 0 (see [START_REF] Kairouz | The Composition Theorem for Differential Privacy[END_REF], for a discussion of the trade-offs in the composition of DP mechanisms). The noise scale needed to guarantee DP for an agent i is inversely proportional to the size m i of its local dataset S i . This is a classic property of DP, but it is especially appealing in our collaborative formulation as the confidence weights c i 's tune down the importance of agents with small datasets (preventing their noisy information to spread) and give more importance to agents with larger datasets (who propagate useful information). Our next result quantifies how the added noise affects the convergence.

Theorem 2 (Utility loss). For any T > 0, let ( Θ(t)) T t=1 be the sequence of iterates generated by T iterations of update (6) from an initial point Θ(0) ∈ R np . For σ-strongly convex Q L , we have:

E Q L ( Θ(T )) -Q L ≤ 1 - σ nL max T Q L ( Θ(0)) -Q L + 1 nL min T -1 t=0 n i=1 1 - σ nL max t µD ii c i s i (t) 2 .
This result shows that the error of the private algorithm after T iterations decomposes into two terms. The first term is the same as in the non-private setting and decreases with T . The second term gives an additive error due to the noise, which takes the form of a weighted sum of the variance of the noise added to the iterate at each iteration (note that we indeed recover the non-private convergence rate of Proposition 1 when the noise scale is 0). When the noise scale used by each agent is constant across iterations, this additive error converges to a finite number as T → ∞.

The number of iterations T rules the trade-off between the two terms. We give more details in the supplementary material and study this numerically in Section 5.

In practical scenarios, each agent i has an overall privacy budget (¯ i , δi ). Assume that the agents agree on a value for T (e.g., using Proposition 1 to achieve the desired precision). Each agent i is thus expected to wake up T i = T /n times, and can use Theorem 1 to appropriately distribute its privacy budget across the T i iterations and stop after T i updates. A simple and practical strategy is to distribute the budget equally across the T i iterations. Yet, Theorem 2 suggests that better utility can be achieved if the noise scale increases with time. Assume that agents know in advance the clock schedule for a particular run of the algorithm, i.e. agent i knows the global iterations T i at which it will wake up. The following result gives the noise allocation policy minimizing the utility loss.

Proposition 2. Let C = 1 -σ/nL max and for any

agent i ∈ n define λ Ti (i) = t∈Ti 3 √ C-1 3 √ C T -1 3 √ C t . As- suming s i (t i ) = 2L0
i(ti)mi for t i ∈ T i as in Theorem 1, the following privacy parameters optimize the utility loss while ensuring the budget ¯ i is matched exactly:

i (t) = 3 √ C-1 3 √ C T -1 3 √ C t ¯ i λ T i (i) for t ∈ T i , 0 otherwise.
The above noise allocation policy requires agents to know in advance the schedule and the global iteration counter. This is an unrealistic assumption in the fully decentralized setting where no global clock is available. Still, Proposition 2 may be useful to design heuristic strategies that are practical, for instance, based on using the expected global time for the agent to wake up at each of its iterations. We leave this for future work.

Remark 3. Theorem 2 implies that a good warm start point Θ(0) is beneficial. However, Θ(0) must be DP. In the supplementary material, we show how to generate a private warm start based on propagating perturbed versions of purely local models in the network.

Related Work

Decentralized ML. Most of the work in fully decentralized learning and optimization has focused on the distributed consensus problem, where the goal is to find a single global model which minimizes the sum of the local loss functions [START_REF] Nedic | Distributed Subgradient Methods for Multi-Agent Optimization[END_REF][START_REF] Ram | Distributed Stochastic Subgradient Projection Algorithms for Convex Optimization[END_REF][START_REF] Duchi | Privacy Aware Learning[END_REF][START_REF] Wei | Distributed Alternating Direction Method of Multipliers[END_REF][START_REF] Colin | Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions[END_REF]. In contrast, we tackle the case where agents have distinct objectives.

The work of [START_REF] Vanhaesebrouck | Decentralized Collaborative Learning of Personalized Models over Networks[END_REF] recently studied the problem of decentralized learning of personalized models and is hence more closely related to our approach, but they did not consider any privacy constraints. At the cost of introducing many auxiliary variables, they cast the objective function as a partial consensus problem over the network which can be solved using a decentralized gossip ADMM algorithm [START_REF] Wei | On the O(1/k) Convergence of Asynchronous Distributed Alternating Direction Method of Multipliers[END_REF]. Our contributions extend over this previous work in several respects: (i) we propose a simpler block coordinate descent algorithm with linear convergence rate, which also proves to be much faster in practice (see Section 5), (ii) we design a differentially private algorithm and provide an analysis of the resulting privacy/utility trade-off, and (iii) we present an evaluation of our approach on real data (in addition to synthetic experiments).

DP in distributed learning. Differential Privacy has been mostly considered in the context where a "trusted curator" has access to all data. Existing DP schemes for learning in this setting typically rely on the addition of noise to the learned model (output perturbation) or to the objective function itself (objective perturbation), see for instance [START_REF] Chaudhuri | Differentially Private Empirical Risk Minimization[END_REF].

The private multi-party setting, in which sensitive datasets are distributed across multiple data owners, is known to be harder [START_REF] Mcgregor | The Limits of Two-Party Differential Privacy[END_REF] and has been less studied in spite of its relevance for many applications. Local DP [START_REF] Duchi | Privacy Aware Learning[END_REF][START_REF] Kairouz | Extremal Mechanisms for Local Differential Privacy[END_REF], consisting in locally perturbing the data points themselves before releasing them, often achieves poor accuracy (especially when local datasets are small). In the master/slave setting, DP algorithms have been introduced to learn a private global model, either by aggregating models trained locally by each party [START_REF] Pathak | Multiparty Differential Privacy via Aggregation of Locally Trained Classifiers[END_REF][START_REF] Hamm | Learning privately from multiparty data[END_REF] or by perturbing the gradients and/or the objective in a distributed gradient descent algorithm [START_REF] Song | Stochastic gradient descent with differentially private updates[END_REF][START_REF] Rajkumar | A Differentially Private Stochastic Gradient Descent Algorithm for Multiparty Classification[END_REF][START_REF] Shokri | Privacy-Preserving Deep Learning[END_REF]. Some of these approaches rely on the assumption that local datasets are drawn from the same global distribution. The work of [START_REF] Huang | Differentially Private Distributed Optimization[END_REF] considers the decentralized setting, using a privacy model similar to ours. However, they still learn a single global model and it is not clear how their algorithm and analysis can be adapted to our multi-task problem. Moreover, their approach is synchronous, relies on additional assumptions (e.g., bounded second derivatives) and does not have established convergence rates.

We conclude this section by briefly mentioning the recent work of [START_REF] Hitaj | Deep Models Under the GAN: Information Leakage from Collaborative Deep Learning[END_REF] describing an attack against differentially private collaborative deep learning approaches (such as [START_REF] Shokri | Privacy-Preserving Deep Learning[END_REF]. They show how a malicious participant may actively train a Generative Adversarial Network (GAN) which is able to generate prototypical examples of a class held by another agent. While this does not violate DP, it can still constitute a privacy breach in applications where a class distribution itself is considered pri- vate. We believe that the key features of our approach, namely the fully decentralized architecture and the graph regularization over personal models, can significantly limit the effectiveness of the above attack. We leave a careful study of this question for future work.

5 Numerical Experiments

Linear Classification

We first conduct experiments on a linear classification task introduced by [START_REF] Vanhaesebrouck | Decentralized Collaborative Learning of Personalized Models over Networks[END_REF]. We briefly recall the setup. Consider a set of n = 100 agents. Each of these agents has a target linear separator in R p (unknown to the agent). The weight between two agents i and j is given by W ij = exp((cos(φ i,j ) -1)/γ), where φ i,j is the angle between the target models and γ = 0.1 (negligible weights are ignored). Each agent i receives a random number m i of training points (drawn uniformly between 10 and 100), where each point is drawn uniformly around the origin and labeled according to the target model. We then add some label noise, independently flipping each label with probability 0.05. We use the logistic loss (θ; x, y) = log(1+exp(-yθ T x)) (which is 1-Lipschitz), and the L2 regularization parameter of an agent i is set to λ i = 1/m i > 0 to ensure the overall strong con-vexity. The hyperparameter µ is tuned to maximize accuracy of the non-private algorithm on a validation set of random problems instances. For each agent, the test accuracy of a model is estimated on a separate sample of 100 points.

Non-private setting: CD vs ADMM. We start by comparing our Coordinate Descent (CD) algorithm to the ADMM algorithm proposed by [START_REF] Vanhaesebrouck | Decentralized Collaborative Learning of Personalized Models over Networks[END_REF] for the non-private setting. Both algorithms are fully decentralized and asynchronous, but our algorithm relies on broadcast (one-way communication from an agent to all neighbors) while the ADMM algorithm is gossip-based (two-way communication between a node and a random neighbor). Which communication model is the most efficient strongly depends on the network infrastructure, but we can meaningfully compare the algorithms by tracking the objective value and the test accuracy with respect to the number of iterations and the number of p-dimensional vectors transmitted along the edges of the network. Both algorithms are initialized using the purely local models, i.e. Θ i (0) = Θ loc i for all i ∈ n . Figure 1 shows the results (averaged over 5 runs) for dimension p = 100: our coordinate descent algorithm significantly outperforms ADMM despite the fact that ADMM makes several local gradient steps at each it-Purely local models Non-priv. CD Priv. ¯ = 1 Priv. ¯ = 0.5 Priv. ¯ = 0. eration (10 in this experiment). We believe that this is mostly due to the fact that the 4 auxiliary variables per edge needed by ADMM to encode smoothness constraints are updated only when the associated edge is activated. In contrast, our algorithm does not require auxiliary variables.

Private setting. In this experiment, each agent has the same overall privacy budget ¯ i = ¯ . It splits its privacy budget equally across T i = T /n iterations using Theorem 1 with δi = exp(-5), and stops updating when it is done. We first illustrate empirically the trade-offs implied by Theorem 2: namely that running more iterations per agent reduces the first term of the bound but increases the second term because more noise is added at each iteration. This behavior is easily seen in Figure 2(a), where Θ( 0) is initialized to a constant vector. In Figure 2(b), we have initialized the algorithm with a private warm start solution with = 0.05 (see supplementary material). The results confirm that for a modest additional privacy budget, a good warm start can lead to lower values of the objective with less iterations (as suggested again by Theorem 2). The gain in test accuracy here is significant.

Figure 2(c) shows results for problems of increasing difficulty (by varying the dimension p) with various privacy budgets. We have used the same private warm start strategy as in Figure 2(b), and the number of iterations per node was tuned based on a validation set of random problems instances. We see that even under a small privacy budget (¯ = 0.15), the resulting models significantly outperform the purely local models (a perfectly private baseline). As can be seen in the supplementary material, all agents (irrespective of their dataset size) get an improvement in test accuracy. This improvement is especially large for users with small local datasets, effectively correcting for the imbalance in dataset size. We also show that perturbing the data itself, a.k.a. local DP [START_REF] Duchi | Privacy Aware Learning[END_REF][START_REF] Kairouz | Extremal Mechanisms for Local Differential Privacy[END_REF], leads to very inaccurate models.

Recommendation Task

To illustrate our approach on real-world data, we use MovieLens-100K, 7 a popular benchmark dataset for recommendation systems which consists of 100,000 ratings given by n = 943 users over a set of n items = 1682 movies. In our setting, each user i corresponds to an agent who only has access to its own ratings 7 https://grouplens.org/datasets/movielens/100k/ r ij1 , . . . , r ijm i ∈ R, where j 1 , . . . , j mi denote the indices of movies rated by agent i. Note that there is a large imbalance across users: on average, a user has rated 106 movies but the standard deviation is large ( 100), leading to extreme values (min=20, max=737). For simplicity, we assume that a common feature representation φ j ∈ R p for each movie j ∈ n items is known a priori by all agents (p = 20 in our experiments). The goal of each agent i is to learn a model θ i ∈ R p such that θ T i φ j is a good estimate for the rating that i would give to movie j, as measured by the quadratic loss (θ; φ, r) = (θ T φ-r) 2 . This is a very simple model: we emphasize that our goal is not to obtain state-of-the-art results on this dataset but to show that our approach can be used to improve upon purely local models in a privacy-preserving manner. For each agent, we randomly sample 80% of its ratings to serve as training set and use the remaining 20% as test set. The network is obtained by setting W ij = 1 if agent i is within the 10-nearest neighbors of agent j (or vice versa) according to the cosine similarity between their training ratings, and W ij = 0 otherwise. Due to the lack of space, additional details on the experimental setup are deferred to the supplementary material.

Table 1 shows the test RMSE (averaged over users) for different strategies (for private versions, we use δi = exp(-5) as in the previous experiment). While the purely local models suffer from large error due to data scarcity, our approach can largely outperform this baseline in both the non-private and private settings.

Conclusion

We introduced and analyzed an efficient algorithm for personalized and peer-to-peer machine learning under privacy constraints. We argue that this problem is becoming more and more relevant as connected objects become ubiquitous. Further research is needed to address dynamic scenarios (agents join/leave during the execution, data is collected on-line, etc.). We will also explore the use of secure multiparty computation and homomorphic encryption as an alternative/complementary approach to DP in order to provide higher accuracy at the cost of more computation.

SUPPLEMENTARY MATERIAL

This supplementary material is organized as follows. Section A contains the proofs of the results in the main text. Section B provides further analysis of Theorem 2 for the case where the noise scales are uniform across iterations. Section C deals with the interesting special case of model propagation and its use as a private warm start strategy. Finally, Section D presents additional experimental results and details.

A Proofs

A.1 Proof of Theorem 1

We first show that for agent i and an iteration t i ∈ T i , the additional noise η i (t i ) provides ( i (t i ), 0)-differential privacy for the published Θ i (t i + 1). In the following, two datasets S 1 i and S 2 i are called neighbors if they differ in a single data point. We denote this neighboring relation by S 1 i ≈ S 2 i . We will need the following lemma.

Lemma 1. For two neighboring datasets S 1 i and S 2 i of the size m i :

∇L i (Θ i ; S 1 i ) -∇L i (Θ i ; S 2 i ) 1 ≤ 2 • L 0 m i .
Proof. Assume that instead of data point (x 1 , y 1 ) in S 1 i , there is (x 2 , y 2 ) in S 2 i . As S 1 i and S 2 i are neighboring datasets, the other data points in S 1 i and S 2 i are the same. Hence:

∇L i (Θ i ; S 1 i ) -∇L i (Θ i ; S 2 i ) 1 = 1 m i ∇ (Θ i ; x 1 , y 1 ) -∇ (Θ i ; x 2 , y 2 ) 1 ≤ 2 • L 0 m i ,
since the L 0 -Lipschitzness of (•; x, y) (with respect to the L 1 -norm) for all (x, y) ∈ X × Y implies that for any Θ i ∈ R p and (x, y) ∈ X × Y, we have ∇ (Θ i ; x, y) 1 ≤ L 0 .

We continue the proof by bounding the sensitivity of Θ i (t i + 1) to find the noise scale needed to satisfy ( , 0)differential privacy. Using Eq. 3, Eq. 4 and Lemma 1, we have:

sensitivity(Θ i (t i + 1)) = max S 1 i ≈S 2 i Θ i (t i + 1) 1 = max S 1 i ≈S 2 i 1 L i [∇Q L (Θ(t i ))] i 1 (7) = µc i D ii L i max S 1 i ≈S 2 i ∇L i (Θ i ; S 1 i ) -∇L i (Θ i ; S 2 i ) 1 (8) ≤ 2µc i D ii L 0 m i L i , (9)
where ( 7)-( 8) follow from the fact that [∇Q L (Θ(t i ))] i is the only quantity in the update (4) which depends on the local dataset of agent i.

Recalling the relation between sensitivity and the scale of the addition noise in the context of differential privacy [START_REF] Dwork | Calibrating Noise to Sensitivity in Private Data Analysis[END_REF], we should have:

i (t i ) • s * i ≥ sensitivity(Θ i (t i + 1)) = 2µc i D ii L 0 m i L i ,
where s * i is the scale of the noise added to Θ i (t i + 1). In the following we show that s * i ≥ 2µciDiiL0 miLi i(ti) . To compute s * i , we see how the noise η i (t i ) affects Θ i (t i + 1). Using Eq. 6, definitions of α (Update step page 3) and L i (the block Lipschitz constant) we have:

Θ i (t i + 1) = (1 -α)Θ i (t) + α j∈Ni W ij D ii Θ j (t) -µc i (∇L i (Θ i (t); S i ) + η i (t)) = (1 -α)Θ i (t) + α j∈Ni W ij D ii Θ j (t) -µc i ∇L i (Θ i (t); S i ) -αµc i η i (t) = Θ i (t i + 1) - µc i η i (t) 1 + µc i L loc i = Θ i (t i + 1) - µc i D ii L i • η i (t i ).
So the scale of the noise added to Θ i (t i + 1) is:

s * i = µc i D ii L i • s i (t i ) = µc i D ii L i • 2L 0 i (t i )m i = 2µc i D ii L 0 i (t i )m i L i . Therefore, s * i ≥ sensitivity(Θi(ti+1)) i(ti)
is satisfied, hence publishing Θ i (t i + 1) is ( i (t i ), 0)-differentially private.

We have shown that at any iteration t i ∈ T i , publishing Θ i (t i + 1) by agent i is ( i (t i ), 0) differentially private.

The mechanism M i published all Θ i (t i + 1) for t i ∈ T i . Using the composition result for differential privacy established by [START_REF] Kairouz | The Composition Theorem for Differential Privacy[END_REF], we have that the mechanism M i (S i ) is (¯ i , δi )-DP with ¯ i , δi as in Theorem 1.

Theorem 1 considers the case where (•; x, y) is L 0 -Lipschitz for all (x, y) ∈ X × Y with respect to the L 1 -norm.

We could instead assume Lipschitzness with respect to the L 2 -norm, in which case the noise to add should be Gaussian instead of Laplace. The following remark computes the additional normal noise to preserve differential privacy in this setting.

Remark 4. Let i ∈ n . In the case where (•; x, y) is L * 0 -Lipschitz with respect to the L 2 -norm for all (x, y) ∈ X × Y, for any t i ∈ T i , let s i (t i ) ≥ 2L * 0 2 ln(2/δ i (t i ))/ i (t i ) for some i (t i ) > 0 and δ i (t i ) ∈ [0, 1]. For the noise vector η i (t) drawn from a Gaussian distribution N (0, s i (t)) p ∈ R p with scale s i (t i ), and for any δi ∈ [0, 1] and initial point Θ(0) ∈ R np independent of S i , the mechanism

M i (S i ) is (¯ i , 1 -(1 -δi ) Ti ti=1 (1 -δ i (t i )))-DP with ¯ i = min Ti ti=1 i (t i ), Ti ti=1 (e i(ti) -1) i (t i ) e i(ti) + 1 + Ti ti=1 2 i (t i ) 2 log e + Ti ti=1 i (t i ) 2 δi , Ti ti=1 (e i(ti) -1) i (t i ) e i(ti) + 1 + Ti ti=1 2 i (t i ) 2 log(1/ δi ) .

A.2 Proof of Theorem 2

We start by introducing a convenient lemma.

Lemma 2. For any i ∈ [n], Θ ∈ R np and d ∈ R p we have:

Q L (Θ + U i d) ≤ Q L (Θ) + d T [∇Q L (Θ)] i + L i 2 d 2 .
Proof. We get this by applying Taylor's inequality to the function

q x Θ : R p → R d → Q L (Θ + U i d).
Recall that the random variable η i (t) ∈ R p represents the noise added by agent i ∈ n due to privacy requirements if it wakes up at iteration t ≥ 0. To simplify notations we denote the scaled version of the noise by η i (t) = µD ii c i η i (t).

Let i t be the agent waking up at iteration t. Using Lemma 2, we have:

Q L ( Θ(t + 1)) = Q L Θ(t) - U it L it [∇Q L ( Θ(t))] it + η it (t) ≤ Q L ( Θ(t)) - 1 L it [∇Q L ( Θ(t))] T it [∇Q L ( Θ(t))] it + η it (t) + 1 2L it [∇Q L ( Θ(t))] it + η it (t) 2 = Q L ( Θ(t)) - 1 L it [∇Q L ( Θ(t))] it 2 + 1 2L it [∇Q L ( Θ(t))] it 2 + 1 2L it η it (t) 2 ≤ Q L ( Θ(t)) - 1 2L max [∇Q L ( Θ(t))] it 2 + 1 2L min η it (t) 2 ,
where L min = min 1≤i≤n L i .

Recall that under our Poisson clock assumption, each agent is equally likely to wake up at any step t. Subtracting Q * L and taking the expectation with respect to i t on both sides, we thus get:

E it [Q L ( Θ(t + 1))] -Q * L ≤ Q L ( Θ(t)) -Q * L - 1 2L max 1 n n j=1 [∇Q L ( Θ(t))] j 2 + 1 2L min 1 n n j=1 η j (t) 2 = Q L ( Θ(t)) -Q * L - 1 2nL max ∇Q L ( Θ(t)) 2 + 1 2nL min η(t) 2 , (10)
where

η(t) = [ η 1 (t); . . . , ; η n (t)] ∈ R np .
For convenience, let us define

P t = E[Q L ( Θ(t))] -Q * L where E[•]
denotes the expectation with respect to all variables {i t } t≥0 and {η(t)} t≥0 . Using (10) we thus have:

P t+1 ≤ P t - 1 2nL max E[ ∇Q L ( Θ(t)) 2 ] + 1 2nL min E[ η(t) 2 ] (11)
Recall that Q L is σ-strongly convex, i.e. for any Θ, Θ ∈ R np we have:

Q L (Θ ) ≥ Q L (Θ) + ∇Q L (Θ) T (Θ -Θ) + σ 2 Θ -Θ 2 2 .
We minimize the above inequality on both sides with respect to Θ . We obtain that Θ = Θ * minimizes the left-hand side, while Θ = Θ -∇Q L (Θ)/σ. We thus have for any Θ:

Q * L ≥ Q L (Θ) - 1 σ ∇Q L (Θ) T ∇Q L (Θ) + 1 2σ ∇Q L (Θ) 2 2 = Q L (Θ) - 1 2σ ∇Q L (Θ) 2 .
Using the above inequality to bound ∇Q L ( Θ(t)) 2 in (11), we obtain:

P t+1 ≤ P t - σ nL max P t + 1 2nL min E[ η(t) 2 ] = 1 - σ nL max P t + 1 2nL min E[ η(t) 2 ].
A simple recursion on P t gives:

P t ≤ 1 - σ nL max t P 0 + 1 2nL min t-1 t =0 1 - σ nL max t E[ η(t ) 2 ]. ( 12
)
For any t ≥ 0 and i ∈ n , the entries of η i (t) are drawn from independent Laplace distributions with mean 0 and scale s i (t), hence we have:

E[ η(t) 2 ] = E n i=1 µD ii c i η i (t) 2 = n i=1 2(µD ii c i s i (t)) 2 .
This concludes the proof.

A.3 Proof of Proposition 2

We start the proof with the following lemma.

Lemma 3. Let C = 1 -σ/nL max . Assume that for any i ∈ n , we have s i (t i ) = 2L0 i(ti)mi for t i ∈ T i as in Theorem 1. Given a total number of iterations T and the overall privacy budgets ¯ 1 , . . . , ¯ n > 0 of each agent, the following privacy parameters minimize the utility loss:

* i (t) = 3 √ C -1 3 √ C T -1 3 √ C t ¯ i , ∀i ∈ n , 0 ≤ t ≤ T -1. Proof. Denote A i = µciDiiL0 mi .
As the first part of the upper-bound of the utility loss in Theorem 2 does not depend on the i (t)'s, we need to find the i (t)'s which minimize the following quantity:

min T -1 t=0 n i=1 1 - σ nL max t µc i D ii s i (t) 2 = min T -1 t=0 n i=1 1 - σ nL max t 2µc i D ii L 0 i (t i )m i 2 = min T -1 t=0 C t n i=1 A 2 i 2 i (t) = min n i=1 T -1 t=0 A 2 i C t 2 i (t) , (13)
under the constraints: ∀i, i (t) ≥ 0 and

T -1 t=0 i (t) = ¯ i .
As the agents are independent, we can solve the above optimization problem separately for each agent i to minimize

T -1 t=0 A 2 i C t ( i(t)) 2 under the constraint T -1 t=0 i (t) = ¯ i . Denote i (t) = x it . We have x i0 = ¯ i - T -1 t=1 x it .
Replacing x i0 in the objective function of Eq. 13, we can write the objective function as follows:

∀i : F i (x i1 , • • • , x iT -1 ) = A 2 i (¯ i - T -1 t=1 x it ) 2 + T -1 t=1 A 2 i C t x 2 it .
The problem is thus equivalent to finding min F i (x i1 , • • • , x it-1 ) ∀i under the previous constraints. To find the optimal x it we find set its partial derivative ∂Fi ∂xit to 0:

∂F i ∂x it = -2A 2 i C t x 3 it + 2A 2 i (¯ i - T -1 t=1 x it ) 3 = 0.
Hence the value of x it satisfies:

∀t ∈ [1 : T -1] : x it = 3 √ C t ¯ i - T -1 j=1 x ij . ( 14
)
For a fixed i, after summing up all x it s, we get:

T -1 j=1 x ij = T -1 j=1 3 √ C j ¯ i - T -1 j=1 x ij = 3 √ C T -3 √ C 3 √ C -1 ¯ i - T -1 j=1 x ij .
And hence:

x i0 = ¯ i - T -1 j=1 x ij = 3 √ C -1 3 √ C T -1 ¯ i .
Using Eq. 14, we thus finally get:

∀i, t : * i (t) = 3 √ C -1 3 √ C T -1 3 √ C t ¯ i
The noise allocation strategy given by the above lemma optimizes the utility loss, which is an expectation with respect to the clock ticks. Hence * i (t) gives the amount of noise that an agent should add in expectation at a given global iteration t. Note that we have T -1 t=0 * i (t) = ¯ i , hence the budget is matched exactly in expectation. For a particular run of the algorithm however, each agent i only wakes up at a subset T i of all iterations and only uses its privacy budget at these iterations t ∈ T i . Thus, for a single run, the above strategy does not use up the entire privacy budget ¯ i .

If we instead condition on a particular schedule, i.e. each agent i knows T i in advance, we can appropriately renormalize the privacy parameters to make sure that the agents truly utilize their entire privacy budget. The overall privacy parameter for agent i with optimal noise allocation as in Lemma 3 given T i is as follows:

t∈Ti * i (t) = λ Ti (i) • ¯ i . Hence we can set t∈Ti i (t) = t∈Ti * i (t) λ Ti (i) = ¯ i .
This shows that the privacy parameters defined in Proposition 2 fulfills the overall privacy budget of an agent i during the iterations that agent i wakes up. Furthermore, for * i (t) defined in Lemma 3,

T -1 t=0 * i (t) = ¯ i ∀i ∈ n .
We then conclude that λ Ti (i) ≤ 1 as T i ⊆ T . The additional noise to provide i (t) differential privacy (as in Proposition 3) is thus lower than the additional noise to provide * i (t) differential privacy in Lemma 3.

B Further Analysis of Theorem 2

We further analyze the utility/privacy trade-off of Theorem 2 in the special case where the noise scales are uniform across iterations, i.e. s i (t) = s i for all t and i. Let us denote

a = 1 nL min n i=1 (µD ii c i s i ) 2 , b = Q L (Θ(0)) -Q * L , ρ = σ nL max .
The additive error due to the noise is a sum of a geometric series and thus simplifies to

T -1 t=0 a(1 -ρ) t = a 1 -(1 -ρ) T ρ .
Hence we can write the inequality of Theorem 2 as

E [Q L (Θ(T )) -Q L ] ≤ b(1 -ρ) T optimization error + a ρ 1 -(1 -ρ) T noise error
.

The optimization error after T iterations thus decomposes into two terms: an optimization error term (which is the same quantity that one gets in the non-private setting) and a noise error term due to privacy. One can see that if the algorithm is run until convergence (T → ∞), the (additive) utility loss due to privacy is given by

a ρ = L max σL min n i=1 (µD ii c i s i ) 2 .
However, this additive loss due to noise can actually be smaller than a ρ for T < ∞. Indeed, increasing T from 0 to ∞ makes the noise error go from 0 to a ρ , but also drives the optimization error from b to 0. This suggests that the number of iterations T can be used to minimize the overall error and should be carefully tuned. This is confirmed by our numerical experiments in Figures 2(a)-2(b).

C Propagation of (Private) Local Models

In this section, we give some details on an interesting special case of our framework. The idea is to smooth models that are pre-trained locally by each agent. Formally, the objective function to minimize is as follows:

Q MP (Θ) = 1 2 n i<j W ij Θ i -Θ j 2 + µ n i=1 D ii c i Θ i -Θ loc i 2 , (15)
which is a special case of (2) when we set

L i (Θ i ; S i ) = 1 2 Θ i -Θ loc i 2 with Θ loc i ∈ arg min θ∈R p mi j=1 (θ; x j i , y j i ) + λ i θ 2 . Each L i is 1-strongly convex in Θ i with 1-Lipschitz continuous gradient, hence we have L i = D ii (1 + µc i ) and σ ≥ µ min 1≤i≤n [D ii c i ].
Developing the update step (4) for this special case, we get:

Θ i (t + 1) = 1 1 + µc i j∈Ni W ij D ii Θ j (t) + µc i Θ loc i . ( 16
)
Because the objective function ( 15) is quadratic and separable along the p dimensions, ( 16) corresponds to the exact minimizer of Q MP along the block coordinate direction Θ i . Hence Θ i (t + 1) does not depend on Θ i (t), but only on the solitary and neighboring models.

It turns out that we recover the update rule proposed specifically by [START_REF] Vanhaesebrouck | Decentralized Collaborative Learning of Personalized Models over Networks[END_REF] for model propagation. Our block coordinate algorithm thus generalizes their approach to general local loss functions and allows to obtain convergence rate instead of only asymptotic convergence.

Private setting In the above objective, the interaction with each local dataset S i is only through the pretrained model Θ loc i learned by minimizing the (regularized) empirical risk as denoted in (1). Therefore, if we generate a DP version Θ loc i of Θ loc i , we can run the non-private coordinate descent algorithm (16) using Θ loc i instead of Θ loc i without degrading the privacy guarantee. We can thus avoid the dependency on the number of iterations of the coordinate descent algorithm. Several well-documented methods for an agent to generate a DP version of its local model Θ loc i exist in the literature, under mild assumptions on the loss function and regularizer. One may for instance use output or objective perturbation [START_REF] Chaudhuri | Differentially Private Empirical Risk Minimization[END_REF].

Recall that Theorem 2 emphasizes that it is beneficial to have a good warm start point Θ(0) for the general algorithm: the smaller Q L (Θ(0)) -Q L , the less iterations needed to decrease the optimization error to the desired precision and hence the less noise added due to privacy. However, to ensure the overall privacy of the algorithm, Θ(0) must be also be differentially private. In light of the discussion above, we can use the private model propagation solution as a good private warm start.

D Additional Experimental Results and Details

D.1 Linear classification

We present here some additional experimental results on the linear classification task to complement those displayed in the main text.

Test accuracy w.r.t. size of local dataset Figure 3 shows the test accuracy of our algorithm under different private regimes depending on the size of the local dataset of an agent. First, we can see that all agents (irrespective of their dataset size) benefit from private collaborative learning, in the sense that their final accuracy is larger than that of their purely local model. This is important as it gives an incentive to all agents (including those with larger datasets) to collaborate. Second, the algorithm effectively corrects for the imbalance in dataset size: agents with less data generally get a larger boost in accuracy and can almost catch up with better-endowed agents (which also get an improvement, albeit smaller).

Local Differential Privacy baseline As mentioned in Section 4, local Differential Privacy [START_REF] Duchi | Privacy Aware Learning[END_REF][START_REF] Kairouz | Extremal Mechanisms for Local Differential Privacy[END_REF] consists in adding noise to each data point itself (proportional to the sensitivity of its features) so that the resulting perturbed point does not reveal too much about the original point. Local DP can be used trivially in the distributed/decentralized setting as it is purely local. However it is also a very conservative approach as it is agnostic to the type of analysis done on the data (the perturbed dataset can be released publicly). Figure 4 shows the accuracy of purely local models learned after applying ( , 0)-local DP to each local dataset. As expected, the loss in accuracy compared to purely local models learned from unperturbed data is huge. We were not able to improve significantly over these models by applying our collaborative learning algorithm on the perturbed data, confirming that it contains mostly random noise. This confirms the relevance of our private algorithm based on perturbing the updates rather than the data itself.

D.2 Recommendation Task

We provide here some details on our experimental setup for MovieLens-100K:

• Normalization: Following standard practice, we normalize the data user-wise by subtracting from each rating the average rating of the associated user.

• Movie features: In principle, for privacy reasons, the features should be computed independently of the training data (e.g., computed from a separate set of user ratings, or descriptive features obtained from IMDB). For convenience, we simply use the movie features generated by a classic alternating least square method for collaborative filtering [START_REF] Zhou | Large-Scale Parallel Collaborative Filtering for the Netflix Prize[END_REF] applied to our training set (i.e., random 80% of the ratings). We set the feature dimensionality p to 20 as it is typically enough to reach good performance on MovieLens-100K.

• Lipschitz constant: One can bound the Lipschitz constant of the quadratic loss by assuming a bound on the norm of model parameters and movie features. However, this often results in overestimating the Lipschitz constant and hence in an unnecessarily large scale for the added noise used to enforce differential privacy. In such cases it is easier to clip the norm of all point-wise gradients when they exceed a constant C (see for instance [START_REF] Abadi | Deep Learning with Differential Privacy[END_REF]. This ensures that (9) holds (replacing L 0 by C). We set C = 10, which is large enough that gradients are almost never clipped in practice.

• Hyperparameters: We simply set the L2 regularization parameter of each agent i to λ i = 1/m i , and use µ = 0.04 as in the previous synthetic experiment. For our private algorithm, the number of iterations per node is tuned for each value of ¯ on a validation set (obtained by a 80/20 random split of the training set of each agent).

Figure 1 :

 1 Figure 1: Our Coordinate Descent (CD) algorithm compared to the existing ADMM algorithm.

Figure 2 :

 2 Figure 2: Linear classification results in the private setting (averaged over 5 runs). (a)-(b) Evolution of the objective and test accuracy along the iterations for two types of initialization (p = 100). (c) Final test accuracy for different dimensions and several privacy regimes. Best seen in color.

Figure 3 :

 3 Figure 3: Final test accuracy (averaged over 5 runs) per local dataset size for dimension p = 100 and several privacy regimes for our private and non-private coordinate descent algorithms. Agents with small datasets get larger improvements. Best seen in color.

Figure 4 :

 4 Figure 4: Test accuracy (averaged over 5 runs) of purely local models learned from perturbed data (local DP) w.r.t. to data dimension, for different privacy regimes. Best seen in color.

Table 1 :

 1 Per-user test RMSE (averaged over users and 5 random runs) on MovieLens-100K.

	1

In practice we will set ci = mi/ maxj mj (plus some small constant when mi = 0).

This follows from the fact that the first term in (2) is a Laplacian quadratic form, hence convex in Θ.

This second property is in contrast to a (centralized) gradient descent approach which would use the same constant, more conservative step size (equal to the standard Lipschitz constant of QL) for all agents.

We assume a honest-but-curious model for the agents: they want to learn as much as possible from the information that they receive but they truthfully follow the protocol.

Acknowledgments. This work was partially supported by grant ANR-16-CE23-0016-01, by a grant from CPER Nord-Pas de Calais/FEDER DATA Advanced data science and technologies 2015-2020 and by European ERC Grant 339539 -AOC.