text:
Eugen Rosenstock-Huessy Live! » Volume 19: American Social History (1959)
http://www.erhfund.org/wp-content/uploads/Volume19AmericanSocial%20History1959/AmericanSocialHistory-1959-02.mp3
Editors' note: The original of this lecture is badly distorted and very difficult to understand. This transcription reflects our best judgment about what is on the tape, but we caution the reader that we are less sure of the words than usual.
...{ }. { }? I -- I do not know your {rules}, and I do not -- { } wish to interfere with Los Angeles' {glory}. {And -- they have the social problem of history. But how about the -- I don't know. { }? Anybody {know}? { }.
I said to you last time in all seriousness that the area of a social history of the United States from 1800 until 1960 had to be carved out against very many ambiguities. The first was that history must be predicated on the future--and this is today not recognized at all; many people treat history as a knowledge of a past that has no relation to the future, that is finished, and -- after this, that somehow and somewhere, the future begins and {acts}. To me, that's a heresy. That's the abolition of history. And I have to say something about our relation -- the relation of this course to the future very definitely today.
The past is that part of the future for which you and I must -- are responsible because it already got started and only through us can it continue. So we are only concerned in human history with that past which was created by our forefathers, our antece- -- predecessors so that it may come to full bloom in the end. Take speech. Obviously people at one mysterious time created all the languages. There must have been in the beginning over 100,000 languages, a fertility which favorably compares to the pattern of -- your inventions of the United States the last hundred years. They were the great creations of -- ancient times, languages. Only on this continent, of America there are still, as you know, several thousand of them. In Africa, there are over 10,000. I only mention this because you have, in the social history, to -- be quite clear about this profound and painful question: will languages endure? How many languages will still have to perish? Obviously, many of these 10,000 in Africa {will} -- disappear, in the dictionary, in print. Nobody is going to speak Swahili and Bantu very long anymore. It's even worse in the Amazonas Basin.
So language, the power to speak, you and I are responsible for, and that must go on. Even though you try to abolish language by slang, it can't be helped. Somebody would have to know the language in which the Bible and in which Shakespeare is written. It may not be English. It may be -- but speech, the power to speak is the first historical phenomenon which was created in the past, and for which you and I--although we don't contribute too much to it--you and I, we are {all} responsible. Somebody has to teach the children, really, and not just the
comic strips.
This is very {seriously threatened} today. Society today moves very rapidly to a -- to a situation in which to learn language is unusual. "So what?" is the -- usually the content of most speeches to which I listen. Very few people can speak. That has nothing to do with the individual idiom. It has nothing to do with English, or with Latin, or with Greek. Understand me right. The power to speak is -- the pow- -- the power to confide in each other, to coalesce with each other. All unionism, all co- -- all cohesion of peoples, nations, depends on our power to speak. And the less you think it is necessary that you -- you say -- I just listen to any conversation, and every important name and stated name, beginning from God and ending with the devil, is replaced in your language by the word "thing." "That thing," and then I know you speak of God. Or "somehow." Also, when a person doesn't know quite, he says, "somehow." This is the abolition of speech, and it's rapidly progressing, and has never for -- disappeared so -- so quickly as in our generation. Or I'm afraid I already covered more than one { }.
So that's a serious question in society: how far is this heritage of ours, that we take for granted that human beings do speak--how far is this going to reach the future? So the historical problem of society in this century, and in all technical life, in all industrialized societies at this moment is: will that which started in the past--the power to speak--will this wither on the stem? Will it disappear? Will it be reduced to U- -- what is it?--UCLA? Or -- or will you still understand that it is the University of California at Los Angeles?
One is speech, and the other is shorthand. And you cannot get speech only in the form of AAA, BBB, CCC, et cetera. But most of you, if you count your vocabulary, really excel in replacing all the true words by "something," "somehow," "somewhere," "some-when." We all -- becoming very quickly somebodies. That's not enough. And a society would disintegrate not only, but they would probably be called traitors to our tradition, because in the matter of speech -- we -- we give up what we have inherited and which was created on the first day to last forever. Because people do speak--may I throw this out as a -- an important truth?--people did speak from the very beginning to reach the end of time. The great desire of man to speak was to name their {ancestor} in such a way that he could never be forgotten by now. Take the great chieftain, take the great spirit. All these were -- were processes--speech is -- is process--by which we enter history, stay in history, and are never forgotten, and never extrapolated from history.
If your -- corpse is dead on the ground, your name is still allowed to live on. And there is nothing in human history that doesn't live by this power of speech. There is no other way. You can erect monuments -- from sheet metal, or
from bronze, or from gold, or from mercury, or whatever the last metal is -- you use, uranium--if there is no inscription, and nobody knows who is meant on this { } monument, { }. We cannot monumentalize our existence on this earth. It {can --} no endurance without this power of sacred, important, remembered, and taught names. And since you abolish names if you possibly can, and say, "I know somebody who," you are -- we are guilty -- all of us are guilty in diminishing our inheritance. And if you think how -- what children rea- -- learn today, and what they did learn in 1870 in a Vermont schoolhouse with regard to language, you will see that there is little progress, and very much reduction to nothing.
That's just one example of this strange fact. Strange, because not one of you is prepared to admit it, that history is not a luxury. History is not interesting as a science. History is not for the librarians. History is not even for professors. But history--and not even for you, gentleme- -- ladies and gentlemen, who take courses in history--but history is an action. It is a constant percolating, a constant shifting process by which that from the past, which -- must never perish, is continued, and that which must perish is eliminated. It's a process of metabolism, of elimination, and of continuation.
And let me say once more as a crude, but I think useful, definition, that I shall not treat anything as an historical phenomenon over which there hasn't been passed -- passed judgment, as on the last Judgment Day, whether it deserves to be carried on, or whether it has to be eliminated and buried. And there are such great things, like writing, and speaking, and sharing, and { }, and law that have started long ago, and that you and I are responsible for, lest they perish.
So history is the problem of Rudyard Kipling's recessional, "Lest We Forget." It is a constant action of revival of the past. And to make the point very clearly, you see, there are two kinds of revival, which may tempt you to understand that what I'm doing, because you'll see that all mankind has -- has been doing this for the last 2,000 years--there are two kinds of such revival of his- -- of the beginnings of the future. And I may now, perhaps with your understanding, con- -- define the past.
...which are in danger not to be carried into the future. History is concerned with its own beginnings of the past, which the historian, the history-teller, the mother who tells her child, the pater who tells his -- the confirmation class, those things which have to be kept alive, because they have begun the future at a certain point in the past. And you will admit that to speak English is
not an -- an adventure of 1959, but is the revival of English, you see. And we may be very satisfied if we ever achieve to the eloquence of William Shakespeare again.
But there are two kinds of revival. One is in direct succession. Your child is born; it has to learn English. You feel that you still are capable of doing -- speaking it. You have to revive in this brute--in this little brat--the power to speak. Yes, I don't think that children by themselves are very celestial. I don't share this adoration of children. For the historian, children endanger history.
Yes, they have to be brought up to live it. I mean, they are out of history, this side of history. They do not automatically represent the future. They are handicaps to the future unless you bring them up to parity. You make them, for example, speak real English, otherwise they're just below the level that already was attained a hundred years ago. And I think you will, if you look around, it's obvious that many more people in our society are historically misfit to -- to -- to carry anything, to -- to inherit the earth, to bring anything to fruition in the next generation. They send their children to kindergarten. They send them to feebleminded schools, or to high-endow- -- gifted schools, or whatever the nomenclature is. But they certainly dump them. And by dumping them, they leave it to the organized forces of -- this government, or the Church, or whatever it is, to learn what they should learn from their parents. And therefore we are in a -- at this moment in a turmoil to find the institution by which children should be initiated to the same stamina which they have inherited from the past. You just have to think of juvenile delinquents. Why do they exist? Because between 14 and 21, nobody in this country is initiated through hardship. It's the same where any primitive tribe initiated its young to real life.
And if you do not experience and you do not learn to -- to suffer pain, and to love, and feel affection for several years in a serious manner, you just remain as stupid -- if you don't learn to listen, and to obey, and -- not -- learn to speak. Learn -- feeling, hearing, suffering, and loving are great acts, and they have to be dinned into people by great acts of education and training. Instead, you see that from 14 to 21 or 22, as long as you are in this college, you are -- we are doomed to { } examinations. That's not life.
So I think that at this moment, the ordinary revival, in the next generation, which I hear at this moment {called} "revival," is threatened. The ordinary tradition -- you call it "tradition," "continuation," "education," call it as ever you like--I prefer to call it "revival," because here you have millions of newborn fishes. They are fishes because they can't speak. And certainly they can't obey. And
they don't obey. And they aren't even asked to obey. They are made happy. They are sent to the psychoanalyst--or the parents are sent to the psychoanalyst--and -- because the -- they -- the routine process of obedience, and -- and teaching doesn't function. And anybody who isn't constantly in the stream of history falls sick. Man can be made so plastic, that if he isn't filled with the -- the {noted} rhythm of constant speech, song, art, religion, prayer, historical anecdotes, speak -- speech in the highest sense of the word, he becomes mere self. And I had yesterday a terrible talk with some of you -- group of you who always insisted that they themselves didn't think so, and they had all themselves an individual opinion, and of course no understanding whatsoever, because these poor children didn't know that history is a big stream in which we swim; and it is nothing to be looked upon from the bookstore or the bank, and criticized by oneself. You are in the midst of -- of life.
I've made -- stressed this revival. It is necessary in every living generation {which is meant} to come to life, to real life, to historical existence, to action, to responsibility, to love, affection, courage, creativity.
By this story, which I heard a few weeks ago--it -- was told to me by a South African, Laurens van der Post. You -- some of you may have read his books and -- about the situation in Africa. He is a South African, {Boer} { } married to an Englishwoman, and he has written some very famous books on the South African situation. His most beautiful and most recent book is on the Kalahari Desert. And he made it in the Kalahari Desert. And it has to do with speech, as a model case of how speech is revived in every generation. And for us, who are losing it, this power, at this moment so considerably, I think it -- it exemplifies what is threatening the historical process in the western world {at this moment}. And Mr. Laurens van der Post had a grandfather who, in his struggle with the bushmen, killed many of them with his, of course, superior gunnery. But two of them, as young boys, he caught and kept at the house, and cared for them very tenderly, as a matter of fact. They became old men in the -- his grandfather's house. And this young Laurens came to love these people, and they came to love him. And they said to him that they would send him to his -- their tribe. When he was grown up, he should go there and report, and hold certain things, and he would be well received. And they -- the -- these warriors at home in the desert would then tell him the true story of the bushman.
So when he -- was -- {began on the strength of this}, and so finally he had an occasion to do so; and he went into the Kalahari Desert, and he joined these bushmen, whose language he knew, and gave them the message, and they were very hospitable. And he said, "Now tell me your stories. I'm eager to listen."
And they said, "Now, you wait a minute. You first have to be -- to go
hunting with us."
He didn't quite understand, but { } all the seasons went by, and the different kinds of hunt. Finally the big elephant hunt. And after he had proved to be a co-hunter, a co-warrior of the tribe, because hunter and warrior of course is the same status of full-fledged allegiance, they sat down and he was allowed to listen to their tales. And these tales were the legislation, the constitution, the history, the poetry, the religion of the tribe.
In this living tradition of telling these stories, these people felt, he said, that they had their whole {pleasure} of life. This made them into conscious, living beings. And anybody who was allowed to listen to these stories was invited, instilled with the faith, the courage, the confidence of this tribe. Therefore, only a member was allowed to listen. And as hospitality goes, you know, you take a man -- into your home under the consideration that for the time being, he is a member of your household. In the same sense, he had to hunt first with these people, you see, in order to make sure that he wouldn't look like a scientist or an historian in the western world on this poor tribesman, but would acknowledge his equality with them, and he would treat them not objects of his curiosity, exploit them, write a book about them, and get a doctor's degree for that, but that he would settle -- settle down with them and share this living process of bringing to light the past in the stories told. That's all they had. They had no libraries; they had no money; they hardly had dress. But they had this treasure of living traditions which come to life in every one who is initiated into this {tribe}.
And I think that's the relation to the creation of speech by which the living generation is revived -- or the language is revived, this treasure spirit is revived in the hearts of the newborn. As I say, they were animals who become human beings only through this action. That's their baptism of fire. Baptism is not a scene -- a scene in the Church. It is the same, you see. Baptism is the first word said over a child; it gets a name. And from that moment on, it can be filled with speech. And so baptism simply unlocks the door for the historical existence of a human being. It's the same with any ritual. Take circumcision in the Jewish community. At some moment, this inheritage begins. That's why, for example, circumcision and -- before Judaism never was practiced on the babies, but it was only {unlocked} if -- the baby was only -- the -- the youngborn was only called into life much later. Circumcision went with the hardships of initiation. And it is important, I think, to recover this sense of these rituals, because originally all these introductory rituals didn't happen at birth, and were not put on the shoulders of the parents or the godparents, but were just put on the young man himself. And he was told that this was his second birth, which I call the "revival."
So it's not my invention that I call this "revival." But it was the deep feel-
ing of these people that this was their second birth. They become only really fullborn, when the stream of history enters their heart and their consciousness.
There is a second kind of revival, and if you -- look around this campus, we are even overwhelmed by this kind of other revival so that you have lost sight of the first. The first has to do with the next generation. But we, as you know, have lived through an era which is called the Renaissance. We have Olympic Games, and we have Moorish, and { }, and Gothic, and pseudoGothic, and pseudo-Gothic cathedrals with barbershops inside. What is this?
Our history is -- is longer than the history of the Kalahari tribe. The Kalahari tribe in Africa is older than we in fact, but not in consciousness. What they have to convey is a short history. It's compressed. The memory of a tribe is usually six, seven generations long. And if we would live like the Mormons in Utah, only on a truly American tradition, then this would also be here a shortlived story. We would only have the natural {progress} the Mormons have, to make every young Mormon, you see, into a true Mormon by sending him abroad. As you know, that's their practice. It's a very wise one. In the Mormons, you have an example of the tribal form of existence, with a short-lived memory, because after all the Mormons are no older than {150} years now. As a matter of fact, the Mormons very much coincide with the -- with the period of -- with which we are dealing here in this course, because Joseph Smith, as far as they record, was born {1805} -- 1845, you see. And proselytizing all of America at this { }. { } see, right across from the Longfellow { } there is a huge Mormon temple, opened two years ago. Quite {a fact}.
A very important fact. But the Mormons don't have your and my problem of any Renaissance buildings, from Greek and Roman architecture, and Gothic and -- medieval architecture. They are plagued by an open history through all the ages. So as long -- as soon as you go before our period, from 1800 and 1906, and have to cover a -- the human history, beginning in 8000 B.C., all the rest is bunk. Don't believe in any of the geological figures for man, because -- all { }; {mythology}. And -- but it's long enough to this day, I remind you. And since we today have to cover the ground from the creation of speech to -- through the creation of architecture, and temples, and priests, to the creation of literature and Greece and to the writing of the Bible, and of prophecy and Judaism, through Christianity, you see, through the Inquisition, the Crusades, and what-not, you can imagine that we {usually} are hard-put to cover this ground constantly. Not one child can be really introduced into the great achievements of all these periods at one { } of our power. So we have this second kind of revival, which you have learned to call the Renaissance { }.
We select one of the most forgotten periods, which seem to contain impor-
tant truth and {urgent} truth -- standing in need of regeneration, of rebirth. We take that out, and we give a new second birth to these {very} remote, you see, things, from whom we already have been separated so long that there had to be a special effort { } what I have done at the moment with the Kalahari Desert -- is a { } act, you see, of a second type of regeneration, trying to interest you in accepting that go -- has happened long before our usual, you see, arena of thinking.
And so the second gen- -- or regenerations in history are not dealing with the young, trying to bring them up to {pari- --} history, but are dealing with the grownups' loss of perspective. And we are entering at this moment obviously a period in which the Roman and Greek Renaissance will give way to another kind of renaissance. And from 1960--I'm sure it has already begun, with the two world wars--the renaissance of a still more remote past -- from you and me, and is the -- of universal interest to the human race not yet in this country. Not an American problem. It's not a European problem. It's not an African problem. But to go before Jews and Greece in our {unearthing} order, creativity and law is today the order of the day. We -- we'll talk about this at the end of the course again. But I want to announce today that one of the topical questions of any social history that tries to keep perspective and direction, and tries not to lure you into the swamp of some antiquarian past, but wants to open a path into the future, would have to be the understanding that we go from renaissance to renaissance.
In order to set your mind at rest from the very beginning for this rather puzzling second regeneration, which is the action of educators, of artists, of historians, you see, of linguists, of prophets, you, by the way, of creature -- I gave you already the example of the Kalahari Desert; I think that without this example, I cannot wake you up to what we are { }. Initiation is the order of the day for the next 200 years in our society. You cannot just go to high school, become a factory hand, or a clerk in an office, or a type- -- secretary, a typist, without losing your birthright as a member of human so- -- history, of human society. That isn't good enough. What -- how to do this is a pain in the neck for any serious-minded person. I have done -- spent all my life since 1912 in trying to find the moral equivalent of war, of which William James spoke at that time before his death. And this is what initiation is: it's the moral equivalent of war. And {today} to find this for young women is a very serious business. And you haven't solved your educational problems as long as you think they consist in testing the IQ of a person, because the ladies will pardon me, to hell with IQs. That's -- doesn't make an historical person -- character in a human being, your IQs. And this is before us. It hasn't been solved. And as you know, this -- you just read the newspapers, and you know every day that some youngster is going astray, because he isn't given this necessary direction into initiation, into society. { }
can't do this by {polls}.
It may interest you that this wandering, this migration, this hopping around from one thing to be regenerated in the past to the next, has -- going on under our noses for the last thousand years, at this moment, you go into the books of the philosophy, for example, the highest appreciation at this moment is given not to Aristotle and Plato, but to the pre-Socratics. That is, we are gradually moving backward within the Greek and Roman renaissance. The excavations in Delphi {date} these people {in the} { } because there we come to the earliest beginning of Greek religion. Mr. Robert Graves, who--you know him perhaps, his wild genius?--has written a very book -- a very fine poem, "Hercules, My Shipmate." Wha- -- has anybody seen it? Who has? No response? He's a contemporary, so you are obsolete { }.
"Hercules, My Shipmate," an excellent book on the Argonauts and {Iaethon}. And it's pre-Homeric. What I'm driving at is, that at this moment, preHomeric Greece -- Greek, for example, {Mycenae}, you see, {Klosters}. The language, as you know, has been discovered which Nestor and Achilles spoke. We have now contemporary potsherd in which the name Achilles and Athene appear, in 1200 B.C. That is, we are 400 years before Homer -- the Homeric poems were written on which a professor of history would be { } and -- and educated { } a hundred years ago. We are going backward in the regeneration of Greece. And the same, by the way, of Rome. Etruscan antiquities are now higher valuated than the Roman ones. You will -- may have heard that there was a most excellent exhibition of Etruscan antiquities in Zrich, Switzerland, last year which took the country by storm. And I think even some of you tour- -- American tourists may have been misled into this ex- -- exhibition.
But the -- Renaissance of Rome and Greece began when you think of Dante's poem with Virgil. Now Virgil was a contemporary of Caesar Augustus and of Augustus -- of Julius Caesar and Caesar Augustus. And anybody who has ever heard even, in the strange, excellent -- strange book which I found in the college bookstore called High Mark or -- Outlines of Dante, Outlines of Religion, Outlines of the University of California, Outlines of Examinations -- how do you call it, I mean { }?
(College Outline Series.)
Yes, yes. Wonderful institution.
There even Dante had to be mentioned. Now he is the first of these regenerators, gentlemen, of the Greek and Latin Renaissance. But his only hero is -- is Virgil. That's only a few years B.C. He died in I think 19 B.C. Then we come to Thomas Aquinas, of whom you may have heard also, through this wonderful institution. He was a great thinker in -- 13th century, and he uses Aristotle. Now Aristotle lived in -- is a contemporary of Alexander the Great. That's 300 years backwards from Julius Caesar, you see. Now 200 years later, with the -- in Florence, the first Platonic academy was founded, around 1456. That's 200 years after the life of Thomas Aquinas. And Plato is, as you know, the teacher of Aristotle. So we go back one more step, you see. Then Pope, and in Germany Voss, and -- translate Homer. And Homer becomes popular, and the Greek tragedy. Or you can go to the 17th century in our history, and you come to Racine and Corneille, and they revive the Greek tragedy. Of course, they are tragedians, and not philosophers. And today, as I said, Mr. Robert Graves tries to compete with Homer by writing the epics of the Argonaut.
So it's very -- a very wonderful and mysterious part of our own history that while we are going forward to build Sputniks, and railroads, and airplanes, at the same time, we went backwards more and more, you see, away from the beginning of our era, digging up the {far-ago} past, and using them as educational food and asking every youngster to know -- {fill} himself with architecture, and forms of thinking, like Platonic ideas, and Aristotelian realism, and what-not, and so combining this second revival, you see, of a lost time with our own progress.
Now human beings, gentlemen, are human only as soon -- or as long as they retain the power to move forward and to look backward at the same time. The difference between a natural animal, you see, and a -- human beings, from the very beginning of man's creation on this earth, is not that both have bowels, and one goes upright, and the other crawls on the ground. It's a much more simpler freedom in humanity. And anybody who does it is human, and anybody who can't do this has not yet reached the sto- -- the stage of humanity.
In this sense, this regeneration, this Renaissance, which you think is a special period in history, is nothing but a special application of this constant principle: a man is free who at the same time can look backward to the law which has come down to him as tradition, and can look forward, and then decide whether to break the law or whether he has to continue. Because we are all lawbreakers, and we are all law-abiding. And anybody who is only law-abiding is not yet a human being. And only -- and on- -- anybody who is only a law-breaker is not yet a human being. Your and my problem is to know when to break the law, and when to abide by it. That's very serious. This is called Christian liberty. And we live in a Christian era, and you can't leave it. The full historicity of
human beings was proclaimed 1959 years ago, when a child was born that was at the same time under the law and {in liberty}. He was Joseph's son and He was the son of God at the same time. That's another way of stating the truth, which I have tried to reformulate, so to speak, in primitive -- more primitive terms, that we are free for any future, and that we are bound by the whole past, at the same time. Any girl who elopes, or any Juliet -- in Romeo and Juliet knows that she can elope, but she has to pay the penalty.
That is, every step forward costs a price. It costs a price of being delivered, of being emancipated from the past. And where this emancipation has gone so far, that everybody in this country has to think now he has a private religion, a private opinion, a private conviction, a little { } as an individual, and has lost all direction in history, there comes along some kind of regenerative, common effort from humanity to impose on him some discipline from the past that he has forgotten. That's why I think initiation will be in order, you see, for the last -- next 200 years, as a real question. As philosophy was in order for the clergy of the Middle Ages, you make out of these childish superstitious people, you see, intelligent, and fruitful, and truth-seeking, scholastic schoolmen. Each period is threatened with the same loss of direction.
Now you -- remember last -- last time, I tried to convince you--I don't know if I succeeded--that any future is only our common future so long as we keep alive the true power of the future: that is, to change direction in solidarity. Not the single individual. You and I may seem to be able to change direction. We have to take the whole society with us; before, it is fruitless; it's sterile. You people from the newspapers know this very well. They know many more things than the ones they are allowed to print.
These were the two principles I laid down; and I come back to them, and I haven't -- done nothing but to {catch} this principle today, to give you some substantial filling material to understand why the whole of your future consists--or not the whole { }--we must keep as our common destiny the avenue open to change together our direction. Otherwise we can no longer be human beings. If we are predetermined, if the whole future at this moment is just rushing into some kind of given form, like a -- in a -- in a steel -- foundry, if we are nothing but melting-pot metal, to be melted down into some form already predetermined by our technical civilization, then we would have ceased to be crea- -- creatures of our { }. We would just become -- we become { }. And if we would not believe it to take our sisters and brothers with us into this {future}, we would destroy the so- -- the fabric of society, because we would deny the solidarity that all men together are -- man must move at once. Or at least not at once, at least in such a piece that the stragglers from the end, from the rear, you see, and the avant-garde may keep the cohesion and their peace. The whole
army of mankind must move somehow in -- in unity. Can you see this?
Now, obviously therefore the historical process is a slow one, and yet it is a constantly renewing one, because any one moment, we have to be -- assert our freedom to change direction. { } last time to change direction from the Cadillac to the Volkswagen. That would be a change in direction, because for the first time the Uni- -- people of the United States would abandon their -- their notion by which they are known all over the world: bigger and better. It would -- suddenly be smaller and better. { }. And I don't know if { }.
[tape interruption; end.]

