AI Paper Atlas

Research map / Learning theory and algorithms / Sample complexity

Sampling Sketches for Concave Sublinear Functions of Frequencies

Edith Cohen, Ofir Geri

NeurIPS 2019 · Learning theory and algorithms › Sample complexity · approach: Density and property estimation · 3 citations (OpenAlex)

Read the paperCheck your idea against 137,217 papers

AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Measured effects reported in the paper

What was changedWhereMeasuredEffect
Use the proposed composable sampling sketch instead of aggregating keys before samplingWeighted frequency estimation · Real and synthetic datasets; ν^0.5 and ln(1+ν)NRMSEMixed
Increase sample size k from 25 to 100Sampling sketch · abcnews, f(ν)=ν^0.5NRMSE: 0.213 -> 0.105Improved
Increase sample size k from 25 to 100Sampling sketch · flickr, f(ν)=ln(1+ν)NRMSE: 0.227 -> 0.097Improved
Use the sketch rather than aggregated PPSWORFrequency estimation · abcnews, f(ν)=ln(1+ν), k=100NRMSE: 0.115 -> 0.102Improved
Use the sketch rather than aggregated PPSWORFrequency estimation · flickr, f(ν)=ν^0.5, k=100NRMSE: 0.095 -> 0.115Hurt
Use the sketch rather than priority samplingFrequency estimation · zipf1.2, f(ν)=ν^0.5, k=100NRMSE: 0.096 -> 0.098Hurt
Use the sketch rather than aggregated priority samplingFrequency estimation · abcnews, f(ν)=ln(1+ν), k=100NRMSE: 0.103 -> 0.102No clear effect
Use the adaptive split between low- and high-range contributions with stochastic PPSWOR samplingSampling sketch · Theorem-level estimator guaranteeVariance upper bound: 4/((1-ε)^2 (k-2)) times the corresponding frequency-weight productImproved
Use a concave sublinear function to weight key frequencies instead of raw frequencyFrequency-weighted sampling · Applications with skewed frequenciesHigh-frequency key influenceImproved

Closest papers by meaning

Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy