Joëlle Vailly

The expansion of abnormality and the biomedical norm: Neonatal screening, prenatal diagnosis and cystic fibrosis in France

Developments in biomedicine have remodelled the time-honoured questions of how to define the normal and the connection between the normal and the norm. My work deals with the expansion of the idea of abnormality through a study of the practices involved in neonatal screening for cystic fibrosis in France. It is based on observations made at meetings between paediatricians and geneticists involved in the screening programme, and a seven-month study in a tertiary care centre for cystic fibrosis. On the one hand, the study highlights the technical limitations of screening, which have the effect of expanding biological abnormality. On the other, it deals with the rationales and associated practices used by health care professionals for paediatric monitoring that are behind the expansion of clinical abnormality. Lastly, the consequences of those practices are analysed at the point where neonatal screening and prenatal diagnosis meet, showing how the biomedical norm, with respect to foetuses, is altered. The political and moral space in which this development has occurred is discussed.

Introduction

The unending medical enterprise that consists in distinguishing the normal from the abnormal and the pathological has a long-standing history, which [START_REF] Canguilhem | Le normal et le pathologique[END_REF] analyzed in his famous book "The normal and the pathological". As it is usually understood today, the notion of normality can be historically dated. It goes back to the 1820's when Broussais, a French physiologist, offered a novel organic theory of disease according to which pathological phenomena were purely quantitative variations of normal physiological phenomena [START_REF] Canguilhem | Le normal et le pathologique[END_REF][START_REF] Hacking | The taming of chance[END_REF]. This idea was a huge success, particularly under the influence of Comte, who shaped it into a vast political design. In Comte's view, for society as a whole to be in a state of normality is an assurance of progress and normality should hence be everyone's goal [START_REF] Canguilhem | Le normal et le pathologique[END_REF][START_REF] Hacking | The taming of chance[END_REF]. Clearly, from a very early stage, normal and abnormal phenomena conveyed not only purely factual circumstances, but also an attachment to a value. In other words, they were linked to an ideal state. Generally speaking, this attachment takes place through a shift from the normal to the norm: "The normal is at once the extension and the exhibition of the norm… A norm, a rule, is what can be used to right, to square, to straighten," Canguilhem (1978, pp. 176-177) emphasizes. In the same spirit, Hacking (2005, p. 3) recalls that the idea of normality establishes a bridge between description and evaluation, and that it has two purposes -one, descriptive, the other normative: "It is an idea we ostensibly use for objective descriptions, based on facts… It is also an idea that we use when making value judgments, instituting rules or establishing principles." The separation between the normal and the abnormal is by no means neutral because it contributes to delineating a social and moral space. Using several contemporary examples, such as the "nevra" (nerves) disease of immigrant women in Quebec or medicalisation of old age, what [START_REF] Lock | Accounting for disease and distress: morals of the normal and abnormal[END_REF] shows is that, far from being merely a product of biological make-up, normality and abnormality are culturally constructed and associated with a social, political and moral order.

In step with the changes occurring in medicine, in the 1960's [START_REF] Canguilhem | Le normal et le pathologique[END_REF] supplemented his initial proposition. He began to take into consideration what was then the novel study of genetic mutations, relating them to the concept of error. He uses the following formula to sum up the idea: "To be sick is to have been made false… in the sense of a "false fold" [i.e., wrinkle: faux pli] or a false rhyme." (Canguilhem, 1978, p. 208). Since then, it has been demonstrated that these mutations can help to establish a diagnosis by elucidating the biological basis of the symptoms or by uncovering a major molecular aberration. However, because these mutations are often unable to predict how severe the disease will be or when it will become apparent, they leave open the question of the boundary between the normal and the pathological and, moreover, the associated prognosis [START_REF] Miller | Ruling in and ruling out: implications of molecular genetic diagnosis for disease classification[END_REF][START_REF] Rose | The politics of life itself[END_REF][START_REF] Temple | Defining disease in the genomic era[END_REF]. In addition to their possible intrinsic ambiguity, genetic criteria for diagnostic purposes are sometimes at odds with physiological and biological criteria [START_REF] Miller | Ruling in and ruling out: implications of molecular genetic diagnosis for disease classification[END_REF], e.g., in the case of leukaemia and lymphoma [START_REF] Keating | Real compared to what?": diagnosis leukemias and lymphomas[END_REF]. Introducing the notion of biomedical platform, [START_REF] Keating | Biomedical platforms: realigning the normal and the pathological in late twentieth-century medicine[END_REF] describe a process through which the clinic, which scrutinizes the pathological, and the laboratory, which scrutinizes the normal, intermingle and are realigned.

My study revisits these issues that are once more in the limelight. Its object is neonatal screening for cystic fibrosis (NSCF), which was launched in France in 2002 [START_REF] Vailly | Genetic screening as a technique of government: the case of neonatal screening for cystic fibrosis in France[END_REF][START_REF] Vailly | Dépister les nouveau-nés : évolutions, débats et consensus[END_REF] 1 . This topic was chosen because neonatal screening has taken on considerable proportions in some countries. Some federal states of the United States screen for more than 40, largely genetic diseases at birth [START_REF] Acmg | Newborn screening: toward a uniform screening panel and system[END_REF]. Until recently, NSCF was conducted only in France, almost the whole of Australia and New Zealand, and some areas in other countries.