redpajama_set_name: RedPajamaCommonCrawl


text:
\section{Introduction}

In this work, we study the problem of clustering while preserving the privacy of individuals in the dataset.  Clustering is an important routine in many machine learning tasks, such as image segmentation \cite{yang2017towards, patel2013latent}, collaborative filtering \cite{mcsherry2009differentially, schafer2007collaborative}, and time series analysis \cite{mueen2012clustering}. Thus, improving the performance of private clustering has a great potential for improving other private machine learning tasks. We consider the clustering problem with differential privacy, which is a privacy framework that requires the algorithm to be insensitive to small changes in the dataset \cite{dwork2014algorithmic}. Formally, suppose we are given a metric $d$, a set $V$ of $n$ points in the metric, and a (private) set of demand points $D \subseteq V$.  Our objective is to choose a set $F \subset V$ of size $k$ to minimize the following objective:
\begin{equation}
    \sum_{v \in V} \min_{f \in F} d(v, f)^p
\end{equation}
This is the $k$-medians problem when $p=1$ and the $k$-means problem when $p=2$.

The $k$-medians problem has been studied extensively in the literature. Previous work in \cite{kariv1979algorithmic} proved that $k$-medians is NP-hard. There is a long line of works on approximation algorithms for $k$-medians without differential privacy \cite{chrobak2006reverse,arya2004local,charikar2002constant, jain2001approximation, jain2003greedy,BPRST17}. The state of the art is a $2.675+\epsilon$ approximation by~\cite{BPRST17}. The private $k$-medians problem was studied in \cite{gupta2010differentially}, which shows that any $(\epsilon_p,0)$-differentially private algorithm for the $k$-median problem must have cost at least ${\sf OPT} + \Omega (\Delta \cdot k \ln (n \slash k) \slash \epsilon_p)$, where ${\sf OPT}$ is the optimal cost. The paper also provided a polynomial time  $(\epsilon_p,0)$-differentially private algorithm that solves the problem with with costs at most $6{\sf OPT}  + O(k^2 \log^2 n\slash\epsilon_p)$. \cite{stemmer2018differentially} states a variant of the algorithm for $(\epsilon_p, \delta_p)$-differential privacy with cost
\begin{equation*}
  O \Big(  {\sf OPT} + \frac{\Delta k^{1.5} }{\epsilon_p} \log\frac{n}{\beta} \sqrt{\log n \cdot \log(1\slash \delta_p)}\Big)
