MSc Margot Ferrand

MSc Alexis Ruffault

MSc Xavier Tytelman

PhD Cécile Flahault

PhD Vélina Négovanska

A Cognitive and Virtual Reality Treatment Program for the Fear of Flying

Keywords: flight phobia, anxiety, pluridisciplinary program

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Background

Since the beginning of the 1960's, passenger air transport has considerably increased [START_REF] Van Gerwen | International Summer School on Aviation Psychology[END_REF]. The airplane has become the most common way of transporting individuals across industrialized countries during the past decades. The International Air Transport Association (IATA) has published the figure of more than 3 billion passengers having been transported in 2013. The Association predicts an increase of 31 % in the number of passengers between 2012 and 2017 and that the figure of 4 billion individuals transported each year will soon be exceeded.

Despite the common idea of the airplane being the safest way to travel [START_REF]Transports : secteur aérien [Site gouvernemental[END_REF][START_REF]Bilan annuel de la sécurité routière en France [Site gouvernemental[END_REF][START_REF]The most common causes of death due to injury in the United States[END_REF], a lot of individuals remain scared of flying, and some are even afraid at the sight of an airplane. In Western countries, among individuals who suffer from a fear of flying, 14 % have never flown, 6 % say that they do not want to fly again, and 10 % take a plane only when they do not have any other choice. In Europe, more than 20 % of individuals argue that they have difficulties in taking the plane because of their fear of flying [START_REF] Van Gerwen | International Summer School on Aviation Psychology[END_REF]. According to several studies, between 7 and 40 % of the general population in industrialized countries suffer from the fear of flying (with all anxiety disorder comorbidities taken into account) [START_REF] Oakes | The psychology of fear of flying (part I): A critical evaluation of current perspectives on the nature, prevalence and etiology of fear of flying[END_REF][START_REF] Van Gerwen | People who seek help for fear of flying: Typology of flying phobics[END_REF].

The Diagnostic and Statistical Manual of mental disorders (DSM-IV-TR) defines a phobia as a "marked and persistent fear that is excessive or unreasonable, cued by the presence or anticipation of a specific object or situation" (p.210) [START_REF]American Psychiatric Association. Diagnostic and Statistical Manual of Mental Disorders, Fourth Edition, Text Revision (DSM-IV-TR)[END_REF]. Fear of flying, classified in the situational type of phobia, answers each of the characteristics of phobia as mentioned above: it is an excessive fear, cued by the presence of an airplane or the anticipation of any situation linked to it (e.g., going to the airport, buying the tickets, ideas of a crash), and exposure to airplanes provokes an immediate anxiety response (which can become a panic attack). The fear of flying could also be the expression of other subtypes of phobia. Thus, 50 to 80 % of individuals suffering from a fear of flying could present comorbidities [START_REF] Medialdea | Phobic fear of flying in aircrews: epidemiological aspects and comorbidity[END_REF][START_REF] Oakes | The psychology of fear of flying (part I): A critical evaluation of current perspectives on the nature, prevalence and etiology of fear of flying[END_REF][START_REF] Van Gerwen | Personality pathology and cognitive-behavioral treatment of fear of flying[END_REF]. Fear of flying is unique because it contains "classical" elements of the fear of flying (e.g., related to the airplane: fear of crash, turbulence, sounds, take off), but may also include other specific phobias such as claustrophobia, fear of heights, or aquaphobia. The etiology of the fear of flying seems to be multifactorial [START_REF] Nousi | The Flight Anxiety Situations Questionnaire and the Flight Anxiety Modality Questionnaire: Norms for people with fear of flying[END_REF][START_REF] Oakes | The psychology of fear of flying (part I): A critical evaluation of current perspectives on the nature, prevalence and etiology of fear of flying[END_REF][START_REF] Van Gerwen | People who seek help for fear of flying: Typology of flying phobics[END_REF]: factors stemming from the individual (e.g., psychiatric comorbidities, sensitivity of the vestibular system, bad flight experiences, lack of information), social factors (e.g., where the fear occurs by the observation of family or peers), and environmental factors (e.g., media reporting and reinforcement of erroneous beliefs, movies, TV shows, and plane crashes). In a study from Schindler and colleagues [START_REF] Oakes | The psychology of fear of flying (part I): A critical evaluation of current perspectives on the nature, prevalence and etiology of fear of flying[END_REF], 70 % of the subjects reported that the information broadcast in the media strongly influenced their apprehensions and fear of flying.

The fear of flying is mostly the concern of industrialized countries (e.g., it represents an economic loss in terms of the sales of airline tickets). It involves a relatively large part of the general population, and impacts different spheres of the personal, social, and/or professional life of individuals [START_REF] Oakes | The psychology of fear of flying (part I): A critical evaluation of current perspectives on the nature, prevalence and etiology of fear of flying[END_REF][START_REF] Saadat | Non-Pharmacologic Treatments for Fear of Flying[END_REF]. Several treatment programs have been developed in order to address this issue [START_REF] Van Gerwen | Fear of flying treatment programs for passengers: an international update[END_REF]. Today, these programs have multiplied but their comparative effectiveness has been studied only in a limited way. Even if they do offer different types of interventions, they rarely take into account the co-morbid nature of fear of flying. The proposed interventions can be in a single or a group design, and their duration varies from a single day to several weeks. The monitoring of patients is not always assured after the interventions, and the programs contain a combination of different cognitive-behavioral techniques such as psychoeducation, exposure, and respiration training. To cite a few examples, there is Air France's "Apprivoiser l'avion" program, the VALK program in the Netherlands, "VisionAir" in Canada, "Fit to Fly" by Swiss Air, and "SOAR" in the USA.

In most cases these programs are developed either by airlines or pilots, and the intervention of a health care professional is not always present. This can be a disadvantage since the clinical complexity of fear of flying with co-morbid mental health conditions could benefit from the assistance of a trained mental health provider.

There are studies that have measured the efficacy of treatment programs of the fear of flying, some with control groups [START_REF] Krijn | Fear of flying treatment methods: virtual reality exposure vs. cognitive behavioral therapy[END_REF][START_REF] Rothbaum | Twelve-month follow-up of virtual reality and standard exposure therapies for the fear of flying[END_REF][START_REF] Van Gerwen | Behavioral and cognitive group treatment for fear of flying: A randomized controlled trial[END_REF]. Other studies aim to measure the effectiveness of certain techniques of the whole program (e.g., exposure and the use of other cognitivebehavioral techniques), or to compare the programs two-by-two [START_REF] Oakes | The psychology of fear of flying (part II): A critical evaluation of current perspectives on approaches to treatment[END_REF][START_REF] Van Gerwen | Behavioral and cognitive group treatment for fear of flying: A randomized controlled trial[END_REF][START_REF] Wiederhold | Three-Year Follow-Up for Virtual Reality Exposure for Fear of Flying[END_REF]. It seems to be essential to focus on the techniques that are used in the programs in order to know whether these techniques are suitable for the fear of flying. These first studies allowed for the promotion of guidelines for the treatment of the fear of flying [START_REF] Nousi | The Flight Anxiety Situations Questionnaire and the Flight Anxiety Modality Questionnaire: Norms for people with fear of flying[END_REF][START_REF] Oakes | The psychology of fear of flying (part II): A critical evaluation of current perspectives on approaches to treatment[END_REF][START_REF] Van Gerwen | Fear of flying treatment programs for passengers: an international update[END_REF]. Our study looks at how effective a defined program of strategies changes symptoms from before to immediately after treatment.

To optimize the treatment and monitoring of the patients, the most important issue appears to be the evaluation of anxiety related to the fear of flying instead of the proof of a specific intervention's effectiveness. The aim of this study is to assess a treatment program that follows the international guidelines highlighted by Van Gerwen and colleagues [START_REF] Oakes | The psychology of fear of flying (part II): A critical evaluation of current perspectives on approaches to treatment[END_REF][START_REF] Van Gerwen | Fear of flying treatment programs for passengers: an international update[END_REF][START_REF] Van Gerwen | Behavioral and cognitive group treatment for fear of flying: A randomized controlled trial[END_REF], and Da Costa and colleagues [START_REF] Costa | Virtual Reality Exposure in the Treatment of Fear of Flying[END_REF]. We will consider the "Prêt à décoller" (i.e., ready to take off) program in Paris. In this initial study, we compare specific anxiety levels before the intervention and after the first flight following the intervention. We hypothesize that this 1day program will allow subjects to reduce their anxiety-related fear of flying after their first flight following the program when compared to their anxiety-related fear of flying before the program.

Methods

Subjects.

A total of 157 individuals gave their signed agreement to participate in this study and filled out the questionnaires before the program (baseline) and after their first flight following the intervention (follow-up). The questionnaires were filled out between September 2013 and May 2014. The inclusion criteria for the participation were: having an email address, an internet access at home or at work, taking a flight after attending the program, and filling out the questionnaire at baseline and follow-up. The subjects were systematically recruited among the patients attending the program, and no exclusion criteria have been defined. Twelve individuals have been excluded from statistical analyses due to missing data in their questionnaires. Finally, one hundred and forty five subjects (69.7% females) aged from 14 to 64 years old (M = 37; SD = 11) were enrolled in this study.

Procedure.

The subjects completed a 1-hour phone interview with one of the professionals prior to their participation in the program, which screened for a diagnosis (i.e., type of fear, comorbidities, previous psychotherapeutic attempts). The subjects then received an email confirming their inclusion in the program. Four days before the 1-day intervention, subjects received another email with a link to fill out the questionnaires (baseline): the QEPA (i.e., Questionnaire d'Evaluation de la Peur de l'Avion) composed with the Flight Anxiety Situations (FAS) and the Flight Anxiety Modality (FAM) in their French version [START_REF] Van Gerwen | Construction and psychometric characteristics of two self-report questionnaires for the assessment of fear of flying[END_REF]. The subjects informed the professionals about the date of their next flight, following the intervention, by phone, email, or the day of the intervention so that we could send them the QEPA on time. The QEPA is filled out before the 1-day intervention (baseline) and after the first flight following the intervention (follow-up). If the subjects wanted more information, had questions about their flight, or needed psychological support before their flight, they could contact the professionals by phone or email. In case of comorbidities, the subjects could have a face-to-face interview with one of the professionals. Professionals and subjects were not blinded to the study hypotheses and aims. They knew that the intervention's purpose was to treat their fear of flying, and that its efficacy was measured. All the subjects were informed of their answers' use for this research and completed a signed consent to participate. Institutional ethical approval was sought and given to conduct this study.

Intervention.

The Centre de Traitement de la Peur de l'Avion (CTPA) (i.e., Fear of Flying Treatment Centre) is a psychology practice specialized in the treatment of the fear of flying. A Cognitive-Behavioral Therapy (CBT) psychologist conducted the 1-day intervention (the first and last authors, MF and VN) in association with an instructor in aviation and aviation safety expert (the second author, XT) and two professional pilots with experience working with anxious individuals. The intervention follows the international guidelines provided in this field: the combination of CBT techniques, information about aviation safety, and virtualreality exposure [START_REF] Costa | Virtual Reality Exposure in the Treatment of Fear of Flying[END_REF][START_REF] Trimmel | Treatment of Fear of Flying: Behavioral, Subjective, and Cardiovascular Effects[END_REF][START_REF] Van Gerwen | Behavioral and cognitive group treatment for fear of flying: A randomized controlled trial[END_REF]. The price of the treatment program is 430 euros for one day with up to 9 subjects.

Firstly, the CBT-trained psychologist informed the subjects about the etiology, the predisposal factors, the treatment methods, and the management of the anxiety linked to the fear of flying. These components, from the CBT techniques, are known to be more effective than a simple behavioral support [START_REF] Van Gerwen | Behavioral and cognitive group treatment for fear of flying: A randomized controlled trial[END_REF]. The management of the anxiety related to the fear of flying was taught with relaxation and respiration techniques, using the Symbiofi® cardiac coherence software [START_REF] Trimmel | Treatment of Fear of Flying: Behavioral, Subjective, and Cardiovascular Effects[END_REF]. Studies suggest that a cardiac coherence software including biofeedback increases the efficacy of the treatment from 80 to 100 % [START_REF] Wiederhold | The treatment of fear of flying: a controlled study of imaginal and virtual reality graded exposure therapy[END_REF]. Moreover, the effects seem to be maintained up to 3 years after the intervention [START_REF] Wiederhold | Three-Year Follow-Up for Virtual Reality Exposure for Fear of Flying[END_REF].

Secondly, the instructor in aviation and aviation safety expert taught the subjects about the planes' safety and functioning (e.g., turbulence, resistance, meteorological disturbances, management of mechanical failures). The pilots answered questions regarding the subjects' concerns during this second phase.

Thirdly, the intervention ended with a flight in a fixed simulator, where the subjects could pilot a Boeing 737 with one of the pilots. For the treatment of the fear of flying, the use of a non-moving simulator appears to be as effective as a real flight, and a moving simulator [START_REF] Boyd | Potential Utility of Full Motion Flight Simulators for Treatment of Individuals with a Fear of Flying[END_REF][START_REF] Rothbaum | Virtual Reality Exposure Therapy and Standard (in Vivo) Exposure Therapy in the Treatment of Fear of Flying[END_REF][START_REF] Rothbaum | Twelve-month follow-up of virtual reality and standard exposure therapies for the fear of flying[END_REF].

The intervention that each patient participated in was exactly the same: with the same professionals at the same location and the same content.

Equipment.

Anxiety was assessed with the FAS and the FAM questionnaires [START_REF] Van Gerwen | Construction and psychometric characteristics of two self-report questionnaires for the assessment of fear of flying[END_REF] in their French version. The detailed questionnaires' reliabilities for each subscale are displayed in Table I. The psychometric characteristics of the scales and subscales have been shown to be excellent in our sample [START_REF] Van Gerwen | Construction and psychometric characteristics of two self-report questionnaires for the assessment of fear of flying[END_REF].

The FAS questionnaire is a self-reported outcome composed of 32 items measuring the levels of anxiety in several situations related to the flight experience on a 5-point Likert scale (ranging from 1 "no anxiety" to 5 "overwhelming anxiety"). The FAS questionnaire is divided between 3 subscales: The FAM questionnaire is a self-reported outcome that contains 18 items assessing the anxiety symptoms related to the flight on a 5-point Likert scale (ranging from 1 "not at all" to 5 "very intensely"). The FAM questionnaire separates 2 types of symptoms displayed in 2 subscales: (1) the somatic modality (assessing the expression of physical symptoms of anxiety) composed of 11 items (minimum possible score = 11; maximum possible score = 55), and (2) the cognitive modality (reporting the presence of disturbing or negative thoughts) that contains 7 items (minimum possible score = 7; maximum possible score = 35).

Statistical analysis.

The data were analyzed using SPSS [5] after the exclusion of the subjects with missing data (n = 12). We compared the mean scores, for each subscale, between baseline and followup assessments with Student t-test at a 0.5% significance threshold. Effect sizes were calculated using Cohen's d coefficient [START_REF] Cohen | Statistical power analysis for the behavioral sciences[END_REF].

Results

We compared the means of each subscale of the FAS and FAM questionnaires between baseline and follow-up (see Table II). Statistical analyses showed a positive and significant effect for each subscale between the two assessment times (all p's < .001). Thus, the specific anxiety scores decreased after the first flight following the intervention, as compared to baseline scores. The scores of the GFA subscale of the FAS questionnaire (t(144) = 28.444; p < .001), the AFA subscale of the FAS questionnaire (t(144) = 14.852; p < .001), the IFA subscale of the FAS questionnaire (t(144) = 9.117; p < .001), the somatic modality of the FAM questionnaire (t(144) = 27.068; p < .001), and the cognitive modality of the FAM questionnaire (t(144) = 12.579; p < .001), decreased between baseline and follow-up.

Moreover, the effect size of the IFA subscale was large (d = 1.04), while the effect sizes of the GFA subscale (d = 3.20), the AFA subscale (d = 1.74), the somatic modality (d = 2.44), and the cognitive modality (d = 1.47) were very large [START_REF] Cohen | Statistical power analysis for the behavioral sciences[END_REF].

Discussion

The aim of this study was to test the efficacy of a treatment program for the fear of flying, hypothesizing that the specific anxiety levels would decrease between the baseline and follow up assessments. The program followed the international guidelines highlighted in previous studies in this field [START_REF] Oakes | The psychology of fear of flying (part II): A critical evaluation of current perspectives on approaches to treatment[END_REF][START_REF] Van Gerwen | Fear of flying treatment programs for passengers: an international update[END_REF].

The results are in line with our main hypothesis, thus they showed a positive significant effect for each subscale of anxiety related to the fear of flying between baseline and follow up measures with large to very large effect sizes. Therefore generalized flight anxiety (e.g., seeing a plane, hearing the sound of an airplane), anticipatory flight anxiety (e.g., decision to take a flight, buying tickets, driving to the airport), and in-flight anxiety (e.g., feeling turbulences, hearing the engine's sounds) decreased after the first flight following the 1-day intervention. Moreover, physical symptoms of anxiety (e.g., sweating, feeling one's heartbeat) and the cognitive symptoms of anxiety (e.g., negative thoughts, anticipating something going wrong, being afraid of dying) before and during the flight were better controlled by the subjects, and were less intense. This evolution allows us to conclude that the subjects were less anxious about flying after their first flight following the intervention than before attending the program. No differences have been shown between male and female subjects.

These results confirm the success of our treatment programs which combats fear of flying by utilizing three strategies: psychoeducation, CBT techniques, and exposure. By associating these three components, we find that the program's effectiveness is optimal and that anxiety decreases significantly after the intervention. Furthermore, our results suggest a benefit from utilizing trained professionals in these interventions, meaning that CBT-trained psychologists and aviation experts (i.e., aviation safety experts and pilots) may be a central pillar of successful treatment results.

Even if the results show the efficacy of the program, limitations must be outlined. First, the absence of a control group does not allow us to conclude that the observed effects are only due to the intervention or whether there are other factors as well. In fact, the price of the program makes difficult the establishment of a control group: subjects who pay for such an intervention should be allowed to get benefits from it. Second, the subjects and professionals were not blind to the study hypotheses (i.e., to measure the program's efficacy). Thus, the blinding of the subjects should be ensured for future studies in this field, in order to limit the bias of social desirability and the placebo effect. And third, the price of the program (i.e., 430 euros for the 1-day intervention) could have excluded individuals who cannot afford it. Future research in this field should assess the economic and professional status of the subjects.

In this study, we quantified the reduction of fear of flying anxiety symptoms in a population of patients using a specifically developed program building on cognitive behavioral treatment and virtual reality strategies. Future research could explore the specificity of the phobia of each participant and its particular intensity (e.g., crash, take off, sounds, landing, fear of being afraid, and fear of panic attacks). A more qualitative investigation of the fear of flying (e.g., including professional and economic status, comorbidities, and previous psychological support attempts) could bring more elements to improve the treatment programs of the fear of flying. With regard to our promising results, we wish to assess the persistence of our patient's gains at a future follow-up date.

( 1 )

 1 Generalized Flight Anxiety (GFA) which contains 7 items (minimum possible score = 7; maximum possible score = 35), (2) Anticipatory Flight Anxiety (AFA) which is composed of 12 items (minimum possible score = 12; maximum possible score = 60), and (3) In-Flight Anxiety (IFA) which contains 10 items (minimum possible score = 10; maximum possible score = 50). Three items are not part of the final score of the FAS questionnaire: items 19, 21, and 26.

Table I .

 I Test of internal consistency for each subscale's reliability.

			Cronbach's α
		T1	T2	Global
	Scale	(N=144)	(N=145)	(N=289)
	FAS
	Generalized	.81**	.89**	.94***
	Anticipatory	.82**	.97***	.92***
	In-Flight	.83**	.93***	.89**
	FAM
	Somatic	.93***	.85**	.97***
	Cognitive	.89**	.92***	.91***
	Notes:
	FAS: Flyght Anxiety Situations; FAM: Flight Anxiety Modality
	*** excellent; ** good; * acceptable

Table II .

 II Comparison of mean scores (M), standard deviations (SD), and effect sizes (d) at baseline as compared to after the first flight following the intervention.

			Baseline	Follow-up
	Variables		M	SD	M	SD	d
	FAS	Generalized 24.60 5.457	9.95 3.502 3.20***
		Anticipatory 39.72 8.328	24.49 9.187 1.74***
		In-Flight	30.00 8.413	21.65 7.687 1.04***
	FAM	Somatic	32.11 8.473	15.19 4.938 2.44***
		Cognitive	22.30 5.728	13.80 5.875 1.47***
	Notes:
	FAM: Flight Anxiety Modality; FAS: Flight Anxiety Situations.
	*** p < .001 (as shown by t test)

Acknowledgements

The authors acknowledge the CTPA (Fear of Flying Treatment Centre) for providing access to the subjects, and the Flight Experience Company. Authors also acknowledge Catherine O'Malley for translation corrections.

Conflicts of interest

Three authors (MF, XT, VN) work at the CTPA, however they declare they have no financial interest.


Raghavendran Balu
email: raghavendran.balu@inria.fr

Teddy Furon
email: teddy.furon@inria.fr

Differentially Private Matrix Factorization using Sketching Techniques

Keywords: Count sketch, differential privacy, matrix factorization, recommender system, collaborative filtering

Collaborative filtering is a popular technique for recommendation system due to its domain independence and reliance on user behavior data alone. But the possibility of identification of users based on these personal data raise privacy concerns. Differential privacy aims to minimize these identification risks by adding controlled noise with known characteristics. The addition of noise impacts the utility of the system and does not add any other value to the system other than enhanced privacy. We propose using sketching techniques to implicitly provide the differential privacy guarantees by taking advantage of the inherent randomness of the data structure. In particular, we use count sketch as a storage model for matrix factorization, one of the successful collaborative filtering techniques. Our model is also compact and scales well with data, making it well suitable for large scale applications.

INTRODUCTION

Recommendation systems has become an indispensable component in Internet based services. It helps user in discovering new products and services by getting personalized suggestions based on their past consumption. Collaborative filtering is one of the popular techniques used in recommendation system. It uses user-item ratings relationship to provide recommendations. Relying on user behavior alone makes it domain independent and requires minimal external knowledge. Many techniques have been suggested in the past including the popular latent factor model. It maps both users and items to a low dimensional representation, retaining pairwise similarity. Matrix factorization learns these representation vectors from some observed ratings. They are then used to predict (by inner product) the missing entries and thereby to fill the incomplete user-item matrix [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF].

There is a cost to it and that is user privacy. The consumed items have to be collected at a centralized database, to perform both analysis and prediction, which compromises user privacy. The usual anonymization alone is not sufficient as demonstrated in [START_REF] Calandrino | you might also like:" privacy risks of collaborative filtering[END_REF]. This calls for robust privacy preserving techniques. One such is differential privacy [START_REF] Dwork | Encyclopedia of Cryptography and Security, chapter Differential Privacy[END_REF], which has gained wide out reach and acceptance from the academic community. Differential privacy provides strong theoretical guarantees and is robust to auxiliary information. There are various mechanisms that can provide differential privacy like Laplacian mechanism [START_REF] Dwork | Encyclopedia of Cryptography and Security, chapter Differential Privacy[END_REF], exponential mechanism [START_REF] Mcsherry | Mechanism design via differential privacy[END_REF] and Bayesian inference [START_REF] Wang | Privacy for free: Posterior sampling and stochastic gradient monte carlo[END_REF].

Our main idea is to promote a sketching technique for matrix factorization to design a highly scalable recommendation system. The prize to be paid is a loss of accuracy in the recommendations because the sketch inherently induces noise. Yet, this noise has two benefits (which are indeed related): it provides a better regularization and protects privacy. We motivate this last argument by stressing the similarities with recent Bayesian learning enhancing differential privacy. We propose an experimental protocol to measure privacy from predicted ratings to validate our claims.

Section 2 introduces the scientific background relevant to this paper. Section 3 describes our differentially private factorization algorithm and Section 4 outlines its main benefits. In Section 5 shows the experimental assessment of the claimed advantages.

BACKGROUND

Matrix factorization

In a typical collaborative filtering system, the given data is a sparse matrix R with non zero entries ru,i representing the rating provided by the user u ∈ U for a given item i ∈ I. Each row vector in R corresponds to an user u and column vector to an item i. In latent factor models, each user u is associated with a vector pu ∈ R d . Similarly, item i is associated to a vector qi ∈ R d . The goal is to approximate the rating ru,i by a simple scalar product p u qi. The latent vectors pu and qi of all users and items are represented as d × |U| matrix P and d × |I| matrix Q. We need to find the latent factors from the observed ratings such that the missing entries of R can be predicted by approximating matrix R ≈ P Q. This is done by minimizing the functional:

R λ (P, Q) = observed u,i L(ru,i, p u qi) + λ 2 ( pu 2 + qi 2 ).
(1)

L(ru,i, p u qi) quantifies the error between an observed rating ru,i and its prediction ru,i = p u qi. In the sequel, L(ru,i, p u qi) = (ru,i -p u qi) 2 /2. The second term is a penalty preventing overfitting the latent factors to the training data (i.e. the observed ratings) for a better generalization over the missing entries of R.

Finding latent factors

Techniques to efficiently find the latent factors (P, Q) minimizers of the objective function R λ (P, Q) of (1) work either offline or online. Offline techniques such as alternate least squares, gradient descent or online approaches such as the stochastic gradient descent proved to work well. This paper considers online techniques as its goal is to cope with the dynamicity of real-world recommendation systems. It is thus insightful to describe the approach proposed in [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF].

At each step, the stochastic gradient descent randomly picks an observed rating ru,i and optimizes the parameters with respect to that rating. This update relies on the gradient of the loss function with respect to parameters, controlled by the learning rate η:

pu ← pu -η∇uR λ (P, Q), (2) qi ← qi -η∇iR λ (P, Q), (3)
where ∇uR λ (P, Q) denotes the gradient of the functional w.r.t. latent vector pu:

∇uR λ (P, Q) = ∂L(ru,i, ru,i) ∂ ru,i ∂ ru,i ∂pu + λpu (4)
= (ru,i -p u qi)qi + λpu.

In the same way, ∇iR λ (P, Q) denotes the gradient of the functional w.r.t. latent vector qi.

As the algorithm is sequential, only the latent factors have to be stored in main memory. The updates can be parallelized as they are local only to the parameters corresponding to a particular rating. Hence the algorithm can scale well to increasing data size.

However, the number of latent factors is linear with the number of users and items. At very large scale, when the number of users and/or items becomes extremely large (millions), then the resulting memory consumption becomes problematic. Furthermore, determining the latent factors is challenging in a dynamic environment, particularly when new users and items are added every now and then. Allocating a d-dimensional vector to every sporadically recurring new user or item quickly becomes non-tractable.

A more compact representation for the factors is therefore needed. We propose the adoption of count sketches that are typically used in other contexts. We therefore review sketching techniques before discussing their ability to fit within a recommendation context.

Sketching techniques

Sketching is an active area of development, particularly in a streaming setup. A data structure maintaining a particular synopsis of the data irrespective of the history of updates can be called a sketch [START_REF] Cormode | Sketch techniques for approximate query processing[END_REF]. Sketching technique have been applied for estimating the items frequency [START_REF] Cormode | An improved data stream summary: the count-min sketch and its applications[END_REF], finding similar items [START_REF] Indyk | Approximate nearest neighbors: towards removing the curse of dimensionality[END_REF] and also limited numerical linear algebra operation [START_REF] Woodruff | Sketching as a tool for numerical linear algebra[END_REF]. The popularity of sketching techniques is attributed to its runtime and space efficiencies. We are in particular interested in the count sketch [START_REF] Charikar | Finding frequent items in data streams[END_REF]. It was origi-nally proposed to find heavy hitters, but can also be used to approximate the frequencies in turnstile model.

Count sketch is a probabilistic data structure originally designed to maintain approximations of quantities constantly updated in a datastream, but with sub-linear space complexity. Define [N ] := {1, • • • , N } and {q

(t) 1 , • • • , q (t)
N } N quantities. We observe a datastream of quantity updates:

< • • • δqe, • • • , δq , • • • >
and we would like to monitor the quantities over the time:

q (t+1) e = q (t) e + δqe.
A count sketch is represented by a k×w matrix C and two sets of pairwise independent hash functions {hj(•), sj(•)} k j=1 . The address hash function hj(•) maps an element of [N ] to the set {1, ..., w} and the sign hash function sj maps an element of [N ] to {+1, -1}. There are two typical processes: the update and the query actions.

Update: Upon the reception of the update δqe of the e-th quantity, k entries of matrix C are updated: ∀j,

1 ≤ j ≤ k c j,h j (e) ← c j,h j (e) + sj(e) • δqe. (6)
Query: At time t, given a query index e, mean or median of {sj(e)c j,h j (e) } k j=1 is returned as an approximation of q (t)

e . The median operator is more robust to noise [START_REF] Charikar | Finding frequent items in data streams[END_REF] but the mean is easier to compute. In the sequel, we choose the mean operator: q(t) e = k -1 k j=1 sj(e)c j,h j (e) . The accuracy of the estimation is related to the size of the count sketch [START_REF] Cormode | Sketch techniques for approximate query processing[END_REF]. Note that if we query index e just before and after its update, the difference of the approximates is the true update: q(t+1) e -q(t) e = δqe. However, updating the e-th quantity might have modified the others due to collision. In the j-th row of the count sketch, one entry has been modified by ±δqe (see ( 6)) whereas the w -1 others remained the same. In other words, the entries of C have been modified by random variables i.i.d. according to the p.m.f. (1-w -1 )∂0+(2w) -1 (∂ δqe +∂ -δqe ), where ∂a represent the Dirac distribution on x = a. The expectation is zero and the variance (δqe) 2 /w. This implies that the update of the e-th quantity adds on all the others qe , e = e, a centered noise of variance (δqe) 2 /wk.

Overall, the estimate based on the mean operator is unbiased with variance σ 2 /wk, where σ 2 = e∈[N ] (δqe) 2 . For a given (w, k), the accuracy decreases with N because the variance of the estimate increases with σ 2 . In other words, the representational capacity N of count sketch can be controlled by varying (w, k).

Differential privacy

Differential privacy argues that absolute privacy is impossible and instead settles to relative level. It has garnered wide spread attention among the research community for its theoretical rigorousness and robustness to side information.

In the context of recommendation system

In our application, differential privacy convinces users to submit their ratings by showing that an attacker querying the recommendation system has difficulty in deciding whether a particular rating has been used for learning the latent factors. Even with the side-information that user u rates item i by the true value ru,i, the attacker cannot say whether the user submitted or not this information. We are thus interested at -DP at the rating level with a trusted recommendation system.

Denote by D the dataset of observed ratings used for learn-ing the latent vectors, and D = D ∪ {< u , i , r u ,i >} s.t. these two datasets differs by one rating. Denote by ru,i(D) the output of a recommendation system trained on dataset D and queried about user u and item i. An -DP recommendation system satisfies:

∀(a, b) ∈ R 2 , a < b, ∀u ∈ U, ∀i ∈ I Pr[a < ru,i(D) < b] ≤ e Pr[a < ru,i(D ) < b]. (7)

A posteriori sampling

Paper [START_REF] Wang | Privacy for free: Posterior sampling and stochastic gradient monte carlo[END_REF] recently proved that Bayesian posterior sampling is differentially private to some extent. We explain it as follows in the context of matrix factorization based recommendation system. We first need a Bayesian framework. We assume the following prior distribution of latent factors:

p(P, Q) = Π U u=1 p(pu)Π I i=1 p(qi), (8)
with p(pu) and p(qi) are Gaussian distribution N (0 d , λ -1 I d ) with 0 d the all zero d × 1 vector, I d the identity matrix of size d and λ > 0. We assume a conditional pdf of the rating knowing the latent factors (i.e. the likelihood):

p(ru,i|P, Q) ∼ = N (p u qi, ν 2 ), with ν = 1. ( 9
)
This implies that, once some ratings are observed, the a posteriori distribution of the latent factors is

p(P, Q|observed < u, i, ru,i >) ∝ e -R λ (P,Q) , (10)
with R λ (P, Q) defined in (1). Therefore, minimizing this functional as proposed in Sec. 2.2 amounts to chose (P, Q) as their MAP (Maximum A Posteriori) estimates. Instead of doing this, [START_REF] Wang | Privacy for free: Posterior sampling and stochastic gradient monte carlo[END_REF][START_REF] Liu | Fast differentially private matrix factorization[END_REF] shows that drawing (P, Q) according to their a posteriori distribution [START_REF] Dwork | Encyclopedia of Cryptography and Security, chapter Differential Privacy[END_REF] enables differential privacy: if | log p(ru,i|P, Q)| < B, then the system is -DP with = 2B. If 2B is too big, then one may scale down log p(ru,i|P, Q), which amounts to pick ν > 1, i.e. a smoother conditional distribution.

The final issue is how to draw according to such a complex a posteriori distribution. Recent papers show that perturbating the stochastic gradient descent by some Gaussian noise is an efficient way to simulate such a sampling [START_REF] Welling | Bayesian learning via stochastic gradient langevin dynamics[END_REF][START_REF] Vollmer | asymptotic properties of stochastic gradient langevin dynamics[END_REF]. This technique is called Stochastic Gradient Langevin Dynamics (SGLD). In our context, this would mean replacing (2) and (3) by:

pu ← pu -η∇uR λ (P, Q) + √ ηBP , ( 11
) qi ← qi -η∇iR λ (P, Q) + √ ηBQ, (12)
with BP and BQ ∼ N (0, 1).

COUNT SKETCHING LARGE MATRIX FACTORIZATION

Sketching vectors

In regular matrix factorization, d-dimensional latent vectors {pu} u∈U and {qi} i∈I are stored as dense arrays P and Q, contiguous in memory. This facilitates indexing on the two dimensional array by increments of d. We propose replacing this matrix representation with a single count sketch. Although user and item vectors carry different semantic, their underlying representations are the same. Therefore we store both of them in the same structure, which should provide estimates for N = d(|U| + |I|) elements. For the sake of clarity, we introduce two families of address hash functions: {h u j (•)} k j=1 for the users, {h i j (•)} k j=1 for the items. Same for the sign hash functions.

Varying (w, k) explores the trade-off between the storage efficiency and the quality of the estimation. The storage improvement comes at the cost of increasing the retrieval complexity from O(d) to O(kd) for a d-dimensional vector.

Sketch based factorization

The sketch based online factorization differs from regular online factorization (Sec. 2) in the latent factor queries and gradient updates merging. When a new tuple < u, i, ru,i > arrives, the count sketch is first queried to approximately reconstruct user and item latent vectors. Both user ID u and component index l, 1 ≤ l ≤ d, are used as inputs to the k pairs of address and sign hash functions to get a mean estimate of the vector component (the same holds for item):

pu,l = 1 k k j=1 s u j (u, l) • c j,h u j (u,l) , ∀l ∈ {1, • • • , d}, (13) qi
,l = 1 k k j=1 s i j (i, l) • c j,h i j (i,l) , ∀l ∈ {1, • • • , d}. (14)
The estimated rating ru,i = p u qi is compared with the observed ru,i to get the loss L(ru,i, ru,i).

If L(ru,i, ru,i) ≤ , the gradient updates for pu and qi are just computed as in ( 2) and (3). Then for each component of pu (as well as qi), the k respective cells C are updated with their sign corrected gradients:

c j,h u j (u,l) ← c j,h u j (u,l) -ηs u j (u, l)∇ u,l R λ ( P, Q), (15) c j,h i j (i,l) ← c j,h i j (i,l) -ηs i j (i, l)∇ i,l R λ ( P, Q). ( 16
)
∇ u,l R λ ( P, Q) denotes the l-th component of the gradient defined in [START_REF] Charikar | Finding frequent items in data streams[END_REF], and similarly for the item gradient. Otherwise (i.e. L(ru,i, ru,i) > ), the cells are not updated at all. This is equivalent to not taking into account this particular observation.

BENEFITS OF OUR APPROACH

Space gain

The use of the count sketch is motivated as a means to trade space versus complexity. The count sketch has a storage space of wk scalars whereas the regular factorization would need (|U| + |I|)d scalars to store the latent factors. We define the space gain γ as

γ := (|U| + |I|)d wk ≥ 1. ( 17
)
On the other hand, at each update triggered by observation < u, i, ru,i >, the count sketch adds O(2dk) more operations to query and update the d components of pu and qi.

Self regularization

The Tikhonov regularization (i.e. L2 norm based) is generally associated with matrix factorization, as it can be controlled by λ and customized well to the needs. There are other methods to regularize like corrupting the input data. It is shown by Bishop et al in [START_REF] Bishop | Training with noise is equivalent to tikhonov regularization[END_REF] that training with corrupted data is equivalent to Tikhonov regularization.

In our scheme, we observe that the sketch structure itself regularizes the learnt latent vectors. At reception of rating ru,i, the gradient of the regular factorization is computed based on the error (ru,i-p u qi) whereas our algorithm computes the gradient based on ru,i -p u qi which can be expressed as ru,i + nu,i -p u qi. This shows the equivalence with working with noisy observed ratings.

This noise is due to the address hash collision among different elements. Thanks to the pairwise independence assumption, the error is independent of the cell location. Also the sign hash function sj(•) makes sure that the expected error on the components of the latent factor is centered: E(p u,l -p u,l ) = 0. This shows that the equivalent noises nu,i on the observations are i.i.d. and centered. We surmise that these indeed provide regularization capabilities. We experimentally prove the claim in section 5.2 by showing that the performance of the our system is less sensitive w.r.t. the regularization parameter λ.

Our algorithm uses regularization with Tikhonov penalization: λ (u,i) pu 2 + qi 2 . This has also an interpretation: the variance of the count sketch estimation error is proportional to σ 2 (Sect. 2.3), which, in our case, is

(u,i) pu 2 + qi 2 .
Our method thus aims at minimizing a combination of the error for predicting the ratings and the error for estimating latent vectors from the count sketch.

Differential privacy

Our algorithm inherently adds noise on the updates thanks to the count sketch. It looks like the SGLD (11) ( 12), but this is not. We can find the following differences. First, when updated, latent factors related to observed ru,i are not corrupted by noise, whereas all the others are. Second, the noise induced by the count sketch has a variance equalling δ 2 /wk where δ is the last update (see Sec. 2.3). Therefore, this variance is proportional to η 2 /wk and not η as in the SGLD algorithm. Third, this noise results from 2d latent factors updates only therefore it is certainly not Gaussian distributed.

The differential privacy is enforced by clipping the loglikelihood s.t.

| log p(ru,i|P, Q)| = (ru,i -ru,i) 2 /2 if (ru,i -ru,i) 2 ≤ /2 otherwise
This enables -DP as shown in [START_REF] Wang | Privacy for free: Posterior sampling and stochastic gradient monte carlo[END_REF][START_REF] Liu | Fast differentially private matrix factorization[END_REF], except that this no longer defines a valid conditional probability.

EXPERIMENTS

This section evaluates the claimed benefits of our approach. We first experimentally study its regularization capabilities. Then we analyze the privacy-utility trade-off and compare to regular factorization (without privacy).

Setup

Dataset

We use two publicly available datasets: Movielens1M [1] and EachMovie. Data characteristics are in Table 1. The data is preprocessed and randomly partitioned into the training, validation and test sets with proportion [0.8, 0.1, 0.1]. Preprocessing includes bias correction and frequency based thresholding: User, item and global means are substracted from ratings; ratings with user/item frequency < 10 are removed from the test and validation sets.

Evaluation

We use root mean square error to measure the quality of recommendations. The error materializes the deviation of the predicted rating from its true value. This squared error is averaged over the testing set:

RM SE(R ) = 1 R 0 r u,i ∈R (p u qi -ru,i) 2 , ( 18
)
where R is the restriction of R to the testing set. We use Kullback-Leibler divergence to gauge privacy. The KL divergence gives the expected amount of information 'leaked' about the fact that user u submitted his rating about item i. This divergence quantifies the difference between the probability distributions of the prediction for observed ratings (the training set) and non observed ratings (the testing set). A low divergence means that the predicted rating ru,i is statistically similar whether ru,i was used in training or not. An attacker observing ru,i and even knowing ru,i can not decide whether this rating was submitted to the recommendation system. To this aim, we experimentally observed that the prediction error (ru,i -ru,i) ∼ N (m, s 2 ). We measure (mtr, s 2 tr ) over the training set and (mte, s 2 te ) over the testing set, and compute

KLD = 1 2 s 2 tr s 2 te + (mtr -mte) 2 s 2 te -1 + log s 2 te s 2 tr . (19)

Parameters

We compare the performance for various configurations (w, k) of the sketch and different latent factor dimensions. The sketch depth k is picked from {1, 4} and the latent factor dimension d is chosen from {8, 16, 32}. We measure the space gain γ by the ratio of space that the regular factorization would need for the same dimension d to the space actually utilized by sketch based factorization. We vary γ within {1, 2, 4}. We determine the sketch width based on the space gain, dimension d and sketch depth k:

w = (|U| + |I|)d γk . (20)
We choose optimal parameters for learning rate η and regularization constant λ by a two stage line search in logscale, based on validation set prediction score. We iterate for T = 100 epochs over the training set, before predicting on the testing set, measuring RM SE(R ) and KLD. Learning rate is scaled down using the formula ηt =

Regularizing effect of count sketch

We now study the effect of regularization parameter λ on RMSE. We use EachMovie dataset under the setup (d = 32, γ = 1). We vary λ from 10 to 0 in log scale. Figure 1 compares the performance. We benchmark our method (k = 4) against regular online matrix factorization and feature hashing based factorization [START_REF] Karatzoglou | Collaborative filtering on a budget[END_REF] as it is a special case of our approach (k = 1). The three techniques share the following observations: The optimal λ is around 0.1 and the RMSE increases with λ beyond this value. When we decrease λ below the optimal value, the RMSE degrades and this is attributed to overfitting. The degradation of count sketch factorization is not as worse as the other two techniques.

Even when the regularization is turned off (λ = 0), our scheme performs better than the other two, for the same d. This shows that the 'noisy' sketch structure by itself provides some regularization capabilities. The heatmap of Figure 2 represents the optimal lambda values for various (d, γ) pairs on MovieLens 1M dataset. The optimal value is often lower than 10 -2 , except in the top right corner, where γ is small while d is big. This setting indeed ensures superfluous parameter space, which does require stronger regularization to avoid overfitting. The λ value diminishes with d: a smaller model requires less regularization. An interesting observation is that λ lowers with increase in γ and it is true even for a fixed d. This increases address hash collisions and hence the variance of the count sketch estimation (Sect. 4.2) which helps model generalization like when learning on noisy data.

Privacy utility tradeoff

In this section, we compare the variation of RMSE with respect to parameter as shown in figure 3. We vary in the range of {2, 4, 8, ∞} and benchmark it against regular factorization. As expected, lowering the privacy by increasing improves the utility, i.e. decreases RMSE. The improvement is significant in the lower range of and drops gradually as we increase further. When the epsilon is above 16 the RMSE is close to regular factorization.

KL divergence as a privacy measure

We take the role of an attacker willing to know whether a particular rating was used in the training. We use KL divergence to measure the amount of information 'leaked' by getting access to its prediction. Figure 4 shows that KL divergence increases along with the targeted level of privacy . The KL divergence of regular factorization without any differential privacy mechanism is higher for most of the cases. This supports our approach. It is also clear from the figure that compact models (higher γ or lower d) produce recommendations leaking less information compared to bigger one. The KL divergence which is a measurement on average is indeed much smaller than the target which is a guaranty on the worst case.

We also had a focused on 'top users', i.e. users who submitted a lot. As foreseen, the RMSE measured on this population is lower: they get better predictions because their models are more precise as they are learned on more data. The difference in performance is indeed small. Yet, very surprisingly, the KL divergence measured on this population is smaller by one order of magnitude. This population enjoys better recommendations together with better privacy.

RELATED WORK

Many mechanisms enable differential privacy including Laplacian mechanism [START_REF] Dwork | ICALP 2006, chapter Differential Privacy[END_REF], exponential mechanism [START_REF] Mcsherry | Mechanism design via differential privacy[END_REF], Bayesian inference [START_REF] Wang | Privacy for free: Posterior sampling and stochastic gradient monte carlo[END_REF], smooth sensitivity, and sample-aggregate frameworks [START_REF] Nissim | Smooth sensitivity and sampling in private data analysis[END_REF]. The works differ on the stage in which the randomization mechanism is added to the system. Initial approaches were advocating at the input and output levels. In [START_REF] Chaudhuri | Differentially private empirical risk minimization[END_REF], they incorporate it at the optimization level and demonstrated its superiority. Differential privacy is also applied to online learning in [START_REF] Jain | Differentially private online learning[END_REF]. A detailed survey of different techniques is available at [START_REF] Sarwate | Signal processing and machine learning with differential privacy: Algorithms and challenges for continuous data[END_REF] and [START_REF] Ji | Differential privacy and machine learning: a survey and review[END_REF]. [START_REF] Friedman | Data mining with differential privacy[END_REF] applied differential privacy to data mining. [START_REF] Kasiviswanathan | What can we learn privately[END_REF] studied the theoretical properties of learning under differential privacy setup.

Recommender systems is one of the compelling applications of differential privacy owing to its data involving sensitive user information. Many approaches have been proposed in the past for different collaborative filtering approaches like neighbor based approaches and matrix factorization. [START_REF] Mishra | Privacy via pseudorandom sketches[END_REF] used sketch to provide privacy. Their notion of privacy is very similar to differential privacy except that the loglikelihood ratio is bounded by a linear parameter instead of exponential. [START_REF] Melis | Efficient private statistics with succinct sketches[END_REF] proposed a recommender system by aggregating co-occurrence count in a privacy preserving way. Paper [START_REF] Mcsherry | Differentially private recommender systems: Building privacy into the net[END_REF] applied differential privacy to the global statistics collected from the rating matrix.

As for matrix factorization, paper [START_REF] Berlioz | Applying differential privacy to matrix factorization[END_REF] compares different ways to ensure differential privacy, among them, the Laplace mechanism on the inputs or on the updates of the stochastic gradient descent. [START_REF] Kapralov | On differentially private low rank approximation[END_REF] proposed a differentially private low rank approximation using exponential mechanism. [START_REF] Nikolaenko | Privacy-preserving matrix factorization[END_REF] devised a matrix factorization using cryptographic garbled circuits, but this does not enable differential privacy.

CONCLUSION

This work shows that sketching techniques can be used to preserve privacy by taking advantage of their inherent randomness. This is in contrast to conventional techniques which uses special mechanism to achieve the same. We also get additional benefits like scalability and adaptivity to dynamic data, making it preferable for realistic large-scale applications. We experimentally validate our approach using standard datasets. Future works include measurement of information leaked by the latent factors themselves. This is relevant when the latent vectors are learned by the server and sent to the users allowing local recommendation.

Figure 1 :Figure 2 :

 12 Figure 1: RMSE w.r.t. λ, EachMovie 1 3 6 11 23

Figure 3 :Figure 4 :

 34 Figure 3: RMSE w.r.t. , Movielens

Table 1 :

 1 Dataset characteristics

	η 1+b•t/T .