Discover and read the best of Twitter Threads about #FOCS2020
Most recents (1)
Weakly weekly quiz, new installment! I'm assuming everyone is very busy with either the #FOCS2020 deadline, the #ICML2020 reviews, or the current global health crisis and juggling with 5 toddlers & 7 Zoom online classes, so I'll keep it short.
Adaptivity 🗘 and testing 🔎.
1/7
Adaptivity 🗘 and testing 🔎.
1/7
Recall testing 🔎: you have a notion of distance d(x,y), a parameter ε, and "access" to an object x (function f, graph G, proba. distribution p...); and in mind, a property ℘. Goal: does x have ℘, or do we have d(x,y) > ε for all y in ℘?
[x has ℘, or is ε-far from it]
2/7
[x has ℘, or is ε-far from it]
2/7
Now, "adaptivity"? Well, to decide the above question, you have to access your object x by making 'queries' (fct eval, edge lookups, samples, etc.). If the queries are decided in advance: non-adaptive algo; if queries depends on the answers to previous ones: adaptive algo.
3/7
3/7