\end{equation*}
where $\beta$ is the failure probability.

\textbf{Our contribution} is a new polynomial time $(\epsilon_p, \delta_p)$-differentially private $k$-medians algorithm with constant multiplicative factor and improved additive error:
\begin{equation*}
     O\left({\sf OPT} + \frac{k\Delta}{\epsilon_p}  \log n \log\left(\frac{e}{\delta_p}\right)\right)
\end{equation*}

Note that our additive error is linear in $k$ instead of $k^{1.5}$ as in the previous work by \cite{gupta2010differentially,stemmer2018differentially}, and almost matches the lower bound of \cite{gupta2010differentially} up to lower order terms (their original lower bound is for $(\epsilon_p,0)$-privacy but it can be extended to $(\epsilon_p,\delta_p)$ privacy with inverse polynomial $\delta_p$). By using the non-private algorithm of \cite{BPRST17} as a subroutine, our multiplicative factor is $6.35+\epsilon$, which is slightly worse than 6 from~\cite{gupta2010differentially}.

The $k$-means problem has also been studied extensively with a long line of works on privacy preserving approximation algorithms~\cite{BDMN05,NRS07,FFKN09,feldman2017coresets,balcan2017differentially,stemmer2018differentially}.
As an extension of our techniques, we also provide an $(\epsilon_p, \delta_p)$-differentially private algorithm for the Euclidean $k$-means problem with constant multiplicative error and better additive cost compared to previous work (see table \ref{tab:compare}). Our algorithm has cost:
\begin{equation*}
O\big({\sf OPT}  +  k\log n +d^{0.51} (\log\log n)^{2.53} \left(k\log k \right)^{1.01} \big)
\end{equation*}

