Clément Canonne Profile picture
Senior Lecturer @Sydney_Uni. Postdocs @IBMResearch, @Stanford; PhD @Columbia. Converts ☕ into puns: sometimes theorems. He/him. @ccanonne@mathstodon.xyz
Aug 8, 2022 21 tweets 9 min read
🧩 Answers and discussions for last week's quiz on (some) inequalities, and hopefully a teaser for many others you may find useful.

Today's menu: union 🧅 bound (and a partial converse), Bernoulli's inequality (but which Bernoulli?), Abel's, and Chebyshev's (not that one!).

1/ Let's start with a PSA: print this. Hang it on the wall near your desk. Make it a t-shirt and wear it to work. lkozma.net/inequalities_c…

It is the single most useful list of inequalities I have ever encountered, and it's a goddamn treasure. (Even if you only ever use a subset!)
2/
Nov 27, 2021 7 tweets 2 min read
Oh, this is a fun one!

(From "Experimentation in Mathematics: Computational Paths to Discovery," Borwein, Bailey, and Girgensohn, 2004) Answered in the affirmative in 2005 by Ravi B. Boppana (and made available in 2020 on arxiv.org/abs/2007.11017.)

Simpler proofs? Better bounds? Variations? Also, that book contains a lot of cool stuff.
Nov 25, 2021 13 tweets 3 min read
📊 Friday here, Thursday there, time for a quiz! The wait is over: now, we weigh. ⚖️

You've been given n indistinguishable (to the eye) potatoes. It is very important to you that they all are identical, and in particular all have the same weight.

Do they though?

1/
Your urgent and all-important task is thus to check whether all n 🥔 have the same exact weight, or if you've been cheated by the potatomonger: their weights, on average, significant depart from identical (average 🥔 weight).

Classic.

Now, how does one do that?

2/ Image
Aug 23, 2021 5 tweets 4 min read
My first foray into shuffle #privacy, spearheaded by my impressive winter research intern Hongyi Lyu (maths undergrad @UniMelb), who managed to learn about DP+shuffle DP+distribution testing, all this in ~6 weeks!

Comments welcome! 📝 arxiv.org/abs/2108.08987
1/4 This was part of the "Winter/Summer Research Internship" program at @Eng_IT_Sydney @Sydney_Uni:
sydney.edu.au/engineering/st…

Our (short) paper builds on|simplifies an algo of Balcer, Cheu, @mgtjoseph, & Mao. One key component of our analysis? This fact!


2/4
Aug 22, 2021 13 tweets 6 min read
📊 Answers and discussions for this week's we(a)ekly quiz on greedy algorithms.

Remember: greedy's only a sin if you *forget* to try it!

1/

Greedy #algorithms can be surprisingly powerful, on top of being very often quite intuitive and natural. (Of course, sometimes their *analysis* can be complicated... but hey, you do the analysis only once, but run the algo forever after!)

Let's have a look at a few examples.

2/
Aug 21, 2021 4 tweets 2 min read
Ninth #AcademicSpotlight: Donlapark Ponnoprat (@BomNaKub), Lecturer at @cmuofficial_tw

Paper: Universal Consistency of Wasserstein k-NN classifiers 📝
arxiv.org/abs/2009.04651

Pitch: understanding universal consistency of the k-NN classifier under Wasserstein distances!

1/4
In more detail: A binary classifier g(Dₙ) trained on dataset Dₙ is universally consistent (UC) if the error proba Pₓ,ᵧ(g(Dₙ)(X)≠Y|Dₙ) converges to the Bayes risk as n→∞, regardless of the joint distribution of X and Y. This paper studies the universal consistency...

2/4
Mar 30, 2021 5 tweets 2 min read
Here is one:
If X has the same distribution as X', Y as Y', and Z as Z', do we have 𝔼[X+Y+Z]=𝔼[X'+Y'+Z']? Note that this is true for only two r.v.'s: if X~X' and Y~Y'
𝔼[X+Y]=𝔼[X'+Y']
whenever 𝔼[X+Y] is defined (regardless of whether 𝔼[X] and 𝔼[Y] are defined). (cf. below from G. Simons (1977)).
Mar 27, 2021 32 tweets 10 min read
📊 Answers and discussions for this week's thread on distinguishing biased coins 🪙. Coin: it's like a die 🎲, but with two sides.