Today, many states in the U.S. have implemented the scheme (NNSGRC, 2006), and Great Britain is planning to expand its coverage to the whole country (http://www.newbornscreening-bloodspot.org.uk/). Another feature that makes cystic fibrosis (CF) a worthwhile study topic is that its history has been marked by the question of its boundaries from the beginning. Cystic fibrosis has undergone an overall process of nosological expansion, with the addition of disorders that are defined as being mild forms of CF, such as pancreatitis or congenital bilateral absence of the vas deferensa form of infertility [START_REF] Hedgecoe | Expansion and uncertainty: cystic fibrosis, classification and genetics[END_REF][START_REF] Kerr | Re)constructing genetic disease: The clinical continuum between cystic fibrosis and male infertility[END_REF][START_REF] Kerr | Understanding genetic disease in a socio-historical context: a case-study of cystic fibrosis[END_REF]. Researchers in social science disagree as to whether this expansion was succeeded by a contraction (due to the subsequent exclusion of congenital bilateral absence of the vas deferens from the CF category) [START_REF] Hedgecoe | Expansion and uncertainty: cystic fibrosis, classification and genetics[END_REF][START_REF] Kerr | Understanding genetic disease in a socio-historical context: a case-study of cystic fibrosis[END_REF]. There is also another debate about whether genetics has played an ascendant or a relative role in this process of reclassification [START_REF] Hedgecoe | Expansion and uncertainty: cystic fibrosis, classification and genetics[END_REF][START_REF] Kerr | Understanding genetic disease in a socio-historical context: a case-study of cystic fibrosis[END_REF].

My study presents an ethnographic analysis of the biomedical definition of the normal and the abnormal that is at work in the borderline forms of genetic disease in the context of NSCF, and some of that definition's "consequences", construed as its social and moral implications [START_REF] Bowker | Sorting things out. Classification and its consequences[END_REF]. The aim of this work is to answer two questions: how does NSCF contribute to the expansion of abnormality? How, in turn, does this expansion alter professional practices? A number of investigations on classification in biomedicine focus on the nosological dimensions and/or professional practices. They rely on an analysis of the biomedical literature [START_REF] Hedgecoe | Expansion and uncertainty: cystic fibrosis, classification and genetics[END_REF][START_REF] Kerr | Re)constructing genetic disease: The clinical continuum between cystic fibrosis and male infertility[END_REF], and on interviews [START_REF] Keating | Real compared to what?": diagnosis leukemias and lymphomas[END_REF][START_REF] Kerr | Understanding genetic disease in a socio-historical context: a case-study of cystic fibrosis[END_REF][START_REF] Miller | Ruling in and ruling out: implications of molecular genetic diagnosis for disease classification[END_REF], or, less frequently, on observations [START_REF] Featherstone | Dysmorphology and the spectacle of the clinic[END_REF]. My study, which relies on observations, aims at supplementing these analyses through the scrutiny of professional practices and their implications. What it does not deal with are the consequences of NSCF for either the child categorized as suffering from CF or the child's family. In the first part of this text, I look at the technical limitations of NSCF that lead to identifying a substantial rate of so-called borderline forms, whereby the purview of biological abnormality is expanded. The second part deals with the expansion of clinical abnormality. It is rooted in the attitudes adopted by health care professionals, which vary from an individually-based to a standardized approach, and the practices associated with paediatric monitoring. Finally, a local field study is used to analyse the consequences of these practices at the point where neonatal screening and prenatal diagnosis meet, showing how the norm, but this time in respect of foetuses, is altered. The political and moral space in which this development has occurred is discussed.

Study description

The research method used for the project comprises two complementary components. One component consists in the observations made at 16 meetings on NSCF conducted between June 2003 and May 2005 (symposia, scientific meetings, national congresses, etc.), including all the major national meetings held on the topic. These meetings lasted between 1 1/2 and 8 hours (mean duration 3 1/2 hours) and their purpose was to provide health care professionals with an opportunity to take stock of techniques and practices used in conjunction with this new screening programme. They were attended by between 15 and 150 health care professionals -mainly paediatricians but also geneticists and biologists -who work in the screening and care centres set up when NSCF was launched, referred to as the CRCMs (French acronym for Cystic Fibrosis Resources and Expertise Centres; [START_REF] Vailly | Genetic screening as a technique of government: the case of neonatal screening for cystic fibrosis in France[END_REF]. In addition but to a lesser extent, representatives of the professional association in charge of organising neonatal screening [START_REF] Vailly | Genetic screening as a technique of government: the case of neonatal screening for cystic fibrosis in France[END_REF], called the AFDPHE (the French Association for Screening for and Preventing Handicaps in Children) also took part in these meetings. For the purpose of this study, extensive notes, including near-verbatim minutes, were taken during these meetings. These observations were associated with informal discussions I conducted with the participants. The analysis forming the basis for this article was performed as follows:

I noted and classified the various occurrences of what was said about the so-called borderline forms of the disease and about related points, such as technical features, the question of naming the disease, an individual case-based versus a standardized approach, care management and prenatal diagnosis. A common method for qualitative surveys was applied that consists in adjusting the analysis while investigations go forward. In this way, theoretical notions can be reformulated and hypotheses are generated [START_REF] Glaser | The discovery of grounded theory[END_REF]. It is similar to the constant comparative method of analysis, inasmuch as it integrates various sources of qualitative information (observations, informal discussions and reviews of documents) for the period under consideration.

The other component of the research method is a qualitative study I conducted in 2005 over a period of seven months in a major Paris hospital. I chose this hospital because it is considered to be a medical and scientific standard of reference for paediatrics and genetics in France. I took part in 91 paediatric consultations and 37 genetic counselling sessions for CF arranged for by the CRCM paediatrics and genetics departments. Willingness to participate and a favourable assessment of participation by the clinical team were the selection criteria for observation. In this centre, consultations in connection with NSCF are not separate from those for cystic fibrosis diagnosed on the basis of symptoms (prior to the implementation of neonatal screening). Out of the 91 paediatric consultations observed, 30 related to children that had been screened (i.e. 12 medical files), and of the 37 genetic counselling sessions, 7 were identified by screening (i.e. 7 medical files). The inclusion criteria called on were selective. They consisted in concentrating on borderline forms detected during neonatal screening for which the full set of databoth paediatric and geneticwas available. Of the various families I followed both from the paediatric and genetic standpoints, two met the full range of criteria and could support an in-depth analysis. Extensive notes, including nearverbatim minutes, were taken during the consultations. From these observations and for the purposes of the present study, I extracted the way in which results bordering on normality are dealt with during consultations and how the information is conveyed to the parents.

All observations were performed with the explicit consent of the interested parties:

clinicians, organisers of the meetings, parents and children (except infants and toddlers). For the sake of confidentiality, names and surnames of the people involved have been altered. The research ethics committee of the hospital where I performed the study does not evaluate social sciences projects, only biomedical ones. This is consistent with French bioethical laws, which focus on biomedical projects.

Techniques and biological abnormality

From form of knowledge to definition of abnormality

Techniques, as has long been shown by researchers in social science, are by no means mere applications of scientific knowledge, free of any social contingencies [START_REF] Vinck | Sociologie des sciences[END_REF].

Indeed, the NSCF procedure in France is based on three techniques that are associated with different stages in the social history of the disease [START_REF] Kerr | Understanding genetic disease in a socio-historical context: a case-study of cystic fibrosis[END_REF]. It relies first on a blood assay of a protein called immuno-reactive trypsin (IRT) performed on all newborns. If this first test is positive, a commercially available kit is used to detect the 30 most frequent mutations of the CFTR gene involved in the aetiology of the disease. If one or two mutations are found or the trypsin level is above a cut-off value, the families are asked to come to the CRCM to have a sweat chloride test performed on the child (sweat test). Complexity would be relatively constrained if there was no overlap between normal and pathological findings obtained by these techniques -an uncommon occurrence in biology [START_REF] Grimes | Uses and abuses of screening tests[END_REF] -, and if they produced consistent classification systems. As described further on, each of the three techniques refers to a different form of knowledge that produces its own definition of normality.

The IRT assay arises from statistical knowledge, based on the increase in IRT levels in young people suffering from CF as compared to a control group. This knowledge is not explanatory, i.e., it does not help us discover the root of the disease because the clinical and biological significance of the IRT level is not known. In spite of its shortcomings, this assay affords the practical benefit of distinguishing the so-called suspect cases from the normal children within the overall population of neonates -but not at this stage between diseased and normal ones. The intervention threshold, which sets up the dividing line between these two categories, is quantitative and defined by the organisers of the screening campaign. They settle on a compromise between sensitivity, that tends to bring the threshold down, and specificity, that tends to raise it. In fact in 2003, the cut-off value was increased on the consideration that the number of children needing genetic investigation was too high (approximately 6000 per year), and that it entailed a considerable financial cost without bringing any added benefit in terms of sensitivity [START_REF] Afdphe | Le dépistage néonatal de la mucoviscidose en France. Statistiques nationales 2002-2003[END_REF]. In spite of the higher cutoff value, there are nonetheless still 4000 suspect cases for 170 confirmed cases of cystic fibrosis every year. In short, the definition of abnormality under this first test, notwithstanding the efforts made by screening programme organisers to reach a balance between specificity and sensitivity, is a broad one. If the result of the first test is suspect, a second technique based on molecular testing comes into play.

The second stage is set in a form of knowledge -genetics -that elucidated the primary cause of the disease which is a mutation in a gene that codes for a chloride channel. The reason this test has been included in the screening procedure is that it increases NSCF specificity and has thereby helped to make NSCF socially acceptable [START_REF] Vailly | Une politique de santé "a priori": le dépistage néonatal de la mucoviscidose en Bretagne[END_REF]. Indeed, the number of children detected that carry one or two mutations is brought to approximately 550 as a result of this test, which classifies into three categories: "normal" (no mutation and IRT below cut-off value), "suspect" (one mutation) and "affected" or "likely to be affected" (two mutations). In cases where one or two mutations are detected, the situation is made more complex for two reasons. First, there is the problem of transposing techniques that arises because the tools used were designed for diagnostic rather than screening purposes. In the case of NSCF, the kit used is capable of identifying 80% of the mutations discovered in France, including some so-called mild mutations which, while helpful in diagnosing adults that show clinical signs, have no clearcut significance in respect of the overall population of newborns. For instance, the mutation referred to as R117H, which turns out to be the second most common mutation in France, indiscriminately entails classic forms of CF, attenuated forms or else simple forms of infertility, or even no symptoms at all. More precisely, R117H leads preferentially to CF when it is associated with another genetic marker called 5T, and preferentially to infertility when it is associated with the marker called 7T. However, some cases of the 7T association with respiratory symptoms have been reported (Roussey, 2005).

The implications of this will become apparent further on. Currently, the R117H mutation represents 8.5% of the mutations detected in the screened population, whereas before NSCF was implemented, it accounted for only 0.3% of the mutations in patients on record in tertiary care centres [START_REF] Onm | Rapport sur la situation de la mucoviscidose en[END_REF]. This significant increase probably arises from the fact that some of the children were considered normal before neonatal screening was implemented and therefore eluded mutation incidence statistics. To set these problems in perspective however, it should be noted that some 500 heterozygous newborns (with one mutation) are detected every year, i.e., a few percent of the total population of heterozygotes. The reason for this is that most heterozygotes are classified as normal following the IRT test and are not therefore subjected to the genetic test. As a result, the issues raised by the genetic test do not concern all heterozygotes born in France each year.

In addition to the problem of transposing techniques, there is a diversification effect.

Indeed, whenever there is uncertainty, the CFTR gene is extensively explored using sophisticated techniques, sometimes leading to the discovery of one of some 1300 different mutations that have been identified in the world. Screening on the scale of a population intensifies this effect of diversification -the broader the population, the higher the probability of isolating rare or ill-known mutations. In other words, as a paediatrician explained at a round table session on NSCF during a national paediatrics congress:

"With the kit and technological breakthroughs [in genetics], the laboratory detects mutations more frequently and the percentage of mild forms has increased" (Paediatrician 1, Observation 12).

In short, with the molecular test, although the definition of abnormality is narrowed as compared with IRT assaying, it is broadened in comparison with criteria which until then had been established on the basis of symptoms, regardless of how mild or severe.

As for the sweat test (ST), it can rely on three quite distinct chloride assaying techniques that will not be described here. It is based on knowledge that is both clinical, tracing back to the physiological causes of the disease, and statistical, showing up higher chloride levels in affected patients than in controls. It leaves the realm of screening and enters into that of diagnosis, performed in the course of paediatric consultations. The associated categories are normal, CF-affected and, as will become clearer further on, potentially an intermediate class whose very existence and denomination are in the balance with NSCF. Differentiating between the normal and the abnormal here relies on quantitative data that generate not a dividing line but rather an indeterminate area that is bounded by two cut-off values. This is a well-known difficulty but one that is aggravated in the case of NSCF by two things. On the one hand, the lower of these two values is contentious in France because there are discussions about bringing it down from the initially chosen value of 40 to 30, so as not to "miss cases".

On the other, test results may differ depending on the chloride assaying technique used. This means that the classification is partially built up out of the local context and by the place where the method is used [START_REF] Roth | Making classification (at) work: ordering practices in science[END_REF]. This aspect comes out clearly in this exchange between professionals at a meeting of some dozen paediatricians and biologists from CRCMs organized to provide an overview of borderline forms:

-"We agreed on a lower value of 30" (Biochemist 1).

- Lowering the cut-off value (for reasons that are examined further on) and projecting into the future in respect of this third test thus expand the idea of abnormality.

Spatial and temporal remodelling of the disease

The difficulties described above should not give the impression that the situation is one of complete confusion. While the variability of cut-off values and measuring methods makes it difficult to precisely assess the number of borderline cases, the elements recorded during the observations indicate that about one fourth of the neonates categorized as affected are borderline. This implies that although the number of borderline infants concerned is low (170 infants are diagnosed as having cystic fibrosis at birth every year in France), they account for a relatively high proportion of diseased infants. Moreover, if all the centres used the 30 cut-off value, that proportion would increase significantly.

Overall, the techniques implemented for NSCF lead to classifying more babies in the abnormal category as the outcome of two effects. One is a cumulative effect. In their interpretations, health care professionals do not privilege either molecular testing or the sweat test. This means that, in the eyes of professionals, uncertainties tend to be incremental rather than cancel each other out (elevated IRT plus a borderline sweat test; intermediate sweat test plus a mutation, etc.). The second effect is that the weight of clinical considerations has declined in this approach. Without entering into the debate about the relationships between the clinical approach and new genetic technologies [START_REF] Latimer | Rebirthing the clinic. The interaction of clinical judgment and genetic technology in the production of medical science[END_REF], which do not come under the scope of this paper, it is useful to compare this result with those of other studies. Featherstone and her colleagues [START_REF] Featherstone | Dysmorphology and the spectacle of the clinic[END_REF] conclude their analysis of the categorization of cases of dysmorphology (congenital malformations) with the idea that "the "clinic" still asserts its symbolic and functional power: the "gaze" of the clinician and the clinician's warrant of personal knowledge exert their influence". This is only an apparent contradiction with the study presented here providing a distinction is made. In the case of dysmorphology, the extreme variability of the symptoms and of the genetic alterations in all of the chromosomes is such that it is not always possible to establish an association between them. Furthermore, the persons monitored are mostly children or adults that show signs or symptoms that physicians seek to categorize. In the case of NCFS, the severity of the disease is variable but it is associated with a gene that is amenable to analysis, making the genetic approach relatively simpler, even though, as we have seen, the results it yields may be ambiguous. In addition, neonates that are borderline display few or no symptoms, a fact which undermines the clinical approach. As a result, the relative weight of the "clinic" compared to biology and genetics declines during the screening period and the early years of the child's life, albeit perhaps temporarily. Finally, in conclusion to this first part, it should be noted that the decline of clinical considerations goes beyond the tension between the clinical aspects and genetic reclassification described by other authors [START_REF] Hedgecoe | Expansion and uncertainty: cystic fibrosis, classification and genetics[END_REF][START_REF] Miller | Ruling in and ruling out: implications of molecular genetic diagnosis for disease classification[END_REF]. In these cases, the process begins for a family when a patient exhibits symptoms of variable severity needing a diagnosis and treatment. The situation is different when the "patient" -but is the term "ill" justifiable? -is still very young and his or her parents have not yet actively sought the advice of a clinician. The conception of disease continues the process of change that was occurring in the 20 th century [START_REF] Kerr | Understanding genetic disease in a socio-historical context: a case-study of cystic fibrosis[END_REF]. It is temporally remodelled because the period prior to the symptoms appearing during which people would previously have been considered healthy is now one where they are considered as patients. The conception is also spatially remodelled because families that previously were never considered to be affected now are.

Medical practice and clinical abnormality

Early treatment in tertiary care centres of CF-affected children was one of the grounds for introducing NSCF in France [START_REF] Vailly | Genetic screening as a technique of government: the case of neonatal screening for cystic fibrosis in France[END_REF]. However, early treatment that requires admitting very young babies into a demanding care management scheme may be seen, in particular by paediatricians, as questionable when the babies exhibit no symptoms. Health care professionals are however under pressure to respond to these ambivalent situations quickly.

What line of reasoning do they call on to take action? How do they classify and manage children whose status is dubious? Just as with other diseases, these practices and the label they generate have some very considerable implications for the individuals concerned because they hugely impact the way others see the person, the person's self-perception, employment prospects, medical cost coverage, etc. [START_REF] Bowker | Sorting things out. Classification and its consequences[END_REF][START_REF] Temple | Defining disease in the genomic era[END_REF].

The weight of words

The first choice that health care professionals must make relates to the name given to the condition and what it implies. The term "pre-CF", offered in biomedical literature [START_REF] Bush | Time to think again -cystic fibrosis, like cancer, is not an "all or none" disease[END_REF], was sometimes brought up during the observations, with reference to the situation whereby, as previously noted, a number of normal or borderline STs tend to go positive with time. Although there seems to be a consensus among professionals that the designation does have major consequences, views about these differ. This conversation between professionals recorded at a national meeting that brought together some fifty leading CRCM paediatricians is evocative:

-"Sometimes the term CF is more of a burden than the disease itself…" (Paediatrician 3).

-"Why use a different term as long as you qualify the information?" (Paediatrician 4).

-"With underprivileged people, sooner or later you have to give a yes or no answer" (Paediatrician 5).

-"I take the entirely opposite view. It's all very well to say mild CF…" (Paediatrician 6).

-"Once it has been established that there is no phenotype-genotype [observable feature, severity of the disease-genetic pattern] correlation, I don't see how we can tell them it is not a serious disease…" (Paediatrician 4).

-"It's a different matter if you label it CF when you have good reason to believe that the only problem will be infertility" (Paediatrician 6, Observation 1).

Clearly, these exchanges show up two things. First, they show that health care professionals express their preoccupation with qualifying the information given to parents.

They are apprehensive about the concern they stir up in parents and express their discomfort in relation to these situations. Sometimes, they long for the hindsight that will enable them to acquire expertise so that, as the children grow older, they can adjust their practices accordingly. At the time the survey was conducted, no stable national consensus had been achieved. Secondly, these exchanges illustrate the way in which children with a dubious diagnosis will sometimes, on the basis of arguments relating to language, social presuppositions or biomedical knowledge, be classified in the generic "CF" category. In 2004, a study conducted by [START_REF] Afdphe | Le dépistage néonatal de la mucoviscidose en France. Statistiques nationales 2002-2003[END_REF] showed up that a CF diagnosis had been established

for 18 children that were homozygous (two identical mutations) or compound heterozygous (two different mutations) for the R117H mutation while having a normal sweat test. These children are not just carriers of a biological anomaly; they have an illness that is generally serious, irrespective of their own particular status. Indeed, all parents in maternity wards are given an information brochure on neonatal screening that specifies: "Cystic fibrosis brings about nutritional disorders and, more critically, a progressive lung disorder that makes it a serious condition." 2 Just as with any disorder, the disease reveals itself through words that include the term CF (pre-CF, atypical CF, etc.). On the other hand, in contrast with other disorders, it severs the link between words and symptoms and once stated resonates even more cruelly.

« Cases» and statistics

What is at stake is not just a matter of naming but also the care that will be given to the child. Health care professionals are in two minds about whether to adopt a standardized or individually-based approach. One set of arguments derives from a preliminary assessment of a regional screening programme that was presented at one symposium. This was an early programme that was launched in the 1980s in Brittany, and had the benefit of greater hindsight as compared to the national programme. Twenty-six children with so-called mild mutations subjected to regular medical monitoring were involved. The assessment was that their respiratory status was generally satisfactory with the exception of one child. Along the same lines as this regional programme assessment, a number of AFDPHE officials mention the need to gather statistical data through a national epidemiological data registry. At a meeting attended by the leading CRCM paediatricians, one stresses: "It is important for us to have statistics" (Paediatrician 7, Observation 1). On the other hand, paediatricians confronted with uncertainty speak repeatedly of an individual "case-related" approach. This is apparent in these three quotes observed and recorded during national NSCF meetings:

"We had a case of mild mutation where the child died" (Pulmonologist 1, Observation 15).

"At [X], we have an experience with a child that has [an] R117H [mutation] and is ST negative, while his older brother is ST positive" (Paediatrician 4, Observation 1).

"There are cases where patients die even with mild mutations. As a rule, these patients have longer life expectancies, but if they die at the age of 12 or 20…" (Paediatrician 1, Observation 8).

Even though clinicians are aware that death is not the inevitable outcome, they tend to underscore these adverse instances, which leave a more lasting impression, than by favourable outcomes. The negative situations are the ones that are being brought into view. This has practical repercussions because the tendency is to be cautious and unwilling to run the risk of failing to detect situations where a child's condition might suddenly deteriorate. At a meeting on borderline cases of about ten paediatricians and biologists from CRCMs, one paediatrician explained to a colleague:

"American investigations have shown that with a [ST] cut-off value of 40, there is a non-negligible risk of missing some children. We cannot allow that to happen; 5 or 6 years from now, it may be up to 59 or 63" (Paediatrician 2, Observation 14).

These precautions mean that a great majority of health care professionals prefer to monitor children that have borderline forms, generally under a more flexible regimen than the one applied to classic CF forms, rather than consider them healthy. On the national scale, a preliminary study conducted by the clinicians themselves in 2005 shows that when a child had two mutations, one of which was mild, he or she was monitored every month or every three months. When a child had two classical mutations and a borderline ST, he or she was monitored every month. When a child had no or one mutation and a borderline ST, one third of health care professionals reassured parents, while two thirds asked families to come back and did not reach a firm conclusion at that stage (Observation 14).

When they make their initial assessments, paediatricians assemble their own local resources which may later be used as guides for classification [START_REF] Roth | Making classification (at) work: ordering practices in science[END_REF]. Along the same line of thought, the organisers of screening schemes call for statistics they hope will bring up the level of generality. Specifically, "sciences that classify people" must be able to "count" and produce the quantitative data most suitable to effective classification [START_REF] Hacking | Seminar "Façonner les gens[END_REF].

But, as we have already seen, genetic mutations are not well-suited to this exercise, and the cases of adverse progression of the disease within the cohorts arouse doubts and induce health care professionals to take a cautious approach. The tension that exists between assessments of entire populations and the starkness of cases is apparently tending to move in favour of the latter. Specifically, the approach to child monitoring both derives and deviates from two medical traditions [START_REF] Desrosières | La politique des grands nombres[END_REF]. It no longer confines itself strictly to the "one-to-one interaction" (colloque singulier) between the patient and physician, whereby the medical supervision focuses exclusively on the individual case. On the other hand, it is not content with statistics based on averages that miss particular situations. More in keeping with Claude Bernard's experimental medicine, the preference is for a medicine that claims to be both scientific and distrustful of probabilities. This generates a situation where statistics appear to be case-driven. In other words, it is as if the whole group whose future is uncertain was under the influence of what is actually happening to the individual patient. In spite of the fact that care management for borderline forms is less demanding than for classic CF -in the latter case, the average daily time spent on care is two hours (personal observations) -, abnormality is expanding its influence on clinical practice in the area of consultations and physiotherapies.

Furthermore, as will become clear further on, this affects not just screened children. It reaches beyond the birth stage to foetuses. Although some questions had begun to arise about what should be done in this respect, this point was not as frequently discussed during the first observations, because NSCF had recently been introduced and the number of pregnancies subject to prenatal testing was still small. The purpose of my local study was to gain a better grasp of the implications of this linkage between the definition of the normal and the establishment of a medical norm.

From the normal to the norm

Two enlightening situations

Situation 1: Catherine and Patrick are the parents of little Lea who was born a month and a half ago. The future appears rosy until Professor Berteau, Head of the Paediatrics Ward in the hospital where I conducted my study phones them to discuss " taking a trypsin level test" on the baby, and arranges for an urgent appointment the next day. The next day, the physician explains that Lea "has two positive indications -a very high trypsin level and the presence of a mutation -but that there must be three [for her to be considered diseased]." Two hours later, on the basis of the sweat test result, Professor Berteau says the test is negative since the value is 25 whereas the norm is 60 and adds, saying every word quite distinctly: "You can definitely assume that your child does not have CF." The parents give a sigh of relief and everything appears to go back to normal. But then the professor suggests that the parents return two months later to check the trypsin level which is decidedly very high (1200 as compared to a cut-off value of 65) and another sweat test, as only one of the two methods usually performed could be interpreted that day. He also urges them to arrange for genetic counselling. Two months later, the parents tell the geneticist that Lea is healthy and her weight gain curve is normal, that the final sweat test is 30 but her trypsin level is still high. The geneticist suggests performing a test to identify which of the two parents is carrier of the identified mutation and conduct a thorough exploration of the gene involved so as to detect a possible second, more rare mutation in the child. He adds: "Assuming that she has some form of CF, it would be a very mild one… The sweat test is normal, so in principle there is a low risk of CF as such, but possibly other genetic anomalies, although I think that is very unlikely, which could lead to pancreatitis." Six months later, genetic exploration continues, there have been multiple consultations and tests, the parents are crushed by uncertainty and a conclusion has yet to be reached.

Two months later, once my field study was over, the parents received a letter from the paediatrician informing them that a second, very rare, mutation had been detected in Lea's DNA, saying that the child suffers, "strictly speaking", from "atypical CF". The letter points out that only two cases of this mutation have ever been described by the literature worldwide:

one of which involved a male who just had a form of infertility, and the other was a female child who had a form of chronic pancreatitis. Nearly three months later, the geneticist told me that Catherine was two and a half months pregnant and had just undergone a prenatal diagnostic test to check the genetic status of the foetus in respect of those two mutations. He continues saying: "I was careful. There are no signs in Lea, but we cannot guarantee that will remain the case in the future." A week later, we learn that the foetus is healthy and the question of terminating the pregnancy does not come up. Catherine speaks to me saying:

"What was clearly stated [in the consultation], was that the decision was ours… but that we were strongly urged to have the prenatal test performed. [The arguments were] that since we have the technical means to identify the foetus's genetic profile, it would be a pity not to do so, knowing there was a risk [of miscarriage due to the sampling operation], quite a low one, I think it was 1%… and the second argument was that I'm fairly young and if the worst comes to the worst we could always consider another pregnancy." Thirteen months had by then gone by since Lea was born.

Situation 2: Bastien and Isabelle are the parents of little Zoe, who was given a sweat test according to the same procedure used for Lea, after a positive IRT level result and detection of a mutation -the famous so-called mild R117H mutation -were discovered during neonatal screening. Very fortunately, the test result (8) was clearly negative and the baby was classified as not affected. A little later, Isabelle and Bastien went to a geneticist to find out whether the mutation was on the maternal or the paternal side so as to be able to warn their respective brothers and sisters in case they wanted to have children. A few months later,

Bastien received a letter from the geneticist stating: "The molecular testing conducted on your DNA... shows that you are a carrier of the R117H mutation (associated with alleles 7T, 7T of intron 8)… We advise you to inform your brother that there is a 1 in 2 risk that he is also the carrier of this mutation so that he can seek the advice of geneticist if he so wishes... On the basis of this information… the risk of you and your mate having a child with CF can be estimated to be in the order of 1/640, i.e. a level close to that of the population at large." The way in which the consultation is conducted and the method for calculating the risk of CF are the same as for any other mutation of the CFTR gene, independently of the fact that this mutation, associated with the 7T allele, as previously explained, most often produces infertility alone. The genetic profile is therefore clearly included in the "CF" category.

The genetic meeting point

The two examples provided above underpin the previously described results about the expansion of abnormality occurring with NSCF. They furthermore are instructive as to what is at stake in the borderline cases, where a population-wide neonatal screening scheme intersects with prenatal diagnosis. While the latter is more personalised, the two are linked.

The two situations described clearly show that when a mutation detected during neonatal screening is poorly known or mostly associated with a benign form, and very rarely with a classic form, prenatal diagnosis is offered for subsequent pregnancies. Clearly, while uncertainty is a long-standing feature of medicine, and indeed inherent to clinical activity, scientific and technical changes alter its contours and fuel it [START_REF] Fox | Medical uncertainty revisited[END_REF]. In fact, in this particular centre, the only situations that are excluded from prenatal diagnosis are those where it can be asserted with certainty that the genetic profile will produce only infertility, because geneticists do not consider infertility as medical grounds for terminating a pregnancy. This threshold of acceptability is confirmed by observations made at genetic counselling sessions during which a finding of an infertility-associated genetic profile was treated as normal. In fact, practices are equally determined by the severity of the disease and the notion of certainty. In practical terms, this means that infertility as such is not defined as a form of CF whereas pancreatitis is; only ascertained infertility is separated from the other disorders. CF and infertility are treated differently in terms of the ethical grounds for performing prenatal diagnosis inasmuch as genetics provides a "guarantee". In contrast, CF, pancreatitis and infertility join up at a genetic meeting point when a given mutation is liable to be present, even if only sporadically. This is where the shift from normal to norm mentioned in the introduction occurs. It is where the expansion of abnormality is embodied by the expansion of the faculty for selection, which may affect other members of the family (uncles, aunts, etc.

with the same mild mutation). As with the paediatricians, these practices are sometimes questioned by the very people who implement them. One of the three geneticists surveyed in the centre told me during a conversation I had with him concerning borderline forms:

"Whenever a mutation is found [by neonatal screening], even the R117H, people are sent to genetic counselling…. That's the way it is, the machinery is in motion whether or not it is justified, I don't know [he sighs]. I don't know… The uncles, aunts, cousins, they all consult" (Geneticist 1).

These results are an encouragement to pursue investigations from the standpoint of parents and on practices relating to pregnancy terminations on medical grounds. One instance that supports this remark is a short article published in the "New Scientist" in 2003 describing pregnancy terminations in the United States on the basis of non-pathogenic polymorphism detected by commercial kits that were confused with the CFTR gene mutations (Concar, 2003).

Conclusion

A more general expansion

Various studies indicate there is an expansion of medical abnormality in the Western countries. This is illustrated by categories such as: the "overweight" where the associated Body Mass Index has been lowered [START_REF] Hacking | Seminar "Façonner les gens[END_REF]; autism, whose enlarged definition produces more core and more related cases [START_REF] Hacking | Seminar "Façonner les gens[END_REF]; lead poisoning, associated with a lowered acceptable lead level in the blood thus turning a rare disease into an epidemic [START_REF] Fassin | Public health as culture. The social construction of the childhood lead poisoning epidemic in France[END_REF]. More generally, screening of the whole population or the so-called "risk" population [START_REF] Armstrong | The rise of surveillance medicine[END_REF][START_REF] Van Hoyweghen | Making the normal deviant: the introduction of predictive medicine in life insurance[END_REF], broadening the scope of mental health [START_REF] Castel | La gestion des risques: de l'anti-psychiatrie à l'après-psychanalyse[END_REF][START_REF] Lock | Accounting for disease and distress: morals of the normal and abnormal[END_REF], the increasing sensitivity of biomedical techniques [START_REF] Getz | Ultrasound screening in pregnancy: advancing technology, soft markers for fetal chromosomal aberrations, and unackowledged ethical dilemmas[END_REF][START_REF] Kaufert | Screening the body: the pap smear and the mammogram[END_REF] are all instrumental in bringing about this expansion. This powerful movement is only slightly disrupted by the major social and economic disparities that prevent certain populations from having access to health care and result in a conception of medical abnormality applicable to the latter that is more restricted [START_REF] Khoshnood | Advances in medical technology and creation of disparities: the case of Down syndrome[END_REF][START_REF] Markovic | Embodied changes and the search for gynecological cancer diagnosis[END_REF]). On the whole, it is quite apparent that biomedicine can increasingly avail itself of techniques capable of uncovering and managing deviants. Today what is central is not to find out whether the abnormal can be distinguished from the normal by qualitative, quantitative factors, or a combination of both, which was Canguilhem's starting point (1978).

It is rather, as Canguilhem himself outlined, to attempt to understand how this expansion and the values of our societies interrelate. As noted by [START_REF] Fassin | Les constructions de l'intolérable[END_REF], bringing down the detection and tolerance thresholds for diseases is part of a broad, albeit very unequally distributed, movement that rejects bodily impairment, a condition that is increasingly considered intolerable. Neonatal screening indeed exemplifies one way in which these levels are lowered.

The space of neonatal screening

My study relates to a given space and time and as such does not presume upon future developments in the area of neonatal screening, nor of practices in centres other than the one where it was conducted, although it is interesting to note that the latter is credited with a high level of scientific and medical legitimacy. It does however provide two pieces of information.

First, it shows how the idea of abnormality is expanding with NSCF, proceeding from its concomitant use of three approaches: a technologization of medicine, a preventive policy geared at the whole population, along with clinical practices geared to the individual. The use of a commercial kit makes no small contribution to this process by facilitating matters materially and hence permitting entire populations to be screened. At a time when other techniques that would make mass genetic testing possible such as "DNA chips" are being developed (HGC, 2005), a conjunction is occurring between totalizing procedures (population screening) and individually-based techniques (medical consultations and genetic counselling).

Second, my study shows that by bringing borderline forms into view, neonatal screening can lead to expansion through prenatal diagnosis. Of course, prenatal diagnosis for mutations referred to as mild may occur from time to time independently from NSCF, but the screening programme amplifies the phenomenon.

Genetic counselling has been the topic of many publications in the social sciences, because of the social and ethical issues these new techniques raise, especially genetic technologies [START_REF] Dusart | La détection des anomalies foetales: analyse sociologique[END_REF][START_REF] Ettore | Reproductive genetics, gender and the body: "Please doctor, may I have a normal baby?[END_REF][START_REF] Rapp | Testing the women, testing the foetus: the social impact of amniocentesis in America[END_REF][START_REF] Remennick | The quest for the perfect baby: why do Israeli women seek prenatal genetic testing?[END_REF][START_REF] Williams | Dilemmas in fetal medicine: premature application of technology or responding to women's choice?[END_REF].

But so far, genetic counselling has not been investigated at the point where the neonatal and the prenatal approaches meet. In one respect, current knowledge enables children, who in many cases are or will be severely affected, to be screened and monitored at birth.

Furthermore, once a first child was screened at birth and found to be affected, this knowledge makes it possible to avoid sibships with several CF-affected members through prenatal screening of any subsequent pregnancy. In another respect, to paraphrase [START_REF] Foucault | Dits et écrits II, 1976-1988[END_REF], there appears to be a price to pay 3 . The price paid is to pronounce foetuses that have good chances of not getting CF to be suspect or even undesirable. Whether the price is low or high is not discussed here, the intention not being to be prescriptive or "normative". But the political and moral space in which this development has occurred is worthy of note.

Indeed, NSCF has a particular contour: while it is deeply rooted in the compassionate and socially acceptable care that must be given to sick children, it does not offer adequate treatment possibilities that would make a prenatal diagnosis redundant. The prenatal diagnosis it proposes under these circumstances is clearly distinguishable from the usual prenatal diagnosis, which is offered on the basis that there is an affected person in the family. It is also clearly distinguishable from systematic heterozygote screening among adults that raises controversy about actual or supposed eugenics [START_REF] Gayon | L'éternel retour de l'eugénisme[END_REF][START_REF] Paul | Is Human Genetics Disguised Eugenics[END_REF]. The shift in the norm occurring here is located in a new political and moral space compared to these other two configurations. On the one hand, it is both individual (sick persons, "suspect" cases and their families are given paediatric advice and genetic counselling) and collective (from the outset, the whole population is targeted). On the other, NSCF is ethically relatively consensual because it is usually offered in connection with neonatal screening and hence targeted at sick children. Let us wager that if genetic tests continue their advance, this space will receive the attention of social scientists investigating the politics of biomedicine.

  "You can't say 30 regardless of the test; my 30 may be different from yours" (Paediatrician 2, Observation 14).

Finally, a borderline result (in the 30/40 -60 range) should be placed in a local, but also a temporal context. In a presentation given before his peers at a round table session on NSCF at a national paediatrics congress, a paediatrician in charge of the CRCM explained: "With time, borderline sweat test results tend to go positive" (Paediatrician 1, Observation 12). This means that the intermediate ST values may increase and fall into the diseased category.


Aaron Defazio

Francis Bach

Simon Lacoste-Julien

SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives

In this work we introduce a new optimisation method called SAGA in the spirit of SAG, SDCA, MISO and SVRG, a set of recently proposed incremental gradient algorithms with fast linear convergence rates. SAGA improves on the theory behind SAG and SVRG, with better theoretical convergence rates, and has support for composite objectives where a proximal operator is used on the regulariser. Unlike SDCA, SAGA supports non-strongly convex problems directly, and is adaptive to any inherent strong convexity of the problem. We give experimental results showing the effectiveness of our method.

Introduction

Remarkably, recent advances [START_REF] Schmidt | Minimizing finite sums with the stochastic average gradient[END_REF][START_REF] Shalev | Stochastic dual coordinate ascent methods for regularized loss minimization[END_REF] have shown that it is possible to minimise strongly convex finite sums provably faster in expectation than is possible without the finite sum structure. This is significant for machine learning problems as a finite sum structure is common in the empirical risk minimisation setting. The requirement of strong convexity is likewise satisfied in machine learning problems in the typical case where a quadratic regulariser is used.

In particular, we are interested in minimising functions of the form

f (x) = 1 n n i=1 f i (x),
where x ∈ R d , each f i is convex and has Lipschitz continuous derivatives with constant L. We will also consider the case where each f i is strongly convex with constant µ, and the "composite" (or proximal) case where an additional regularisation function is added:

F (x) = f (x) + h(x),
where h : R d → R d is convex but potentially non-differentiable, and where the proximal operation of h is easy to compute -few incremental gradient methods are applicable in this setting [3][4].

Our contributions are as follows. In Section 2 we describe the SAGA algorithm, a novel incremental gradient method. In Section 5 we prove theoretical convergence rates for SAGA in the strongly convex case better than those for SAG [START_REF] Schmidt | Minimizing finite sums with the stochastic average gradient[END_REF] and SVRG [START_REF] Johnson | Accelerating stochastic gradient descent using predictive variance reduction[END_REF], and a factor of 2 from the SDCA [START_REF] Shalev | Stochastic dual coordinate ascent methods for regularized loss minimization[END_REF] convergence rates. These rates also hold in the composite setting. Additionally, we show that like SAG but unlike SDCA, our method is applicable to non-strongly convex problems without modification. We establish theoretical convergence rates for this case also. In Section 3 we discuss the relation between each of the fast incremental gradient methods, showing that each stems from a very small modification of another.

SAGA Algorithm

We start with some known initial vector x 0 ∈ R d and known derivatives f ′ i (φ 0 i ) ∈ R d with φ 0 i = x 0 for each i. These derivatives are stored in a table data-structure of length n, or alternatively a n × d matrix. For many problems of interest, such as binary classification and least-squares, only a single floating point value instead of a full gradient vector needs to be stored (see Section 4). SAGA is inspired both from SAG [START_REF] Schmidt | Minimizing finite sums with the stochastic average gradient[END_REF] and SVRG [START_REF] Johnson | Accelerating stochastic gradient descent using predictive variance reduction[END_REF] (as we will discuss in Section 3). SAGA uses a step size of γ and makes the following updates, starting with k = 0: SAGA Algorithm: Given the value of x k and of each f ′ i (φ k i ) at the end of iteration k, the updates for iteration k + 1 is as follows:

1. Pick a j uniformly at random.

2. Take φ k+1 j = x k , and store f ′ j (φ k+1 j ) in the table. All other entries in the table remain unchanged. The quantity φ k+1 j is not explicitly stored.

3. Update x using f ′ j (φ k+1 j ), f ′ j (φ k j ) and the table average:

w k+1 = x k -γ f ′ j (φ k+1 j ) -f ′ j (φ k j ) + 1 n n i=1 f ′ i (φ k i ) , (1)
x k+1 = prox h γ w k+1 . (2)
The proximal operator we use above is defined as prox h γ (y) := argmin

x∈R d h(x) + 1 2γ
x -y 2 .

(3)

In the strongly convex case, when a step size of γ = 1/(2(µn+L)) is chosen, we have the following convergence rate in the composite and hence also the non-composite case:

E x k -x * 2 ≤ 1 - µ 2(µn + L) k x 0 -x * 2 + n µn + L f (x 0 ) -f ′ (x * ), x 0 -x * -f (x * ) .
We prove this result in Section 5. The requirement of strong convexity can be relaxed from needing to hold for each f i to just holding on average, but at the expense of a worse geometric rate (1µ 6(µn+L) ), requiring a step size of γ = 1/(3(µn + L)).

In the non-strongly convex case, we have established the convergence rate in terms of the average iterate, excluding step 0:

xk = 1 k k t=1 x t . Using a step size of γ = 1/(3L) we have E F (x k ) -F (x * ) ≤ 4n k 2L n x 0 -x * 2 + f (x 0 ) -f ′ (x * ), x 0 -x * -f (x * ) .
This result is proved in the supplementary material. Importantly, when this step size γ = 1/(3L) is used, our algorithm automatically adapts to the level of strong convexity µ > 0 naturally present, giving a convergence rate of (see the comment at the end of the proof of Theorem 1):

E x k -x * 2 ≤ 1 -min 1 4n , µ 3L k x 0 -x * 2 + 2n 3L f (x 0 ) -f ′ (x * ), x 0 -x * -f (x * ) .
Although any incremental gradient method can be applied to non-strongly convex problems via the addition of a small quadratic regularisation, the amount of regularisation is an additional tunable parameter which our method avoids.

Related Work

We explore the relationship between SAGA and the other fast incremental gradient methods in this section. By using SAGA as a midpoint, we are able to provide a more unified view than is available in the existing literature. A brief summary of the properties of each method considered in this section is given in Figure 1. The method from [START_REF] Tseng | Incrementally updated gradient methods for constrained and regularized optimization[END_REF], which handles the non-composite setting, is not listed as its rate is of the slow type and can be up to n times smaller than the one for SAGA or SVRG [START_REF] Johnson | Accelerating stochastic gradient descent using predictive variance reduction[END_REF].

SAGA SAG SDCA SVRG FINITO Strongly Convex (SC) ✓ ✓ ✓ ✓ ✓ Convex, Non-SC* ✓ ✓ ✗ ? ? Prox Reg. ✓ ? ✓[6] ✓ ✗ Non-smooth ✗ ✗ ✓ ✗ ✗ Low Storage Cost ✗ ✗ ✗ ✓ ✗ Simple(-ish) Proof ✓ ✗ ✓ ✓ ✓ Adaptive to SC ✓ ✓ ✗ ? ?
Figure 1: Basic summary of method properties. Question marks denote unproven, but not experimentally ruled out cases. (*) Note that any method can be applied to non-strongly convex problems by adding a small amount of L2 regularisation, this row describes methods that do not require this trick.

SAGA: midpoint between SAG and SVRG/S2GD

In [START_REF] Johnson | Accelerating stochastic gradient descent using predictive variance reduction[END_REF], the authors make the observation that the variance of the standard stochastic gradient (SGD) update direction can only go to zero if decreasing step sizes are used, thus preventing a linear convergence rate unlike for batch gradient descent. They thus propose to use a variance reduction approach (see [START_REF] Greensmith | Variance reduction techniques for gradient estimates in reinforcement learning[END_REF] and references therein for example) on the SGD update in order to be able to use constant step sizes and get a linear convergence rate. We present the updates of their method called SVRG (Stochastic Variance Reduced Gradient) in ( 6) below, comparing it with the non-composite form of SAGA rewritten in [START_REF] Johnson | Accelerating stochastic gradient descent using predictive variance reduction[END_REF]. They also mention that SAG (Stochastic Average Gradient) [START_REF] Schmidt | Minimizing finite sums with the stochastic average gradient[END_REF] can be interpreted as reducing the variance, though they do not provide the specifics. Here, we make this connection clearer and relate it to SAGA.

We first review a slightly more generalized version of the variance reduction approach (we allow the updates to be biased). Suppose that we want to use Monte Carlo samples to estimate EX and that we can compute efficiently EY for another random variable Y that is highly correlated with X. One variance reduction approach is to use the following estimator θ α as an approximation to EX:

θ α := α(X -Y )+EY , for a step size α ∈ [0, 1].
We have that Eθ α is a convex combination of EX and EY :

Eθ α = αEX + (1 -α)EY .
The standard variance reduction approach uses α = 1 and the estimate is unbiased Eθ 1 = EX. The variance of θ α is:

Var(θ α ) = α 2 [Var(X) + Var(Y ) -2 Cov(X, Y )],
and so if Cov(X, Y ) is big enough, the variance of θ α is reduced compared to X, giving the method its name. By varying α from 0 to 1, we increase the variance of θ α towards its maximum value (which usually is still smaller than the one for X) while decreasing its bias towards zero.

Both SAGA and SAG can be derived from such a variance reduction viewpoint: here X is the SGD direction sample f ′ j (x k ), whereas Y is a past stored gradient f ′ j (φ k j ). SAG is obtained by using α = 1/n (update rewritten in our notation in (4)), whereas SAGA is the unbiased version with α = 1 (see (5) below). For the same φ's, the variance of the SAG update is 1/n 2 times the one of SAGA, but at the expense of having a non-zero bias. This non-zero bias might explain the complexity of the convergence proof of SAG and why the theory has not yet been extended to proximal operators. By using an unbiased update in SAGA, we are able to obtain a simple and tight theory, with better constants than SAG, as well as theoretical rates for the use of proximal operators.

(SAG)

x k+1 = x k -γ f ′ j (x k ) -f ′ j (φ k j ) n + 1 n n i=1 f ′ i (φ k i ) , (4)
(SAGA)

x k+1 = x k -γ f ′ j (x k ) -f ′ j (φ k j ) + 1 n n i=1 f ′ i (φ k i ) , (5)
(SVRG)

x k+1 = x k -γ f ′ j (x k ) -f ′ j (x) + 1 n n i=1 f ′ i (x) . (6)
The SVRG update (6) is obtained by using Y = f ′ j (x) with α = 1 (and is thus unbiased -we note that SAG is the only method that we present in the related work that has a biased update direction). The vector x is not updated every step, but rather the loop over k appears inside an outer loop, where x is updated at the start of each outer iteration. Essentially SAGA is at the midpoint between SVRG and SAG; it updates the φ j value each time index j is picked, whereas SVRG updates all of φ's as a batch. The S2GD method [START_REF] Konečný | Semi-stochastic gradient descent methods[END_REF] has the same update as SVRG, just differing in how the number of inner loop iterations is chosen. We use SVRG henceforth to refer to both methods. SVRG makes a trade-off between time and space. For the equivalent practical convergence rate it makes 2x-3x more gradient evaluations, but in doing so it does not need to store a table of gradients, but a single average gradient. The usage of SAG vs. SVRG is problem dependent. For example for linear predictors where gradients can be stored as a reduced vector of dimension p -1 for p classes, SAGA is preferred over SVRG both theoretically and in practice. For neural networks, where no theory is available for either method, the storage of gradients is generally more expensive than the additional backpropagations, but this is computer architecture dependent. SVRG also has an additional parameter besides step size that needs to be set, namely the number of iterations per inner loop (m). This parameter can be set via the theory, or conservatively as m = n, however doing so does not give anywhere near the best practical performance. Having to tune one parameter instead of two is a practical advantage for SAGA.

Finito/MISOµ

To make the relationship with other prior methods more apparent, we can rewrite the SAGA algorithm (in the non-composite case) in term of an additional intermediate quantity u k , with

u 0 := x 0 + γ n i=1 f ′ i (x 0
), in addition to the usual x k iterate as described previously:

SAGA: Equivalent reformulation for non-composite case: Given the value of u k and of each f ′ i (φ k i ) at the end of iteration k, the updates for iteration k + 1, is as follows:

1. Calculate x k :

x k = u k -γ n i=1 f ′ i (φ k i ). (7)
2. Update u with

u k+1 = u k + 1 n (x k -u k ). 3. Pick a j uniformly at random. 4. Take φ k+1 j = x k , and store f ′ j (φ k+1 j ) in the table replacing f ′ j (φ k j ).
All other entries in the table remain unchanged. The quantity φ k+1 j is not explicitly stored.

Eliminating u k recovers the update (5) for x k . We now describe how the Finito [START_REF] Defazio | Finito: A faster, permutable incremental gradient method for big data problems[END_REF] and MISOµ [START_REF] Mairal | Incremental majorization-minimization optimization with application to largescale machine learning[END_REF] methods are closely related to SAGA. Both Finito and MISOµ use updates of the following form, for a step length γ:

x k+1 = 1 n i φ k i -γ n i=1 f ′ i (φ k i ). (8)
The step size used is of the order of 1/µn. To simplify the discussion of this algorithm we will introduce the notation φ = 1 n i φ k i . SAGA can be interpreted as Finito, but with the quantity φ replaced with u, which is updated in the same way as φ, but in expectation. To see this, consider how φ changes in expectation:

E φk+1 = E φk + 1 n x k -φ k j = φk + 1 n x k -φk .
The update is identical in expectation to the update for u,

u k+1 = u k + 1 n (x k -u k ).
There are three advantages of SAGA over Finito/MISOµ. SAGA does not require strong convexity to work, it has support for proximal operators, and it does not require storing the φ i values. MISO has proven support for proximal operators only in the case where impractically small step sizes are used [START_REF] Mairal | Incremental majorization-minimization optimization with application to largescale machine learning[END_REF]. The big advantage of Finito/MISOµ is that when using a per-pass re-permuted access ordering, empirical speed-ups of up-to a factor of 2x has been observed. This access order can also be used with the other methods discussed, but with smaller empirical speed-ups. Finito/MISOµ is particularly useful when f i is computationally expensive to compute compared to the extra storage costs required over the other methods.

SDCA

The Stochastic Dual Coordinate Descent (SDCA) [START_REF] Shalev | Stochastic dual coordinate ascent methods for regularized loss minimization[END_REF] method on the surface appears quite different from the other methods considered. It works with the convex conjugates of the f i functions. However, in this section we show a novel transformation of SDCA into an equivalent method that only works with primal quantities, and is closely related to the MISOµ method.

Consider the following algorithm:

SDCA algorithm in the primal

Step k + 1:

1. Pick an index j uniformly at random.

Compute φ

k+1 j = prox fj γ (z), where γ = 1 µn and z = -γ n i =j f ′ i (φ k i ). 3. Store the gradient f ′ j (φ k+1 j ) = 1 γ z -φ k+1 j in the table at location j. For i = j, the table entries are unchanged (f ′ i (φ k+1 i ) = f ′ i (φ k i )).
At completion, return

x k = -γ n i f ′ i (φ k i ) .
We claim that this algorithm is equivalent to the version of SDCA where exact block-coordinate maximisation is used on the dual. 1 Firstly, note that while SDCA was originally described for onedimensional outputs (binary classification or regression), it has been expanded to cover the multiclass predictor case [START_REF] Shalev | Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization[END_REF] (called Prox-SDCA there). In this case, the primal objective has a separate strongly convex regulariser, and the functions f i are restricted to the form

f i (x) := ψ i (X T i x)
, where X i is a d×p feature matrix, and ψ i is the loss function that takes a p dimensional input, for p classes. To stay in the same general setting as the other incremental gradient methods, we work directly with the f i (x) functions rather than the more structured ψ i (X T i x). The dual objective to maximise then becomes

D(α) =   - µ 2 1 µn n i=1 α i 2 - 1 n n i=1 f * i (-α i )   ,
where α i 's are d-dimensional dual variables. Generalising the exact block-coordinate maximisation update that SDCA performs to this form, we get the dual update for block j (with x k the current primal iterate):

α k+1 j = α k j + argmax ∆aj ∈R d -f * j -α k j -∆α j - µn 2 x k + 1 µn ∆α j 2 . (9)
In the special case where f i (x) = ψ i (X T i x), we can see that [START_REF] Defazio | Finito: A faster, permutable incremental gradient method for big data problems[END_REF] gives exactly the same update as Option I of Prox-SDCA in [11, Figure 1], which operates instead on the equivalent p-dimensional dual variables αi with the relationship that α i = X i αi . 2 As noted by Shalev-Shwartz & Zhang [START_REF] Shalev | Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization[END_REF], the update ( 9) is actually an instance of the proximal operator of the convex conjugate of f j . Our primal formulation exploits this fact by using a relation between the proximal operator of a function and its convex conjugate known as the Moreau decomposition:

prox f * (v) = v -prox f (v).
This decomposition allows us to compute the proximal operator of the conjugate via the primal proximal operator. As this is the only use in the basic SDCA method of the conjugate function, applying this decomposition allows us to completely eliminate the "dual" aspect of the algorithm, yielding the above primal form of SDCA. The dual variables are related to the primal representatives φ i 's through

α i = -f ′ i (φ i ).
The KKT conditions ensure that if the α i values are dual optimal then x k = γ i α i as defined above is primal optimal. The same trick is commonly used to interpret Dijkstra's set intersection as a primal algorithm instead of a dual block coordinate descent algorithm [START_REF] Combettes | Proximal Splitting Methods in Signal Processing[END_REF].

The primal form of SDCA differs from the other incremental gradient methods described in this section in that it assumes strong convexity is induced by a separate strongly convex regulariser, rather than each f i being strongly convex. In fact, SDCA can be modified to work without a separate regulariser, giving a method that is at the midpoint between Finito and SDCA. We detail such a method in the supplementary material.

SDCA variants

The SDCA theory has been expanded to cover a number of other methods of performing the coordinate step [START_REF] Shalev | Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization[END_REF]. These variants replace the proximal operation in our primal interpretation in the previous section with an update where φ k+1 j is chosen so that:

f ′ j (φ k+1 j ) = (1-β)f ′ j (φ k j )+βf ′ j (x k ), where x k = -1 µn i f ′ i (φ k i ).
The variants differ in how β ∈ [0, 1] is chosen. Note that φ k+1 j does not actually have to be explicitly known, just the gradient f ′ j (φ k+1 j ), which is the result of the above interpolation. Variant 5 by Shalev-Shwartz & Zhang [START_REF] Shalev | Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization[END_REF] does not require operations on the conjugate function, it simply uses β = µn L+µn . The most practical variant performs a line search involving the convex conjugate to determine β. As far as we are aware, there is no simple primal equivalent of this line search. So in cases where we can not compute the proximal operator from the standard SDCA variant, we can either introduce a tuneable parameter into the algorithm (β), or use a dual line search, which requires an efficient way to evaluate the convex conjugates of each f i .

Implementation

We briefly discuss some implementation concerns:

• For many problems each derivative f ′ i is just a simple weighting of the ith data vector. Logistic regression and least squares have this property. In such cases, instead of storing the full derivative f ′ i for each i, we need only to store the weighting constants. This reduces the storage requirements to be the same as the SDCA method in practice. A similar trick can be applied to multi-class classifiers with p classes by storing p -1 values for each i.

• Our algorithm assumes that initial gradients are known for each f i at the starting point x 0 .

Instead, a heuristic may be used where during the first pass, data-points are introduced oneby-one, in a non-randomized order, with averages computed in terms of those data-points processed so far. This procedure has been successfully used with SAG [START_REF] Schmidt | Minimizing finite sums with the stochastic average gradient[END_REF]. • The SAGA update as stated is slower than necessary when derivatives are sparse. A just-intime updating of u or x may be performed just as is suggested for SAG [START_REF] Schmidt | Minimizing finite sums with the stochastic average gradient[END_REF], which ensures that only sparse updates are done at each iteration. • We give the form of SAGA for the case where each f i is strongly convex. However in practice we usually have only convex f i , with strong convexity in f induced by the addition of a quadratic regulariser. This quadratic regulariser may be split amongst the f i functions evenly, to satisfy our assumptions. It is perhaps easier to use a variant of SAGA where the regulariser µ 2 ||x|| 2 is explicit, such as the following modification of Equation ( 5):

x k+1 = (1 -γµ) x k -γ f ′ j (x k ) -f ′ j (φ k j ) + 1 n i f ′ i (φ k i ) .
For sparse implementations instead of scaling x k at each step, a separate scaling constant β k may be scaled instead, with β k x k being used in place of x k . This is a standard trick used with stochastic gradient methods.

For sparse problems with a quadratic regulariser the just-in-time updating can be a little intricate. In the supplementary material we provide example python code showing a correct implementation that uses each of the above tricks.

Theory

In this section, all expectations are taken with respect to the choice of j at iteration k + 1 and conditioned on x k and each f ′ i (φ k i ) unless stated otherwise. We start with two basic lemmas that just state properties of convex functions, followed by Lemma 1, which is specific to our algorithm. The proofs of each of these lemmas is in the supplementary material. Lemma 1. Let f (x) = 1 n n i=1 f i (x). Suppose each f i is µ-strongly convex and has Lipschitz continuous gradients with constant L. Then for all x and x * :

f ′ (x), x * -x ≤ L -µ L [f (x * ) -f (x)] - µ 2 x * -x 2 6 - 1 2Ln i f ′ i (x * ) -f ′ i (x) 2 - µ L f ′ (x * ), x -x * .
Lemma 2. We have that for all φ i and x * :

1 n i f ′ i (φ i ) -f ′ i (x * ) 2 ≤ 2L 1 n i f i (φ i ) -f (x * ) - 1 n i f ′ i (x * ), φ i -x * .
Lemma 3. It holds that for any φ k i , x * , x k and β > 0, with w k+1 as defined in Equation 1:

E w k+1 -x k -γf ′ (x * ) 2 ≤ γ 2 (1 + β -1 )E f ′ j (φ k j ) -f ′ j (x * ) 2 + γ 2 (1 + β)E f ′ j (x k ) -f ′ j (x * ) 2 -γ 2 β f ′ (x k ) -f ′ (x * ) 2 .
Theorem 1. With x * the optimal solution, define the Lyapunov function T as:

T k := T (x k , {φ k i } n i=1 ) := 1 n i f i (φ k i ) -f (x * ) - 1 n i f ′ i (x * ), φ k i -x * + c x k -x * 2 .
Then with γ =

E[T k+1 ] ≤ (1 - 1 κ )T k .
Proof. The first three terms in T k+1 are straight-forward to simplify:

E 1 n i f i (φ k+1 i ) = 1 n f (x k ) + 1 - 1 n 1 n i f i (φ k i ). E - 1 n i f ′ i (x * ), φ k+1 i -x * = - 1 n f ′ (x * ), x k -x * -1- 1 n 1 n i f ′ i (x * ), φ k i -x * .
For the change in the last term of T k+1 , we apply the non-expansiveness of the proximal operator3 :

c x k+1 -x * 2 = c prox γ (w k+1 ) -prox γ (x * -γf ′ (x * )) 2 ≤ c w k+1 -x * + γf ′ (x * ) 2 .
We expand the quadratic and apply E[w k+1 ] = x k -γf ′ (x k ) to simplify the inner product term:

cE w k+1 -x * + γf ′ (x * ) 2 = cE x k -x * + w k+1 -x k + γf ′ (x * ) 2 = c x k -x * 2 + 2cE w k+1 -x k + γf ′ (x * ), x k -x * + cE w k+1 -x k + γf ′ (x * ) 2 = c x k -x * 2 -2cγ f ′ (x k ) -f ′ (x * ), x k -x * + cE w k+1 -x k + γf ′ (x * ) 2 ≤ c x k -x * 2 -2cγ f ′ (x k ), x k -x * + 2cγ f ′ (x * ), x k -x * -cγ 2 β f ′ (x k ) -f ′ (x * ) 2 + 1 + β -1 cγ 2 E f ′ j (φ k j ) -f ′ j (x * ) 2 + (1 + β) cγ 2 E f ′ j (x k ) -f ′ j (x * ) 2 . (Lemma 7)
The value of β shall be fixed later. Now we apply Lemma 1 to bound -2cγ We can now combine the bounds that we have derived for each term in T , and pull out a fraction 1 κ of T k (for any κ at this point). Together with the inequality - [START_REF] Yu | Introductory Lectures On Convex Programming[END_REF]Thm. 2.1.10], that yields:

