Ian Goodfellow’s tweets showing x years of progress on GAN image generation really bring home how fast things are improving. For example, here’s 4.5 years worth of progress on face generation:
And here we have just 2 years of progress on class-conditional image generation:
I was drawn to this paper to try and find out what’s behind the stunning rate of progress.
Tag: cs
Coding Women History
A good programmer was concise and elegant and never wasted a word. They were poets of bits. “It was like working logic puzzles — big, complicated logic puzzles. I still have a very picky, precise mind, to a fault. I notice pictures that are crooked on the wall.”
What sort of person possesses that kind of mentality? Back then, it was assumed to be women. They had already played a foundational role in the prehistory of computing: During World War II, women operated some of the first computational machines used for code-breaking at Bletchley Park in Britain. In the United States, by 1960, more than 25% of programmers were women. At M.I.T.’s Lincoln Labs in the 1960s, most of those the government categorized as “career programmers” were female. It wasn’t high-status work — yet.
Tail latency aware caching
RobinHood dynamically allocates cache space to those backends responsible for high request tail latency (cache-poor) backends, while stealing space from backends that do not affect the request tail latency (cache-rich backends). In doing so, Robin Hood makes compromises that may seem counter-intuitive (e.g., significantly increasing the tail latencies of certain backends).
Memory leak debugging
Guided by BLeak, we identify and fix over 50 memory leaks in popular libraries and apps including Airbnb, AngularJS, Google Analytics, Google Maps SDK, and jQuery. BLeak’s median precision is 100%; fixing the leaks it identifies reduces heap growth by an average of 94%, saving from 0.5MB to 8MB per round trip.
Kolmogorov Complexity
Now our understanding of our search for meaning is starting to come together. We abhor randomness and love patterns. We are biologically programmed to find some patterns that explain what they see. But we can never be certain that the pattern we’ve identified is the right one. Even if we could somehow be assured that we haven’t made a mistake, and we are exhibiting a computer-like perfection, there may always still be a deeper truth to unearth. This tension helps drive our love of literature, theater, and the cinema. When we read a novel, or watch a play, the author or director is presenting us with a sequence of events that has a common theme, pattern, or moral. Literature, plays, and the cinema offer us a delightful escape from the usual unintelligible, meaningless chaos that we find in the real world around us. Really good literature goes further, and leaves us with the possibility of many interpretations. We come face to face with the incomputability of the Kolmogorov complexity.
Since time-bounded Kolmogorov complexity is computable, a natural next question is how hard it is to compute. And this is the question that Liu and Pass proved holds the key to whether one-way functions exist. Suppose you’ve set your sights on a less lofty goal than calculating the exact time-bounded Kolmogorov complexity of every possible string — suppose you’re content to calculate it approximately, and just for most strings. If there’s an efficient way to do this, then true 1-way functions cannot exist. In that case, all our candidate 1-way functions would be instantly breakable, not just in theory but in practice. “Bye-bye to cryptography”.
Conversely, if calculating the approximate time-bounded Kolmogorov complexity is too hard to solve efficiently for many strings, then true 1-way functions must exist. If that’s the case, their paper even provides a specific way to make one. The 1-way function that they describe in their paper is too complicated to use in real-world applications, but in cryptography, practical constructions often quickly follow a theoretical breakthrough. And if their function can be made practical, it should be used in preference to the candidate 1-way functions based on multiplication and other mathematical operations.
Computation & time travel
Consider a science-fiction scenario wherein you go back in time and dictate Shakespeare’s plays to him. Shakespeare thanks you for saving him the effort, publishes verbatim the plays that you dictated, and centuries later the plays come down to you, whereupon you go back in time and dictate them to Shakespeare, etc. Notice that, in contrast to the grandfather paradox, here there is no logical contradiction: the story as we told it is entirely consistent. But most people find the story “paradoxical” anyway. After all, somehow Hamlet gets written, without anyone ever doing the work of writing it! As Deutsch perceptively observed, if there is a “paradox” here, then it is not one of logic but of computational complexity. Now, some people have asked how such a claim could possibly be consistent with modern physics. For didn’t Einstein teach us that space and time are merely 2 aspects of the same structure? 1 immediate answer is that, even within relativity theory, space and time are not interchangeable: space has a positive signature whereas time has a negative signature. In complexity theory, the difference between space and time manifests itself in the straightforward fact that you can reuse the same memory cells over and over, but you can’t reuse the same moments of time. Yet, as trivial as that observation sounds, it leads to an interesting thought. Suppose that the laws of physics let us travel backwards in time. In such a case, it’s natural to imagine that time would become a “reusable resource” just like space is—and that, as a result, arbitrary PSPACE computations would fall within our grasp. But is that just an idle speculation, or can we rigorously justify it?
Datacenter performance
How do you know how well your large kubernetes cluster is performing? Is a particular change worth deploying? Can you quantify the ROI? To do that, you’re going to need some WSC-wide metric of performance. Not so easy! The WSC may be running 1000s of distinct jobs all sharing the same underlying resources. Developing a load-testing benchmark workload to accurately model this is ‘practically impossible.’ Therefore, we need a method that lets us evaluate performance in a live production environment. Google’s answer is the Warehouse Scale performance Meter (WSMeter), “a methodology to efficiently and accurately evaluate a WSC’s performance using a live production environment.” At WSC scale, even small improvements can translate into considerable cost reductions. WSMeter’s low-risk, low-cost approach encourages more aggressive evaluation of potential new features.
Reducing data movements
Our evaluation shows that offloading simple functions from these consumer workloads to processing-in-memory logic, consisting of either simple cores or specialized accelerators, reduces system energy consumption by 55.4% and execution time by 54.2%, on average across all of our workloads.
Learning by reproducing
Students taking Stanford’s Advanced Topics in Networking class have to select a networking research paper and reproduce a result from it as part of a 3-week pair project. At the end of the process, they publish their findings on the course’s public Reproducing Network Research blog. It’s well worth having a look around the blog: the students manage to achieve a lot in only 3 weeks! In the last 5 years, 200 students have reproduced results from 40 papers.
In ‘Learning networking by reproducing research results’ the authors explain how this reproduction project came to be part of the course, what happens when students try to reproduce research, and the many benefits the students get from the experience. It’s a wonderful and inspiring idea that I’m sure could be applied more broadly too.
ML vulnerabilities
Identifying vulnerabilities in the ML model supply chain
we show that maliciously trained convolutional neural networks are easily backdoored; the resulting “BadNets” have state-of-the-art performance on regular inputs but misbehave on carefully crafted attacker-chosen inputs. Further, BadNets are stealthy, .i.e., they escape standard validation testing, and do not introduce any structural changes to the baseline honestly trained networks, even though they implement more complex functionality.
Gregor J. Rothfuss 