So the goal is, given a 🪙, to distinguish b/w it landing Heads w/ probability p or >p+ε, with as few flips as possible.

1/
Here, p and ε are known parameters (inputs), the goal is to be correct with probability at least 99/100 (over the random coin flips). As we will see, 99/100 is sort of arbitrary, any constant in 1/2 < c < 1 would work.

Also, warning: I'm going to give DETAILS.

2/
Dec 16, 2020 14 tweets 7 min read
Stuff I wish I had known sooner: "Pinsker's inequality is cancelled," a thread. 🧵

If you want to relate total variation (TV) and Kullback-Leibler divergence (KL), then everyone, from textbooks to Google, will point you to Pinsker's inequality: TV(p,q) ≤ √(½ KL(p||q) )

1/ It's warranted: a great inequality, and tight in the regime where KL→0. Now, the issue is that KL is unbounded, while 0≤TV≤1 always, so the bound becomes vacuous when KL > 2. Oops.

2/

*I'm using it with the natural log, by the way, so no pesky log 2 constants.
Dec 4, 2020 10 tweets 6 min read
📊 Answers and discussion for yesterday's quiz on sequences (and their names).

Before we go to the first question, again: if you haven't, bookmark oeis.org. It's useful: the solution to some of your problems may be recorded there!

1/
So, the first question... was a trap. All three answers were valid...

I was personally thinking of 203, since that corresponds to the next Bell number (en.wikipedia.org/wiki/Bell_numb…).

But maybe your were thinking of something else? Maybe the number of...

2/
Dec 3, 2020 5 tweets 2 min read
A paper with a broken and ill-defined "solution" to privacy in ML gets a $50k prize?! While said solution was already fully broken at the time of the award—on a challenge chosen by the authors?🤦‍♂️

The presentation slides must have been hella convincing.
Will Carlini et al. get a share of the prize money for breaking the system prior to the award ceremony? arxiv.org/abs/2011.05315
Dec 3, 2020 8 tweets 3 min read
📊 It's Thursday, time for our weekly (but weakly so) quiz! This week: integers, and remarkable sequences.

See this as an extended ad for the OEIS, if you will. Also, if you don't know the OEIS: go check it out (and come back)! oeis.org

1/ Let's start with a "fun" one. To be unhelpful, let's say as a hint that I'm expanding exp(e^x-1) as a series around 0, and am interested in the coefficients

Q1: Guess what number comes next—maybe this sequence will ring a bell? [There might be a trap]
1, 1, 2, 5, 15, 52, ??

2/
Aug 27, 2020 10 tweets 3 min read
📊 It's Thursday for many, time for this week's quiz! As alluded earlier, we're going to flip coins. Like, a lot.

Today: you have a biased coin which lands heads with some probability p∊(0,1), and you can toss it as many times as you want. You don't know p, though...

