Sergei Vassilvitskii

The third iteration of NYC Privacy Day is going to happen this October. Register and learn about the cutting-edge work done in security and privacy in the last few months :) rsvp.withgoogle.com/events/nyc-pri…

@_onionesque @aryehazan It's almost 16 years old at this point (soda 2007).

@aryehazan @vsergei kmeans++ is very recent, though, and does improve kmeans significantly with little overhead.

In fact, as a challenge, name an empirically successful algorithm that arose from theory. All I got is boosting.

@aryehazan The history of original k-means is interesting, but won't fit in the margins of this tweet. However, k-means++ as the now standard way to initialize k-means did come from theory.

@vsergei Are you telling me that k-means arose from theory and nobody was running it on data before some sort of analysis became available?

Another new paper on the arxiv to talk about: arxiv.org/abs/2308.10316 . This paper is my first foray into differential privacy, which was fun and forced me to learn a lot.

New paper just hit the arxiv, and which was one of the most fun and interesting research projects that I've ever worked on: arxiv.org/abs/2308.05067 . Long story short, we found some super interesting and surprising behavior in the most well-studied online problems: ski rental!

Training ML models with differential privacy could be challenging. To aid practitioners, we wrote a detailed survey with known best practices of DP-training of ML models: arxiv.org/abs/2303.00654

Super excited about a new preprint, "Faster Matchings via Learned Duals", with Sungjin Im, Thomas Lavastida, Ben Moseley, and @vsergei . Long story short: we can use ML to massively speed up min-cost perfect matching computations! arxiv.org/abs/2107.09770

A great line-up for the July 13-14 FODSI workshop on ML for Algos! @AlexGDimakis-Yonina Eldar-@annadgoldie-@HeckelReinhard-Stephanie Jegelka-@tim_kraska-Benjamin Moseley-David Parkes-@AlgoSvensson-Tuomas Sandholm-@vsergei-Ellen Vitercik-David Woodruff! fodsi.us/ml4a.html

Algorithms with Predictions: Survey and Workshop ift.tt/3hyGt6Z

@amitc1 @geomblog @RikSarkarNet @chaturv3di Book!

@geomblog @RikSarkarNet @chaturv3di Book?

2020 is turning out to be a year of shocks. The biggest one yet - I might finally understand what EM does.

@Aaroth A nice simple exercise. Suppose you are estimating the mean of a Gaussian distribution from iid samples. Compare the DP error to the finite sample error. TL;DR; with DP you need O(\sqrt{log n}) more samples to get parity.

This is good news for anyone who is worried that differential privacy will render Census data unusable; Its effect on statistics seems to be comparable to taking a very large random sample of the data, which is better than what statisticians usually get to work with.

"if 𝜖 = 1.0 ... TopDown will be like the uncertainty introduced by working with a 50% sample of the full dataset; if 𝜖 = 2.0, it will be like working with a 75% sample; and if 𝜖 = 6.0, it will have accuracy matching a 95% sample, which is pretty close to having the full data"

@dsivakumar @ravik53 @JeffDean Don't forget @ssuri ! Nailing down the model of computation took many coffees and whiteboard sessions

@moyix @bipr Cc @jakehofman

Does anyone have an example of a pre-registered replication of a paper in computer science ?

Coming out of twitter hibernation to say that part 1 of the clustering book with @geomblog is available at clustering.cc ! As we say in the intro: Clustering is more than just a collection of tools... it is a systematic way to think about how data should be organized.

@bipr Too bad the supervised learning session is in a different room

@geomblog Strongly sublinear? Though we used that to distinguish n^\delta from n/\log n.

@nikete @haldaume3 what's coming online, points or dimensions? Shameless plug from aistats16 arxiv.org/abs/1503.05225

. @dggoldst @jakehofman nicely done!

Joint effort with Sergei Vassilvitskii: "Parallel Models: (Hitchhiker's Guide to Massively Parallel Universes)": grigory.us/blog/massively…