Again in this setting, our additive error is almost linear in $k$ as opposed to $k^{1.5}$ in previous work~\cite{stemmer2018differentially}.

In addition to improved performance guarantee, our $k$-medians and Euclidean $k$-means algorithms use a non-private clustering algorithm as a black-box. This allows practitioner to control the trade-off between approximation guarantee and runtime of the clustering algorithm and even use heuristics with good empirical performance.

\textbf{Our techniques} for $k$-medians and Euclidean $k$-means include two main steps. In the first step, we iterate through distance thresholds from small to large and apply a differentially private Maximum Coverage algorithm to select centers that cover almost as many points as the optimal solution at those thresholds. For the second step, we create a new dataset based on the potential centers and apply a non-private clustering algorithm on this dataset. The new dataset is created by moving each demand points to the nearest potential center, and then applying the Laplace mechanism \cite{laplacenoise} to report the number of points at each potential center. This makes sure that privacy is preserved for the new dataset and no additional privacy cost when we apply the non-private clustering algorithm in the final step.

\section{Related Works}

\begin{table}[]
\begin{tabular}{l|c|c|c}
\textbf{Reference}           & \textbf{Objective}  & \textbf{Multiplicative Error} & \textbf{Additive Error}\\ \hline
Gupta et al. \cite{gupta2010differentially},&    $k$-medians\footnote[1]{The bound in \cite{gupta2010differentially} is for  $\epsilon$-differential privacy, while \cite{stemmer2018differentially} is for $\delta$-approximate $\epsilon$-differential privacy.}              & O(1) & $O(k\log n)^2$        \\
 Stemmer et al.  \cite{stemmer2018differentially} &&&  $O(k \log n)^{1.5}$ \\ \hline
\textbf{Ours} & $k$-medians  & $O(1)$ & $O(k\log n)$ \\ \hline
Feldman et al. \cite{feldman2017coresets}  & Euclidean $k$-means & $O(k \log n)$ & $O\left(k\sqrt{d} \log (nd) \cdot 9 ^{\log^* \left(|X| \sqrt{d}\right)}\right) $ \footnote[2]{ \cite{feldman2017coresets} studies the discrete $d$-dimensional space $X^d$.}\\ \hline
Balcan et al. \cite{balcan2017differentially}  & Euclidean $k$-means & $O\left(\log^3n\right)$ & $O\left(\left(k^2+d\right)\log^5 n \right)$ \\ \hline
Stemmer et al. \cite{stemmer2018differentially} &  Euclidean $k$-means & $O(1)$ & $ O\big((k \log \left(n\log k\right))^{1.5}$  \\ &&& $+d^{0.51} (\log\log n)^{2.53} \left(k\log k \right)^{1.01} \big)$
\\ \hline
 \textbf{Ours}& Euclidean $k$-means& $O(1)$ & $O\big(k\log n $ \\
 &&& $+d^{0.51} (\log\log n)^{2.53} \left(k\log k \right)^{1.01} \big)$\\
\end{tabular}
\caption{\label{tab:compare}
Comparison of our clustering algorithms with prior works, omitting dependence on $\epsilon_p, \delta_p$.}
\end{table}
Table \ref{tab:compare} summarizes the performance of previous work in comparison with our algorithms. In the table, only the work by \cite{gupta2010differentially} is for $(\epsilon_p,0)$-differential privacy, while the others are for $(\epsilon_p, \delta_p)$-differential privacy.  As mentioned above, \cite{gupta2010differentially} gave the first private $k$-medians algorithm with a constant multiplicative approximation and additive error polynomial in the number of centers and logarithmic in the number of points. The algorithm uses the local search approach of \cite{arya2004local}. Our algorithm, on the other hand, can be used with any non-private $k$-medians algorithm.

For the Euclidean $k$-means problem, \cite{balcan2017differentially} proposes the strategy of first identifying a set of potential centers with low $k$-means cost, then applying the techniques of \cite{gupta2010differentially} to find the final centers among the potential centers. However, their  potential centers are only guaranteed to contain a solution with multiplicative approximation $O\left(\log^3 n\right)$. This result was improved by \cite{stemmer2018differentially}, which can construct a set of potential centers containing a solution with constant multiplicative approximation.

Another approach for the $k$-means problem is via the $1$-cluster problem. Given a set of input points in $\mathbb{R}^d$ and $t\leq n$, the goal is to find a center that covers at least $t$ points with the smallest radius. The work of \cite{feldman2017coresets} shows that the $k$-means problem can solved by running the algorithm for the $1$-cluster problem multiple time to find several balls to cover most of data points with $O(k\log n)$ multiplicative error. \cite{nissim2018clustering} proposed an improved algorithm for the $1$-cluster problem, resulting in a differentially private $k$-means algorithm with $O(k)$ multiplicative error.

\section{Preliminaries}

\subsection{Differential privacy}
Differential privacy is a privacy definition for computations run
against sensitive input data sets. Its requirement, informally, is that the computation behaves similarly on two input dataset that are nearly identical. Formally,

\begin{definition} (\cite{dwork2006our})
A randomized algorithm $M$ has $\delta_p$-approximate $\epsilon_p$-differential privacy, or $(\epsilon_p,\delta_p)$-differential privacy, if for any two input sets $A$ and $B$ with a symmetric difference which has a single element, and for any set of outcomes $S \subseteq Range(M)$,
    \begin{align*}
\Pr[M(A) \in S]  \le  \exp(\epsilon_p) \times \Pr[M(B) \in S] + \delta_p\; .
  \end{align*}
\end{definition}

If $\delta_p = 0$, we say that $M$ is $\epsilon_p$-differentially private.
An algorithm with $(\epsilon_p,0)$-differntial privacy ensures that the output $M(A)$ is (almost) equally likely to be observed on neighboring datasets, whereas in $(\epsilon_p,\delta_p)$-differential privacy, $\delta_p$ dictates the probability that $\epsilon_p$-privacy fails to hold \cite{dwork2006our}. In this way, $(\epsilon_p,\delta_p)$-differential privacy is a relaxation of $\epsilon_p$-differential privacy. We use an error parameter $\epsilon$ for utility and we use $\epsilon_p$ and $\delta_p$ to denote parameters for differential privacy (or $\epsilon_s$ and $\delta_s$ for algorithm \ref{alg:setcover}, to differentiate privacy parameters to different algorithms).

One of the most basic constructions for differentially private algorithms is the Laplace mechanism.