1/10 ... which is a real shame, since you want to simulate *another* biased coin which lands heads w/ proba exactly f(p), where f: (0,1)→(0,1) is fixed.
(Also, you'd like to do this efficiently, thank you very much.)

Let's start with a simple function: f(p)=1/2.

Q1: Can you?

2/10
Aug 6, 2020 9 tweets 2 min read
📊 It's Thursday [reference needed], time for a weᵄekly quiz! Given some recent events about randomized polynomial time (RP), it feels like a short discussion about 🎲 is topical.

So, let's go: Las Vegas, Monte Carlo, and... Bellagio (?) algorithms!

1/8 Let's start with some definitions—because that's fun, right. We'll discuss 3 types of decision algorithms: BPP (Monte Carlo), ZPP (Las Vegas), and RP (the... other) algorithms.

All three are randomized 🎲. What's the difference? The type of errors they allow.

2/8
Jul 30, 2020 7 tweets 2 min read
📊 Today, (weakly|weekly) quiz will be about graphs. The ones with nodes and edges, not those plotting against you.

Specifically, *planar* graphs. The nice ones.

1/7
What's an (undirected) graph here? Just a pair G=(V,E) of n=|V| vertices (nodes) and m=|E| edges, where E ⊆ V×V and each edge in E is a pair (v₁,v₂) indicating if the two nodes v₁ and v₂ are connected.
If E=V×V (all possible edges), G is the complete graph, Kₙ.

2/7
Jul 23, 2020 6 tweets 2 min read
📊 It's Thursday: time for our wÆkly quiz! I'll build a little bit on last week's statistics/algorithms thread (see below for a recap), and ask you two 2️⃣ questions.

General topic: testing distributions, "leaky" measurements, and adaptivity. 🔍

1/6
Suppose you have the following type of measurements: at each time step, you get to specify a subset S⊆[k], your "question"; and *try* to observe a fresh sample x from the unknown distribution p (over [k]). With probability η, you get to see x: it's leaked to you 🎁...

2/6
Jul 16, 2020 46 tweets 15 min read
📊 Two days ago, I asked a question. Way more people answered than expected, and... well, this week's weₐekly #quiz will be slightly ≠: a long thread on uniformity testing, trickling down all day long.

Be careful what you wish for :) #statistics

1/n

So.... uniformity testing. You have n i.i.d. samples from some unknown distribution over [k]={1,2,...,k} and want to know: is it *the* uniform distribution? Or is it statistically far from it, say, at total variation distance ε?

2/n
Jul 10, 2020 18 tweets 9 min read
📊 Answers and comments about yesterday's online quiz on learning.

Not a quiz on online learning. Though there was an (online learning) component on that online (learning quiz), which maybe led to some learning online, so... I am confused now.



1/16 Let's start with PAC learning. All I'm saying here applies for classification, i.e., learning functions over some space 𝒳 taking boolean values: f: 𝒳 →{0,1}.

Q1 asked what quantity, if any, captured PAC-learnability. 71.3% got it right...



2/16
Jul 4, 2020 20 tweets 9 min read
⁉️ Answers and discussion for yesterday's quiz: and yes, you are a Ravenclaw. (BuzzFeed has nothing on me.)

First I'd like to apologize for the original erroneous phrasing of Q1. If your answer was wrong, it was my fault.

[As usual, refs at the end]

1/19 Corrected Q1: Can you give me a poly(n,k)-time Φ mapping pairs of circuits to pairs of circuits s.t. for all C₀, C₁ the circuits (D₀, D₁)=Φ(C₀,C₁), Φ(C₁) are close if C₀, C₁ are far, and vice-versa?

43.3% got it right! Yes. To see why...

2/19

Jul 2, 2020 12 tweets 3 min read
📊 Wæekly quiz: "The answer may surprise you (or not)."

Four results I find surprising (among many). Three of the statements below are true, one is false. Choose... wisely.

1/11 First question: "Can you make things be far and things far be close?"

Context: Take a Boolean circuit C:{0,1}ⁿ→{0,1}ᵏ mapping n bits to k bits. Feeding it a uniformly random n-bit string defines a proba distribution on k bits. Let's abuse notation, call that C as well.

2/11
Jun 26, 2020 18 tweets 7 min read
🧑‍🏫 Answers and discussions for yesterday's quiz on Boolean functions, halfspaces (LTFs), and Chow parameters.

Our focus here will be functions of the form f: {-1,1}ⁿ→{-1,1} (i.e., bits=±1)

[References for all results at the end of the thread.]

1/18
Central to their study is the corresponding Fourier transform: each such f is uniquely determined by the truth table of its 2ⁿ values, or, equivalently, by the list of its 2ⁿ Fourier coeffs f̂(S), one for each S⊆[n].

[See O'Donnell's book [1] for a great exposition.]

2/18