Share this page!

Enter URL or ID to Unroll

You can paste full URL like: https://x.com/threadreaderapp/status/1644127596119195649
or just the ID like: 1644127596119195649

How to get URL link on X (Twitter) App

  1. On the Twitter thread, click on or icon on the bottom
  2. Click again on or Share Via icon
  3. Click on Copy Link to Tweet
  4. Paste it above and click "Unroll Thread"!
  5. More info at Twitter Help
Clément Canonne Profile picture
Clément Canonne
@ccanonne_
Lecturer #USydCompSci @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