It's absolutely wild to me that anyone finds this python code easier to read than the equation. Does anyone who follows me feel this way? Can you please explain yourselves?
If you're like me and find it easier to read *code* than *math*, and you have access to
@OpenAI
GPT 4V (or use
@bing
or
@google
Bard), try pasting a image of an equation you wanna understand in there.
It might just blow your mind.
1/🧵
"What is the definition of twice differentiable? Is the term related to differential privacy?" is from now on my favourite paper review quote. It will be hard to beat this one!
Shouldn’t we disentangle publication from conference attendance in CS? Seems to lead to a lot of inequality, and, honestly, I think it’s total nonsense. Why does one need to pay a flight ticket, a hotel stay, and potentially get a visa in order to publish?
A female student could not travel to present her paper at a top CS conference because of her national origin. PC chair responds to her advisor's query about alternatives: "If you knew in advance that the authors would be unable to attend, you should not have submitted." Yikes!!
Today I decided to look up what an “R1 university” is, and the methodology of dividing doctoral institutions into R1 and R2 is kind of wild. They do PCA onto 1d in two different ways and then recenter and compute ell_2 distance from the lower left corner?
Had a twitter hiatus for the past three weeks because this little guy showed up. Since i have no time for sleep, i can now go back to complaining about the slow vaccination rates in Ontario and other ridiculous things you find online
How does anyone summon the energy or focus to do
#icml2020
reviews right now? I forced myself to start, and the second paper I looked at is taking an inner product of a vector and a set, and calling the result a distribution, and now I have lost all motivation again.
@sp_monte_carlo
In this particular example the code feels harder to parse for me, because reading the code requires thinking about a variable changing its state, whereas I think of the sigma notation more directly as a macro for an n-term summation.
Studies have shown that listening to the sound of beavers enthusiastically munching on white cabbage can temporarily reduce stress levels by up to 17%.
Apple do a better job than most on privacy, but this is complete nonsense. "Mathematical representations" can still have all the information needed to reconstruct your face, and this has been shown to be true for deep learning models, too. h/t
@ilyaraz2
Let me present to you this thread, which is the perfect Friday morning treat. It has all the greatest hits: (1) spurious correlation with GDP. The plots go up, can it be an accident?!! (THREAD for more amazingness)
Here is the annual "How the hell is SODA so freaking expensive?" tweet. This year, non-member in-person registration is 940 Euro. That's more than $1300 Canadian. Even more astounding is the virtual registration fee: 835 Euro!
A recent CACM article, supposedly about the limits of differential privacy (DP), reminds me that often arguments against DP are really arguments against *any* meaningful privacy protection. Let me give one example from the article: composition👇
A good number of these are *not* algorithms. What is the neural networks algorithm? The decision tree algorithm? The k-means algorithm? As a theorist, it really grinds my gears when people don't distinguish models, problems, and algorithms.
There are thousands of machine learning algorithms out there, but you'll rarely need more than a handful.
A good start:
• Linear/Logistic Regression
• Decision Trees
• Neural Networks
• XGBoost
• Naive Bayes
• PCA
• KNN
• Random Forests
• K-Means
How the 1958 Fields Medal was decided: ‘Hopf began by crossing off the list the two oldest nominees, Gårding and Bers...he ruled out Hirzebruch who “did not need further encouragement”...the 1958 awards went to Roth and Thom, [for being] promising but not too accomplished.’
The response by Williamson contains an interesting story: he and Goemans had been working on SDPs for Max-Cut, got stuck, and Williamson instead wrote his thesis on primal-dual approximation algorithms. Once the thesis was submitted, they had the random hyperplane idea.
Michel Goemans and David Williamson will receive the 2022 AMS Steele Prize for Seminal Contribution to Research for their paper "Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming":
A while ago I discovered that Theorem 10 in my 2014 paper was also proved in a 1989 article by Keith Ball. Today I decided to open this famous 1950 paper by Dvoretzky and Rogers, which has "my" theorem as their Theorem 5B.
I was recently in a meeting with a *very* prominent biologist and a few other young scientists. One asked him how he picks people for his lab. He said, “If they ask about work-life balance, I don’t want them…If you are not going to be first then why do it?”
There is a desperate need in academic research environments for people whose top 3 outside-work activities don’t include rock-climbing, hiking and board games.
#academichatter
@roydanroy
As an outsider to DL, I think this is bonkers. If your results are not robust to choosing a seed, then I don't see how you have any understanding of what's going on. If you don't have understanding, then I don't see the scientific value. Happy to hear if/why I am wrong.
Let me amplify this one: I am looking for students interested in differential privacy or geometric algorithms. Please apply.
Also if you are looking for a postdocs in algorithms or differential privacy, definitely apply to our group
Many of us at our (large) theory group are also looking for PhD students! Please apply and mention the theory group and faculty you are interested in working with.
I just sent off two 40 page papers to STOC, and I am very proud of both of them, but I also need someone to promise me they will read them, because academia can feel too much like shouting in a void.
New paper with two amazing U of T undergrads . The problem is geometric transportation/Earth Mover’s distance: transport one discrete distribution on R^d to another to minimize total distance traveled. We get (1+eps)-apx in time n*polylog (n=total support)
@suriyagnskr
Recently I checked reviews for a paper that was rejected from ICML because of many nonsense proofs, but made it into NeurIPS. The NeurIPS reviews were all “I don’t know this area but seems cool” ..I generally check reviews when I’m wondering “how the hell did this get in?”
Here, for the people who say they find python easier to read than an equation. What is the output of np.sum([[0, 1, 3], [0, 5, 4]], axis=1)? (Don't look it up or run the code)
Taught the first online lecture of my graduate Private Data Analysis course yesterday. The lecture was about attacks (a cat modelling the attack 👇). This year the course is hidden behind our LMS, but I will be posting updated lecture notes here
@ilyaraz2
Definitely taking care of this man who turned 10 months old recently. It’s the year I got tenure too, but I’ll remember it as the year I became a dad
Whenever I correct or simplify a proof in a review and then see a new version of the paper on arxiv, I check the acknowledgements and think, “Damn right you thank the anonymous reviewer!”
We have postdoc positions available at U of T’s theory group. I, in particular, would love to have a differential privacy postdoc. Lots of amazing people working in TCS, ML, privacy in the area! Here is the ad . Feel free to apply or share
Stages of a math proof: (1) “This is trivial. QED” (2) “Wait..it’s not trivial..is it even true?” (3) “I just hit this with the heaviest hammers I know, so it’s true. QED”
@ccanonne_
Cool fact: for any symmetric matrix A with eigenvalues λ=(λ1, ..., λn), the vector diag(A)=(A_11, ..., A_nn) is in the convex hull of permutations of λ. So for any quasi-concave symmetric function f you have f(λ) <= f(diag(A)).
Some reviewer objects to the use of Byzantine in a paper (as in “Byzantine generals”), says it’s offensive because it’s used in a derogatory way. But who is it offensive to? The slit nosed ghost of emperor Justinian II? I’m so confused!
A reviewer thought my proof had an error because they didn't believe asymptotically good codes existed. To be fair, it's one of those simple but amazing facts. I am excited to tell them about Gilbert and Varshamov .
One of the FOCS 2020 best paper awards goes to the beautiful work of
@markmbun
Roi Livni and Shay Moran showing that differentially private and online learning are equivalent (and video ). Congrats to them and all other winners!
Locally Private Hypothesis Selection, with Sivakanth Gopi, Janardhan Kulkarni, Aleksandar Nikolov (
@thesasho
), Zhiwei Steven Wu (
@zstevenwu
), and Huanyu Zhang. How much does it cost to pick the best-fit distribution from k choices, under LDP? A thread. 1/n
I hope to see a response from
@BellLabs
or the Instahide authors to this post by Nicholas Carlini. I still don’t understand what Instahide is supposed to achieve and what the theorems in the paper have to do with it
I can’t believe I’m watching a guy on tv click counties for hours and tell me to be patient. Also things like “if you add you gotta subtract”
#ElectionNight
I can’t stop thinking how perfect of an ending the Four Seasons Total Landscaping thing is for Trump’s presidency. Rudy Giuliani denying reality in front of a garage door next to a porn store while Trump is golfing.
New paper where we analyze Brownian motion as an SDP rounding algorithm for CSPs. I feel there is a lot more out there that can be done with these techniques. Side benefit: a bunch of cool complex analysis goes into it.
New paper up, with amazing U of T student Deepanshu Kush and Haohua Tang (who was an undergrad while working on this): Near Neighbor Search via Efficient Average Distortion Embeddings . 🧵 [1/9]
Q. "But, but, but.. mumble mumble scooped."
A. Yes, that's likely to happen if you're doing the blindingly obvious next thing in a crowded field. Don't do that. Do something harder.
New co-author 4 is Aleksandar "
@thesasho
" Nikolov. Sasho is an assistant professor at
@UofTCompSci
. He's interested in high-dimensional geometry through applications to a number of areas, including differential privacy, NN search, and discrepancy. 1/n
@FeiziSoheil
My academic brother at Univ. Michigan, who is from Iran, received best paper award, but the conference didn't give it to him eventually, bc the conference was held outside US and he can't be there in person due to visa constraints. My advisor strived very hard but still in vain😐
@thegautamkamath
Been rejected from grad schools, conferences, journals, jobs, fellowships.. It gets easier when you have had some success too, but still stings. Also, failing to solve math problems I’ve spent years on gets me down sometimes, and makes me doubt myself.
Here, for the people who say they find python easier to read than an equation. What is the output of np.sum([[0, 1, 3], [0, 5, 4]], axis=1)? (Don't look it up or run the code)
After years of talking about DP, Jon Ullman and I finally wrote a paper together . Also first paper with Alex Edmonds, supervised by me and Toni Pitassi. We give an essentially optimal algorithm to answer any set of statistical queries in local DP.
One time in college another student (from the US) asked me if we celebrate Thanksgiving in Bulgaria, and when I said "no", they followed up with "is it because of your religion?" Anyways, happy Thanksgiving, Americans!
I do wish that in computer science we had more of a culture of telling complete stories in our papers. Of course you can't always do that, and sometimes you realize you didn't understand the story after all, but that's ok.
Comment from
#ICML2020
reviews: "Reading it, one definitely feels this is a 'complete' research project --- studying a highly relevant problem in (area)."
I love this! I make an effort to tell the "complete story" in a paper. It frustrates me endlessly when I can't.
Today was the last class of this deeply strange semester. My favourite thing about the last day is when students kindly send me off with applause. This time the applause was in the form of emoji. This is a weird new world and I can't wait for it to be over.
New paper with PhD student Lily Li . We prove some algorithmic and hardness results about linear discrepancy, a quantity related to rounding (e.g., LP rounding). We also leave lots of problems open! To appear in ESA 2020. Small teaser in thread 👇 (1/4)
Same. Everyone moans about bad reviews in ML conferences, but no one can properly review 5 theory papers in 12 days. Please remind me to reject these invitations in the future
As a high school student in Bulgaria I somehow ended up on the paintball team of the local technical university, for a tournament. Our first matchup was against the naval academy. We were all taken out in five minutes or less.
Paintballing is fun but only if you go with people of comparable skill. The second I see somebody pull out a paintball gun with a collapsible shoulder stock I’m going to the bar.
After an eight-year struggle, Shinichi Mochizuki has finally gotten his 600-page proof of the abc conjecture accepted in a peer-reviewed journal. But some experts are still unconvinced.
Photo credit: Kyoto University
This is more or less how I like to open my differential privacy grad course. While I aim to make my course accessible to non-theory students, there are theorems in it, because privacy guarantees require proofs.
I'm not the first to say this, but I'll repeat: an interesting thing about differential privacy is it needs theorems even in practice. You can implement heuristic algs that are fast on your data, but 'heuristic privacy' doesn't exist. A mechanism isn't private without a theorem.
This looks really cool! With the right priority queue, Dijkstra's algorithm is universally optimal: for any graph G and any other algorithm A, there exist weights on the graph edges for which A would make at least as many comparisons as Dijkstra's.
New paper with Vivek Madan,
@mohitsinghr
, and Tao Tantipongpipat, the result of an awesome visit to Atlanta last August (which feels approximately a century ago). "Maximizing Determinants under Matroid Constraints"
When I was a new PhD student, putting full versions of papers on arxiv was not yet the norm in TCS, at least not in every subfield. Trying to fill in missing proofs from proceedings versions was a real struggle for someone who didn’t know the standard tricks yet.
@chriswolfvision
What I am taking away from this is that you can write any random nonsense in the ethics review and in the worst case it will be labeled an “emerging issue” by the ethics reviewers. What’s emerging here, is the Eastern Roman Empire coming back?
If you didn't know, Toronto is now home to
@TorontoSRI
, an institute focusing on tech & society, with an impressive multidisciplinary leadership team . Excited to see what's coming! Also, some guy Sasho is a faculty affiliate.
This thread is a great starting point for learning how differentially private algorithms can exploit problem structure to do better than "add iid Laplace noise". How the geometry of the queries asked affects optimal noise is something I have been working on since my PhD.
@anonymity_R_Us
@TedOnPrivacy
Let me dig up a couple of specific references for these examples. It's hard to pick best 2-3 papers, since most of the Differential Privacy literature is about better ways to answer more queries.
In this incredible 5 page paper , Hao Huang resolves the sensitivity conjecture, one of the best known open problems in boolean function complexity. He proves that sensitivity is at least the square root of the degree. 1/3
To the “let’s not publish theory because it’s so hard to verify” people, and to reviewers who think reviews are the place for playing conference politics.
@tourzhao
I am sorry you had to read this and expect the AC ignore this. An incredibly bad take and the wrong place to express it. To those who find the points valid, you might also like my revised version below. All reviewers are free to use this to save time and kill the conference.
Another exciting announcement related to
@TorontoSRI
: I am proud to be among the inaugural faculty fellows, together with my colleague Nisarg Shah. Several terrific
@UofTCompSci
graduate students are also fellows:
@david_madras
, Elliot Creager, Evi Micha.
After years of talking about DP, Jon Ullman and I finally wrote a paper together . Also first paper with Alex Edmonds, supervised by me and Toni Pitassi. We give an essentially optimal algorithm to answer any set of statistical queries in local DP.
Jirka is my favourite mathematical writer. I was lucky to co-author one paper with him, and seeing how he would change wording and notation in what I wrote, and how he would look for simplifications and intuition for every claim felt like a master class in exposition. (1/2)