f ′ (x k ), x k -x * and Lemma 6 to bound E f ′ j (φ k j ) -f ′ j (x * ) 2 : cE x k+1 -x * 2 ≤ (c -cγµ) x k -x * 2 + (1 + β)cγ 2 - cγ L E f ′ j (x k ) -f ′ j (x * ) 2 - 2cγ(L -µ) L f (x k ) -f (x * ) -f ′ (x * ), x k -x * -cγ 2 β f ′ (x k ) -f ′ (x * ) 2 + 2 1 + β -1 cγ 2 L 1 n i f i (φ k i ) -f (x * ) - 1 n i f ′ i (x * ), φ k i -x * .
f ′ (x k ) -f ′ (x * ) 2 ≤ -2µ f (x k ) -f (x * ) -f ′ (x * ), x k -x * [
E[T k+1 ] -T k ≤ - 1 κ T k + 1 n - 2cγ(L -µ) L -2cγ 2 µβ f (x k ) -f (x * ) -f ′ (x * ), x k -x * + 1 κ + 2(1 + β -1 )cγ 2 L - 1 n 1 n i fi(φ k i ) -f (x * ) - 1 n i f ′ i (x * ), φ k i -x * + 1 κ -γµ c x k -x * 2 + (1 + β)γ - 1 L cγE f ′ j (x k ) -f ′ j (x * ) 2 . ( 10
)
Note that each of the terms in square brackets are positive, and it can be readily verified that our assumed values for the constants (γ = L ensure that each of the quantities in round brackets are non-positive (the constants were determined by setting all the round brackets to zero except the second one -see [START_REF] Defazio | New Optimization Methods for Machine Learning[END_REF] for the details). Adaptivity to strong convexity result: Note that when using the γ = 1 3L step size, the same c as above can be used with β = 2 and 1 κ = min 1 4n , µ 3L to ensure non-positive terms.

Corollary 1. Note that c x k -x * 2 ≤ T k , and therefore by chaining the expectations, plugging in the constants explicitly and using µ(n -0.5) ≤ µn to simplify the expression, we get:

E x k -x * 2 ≤ 1 - µ 2(µn + L) k x 0 -x * 2 + n µn + L f (x 0 ) -f ′ (x * ), x 0 -x * -f (x * ) .
Here the expectation is over all choices of index j k up to step k.

Experiments

We performed a series of experiments to validate the effectiveness of SAGA. We tested a binary classifier on MNIST, COVTYPE, IJCNN1 and a least squares predictor on MILLIONSONG. Details of these datasets can be found in [START_REF] Defazio | Finito: A faster, permutable incremental gradient method for big data problems[END_REF]. We used the same code base for each method, just changing the main update rule. SVRG was tested with the recalibration pass used every n iterations, as suggested in [START_REF] Konečný | Semi-stochastic gradient descent methods[END_REF]. Each method had its step size parameter chosen so as to give the fastest convergence.

We tested with a L2 regulariser, which all methods support, and with a L1 regulariser on a subset of the methods. The results are shown in Figure 2. We can see that Finito (perm) performs the best on a per epoch equivalent basis, but it can be the most expensive method per step. SVRG is similarly fast on a per epoch basis, but when considering the number of gradient evaluations per epoch is double that of the other methods for this problem, it is middle of the pack. SAGA can be seen to perform similar to the non-permuted Finito case, and to SDCA. Note that SAG is slower than the other methods at the beginning. To get the optimal results for SAG, an adaptive step size rule needs to be used rather than the constant step size we used. In general, these tests confirm that the choice of methods should be done based on their properties as discussed in Section 3, rather than their convergence rate.

A The SDCA/Finito Midpoint Algorithm

Using Lagrangian duality theory, SDCA can be shown at step k as minimising the following lower bound:

A k (x) = 1 n f j (x) + 1 n n i =j f i (φ k i ) + f ′ i (φ k i ), x -φ k i + µ 2 x 2 .
Instead of directly including the regulariser in this bound, we can use the standard strong convexity lower bound for each f i , by removing µ 2 x 2 and changing the expression in the summation to

f i (φ k i )+ f ′ i (φ k i ), x -φ k i + µ 2 x -φ i 2 .
The transformation to having strong convexity within the f i functions yields the following simple modification to the algorithm:

φ k+1 j = prox fj (µ(n-1)) -1 (z)
, where:

z = 1 n -1 i =j φ k i - 1 µ(n -1) i =j f ′ i (φ k i ).
It can be shown that after this update:

x k+1 = φ k+1 j = 1 n i φ k+1 i - 1 µn i f ′ i (φ k+1 i ).
Now the similarity to Finito is apparent if this equation is compared Equation 8:

x k+1 = 1 n i φ k i - γ n i=1 f ′ i (φ k i ).
The only difference is that the vectors on the right hand side of the equation are at their values at step k +1 instead of k. Note that there is a circular dependency here, as φ k+1 j := x k+1 but φ k+1 j appears in the definition of x k+1 . Solving the proximal operator is the resolution of the circular dependency. This mid-point between Finito and SDCA is interesting in it's own right, as it appears experimentally to have similar robustness to permuted orderings as Finito, but it has no tunable parameters like SDCA.

When the proximal operator above is fast to compute, say on the same order as just evaluating f j , then SDCA can be the best method among those discussed. It is a little slower than the other methods discussed here, but it has no tunable parameters at all. It is also the only choice when each f i is not differentiable. The major disadvantage of SDCA is that it can not handle non-strongly convex problems directly. Although like most methods, adding a small amount of quadratic regularisation can be used to recover a convergence rate. It is also not adapted to use proximal operators for the regulariser in the composite objective case. The requirement of computing the proximal operator of each loss f i initially appears to be a big disadvantage, however there are variants of SDCA that remove this requirement, but they introduce additional downsides.

B Lemmas

Lemma 4. Let f be µ-strongly convex and have Lipschitz continuous gradients with constant L. Then we have for all x and y:

f (x) ≥ f (y) + f ′ (y), x -y + 1 2 (L -µ) f ′ (x) -f ′ (y) 2 + µL 2 (L -µ) y -x 2 + µ (L -µ) f ′ (x) -f ′ (y), y -x .
Proof. Define the function g as g

(x) = f (x) -µ 2 x 2 .
Then the gradient is g ′ (x) = f ′ (x) -µx. g has a Lipschitz gradient with constant L -µ. By convexity, we have [13, Thm. 2.1.5]:

g(x) ≥ g(y) + g ′ (y), x -y + 1 2(L -µ) g ′ (x) -g ′ (y) 2 .
Substituting in the definition of g and g ′ , and simplifying the terms gives the result.

Lemma 5. Let f (x) = 1 n n i=1 f i (x).
Suppose each f i is µ-strongly convex and has Lipschitz continuous gradients with constant L. Then for all x and x * :

f ′ (x), x * -x ≤ L -µ L [f (x * ) -f (x)]- µ 2 x * -x 2 - 1 2Ln i f ′ i (x * ) -f ′ i (x) 2 - µ L f ′ (x * ), x -x * .
Proof. This is a straight-forward corollary of Lemma 4, using y = x * , and averaging over the f i functions.

Lemma 6. We have that for all φ i and x * :

1 n i f ′ i (φ i ) -f ′ i (x * ) 2 ≤ 2L 1 n i f i (φ i ) -f (x * ) - 1 n i f ′ i (x * ), φ i -x * .
Proof. Apply the standard inequality f (y)

≥ f (x) + f ′ (x), y -x + 1 2L f ′ (x) -f ′ (y)
2 , with y = φ i and x = x * , for each f i , and sum. Lemma 7. It holds that for any φ k i , x * , x k and β > 0, with w k+1 as defined in Equation 1:

E w k+1 -x k -γf ′ (x * ) 2 ≤ γ 2 (1 + β -1 )E f ′ j (φ k j ) -f ′ j (x * ) 2 + γ 2 (1 + β)E f ′ j (x k ) -f ′ j (x * ) 2 -γ 2 β f ′ (x k ) -f ′ (x * ) 2 .
Proof. We follow a similar argument as occurs in the SVRG proof [START_REF] Johnson | Accelerating stochastic gradient descent using predictive variance reduction[END_REF] for this term, but with a tighter argument. The tightening comes from using x + y

2 ≤ (1 + β -1 ) x 2 + (1 + β) y 2
instead of the simpler β = 1 case they use. The other key trick is the use of the standard variance decomposition

E[ X -E[X] 2 ] = E[ X 2 ] -E[X] 2 three times. E w k+1 -x k + γf ′ (x * ) 2 = E - γ n i f ′ i (φ k i ) + γf ′ (x * ) + γ f ′ j (φ k j ) -f ′ j (x k ) := γX 2 = γ 2 E X f ′ j (φ k j ) -f ′ j (x * ) - 1 n i f ′ i (φ k i ) + f ′ (x * ) -f ′ j (x k ) -f ′ j (x * ) - E[X] f ′ (x k ) + f ′ (x * ) 2 + γ 2 E[X] f ′ (x k ) -f ′ (x * ) 2 ≤ γ 2 (1 + β -1 )E f ′ j (φ k j ) -f ′ j (x * ) - 1 n i f ′ i (φ k i ) + f ′ (x * ) 2 + γ 2 (1 + β)E f ′ j (x k ) -f ′ j (x * ) -f ′ (x k ) + f ′ (x * ) 2 + γ 2 f ′ (x k ) -f ′ (x * ) 2
(use variance decomposition twice more):

≤ γ 2 (1 + β -1 )E f ′ j (φ k j ) -f ′ j (x * ) 2 + γ 2 (1 + β)E f ′ j (x k ) -f ′ j (x * ) 2 -γ 2 β f ′ (x k ) -f ′ (x * ) 2 .
C Non-strongly-convex Problems Theorem 2. When each f i is convex, using γ = 1 3L , we have for xk = 1 k k t=1 x t that:

E F (x k ) -F (x * ) ≤ 4n k 2L n x 0 -x * 2 + f (x 0 ) -f ′ (x * ), x 0 -x * -f (x * ) .
Here the expectation is over all choices of index j k up to step k.

Proof. A more detailed version of this proof is available in [START_REF] Defazio | New Optimization Methods for Machine Learning[END_REF]. We proceed by using a similar argument as in Theorem 1, but we add an additional α x k -x * 2 together with the existing c x k -x * 2 term in the Lyapunov function.

We will bound α x k -x * 2 in a different manner to c x k -x * 2 . Define ∆ = -1 γ w k+1 -x k -f ′ (x k ), the difference between our approximation to the gradient at x k and true gradient. Then instead of using the non-expansiveness property at the beginning, we use a result proved for prox-SVRG [4, 2nd eq. on p.12]:

αE x k+1 -x * 2 ≤ α x k -x * 2 -2αγE F (x k+1 ) -F (x * ) + 2αγ 2 E ∆ 2 .
Although their quantity ∆ is different, they only use the property that E[∆] = 0 to prove the above equation. A full proof of this property for the SAGA algorithm that follows their argument appears in [START_REF] Defazio | New Optimization Methods for Machine Learning[END_REF].

To bound the ∆ term, a small modification of the argument in Lemma 7 can be used, giving:

E ∆ 2 ≤ 1 + β -1 E f ′ j (φ k j ) -f ′ j (x * ) 2 + (1 + β) E f ′ j (x k ) -f ′ j (x * ) 2 .
Applying this gives:

αE x k+1 -x * 2 ≤ α x k -x * 2 -2αγE F (x k+1 ) -F (x * ) + 2(1 + β -1 )αγ 2 E f ′ j (φ k j ) -f ′ j (x * ) 2 + 2 (1 + β) αγ 2 E f ′ j (x k ) -f ′ j (x * ) 2 .
As in Theorem 1, we then apply Lemma 6 to bound

E f ′ j (φ k j ) -f ′ j (x * ) 2 .
Combining with the rest of the Lyapunov function as was derived in Theorem 1 gives (we basically add the α terms to inequality [START_REF] Mairal | Incremental majorization-minimization optimization with application to largescale machine learning[END_REF] with µ = 0):

E[T k+1 ] -T k ≤ 1 n -2cγ f (x k ) -f (x * ) -f ′ (x * ), x k -x * -2αγE F (x k+1 ) -F (x * ) + 4(1 + β -1 )αLγ 2 + 2(1 + β -1 )cLγ 2 - 1 n 1 n i f i (φ k i ) -f (x * ) - 1 n i f ′ i (x * ), φ k i -x * + (1 + β)cγ + 2(1 + β)αγ - c L γE f ′ j (x k ) -f ′ j (x * ) 2 .
As before, the terms in square brackets are positive by convexity. Given that our choice of step size is γ = 1 3L (to match the adaptive to strong convexity step size), we can set the three round brackets to zero by using β = 1, c = 3L 2n and α = 3L 8n . We thus obtain:

E[T k+1 ] -T k ≤ - 1 4n E F (x k+1 ) -F (x * ) .
These expectations are conditional on information from step k. We now take the expectation with respect to all previous steps, yielding

E[T k+1 ] -E[T k ] ≤ -1 4n E F (x k+1 ) -F (x * )
, where all expectations are unconditional. Further negating and summing for k from 0 to k -1 results in telescoping of the T terms, giving:

1 4n E k t=1 F (x t ) -F (x * ) ≤ T 0 -E[T k ].
We can drop the -E T k term since T k is always positive. Then we apply convexity to pull the summation inside of F , and multiply through by 4n/k, giving:

E F ( 1 k k t=1 x t ) -F (x * ) ≤ 1 k E k t=1 F (x t ) -F (x * ) ≤ 4n k T 0 .
We get a (c + α) = 15L 8n ≤ 2L n term that we use in T 0 for simplicity.

D Example Code for Sparse Least Squares & Ridge Regression

The SAGA method is quite easy to implement for dense gradients, however the implementation for sparse gradient problems can be tricky. The main complication is the need for just-in-time updating of the elements of the iterate vector. This is needed to avoid having to do any full dense vector operations at each iteration. We provide below a simple implementation for the case of least-squares problems that illustrates how to correctly do this. The code is in the compiled Python (Cython) language.

1 2 (

 2 µn+L) , c = 1 2γ(1-γµ)n , and κ = 1 γµ , we have the following expected change in the Lyapunov function between steps of the SAGA algorithm (conditional on T k ):

FunctionFigure 2 :

 2 Figure 2: From left to right we have the MNIST, COVTYPE, IJCNN1 and MILLIONSONG datasets. Top row is the L2 regularised case, bottom row the L1 regularised case.

1 2(µn+L) , c = 1 2γ( 1 -

 111 γµ)n , and κ = 1 γµ ), together with β = 2µn+L

1 #

 1 import random import numpy as np cimport numpy as np cimport cython from cython .view cimport array as cvarray # Performs the lagged update of x by g. cdef inline lagged update (long k, double [:] x, double [:] g, unsigned long [:] lag , long [:] yindices , int ylen , double [:] lag scaling , double a): cdef unsigned int i cdef long ind cdef unsigned long lagged amount = 0 for i in range(ylen ): ind = yindices [i] lagged amount = k-lag[ind] lag[ind] = k x[ind] += lag scaling [ lagged amount ] * (a * g[ind ]) # Performs x += a * y, where x is dense and y is sparse . cdef inline add weighted ( double [:] x, double [:] ydata , long [:] yindices , int ylen , double a): cdef unsigned int i for i in range(ylen ): x[ yindices [i]] += a * ydata[i] # Dot product of a dense vector with a sparse vector cdef inline spdot( double [:] x, double [:] ydata , long [:] yindices , int ylen ): cdef unsigned int i cdef double v = 0.0 for i in range(ylen ): v += ydata[i] * x[ yindices [i]] return v def saga lstsq (A, double [:] b, unsigned int maxiter , props ): # temporaries cdef double [:] ydata cdef long [:] yindices cdef unsigned int i, j, epoch , lagged amount cdef long indstart , indend , ylen , ind cdef double cnew , Aix , cchange , gscaling # Data points are stored in columns in CSC format . cdef double [:] data = A.data cdef long [:] indices = A. indices cdef long [:] indptr = A. indptr cdef unsigned int m = A.shape [0] # dimensions cdef unsigned int n = A.shape [1] # datapoints cdef double [:] xk = np.zeros(m) cdef double [:] gk = np.zeros(m) cdef double eta = props['eta '] # Inverse step size = 1/ gamma cdef double reg = props.get('reg ', 0.0) # Default 0 cdef double betak = 1.0 # Scaling factor for xk. # Tracks for each entry of x, what iteration it was last updated at. cdef unsigned long [:] lag = np.zeros(m, dtype='I') # Initialize gradients cdef double gd = -1.0/n for i in range(n): indstart = indptr [i] indend = indptr [i+1] ydata = data[ indstart : indend ] yindices = indices [ indstart : indend ] ylen = indend-indstart add weighted (gk , ydata , yindices , ylen , gd * b[i]) # This is just a table of the sum the geometric series (1-reg/eta) # It is used to correctly do the just-in-time updating when # L2 regularisation is used. cdef double [:] lag scaling = np.zeros(n * maxiter +1) lag scaling [0] = 0.0 lag scaling [1] = 1.0 cdef double geosum = 1.0 cdef double mult = 1.0reg/eta for i in range (2,n * maxiter +1): geosum * = mult lag scaling [i] = lag scaling [i-1] + geosum # For least-squares , we only need to store a single # double for each data point , rather than a full gradient vector . # The value stored is the A i * betak * x product cdef double [:] c = np.zeros(n) cdef unsigned long k = 0 # Current iteration number for epoch in range( maxiter ): for j in range(n): if epoch == 0: i = j else: i = np. random . randint (0, n) # Selects the ( sparse ) column of the data matrix containing datapoint i. indstart = indptr [i] indend = indptr [i+1] ydata = data[ indstart : indend ] yindices = indices [ indstart : indend ] ylen = indend-indstart # Apply the missed updates to xk just-in-time lagged update (k, xk , gk , lag , yindices , ylen , lag scaling , -1.0/(eta * betak)) Aix = betak * spdot(xk , ydata , yindices , ylen) cnew = Aix cchange = cnew-c[i] c[i] = cnew betak * = 1.0reg/eta # Update xk with sparse step bit (with betak scaling ) add weighted (xk , ydata , yindices , ylen , -cchange/(eta * betak)) k += Perform the gradient-average part of the step lagged update (k, xk , gk , lag , yindices , ylen , lag scaling , -1.0/(eta * betak)) # update the gradient average add weighted (gk , ydata , yindices , ylen , cchange /n) # Perform the just in time updates for the whole xk vector , so that all entries are up-to-date. gscaling = -1.0/(eta * betak) for ind in range(m): lagged amount = k-lag[ind] lag[ind] = k xk[ind] += lag scaling [ lagged amount] * gscaling * gk[ind] return betak * np. asarray (xk)

More precisely, to Option I of Prox-SDCA as described in [11, Figure1]. We will simply refer to this method as "SDCA" in this paper for brevity.

This is because f * i (αi) = inf αi s.t. α i =X i αi ψ * i ( αi).

Note that the first equality below is the only place in the proof where we use the fact that x * is an optimality point.

The first author completed this work while under funding from NICTA. This work was partially supported by the MSR-Inria Joint Centre and a grant by the European Research Council (SIERRA project 239993).