\begin{definition} ($L_1$ sensitivity)
A function $f: \mathbb{N}^{|X|} \rightarrow \mathbb{R}^k  $ has $L_1$ sensitivty $\Delta f$ if
$ \| f(A) - f(A') \|_1 \leq \Delta f$ for all $A,A'$ with a symmetric difference which has a single element.
\end{definition}

\begin{theorem} (Laplace mechanism  \cite{laplacenoise})
\label{thm:laplacemech}
Let function $f: \mathbb{N}^{|X|} \rightarrow \mathbb{R}^k  $ have $L_1$ sensitivty $\Delta f$ and $\epsilon_p > 0$. Mechanism $M$ that on input $A$ outputs  $f(A) + Lap(\frac{\Delta f}{\epsilon_p})$ is $(\epsilon_p,0)$-differentially private, where $Lap(\frac{\Delta f}{\epsilon_p})$ denotes a random variable following Laplace distribution with scale parameter $b = \frac{\Delta f}{\epsilon_p}$.
\end{theorem}

Another tool for construction of differential private algorithm we use in this work is the exponential mechanism. This construction is parameterized by a query function $q(A,r)$ mapping a pair of input data set $A$ and candidate result $r$ to a real valued. With $q$ and a privacy value $\epsilon_p$, the mechanism selects an output in favor of high score value:
  \begin{align}
    \label{eqn:expmech}
Pr[{\mathcal E}_q^\epsilon(A) = r]  \propto & \exp(\epsilon_p q(A,r))
  \end{align}
\begin{theorem}
\label{theorem:expLoss} (\cite{mcsherry2007mechanism})
  The exponential mechanism, when used to select an output $r \in R$ gives $2\epsilon_p\Delta$-differential privacy, letting $R_{\sf OPT}$ be the subset of $R$ achieving $q(A,r) = \max_r q(A,r)$, ensures that
\begin{align*}
    \Pr[q(A, \mathcal{E}_q^\epsilon(A)) < \max_r q(A,r) -
    \ln(|R|/|R_{\sf OPT}|)/\epsilon_p - t/\epsilon_p] \leq \exp(-t)
 \end{align*}

\end{theorem}

\subsection{Maximum Coverage}

 \begin{wrapfigure}[12]{R}{0.5\textwidth}

\begin{algorithm}[H]
\caption{Maximum Coverage}
\label{alg:setcover}
\DontPrintSemicolon
\LinesNotNumbered
\SetAlgoLined
\KwIn{Set system $(U,\mathcal{S})$, a private set $R \subset U$ to cover, $\epsilon_s, \delta_s$, $m$ }

 $i \leftarrow 1$, $R_i = R$, $\mathcal{S}_i
    \leftarrow \mathcal{S}$. $\epsilon' \leftarrow \epsilon_s/2\ln(\frac{e}{\delta_s})$.

    \For{$i=1,2,\ldots,m$} {
  Pick a set $S$ from $\mathcal{S}_i$ with probability
    proportional to $\exp(\epsilon' |S \cap R_i|)$.

Output set $S$.

 $R_{i+1} \leftarrow R_i \setminus S$, $\mathcal{S}_{i+1} \leftarrow \mathcal{S}_i - \{S\}$.
}
\end{algorithm}

  \end{wrapfigure}

Our differentially private $k$-medians algorithm solves the Maximum Coverage problem as a subproblem.   The Maximum Coverage problem is defined as follows: on a universe $\mathcal{U}$ of items and a family $\mathcal{S}$ of subsets of $\mathcal{U}$, and a parameter $z$, the goal is to select $z$ sets in $\mathcal{S}$ to cover the most elements of $\mathcal{U}$. Formally, we are looking to find
\[\arg\max_{\mathcal{C}\subseteq \mathcal{S}, |\mathcal{C}| = z} \Bigl|\bigcup_{c\in\mathcal{C}}c\Bigr|.\]

Our approach for solving private Maximum Coverage is based on the Unweighted Set Cover algorithm in \cite{gupta2010differentially}. To preserve privacy, algorithm \ref{alg:setcover} chooses sets using the exponential mechanism, with probability related to the improvement in coverage caused by choosing the set.

Assume that there exists a selection of $z$ sets that covers $\mathcal{U}$.  A classic fact for the maximum coverage problem is that if we build the family $\mathcal{C}$ by always selecting the item in $\mathcal{S}\setminus\mathcal{C}$ that covers the largest number of uncovered elements in $\mathcal{U}$, then after $z$ iterations, $|\cup_{c\in\mathcal{C}}c| \geq (1- 1/e) |\mathcal{U}|$. Here we show an observation that will be useful for our algorithm later. The proof is in the appendix.
\begin{lemma}
\label{lem:2eps}
For $\epsilon > 0$, if we always select a set that covers at least half as many uncovered elements as the set that covers the most uncovered elements, then after $2z\ln 1/\epsilon$ iteration, \(\Bigl|\bigcup_{c\in\mathcal{C}}c\Bigr| \geq (1- \epsilon) | \mathcal{U}|\).
\end{lemma}

\section{Private k-medians}
\label{sec:privatekmedians}
Given a set of points $V$, a metric $d: V \times V \rightarrow \mathbb{R}$, a private set of demand points $D  \subseteq V$, and a value $k < |V|$, the objective of the $k$-medians problem is to select a set of points (centers) $F \subset V$, $|F| = k$ to minimize $\text{cost}(F) = \sum_{v \in D} d(v,F)$, where $d(v,F) = \min_{f \in F} d(v,f)$. Let $\Delta= \max_{u,v \in V} d(u,v)$ be the diameter of the metric space. We use $\epsilon$ as the approximation parameter for maximum coverage problem in lemma \ref{lem:2eps}, and $\epsilon_p$ and $\delta_p$ as privacy parameters. Let $B_t(v)$ be the ball of radius $t$ centered at $v$ i.e. the set of all points in the metric space within distance $t$ from $v$.

Our approach is based on the Maximum Coverage problem. One way to compute the clustering cost is by computing for every distance threshold $t$, the number of points within distance $t$ from the centers and integrating the counts from $0$ to the maximum distance. Thus, if for every threshold $t$ the number of points farther than $t$ from the our solution's centers is not much more than the number of points farther than $t$ from the optimal centers, then our cost is not much larger than the optimal cost. Thus, our algorithm goes through distance thresholds from small to large and tries to ``cover'' as many points as possible using fresh centers every time. For each threshold, we aim to cover $1-\epsilon$ times the number of points the optimal solution can cover. The result is that our clustering cost is not much larger than the optimal cost, albeit using more centers. Since we use exponentially growing thresholds, we only use $O(\log n)$ times more centers, which results in a small error due to privacy noise. The full algorithm is described in Algorithm~\ref{alg:kmedian}.

\begin{algorithm}[]
\caption{The $k$-medians algorithm}
\label{alg:kmedian}
\DontPrintSemicolon
\SetAlgoLined
\KwIn{ a set of points $V$, a private set of demand points $D \subseteq V$, a metric $d$, $\epsilon$, $\epsilon_{p}$, $\delta_p$}

$V'=D, C = \emptyset, r = \lc 1+\log_{1+\epsilon}n \right\rceil$

\For{$i$ from $1$ to $r$}{
Set $t_i = (1+\epsilon)^{i-1}\Delta/n$

Run algorithm \ref{alg:setcover} for the set system $\mathcal{U}=V, \mathcal{S}= \{B_{t_i}(v) \cap V': v \in V\}$, with $\epsilon_{s} = \frac{\epsilon_p}{2}, \delta_s = \delta_p$ for  $m = 2k\ln(1 \slash \epsilon) $  iterations to get $C_i$

$V_i = \bigcup_{v\in C_i} B_{t_i}(v) \cap V'$

$V' = V' \setminus   V_i $

$C = C \cup C_i$
}

Assign each point in $D$ to its closest point $c \in C$

Let $n_c$ be the total number of points assigned to $c$ for each $c\in C$

For each $c\in C$, set $n_c' = n_c + Y_c$ where $Y_c \sim \text{Lap}\left(\frac{2}{\epsilon_p} \right)$

Run a k-medians algorithm to select $k$ centers from $V$, with demand points at each $c\in C$ with multiplicity $n_c'$
\end{algorithm}

The algorithm begins with the discretization of distance thresholds.  The goal is similar to our discussion above. We apply algorithm \ref{alg:setcover} to select a set of points that cover a large set of demand points across different distance thresholds. Note that the objective cost of any set of center following the discretization scheme is not too far from the actual costs, as we will show in lemma \ref{lem:approx}. Thus, the set of centers that we find across different thresholds $t$ should also have cost similar to ${\sf OPT}$.

Our final step is to obtain the final set of centers from the potential centers. To preserve privacy for this step, we create a new dataset similar to the original one with some privacy. In this new dataset, every demand point is shifted towards the closest center from the previous step, and we apply the Laplace mechanism to the assigned number of demands points of each center to preserve privacy. At this point, we can use a $k$-medians algorithm on this dataset to output the final $k$ centers. In this new problem, although the objective changes because of shifting and the Laplace mechanism, the point that can be selected to be centers are the same as before. Thus, the cost of the centers returned in the final step is at most the the cost of this new objective plus the total shifting distance.  In the following sections, we will first analyze the privacy and then the utility of this algorithm.

\subsection{Privacy Analysis}
We first show that this algorithm is $(\epsilon_p, \delta_p)$ differentially private.
To show this, we first show that the entirety of the for loop is $(\epsilon_p / 2, \delta_p)$ differentially private, and then take advantage of composition and apply lemma \ref{thm:laplacemech} at line 12 to obtain the final result. Note that the analysis of the loop very closely follows the proof for privacy of Unweighted Set Cover in \cite{gupta2010differentially}; their algorithm selects sets in a particular order to form a cover, while our algorithm selects candidate centers with increasing distance thresholds, where a center is assumed to cover all demand points within its distance threshold. The significant difference in the two proofs is that our algorithm could select the same center twice with different distance thresholds while a set will never be chosen twice in set cover in \cite{gupta2010differentially}. This re-selection of the same center will not affect the differential privacy of the algorithm, because the privacy analysis hinges on which demand points have been covered, not which centers have been selected. As a result of this, we save an additional $\log n$ factor on privacy, which removes a $\log n$ term from the additive error in lemma \ref{lem:coverage} which carries through the additive error in the utility. We include the proof in the appendix and omit it here, due to its close similarity to \cite{gupta2010differentially}.

\begin{lemma} \label{lem:kmediansloopprivacy}
The for loop in algorithm \ref{alg:kmedian} preserves $(\epsilon_p / 2, \delta_p)$ differential privacy.
\end{lemma}

The function affected by the Laplace mechanism in line 11 returns a vector of the counts $n_c$. In the case of sets $A, A'$ as in theorem \ref{thm:laplacemech}, the difference between $f(A)$ and $f(A')$ is exactly one for one item in this vector, and therefore $\|f(A) - f(A')\|$ = 1, so the function has $L_1$ sensitivity 1. Thus, line 11  is $(\epsilon_p / 2, 0)$ differentially private by theorem \ref{thm:laplacemech}. By composition, this fact and lemma \ref{lem:kmediansloopprivacy} yield the following lemma:

\begin{lemma}
\label{lem:kmedianprivacy}
Algorithm \ref{alg:kmedian} is $(\epsilon_p, \delta_p)$ differentially private.
\end{lemma}

\subsection{Utility Analysis}

We define $t_0 = 0, t_1 = \frac{\Delta}{n},  t_2 = \frac{\Delta(1+\epsilon)}{n},..., t_r = \Delta$ as shorthand for the thresholds. Also, let $o_i$ be the number of points at distance in the range $[t_{i-1}, t_i)$ from their center in the optimal solution (which we denote ${\sf OPT}$), and let $a_i$ be the the number of points at distance in the range $[t_{i-1}, t_i)$ from their closest point in $C$ after the for-loop in algorithm \ref{alg:kmedian}. To bound the performance of our solution, we first show that discretizing the distance thresholds at $t_i$'s instead of integrating from $0$ to $\Delta$ introduces negligible error to the cost of the solution (see Lemma~\ref{lem:approx}). Next, for each distance threshold, lemma \ref{lem:coverage} uses the approximation guarantee of maximum coverage to show that we are efficiently covering demand points using not many more centers than ${\sf OPT}$. Crucially, lemma \ref{lem:solutionapprox} shows that by covering almost as well as ${\sf OPT}$ at every distance threshold, our solution has cost not much more than that of ${\sf OPT}$.

The following lemmas bound ${\sf OPT}$ by the threshold approximation and then bound our solution by that approximation respectively.

\begin{lemma}
\label{lem:approx}
$\sum_{i=1} o_i t_i \leq (1+\epsilon) {\sf OPT} + \Delta$
\end{lemma}

\begin{proof}
On all $u \in D$ and set of centers $F$, define $d'(u,F)$ as the minimum distance threshold $t_i$ which is larger than $d(u,F)$. If $d(u,\text{OPT}) > \frac{\Delta}{n^2}$ then $d'(u,\text{OPT}) \leq (1+\epsilon) d(u,\text{OPT}) $. If $d(u,\text{OPT}) \leq \frac{\Delta}{n^2}$, then $d'(u,\text{OPT}) = \frac{\Delta}{n} \leq d(u, \text{OPT}) + \frac{\Delta}{n}$. Summing over $d \in D$ yields the bound.
\end{proof}

For each distance threshold $t_i$, the following lemma shows that the algorithm covers almost as many points as ${\sf OPT}$. Its proof is left in the appendix. The result follows mostly from lemma \ref{lem:2eps} and the error of the exponential mechanism in algorithm \ref{alg:setcover}.

\begin{lemma}
\label{lem:coverage}
Consider iteration $i$ of the for-loop and let $M_i$ be the maximum coverage of $k$ centers with radius $t_i$ over points in $V'$.  With high probability, at line 5,  $|V_i| \geq (1-\epsilon)M_i - \frac{24k \ln n \ln \left(\frac{e}{\delta_p}\right)}{\epsilon_p}$.
\end{lemma}

The next lemma relates the cost of our solution and that of ${\sf OPT}$ given that we cover almost as well as ${\sf OPT}$ at every distance threshold.

\begin{lemma}
\label{lem:solutionapprox}
$ \sum_{i=1}^r a_i t_i \leq   \frac{1-\epsilon}{1-\epsilon - \epsilon^2}  \sum_{i=1} o_i t_i +   \frac{24\Delta k \ln n \ln \left(\frac{e}{\delta_p}\right)}{\epsilon_p (1-\epsilon -\epsilon^2)}  $
\end{lemma}

\begin{proof}
Let $O_i = \sum_{j=i}^r o_j, A_i = \sum_{j = i}^r a_j$ and $ E = \frac{24k \ln n \ln \left(\frac{e}{\delta_p}\right)}{\epsilon_p}$. Given a threshold $t_i$, we know that the centers in OPT cover $n-O_{i+1}$ points with distance at most $t_i$. At threshold $t_i$, algorithm \ref{alg:kmedian} has already covered $n-A_{i}$ points so we know that there is a solution covering at  additional $(n-O_{i+1}) - (n-A_{i}) = A_{i}-O_{i+1}$ points. By the guarantee of the greedy set cover algorithm in lemma \ref{lem:coverage}, we  cover $a_i \geq (1-\epsilon) (A_{i} - O_{i+1}) - E$ new points on the next iteration. By substituting $A_i = a_i + A_{i+1}$, we have $a_i \geq \frac{(1-\epsilon)}{\epsilon} (A_{i+1}-O_{i+1}) - \frac{E}{\epsilon}$. Notice that:
\begin{align*}\sum_{i=1}^ra_i t_i= \sum_{i=1}^r A_i (t_i - t_{i-1}) \leq  \sum_{i=1}^r \left(\frac{\epsilon a_{i-1}}{1-\epsilon} + O_i + \frac{E}{1-\epsilon}\right) (t_i - t_{i-1}) &\\=  \sum_{i=1}^r \frac{\epsilon a_{i-1}}{1-\epsilon}  (t_i - t_{i-1}) + \sum_{i=1}^r o_i t_i + \frac{\Delta E}{1-\epsilon}
\end{align*}
The equality is because of the telescoping sums. Also notice that:
\begin{equation*} \sum_{i=1}^r \frac{\epsilon a_{i-1}}{1-\epsilon}  (t_i - t_{i-1}) = \sum_{i=1}^{r-1} \frac{\epsilon a_{i}}{1-\epsilon}  (t_{i+1} - t_{i}) \leq \sum_{i=1}^{r-1} \frac{\epsilon^2 }{1-\epsilon} a_{i} t_{i}  \end{equation*}

The last inequality is because for all $1 \le i \le r-1$, $t_{i+1} = (1+\epsilon)t_i$ by definition. We are also able to drop the term $i = 0$ from the last two sums because $a_0 = 0$.

Thus:
\begin{align*}
   & \sum_{i=1}^r a_i t_i - \sum_{i=1}^{r-1} \frac{\epsilon^2 }{1-\epsilon} a_{i} t_{i} = \frac{1-\epsilon - \epsilon^2}{1-\epsilon}   \sum_{i=1}^{r-1} a_i t_i + a_rt_r  \leq  \sum_{i=1} o_i t_i + \frac{\Delta E}{1-\epsilon} \\ & \implies  \sum_{i=1}^r a_i t_i \leq   \frac{1-\epsilon}{1-\epsilon - \epsilon^2}  \sum_{i=1} o_i t_i + (1-\epsilon -\epsilon^2) \Delta E
\end{align*}
\end{proof}

Combining the results of lemmas \ref{lem:approx} and \ref{lem:solutionapprox}, we see that
\[\sum_{i=1}^r a_it_i \le \frac{1-\epsilon}{1-\epsilon - \epsilon^2}\left((1+\epsilon){\sf OPT} + \Delta\right) + (1-\epsilon - \epsilon^2)\Delta E\]
which gives us a bound on the cost of snapping points in $D$ to points in $C$.

\begin{lemma}
\label{lem:prelimcost}
Consider the k-medians problem in the last line of algorithm \ref{alg:kmedian}, where demand points in $D$ are shifted to points in $C$ and Laplace noise is applied. With high probability, the optimal objective cost of this new k-medians problem is at most
 \begin{equation*}
     {\sf OPT} + \sum a_i t_i + \frac{4\Delta k\ln(1/\epsilon)}{\epsilon_p}\left(\frac{\ln(n)}{\ln(1+\epsilon)} + 2\right)
 \end{equation*}
where ${\sf OPT}$ is the cost of the original k-medians problem.
\end{lemma}

We leave the details of this proof in the appendix. Briefly, we can choose OPT of the original problem as a solution to the new problem. In this case, the original points get the cost of OPT plus the cost of snapping to the centers in $C$, which is $\sum a_i t_i$. The last term is an upper bound on the error from using the Laplace mechanism, with high probability.

Using an approximation algorithm for the k-medians problem with approximation factor $M$ in the last step of algorithm \ref{alg:kmedian}, the entire cost gains a multiplicative factor $M$. Therefore, we can summarize the utility of algorithm \ref{alg:kmedian} into the following lemma and even simpler theorem:

\begin{lemma}
\label{lem:utility}
With high probability, algorithm \ref{alg:kmedian} preserves $(\epsilon_p, \delta_p)$ differential privacy and solves the k-medians problem with cost
\[O\left(M(1+\epsilon)\right){\sf OPT} + O\left(\frac{Mk\Delta}{\epsilon_p}\ln n \left(\ln\left(\frac{e}{\delta_p}\right) + \frac{\ln(1/\epsilon)}{\ln(1+\epsilon)} \right) \right)\]
where the black-box k-medians algorithm used in the last step of algorithm \ref{alg:kmedian} has approximation factor $M$ and $\epsilon$ is a small, positive constant.
\end{lemma}

The full proof of this lemma can be found in the appendix. In short, we merge the results of lemmas \ref{lem:approx}, \ref{lem:solutionapprox}, and \ref{lem:prelimcost},
and bound the final cost using the private problem's cost, the snapping cost, and the triangle inequality.

\begin{corollary}
By using a constant approximation non-private algorithm for $k$-medians, there is a $(\epsilon_p, \delta_p)$-differentially private algorithm for the $k$-medians problem that, with high probability, outputs a solution at cost \[O\left({\sf OPT} + \frac{k\Delta}{\epsilon_p} \ln (n)  \left(\ln\left(\frac{1}{\delta_p}\right) + \frac{\ln(1/\epsilon)}{\ln(1+\epsilon)} \right) \right). \]
\end{corollary}
Note that our algorithm allows for any $k$-medians algorithm to be used at the last step. One can choose a preferred trade-off between runtime and performance to select a suitable algorithm. This is in contrast to the approach in \cite{gupta2010differentially}, where the algorithm builds on the $k$-median algorithm in \cite{arya2004local}.

redpajama_set_name: RedPajamaArXiv


Discussion in 'English Only' started by avi7, Dec 28, 2013.
"Manchester City, who have been imperious at home this season, fell behind to an early goal by Liverpool's Philippe Coutinho."
Now, Manchester City is a club. And since it is a club, my question is: "why is 'have' being used here?".
if you think of a club as a collection of individuals and not as a single unit, then "have" is appropriate.
The team are OR the team is?
That is British usage. The club, or a corporation, etc. is treated as a group, so the plural verb is used. In America, we'd say who has been imperious.
Exception: if there is a definite article before the team name, e.g. the Yankees, the Nets, etc. would take "have."
"Manchester City, who has been imperious at home this season..."
Wouldn't it technically have to be "which" instead of "who"?
Yes, there are quite a few previous threads about this (though they're quite hard to find ). BrE usage is different from AmE usage here.
Though I have the suspicion I've read that even in AmE you'd be likely to use a plural pronoun to refer to a team: so Team X has been very successful recently: they've won seventeen games rather than It's won seventeen games.
Am I right, or have I got the wrong end of the stick?
EDIT: cross-posted with dn88, who raises an interesting question.
Further EDIT: I see Julian's answered it!
Just to clarify: the US singular usage (for such a collection of individuals) applies only in the verb which immediately follows the collective name (it is a grammatical agreement, regardless of the sense). Later in the sentence or in the following sentence, AE will use the plural pronoun (i.e. AE uses 2 below not 3)..
1) BrE "Manchester City, who have been imperious at home this season, fell behind to an early goal by Liverpool's Philippe Coutinho. They will need to do better in away games if they want to win the EPL"
2) AmE "Manchester City, which has been imperious at home this season, fell behind to an early goal by Liverpool's Philippe Coutinho. They will need to do better in away games if they want to win the EPL"
3) AmE does not use the singular verb later, as in :"Manchester City, which has been imperious at home this season, fell behind to an early goal by Liverpool's Philippe Coutinho. It will need to do better in away games if it wants to win the EPL"
I forgot to ask one thing: Would you regard this as personification (of the club)?
No, the 'who' in "who have" does not personify the club (which is, after all, singular). It refers to its members, who are persons already, so do not need to be personified.
It would be personification if we said "who has", but we don't say that.


text:
Welcome to Carthago Owners UK
Carthago Owners UK is an informal group of like minded, discerning people who have chosen to own a Carthago motorhome. Membership is open to all Carthago and Malibu owners in UK and to those English speaking owners abroad who would like to be kept informed of the UK based activities. We also welcome new members who are waiting for their new Carthago to arrive. The purpose of the group is to share information and experiences and to get together every so often at meetings both at home and abroad. Our meetings are informal and give our members an opportunity to chat to friends old and new in a relaxed environment. We usually get together in the evenings for a meal and a natter. If you are a Carthago owner or plan to be then we would love you to join us. We are an enthusiastic clan of people who share a love of their Carthago motorhomes, walking, cycling, nature, photography, history, music and much more. Our individual experience ranges from complete novices to people with many years and tens of thousands of miles of motorhome travels behind them.
Carthago Owners UK webmaster: George Pennells
Our Annual General Meetings are held in May. The elected officers of the club May 2019/20 are:
Chair: Paul Brennan Treasurer: John Davies Secretary: Gill Davies Technical Support George Pennells Member John Hunter Member Colin Moy Member Simon Humphreys
Last Updated 7 th July 2019
We currently have 10 Carthagos advertised on our Sales page. Please tell your friends or maybe you fancy an upgrade?
Carthago Owners Gathering - Cromford, Derbyshire - May 2019
Dealer - Member Reviews
What is the Review Process
Points to Consider in Reviews
Carthago Motorhomes
Carthago Owners Gathering Cromford, Derbyshire - May 2019


text:
Image from MegCabot.com About Meg Cabot | Quotes from Meg | Meg's Books for Young Adults
Meg's Books for Adults | Home
Image from MovieGoods.com
Meg's Books for Adults
If you're looking for something a little more mature than The Princess Diaries, Meg has also written a number of romance novels for adults. These books still feature Meg's signature humor and lovable characters, but with R-rated romance scenes.
Links will direct you to the book's catalog entry at the Champaign Public Libary. There you can see if any copies of the book are on the shelf, and request a copy if it is not.
The "Boy" series
This series uses emails and IMs to tell funny and charming urban love stories. The three books share the same style, but have different characters.
The Boy Next Door
Every Boy's Got One
In her debut adult novel, Cabot (known for her extremely successful young adult fiction series the Princess Diaries, published under the name Meg Cabot) relies entirely on highly amusing e-mails to tell a fetching meet-cute story. New York City gossip columnist Melissa Fuller is known for being obsessive about Winona Ryder, dating the wrong men and being tardy for work. Arriving particularly late one morning, she explains to her colleagues at the New York Journal that she was detained by the attempted murder of her elderly next-door neighbor, Mrs. Friedlander, who is in a coma. Always the good girl, Mel has volunteered to take care of Mrs. Friedlander's many pets until the neighbor's nephew Max, a famous fashion photographer, can be reached. Her co-workers warn her about Max, a notorious lady's man. Contrary to the gossip, when she meets Max he is down to earth, funny and kind. Despite the strange fact that he likes to be called John and appears to be between photo shoots, she begins to date him and learns that he shares her love for Stephen King novels and natural disasters. It doesn't take long for her to fall head over heels, or for Mel's mom to write, "Get a ring on your finger before you uncross those legs, sweetie." When a mysterious e-mail arrives explaining that there is more to her beau than meets the eye, she is duly upset and uses the power of her pen to get even. But when Mrs. Friedlander's attacker returns, will Mel and Max be able to put their differences aside to catch a killer? Full of clever e-mail banter and tongue-in-cheek humor, this cheeky novel should be enjoyed in one sitting.
Heather Wells series
Heather Wells used to be a pop star, but her label dropped her for gaining a few pounds. She's happy with her new size and her new job at a college dorm--until a dead student turns up and she has a mystery to solve.
Size 12 Is Not Fat
Size 14 Is Not Fat Either
Big Boned
Bag the tiara and get out the gun: Heather Wells, former teen idol, turns detective in the cute debut of a new mystery series from bestseller Cabot (The Princess Project and other titles in her Princess Diaries series). After the 20-something Heather's rocker boyfriend dumps her, and her mother and manager flee with her earnings, she becomes an assistant director of an undergraduate residence hall at Manhattan's New York College (read: NYU) in hopes of free tuition. When students start to die mysteriously while "elevator surfing" in the building, weight-conscious, romance-obsessed Heather goes on a crazed hunt to uncover the truth—with an unwavering sense of style. As Magda, Heather's dorm cashier friend, says: "Even if the rest of your life is going down the toilet... at least your toes can still look pretty." Cabot delivers Heather's amateur sleuthing adventures in a rapid-fire narrative that may leave some readers begging for time-outs to control sudden laughing fits.
Meena Harper uses her psychic power to predict death to write complicated plots for the popular soap opera Insatiable. Unfortunately, her ability gets her involved with tracking down some modern-day vampires, one of whom Meena finds very attractive.
Cabot (Princess Diaries) winningly applies her trademark likably fallible protagonists and breezy storytelling to a vampire war in New York City. TV writer Meena Harper creates fabulous plots for Insatiable, the second-highest–rated soap opera, thanks to her burdensome if lucrative psychic ability to see into the future and determine how people are going to die. And just as Insatiable is switching to a vampire theme to attract a younger demographic, a spate of chilling murders-by-exsanguination grips New York City. Enter Lucien Antonescu, a sexy, melancholic Romanian history professor/vampire who recognizes that the murders are the work of rogue vampires who have broken away from his order. (Lucien happens to be the son of Vlad the Impaler, whom Bram Stoker gave such a bad rep.) Lucien's opposition: Alaric Wulf, a sympathetic detective from the Palatine Guard, who hopes to use Meena and her prophetic gift to stop the murders and track down Lucien. Unfortunately for Alaric, Meena is a little in love with Lucien. Cabot is less concerned with creating a convincing family tree for Lucien than with creating sparks between her characters, who feel pleasantly natural even as they live alongside the vampires next door.
Queen of Babble series
Lizzie Nichols has a passion for fashion and a big mouth. Can she find a career in the wedding dress restoration field and keep her gift of babble from sabotaging her relationships? The first Queen of Babble book has been optioned as a movie, with Kristen Bell set to star as Lizzie.
Queen of Babble
Queen of Babble in the Big City
Queen of Babble Gets Hitched
Cabot, author of the wildly popular Princess Diaries, delivers another charmer, this time taking on the misadventures of a college girl looking for Mr. Right in Europe. Fresh out of the Univ. of Michigan with a B.A. in history of fashion, Lizzie Nichols sets off across the pond to spend the summer with British boyfriend Andrew, whom she barely knows. When Lizzie learns that Andrew isn't the man she imagined, she changes direction and heads for France, where her best friend Shari is working at Chateau Mirac in the Dordogne wine country. En route, she meets Jean-Luc de Villiers, a French-American hottie whose father owns the chateau, and who would be so easy to fall in love with if he weren't already taken. Lizzie discovers sixteenth-century wineries, kir royals and vintage Givenchy dresses stored in the attic, while matching wits with Jean-Luc's ambitious girlfriend. Although blunt dialogue about oral sex adds a titillating edge, the book is sweet to the core.
She Went All The Way
Screenwriter Lou Calabrese is known for writing the tough Copkiller movies. When she and movie star Jack Townsend survive a helicopter crash in the Arctic wilderness, they have to draw on everything they've learned from Hollywood to survive in the woods.
Amazon.com User Review
If you enjoy contemporary romance with a touch of thriller in the wilds of Alaska, then you might want to try this romance story. Lou Calabrese, Hollywood screenwriter and Jack Townsend, Hollywood hunk and action star are lost in Alaska after a helicopter they are in goes down in the far reaches of Alaska. They survive the crash but will they survive their dislike for one another? Will they survive the killers that are tracking them and trying to do away with them? The dialogue is good and the action scenes are great. The romance between the characters is fun as well. I enjoyed this as light reading and you will too.
Patricia Cabot Books
Meg's first books were adult romance novels written under the pen name Patricia Cabot. You can read about these on Meg's web site, but they are largely out of print.


text:
Global IPO Overview
By SoFi | Jun 03, 2020 | invest | Comments Off on Global IPO Overview
JDE Peet's BV Wins Big on Caffeine-Fueled IPO
JDE Peet's BV (JDEP), which owns American coffee brands like Peet's, Intelligentsia, and Stumptown, completed its IPO last Friday in record time: ten days. While an IPO traditionally takes up to four weeks, the company moved swiftly in an attempt to skirt the market's instability during coronavirus.
Valued at €15.6 billion ($17.3 billion) after raising €2.25 billion ($2.5 billion), JDE Peet's BV traded 18% above its original offer price at €37, or $41 per share, by noon Amsterdam time last Friday. The company's debut was the second-largest this year and welcome bit of good news during an otherwise dismal quarter. European, Middle Eastern, and African markets had only 28 IPOs in the first three months of 2020, which is the lowest number for a quarter in the past seven years.
JDE Peet's, and investors, are betting on a continued demand for coffee. Most of the company's revenue comes from its home-brewed offerings, which are in high demand as many people are still mostly confined to their homes.
Asia: South Korea's Big Hit Entertainment Rides K-Pop Wave to IPO
South Korea's Big Hit Entertainment, home of massive K-Pop acts like BTS, filed for its IPO on May 27, after years of speculation.
In 2019, the company had its biggest year yet with a reported revenue of $507.9 million in US dollars fueled in part by the global success of boy-band BTS. There's no set date for the IPO, but the Korea Exchange said in a statement that JP Morgan (JPM), NH Investment & Securities, and Korea Investment & Securities are underwriting the deal.
Presently, the company's majority shareholders are Founder and Chairman-CEO Bang Hi-Syuk and gaming company Netmarble. The company will join just a few other publicly traded South Korean entertainment companies including SM Entertainment, JYP Entertainment, and YG Entertainment.
United States: Warner Music Group Presses Play on IPO
Stateside, Warner Music Group made its public debut yesterday after originally filing in February and redacting in March when the coronavirus pandemic hit. For this updated IPO, the music company ended up raising $1.8 billion by selling 70 million shares of Class A common stock at $23 to $26 per share.
Though market volatility initially delayed the plan, Warner Music Group is encouraged by the recent success of music streaming which has only continued amid the pandemic. Share prices for streaming company Spotify (SPOT) surged 36% in the time since Warner's shelved IPO.
Today, keep an eye out for another public offering from ZoomInfo Technologies Inc, a SaaS company that focuses on cloud intelligence for sales and marketing teams. JPMorgan Chase & Co. (JPM) and Morgan Stanley (MS) are planning to help ZoomInfo price shares of the company between $19 and $20 each, with an aim to sell 44.5 million shares to the public. The takeaway is that after a long winter and late spring, the IPO market appears to be showing signs of life around the world.


#GBBO – Can you watch your cake and eat it?
It's finally back – I didn't realise I had missed it until it was on again! I'm talking, of course, about 'The Great British Bake Off' which was back on our screens last night for the first episode of the 7th series. According to the BBC, last night's programme was watched by over 10 million people.
According to my WW leader, research shows that watching a food related show such as the Bake Off or Masterchef gives you as much satisfaction as actually eating the food – Not sure I agree on that one!
The Bake Off is fascinating though, and hopefully will encourage those of us who are trying to be good to create healthier alternatives to the butter and sugar filled delicacies that the contestants make!
Look away now – Andrew's Chocolate Mirror Glaze Cake – I dread to think of the Smartpoints!
A very good friend of mine is trying to complete the technical challenges but is using low-fat recipes. I think in a way this makes them even more challenging and fun! Well done Beth!
I was also inspired to try to make a low-fat Apple Crumble in a mug today (see below), the recipe still needs tweaking, but was very tasty for a mere 6 Weight Watcher's Smartpoints.
I'm going to try to bake a few more things as the Bake Off is going on and will post about them in the coming weeks. Let me know if you've been inspired to bake anything by the Bake Off and whether you've been able to use healthy alternatives.
Previous Post I tried yoga… And didn't hate it!