📊 statistics

Separating Oblivious and Adaptive Models of Variable Selection

यह शोध पत्र $\ell_\infty$ त्रुटि गारंटी के साथ स्पार्स रिकवरी (sparse recovery) के ओब्लिवियस (oblivious) और एडेप्टिव (adaptive) मॉडल्स के बीच एक प्रमाणित पृथक्करण स्थापित करता है, जो यह प्रदर्शित करता है कि जहाँ ओब्लिवियस सेटिंग में नियर-लीनियर समय वाले एल्गोरिदम $\approx k\log d$ नमूनों के साथ इष्टतम बाउंड्स प्राप्त कर सकते हैं, वहीं एडेप्टिव मॉडल्स को $\gtrsim k^2$ नमूनों की आवश्यकता होती है, जो मानक $\ell_2$ सेटिंग के बिल्कुल विपरीत है।

मूल लेखक: Ziyun Chen, Jerry Li, Kevin Tian, Yusong Zhu

प्रकाशित 2026-06-24

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Ziyun Chen, Jerry Li, Kevin Tian, Yusong Zhu

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

यहाँ "Separating Oblivious and Adaptive Models of Variable Selection" पेपर का सरल भाषा और रोज़मर्रा के उदाहरणों के साथ विवरण दिया गया है।

बड़ी तस्वीर: घास के ढेर में सुई ढूँढना

कल्पना कीजिए कि आप एक जासूस हैं जो निर्दोष लोगों की एक विशाल भीड़ (शोर/noise) में कुछ विशिष्ट संदिग्धों (सिग्नल/signal) को खोजने की कोशिश कर रहे हैं। संदिग्धों को पहचानने के लिए आपके पास सवाल पूछने के लिए सीमित संख्या में प्रश्न हैं। डेटा साइंस की दुनिया में, इसे Sparse Recovery कहा जाता है।

आमतौर पर, हम उच्च सटीकता (precision) के साथ संदिग्धों को खोजना चाहते हैं। लेकिन यह पेपर एक विशिष्ट प्रकार की सटीकता पर ध्यान केंद्रित करता है: $\ell_\infty$ error। सरल शब्दों में, इसका अर्थ है कि हम केवल काफी हद तक सही नहीं होना चाहते; हम यह सुनिश्चित करना चाहते हैं कि हमारे अनुमानों में एक भी बड़ी गलती न हो। हम उस हर व्यक्ति के सिग्नल के आकार के बारे में पूरी तरह से आश्वस्त होना चाहते हैं जिसे हम पहचानते हैं।

यह पेपर एक सरल लेकिन गहरा प्रश्न पूछता है: क्या यह मायने रखता है कि संदिग्धों ने छिपने का निर्णय कब लिया?

लेखकों ने पाया कि उत्तर स्पष्ट रूप से "हाँ" है, और अंतर बहुत बड़ा है। उन्होंने पाया कि यदि संदिग्ध आपके प्रश्न डिज़ाइन करने से पहले छिप जाते हैं, तो यह आसान है। लेकिन यदि वे आपके प्रश्नों को देखने के बाद प्रतीक्षा करते हैं और फिर विशेष रूप से आपको धोखा देने के लिए छिपते हैं, तो यह घातीय (exponentially) रूप से कठिन हो जाता है।

दो परिदृश्य: "अंधा" बनाम "चालाक"

पेपर यह तुलना करता है कि "संद संदिग्धों" (डेटा) को दो अलग-अलग तरीकों से कैसे बनाया जा सकता है।

1. द ऑब्लिवियस मॉडल (The "Blind" Scenario - "अंधा" परिदृश्य)

उपमा: कल्पना कीजिए कि आप एक शेफ (रसोइया) हैं जो सूप तैयार कर रहे हैं। आप तय करते हैं कि आप एक बड़े बर्तन में ठीक 5 गुप्त मसाले (सिग्नल) डालेंगे। आप उन्हें मिलाने का काम तब कर देते हैं जब आपको यह भी नहीं पता होता कि सूप का स्वाद कौन लेने वाला है। चखने वाले (मेज़रमेंट मैट्रिक्स) बाद में आते हैं, जो आपके द्वारा किए गए काम से अनजान होते हैं। वे बस एक चम्मच लेते हैं और अनुमान लगाने की कोशिश करते हैं कि वहां कौन से मसाले हैं।

पेपर का निष्कर्ष:
इस परिदृश्य में, चखने वाले उन 5 मसालों को बहुत आसानी से ढूंढ सकते हैं।

उन्हें कितने चम्मच (सैंपल्स) की आवश्यकता होगी? मसालों की संख्या से थोड़ा सा अधिक (लगभग $k \log d$ )।
वे इसे कितनी तेज़ी से कर सकते हैं? बहुत तेज़ (लगभग रैखिक समय)।
परिणाम: वे मसालों को पूरी तरह से पहचान सकते हैं, भले ही उनके पास डेटा की बहुत कम मात्रा हो।

2. द एडेप्टिव मॉडल (The "Sneaky" Scenario - "चालाक" परिदृश्य)

उपमा: अब, कल्पना कीजिए कि जासूस (सिग्नल) आपको देख रहे हैं। आप उनसे कहते हैं, "मैं सूप का एक चम्मच लेने जा रहा हूँ।" जासूस देखते हैं, उन्हें एहसास होता है कि आप मसालों की तलाश कर रहे हैं, और फिर वे तय करते हैं कि वे बर्तन में खुद को ठीक कैसे व्यवस्थित करें ताकि वे साधारण शोर (broth) की तरह दिखें। वे आपके विशिष्ट चम्मच को भ्रमित करने के लिए विशेष रूप से अपना छिपने का स्थान चुनते हैं।

पेपर का निष्कर्ष:
यह सब कुछ बदल देता है। क्योंकि जासूस आपकी रणनीति पर प्रतिक्रिया दे रहे हैं, वे बहुत बेहतर तरीके से छिप सकते हैं।

अब आपको कितने चम्मच की आवश्यकता होगी? आपको बहुत अधिक आवश्यकता होगी। पेपर सिद्ध करता है कि आपको लगभग संदिग्धों की संख्या के वर्ग ( $k^2$ ) की आवश्यकता है।
तुलना: यदि आपके पास 10 जासूस हैं, तो "Blind" परिदृश्य में लगभग 100 चम्मचों की आवश्यकता होगी। "Sneaky" परिदृश्य में, आपको 1,000 चम्मचों की आवश्यकता होगी।
परिणाम: पेपर सिद्ध करता है कि आपका एल्गोरिदम कितना भी स्मार्ट क्यों न हो, यदि सिग्नल "चालाक" (adaptive) है, तो आप "Blind" परिदृश्य में उपयोग किए गए छोटे सैंपल की मात्रा के साथ काम नहीं चला सकते। आपको बहुत अधिक माप (measurements) लेने के लिए मजबूर होना पड़ेगा।

यह आश्चर्यजनक क्यों है?
इस समस्या के मानक संस्करण में (कुल त्रुटि मापना, जिसे $\ell_2$ कहा जाता है), इससे कोई फर्क नहीं पड़ता कि सिग्नल अंधा है या चालाक; आपको समान मात्रा में डेटा की आवश्यकता होती है। यह पेपर पहली बार दिखाता है कि इस विशिष्ट प्रकार की सख्त सटीकता ( $\ell_\infty$ ) के लिए, अनुकूलनशीलता (adaptivity) समस्या को सांख्यिकीय रूप से बहुत कठिन बना देती है।

"पार्शियली एडेप्टिव" मध्य मार्ग

लेखकों ने यह भी सोचा: "क्या होगा यदि सिग्नल चालाक है, लेकिन शोर (पृष्ठभूमि की आवाज़) ईमानदार है?"

उपमा: कल्पना कीजिए कि जासूस आपको देख रहे हैं, लेकिन बैकग्राउंड शोर केवल रैंडम स्टैटिक (static) है जिसे आपकी पूछताछ से कोई फर्क नहीं पड़ता। जासूस छिपने की कोशिश करते हैं, लेकिन वे अपनी मदद के लिए स्टैटिक का उपयोग नहीं कर सकते।

पेपर का निष्कर्ष:
लेखकों ने इस मध्य मार्ग के लिए एक नया एल्गोरिदम बनाया। उन्होंने दिखाया कि यदि आप सूप के उन हिस्सों को "म्यूट" (शांत) कर सकते हैं जिन्हें आपने पहले ही पहचान लिया है (ताकि जासूस अगले दौर में उनके पीछे नहीं छिप सकें), तो आप अभी भी कुशलता से जासूसों को खोज सकते हैं।

आपको पूरी तरह से चालाक परिदृश्य के लिए आवश्यक विशाल $k^2$ सैंपल्स की आवश्यकता नहीं है।
यदि आपको एक चतुर, चरण-दर-चरण तरीके से प्रश्न पूछने की अनुमति दी जाती है, तो आप "Blind" परिदृश्य के समान ही कम सैंपल्स ( $k \log d$ ) के साथ काम चला सकते हैं।

सरल शब्दों में मुख्य बातें

सटीकता मायने रखती है: जब आप हर एक विवरण पर पूर्ण सटीकता (perfect accuracy) की मांग करते हैं (न कि केवल औसत), तो खेल के नियम बदल जाते हैं।
समय ही सब कुछ है: यदि डेटा आपके देखने से पहले उत्पन्न किया जाता है, तो सच्चाई खोजना आसान है। यदि डेटा आपके पूछने के तरीके के बाद (आपको धोखा देने के लिए) उत्पन्न होता है, तो यह अविश्वसनीय रूप से कठिन हो जाता है।
धोखे की कीमत: एक "चालाक" सिग्नल को हराने के लिए, जो आपके प्रश्नों के अनुकूल होता है, आपको "अंधे" सिग्नल की तुलना में लगभग चार गुना अधिक डेटा (वास्तव में, वेरिएबल्स की संख्या का वर्ग) की आवश्यकता होती है।
नए उपकरण: लेखकों ने नए गणितीय उपकरण बनाए (जैसे कि "Restricted Isometry Property" का एक नया संस्करण जिसे $\ell_\infty$ -RIP कहा जाता है), जिससे वे इन सीमाओं को सिद्ध कर सके। उन्होंने दिखाया कि अतीत में उपयोग किए जाने वाले मानक उपकरण इस विशिष्ट प्रकार की सख्त सटीकता के लिए अपर्याप्त थे।

सारांश

यह पेपर डेटा वैज्ञानिकों के लिए एक चेतावनी है: यह मानकर न चलें कि आपका डेटा निर्दोष है। यदि आपका डेटा आपके तरीकों के अनुकूल हो सकता है, तो आपके द्वारा उपयोग किए जाने वाले मानक शॉर्टकट काम नहीं करेंगे। आपको उसी स्तर की सख्त सटीकता प्राप्त करने के लिए काफी अधिक डेटा की आवश्यकता होगी। हालाँकि, यदि आप एक चतुर, पुनरावृत्ति (iterative) तरीके से प्रश्न पूछ सकते हैं (जैसे कि जो आपने पहले ही पा लिया है उसे म्यूट करना), तो आप एक चालाक प्रतिद्वंद्वी के विरुद्ध भी सफल हो सकते हैं।

तकनीकी सारांश: वेरिएबल सिलेक्शन के ओब्लिवियस (Oblivious) और एडेप्टिव (Adaptive) मॉडल्स का पृथक्करण

1. समस्या विवरण (Problem Statement)

यह कार्य $\ell_\infty$ एरर गारंटी के साथ स्पार्स रिकवरी (sparse recovery) के सांख्यिकीय और गणनात्मक परिदृश्यों की जांच करता है, जो हाई-डायमेंशनल लीनियर मॉडल्स में वेरिएबल सिलेक्शन (variable selection) से निकटता से संबंधित एक संस्करण है। मुख्य समस्या एक $k$ -स्पार्स सिग्नल $\theta^\star \in \mathbb{R}^d$ को $n$ लीनियर मेजरमेंट्स $y = X\theta^\star + \xi$ से रिकवर करने की है, जहाँ $X \in \mathbb{R}^{n \times d}$ एक मेजरमेंट मैट्रिक्स है और $\xi$ एक नॉइज़ वेक्टर है।

मुख्य ध्यान एस्टीमेशन एरर के $\ell_\infty$ नॉर्म $\|\theta - \theta^\star\|_\infty$ पर है, न कि मानक $\ell_2$ नॉर्म पर। लेखक तर्क देते हैं कि $\ell_\infty$ रिकवरी, वेरिएबल सिलेक्शन के लिए सही मीट्रिक है: $\ell_\infty$ एरर को कम प्राप्त करने से सिग्नल की स्ट्रेंथ नॉइज़ लेवल से अधिक होने पर, सरल थ्रेशोल्डिंग (thresholding) के माध्यम से $\theta^\star$ के सपोर्ट (नॉन-जीरो एंट्रीज का सेट) की पहचान करना संभव हो जाता है।

इस शोध का एक केंद्रीय वैचारिक योगदान सिग्नल/नॉइज़ और मेजरमेंट मैट्रिक्स के बीच संबंध के संबंध में दो मॉडलिंग धारणाओं के बीच अंतर है:

ओब्लिवियस मॉडल (मॉडल 1): सिग्नल $\theta^\star$ और नॉइज़ $\xi$ को मेजरमेंट मैट्रिक्स $X$ से स्वतंत्र रूप से चुना जाता है। इसे अक्सर "प्रत्येक के लिए" (for each) गारंटी के रूप में वर्णित किया जाता है।
एडेप्टिव मॉडल (मॉडल 2): कोई स्वतंत्रता धारणा नहीं बनाई गई है; $\theta^\star$ और $\xi$ को $X$ के आधार पर प्रतिकूल (adversarial) रूप से चुना जा सकता है। इसे "सभी के लिए" (for all) गारंटी के रूप में वर्णित किया गया है।

यह शोध $\ell_\infty$ एरर प्राप्त करने के लिए आवश्यक सैंपल कॉम्प्लेक्सिटी ( $k$ और $d$ के फलन के रूप में $n$ ) को इन दो अलग-अलग मॉडल्स के तहत लक्षणित करने का लक्ष्य रखता है।

2. कार्यप्रणाली और तकनीकी ढांचा (Methodology and Technical Framework)

एरर मीट्रिक की परिभाषा

लेखक $\ell_\infty$ स्पार्स रिकवरी के लिए एक कैनोनिकल एरर मीट्रिक प्रस्तावित करते हैं:
$\text{err}(X, \xi) := \|X^\top \xi\|_\infty$
वे इस मीट्रिक को यह दिखाकर उचित ठहराते हैं कि यह ओब्लिवियस मॉडल में अन्य साहित्य मीट्रिक्स के समकक्ष है और एडेप्टिव मॉडल में सबसे टाइट (tightest) प्राप्त करने योग्य बाउंड है।

ओब्लिवियस मॉडल ( $\ell_\infty$ स्पार्स रिकवरी)

ओब्लिवियस मॉडल के लिए, लेखक एक तीन-चरणीय एल्गोरिदम (एल्गोरिदम 2) प्रस्तावित करते हैं जो लगभग-लीनियर समय (nearly-linear time) में चलता है:

वॉर्म स्टार्ट (Warm Start): एक प्रारंभिक अनुमान $\hat{\theta}$ प्राप्त करने के लिए इटरेटिव हार्ड थ्रेशोल्डिंग (IHT), जो एक $\ell_2$ स्पार्स रिकवरी एल्गोरिदम है, का उपयोग करें।
सपोर्ट आइडेंटिफिकेशन (Support Identification): संभावित सपोर्ट सेट $L$ की पहचान करने के लिए रेसिड्यूल $X^\top(y - X\hat{\theta})$ पर एक थ्रेशोल्डिंग प्रक्रिया का उपयोग करें। यह चरण यह सुनिश्चित करने के लिए $X$ और $\theta^\star$ के बीच स्वतंत्रता का लाभ उठाता है कि इंटरफेरेंस टर्म्स नॉइज़ स्केल पर केंद्रित हों।
इन-सपोर्ट एस्टीमेशन (In-Support Estimation): अनुमान को रिफाइन करने के लिए सीखे गए सपोर्ट $L$ तक सीमित ऑर्डिनरी लीस्ट स्क्वायर्स (OLS) का उपयोग करें।

इसका विश्लेषण मानक रिस्ट्रिक्टेड आइसोमेट्री प्रॉपर्टी (RIP) तर्कों और नए तकनीकी लेम्मा पर निर्भर करता है जो दिखाते हैं कि स्वतंत्र वेक्टर्स के लिए, एक सपोर्ट सेट पर प्रतिबंधित इनवर्स ग्राम मैट्रिक्स का $\ell_\infty$ ऑपरेटर नॉर्म $n \approx k \log d$ सैंपल्स के साथ अनुकूल व्यवहार करता है।

एडेप्टिव मॉडल ( $\ell_\infty$ स्पार्स रिकवरी)

एडेप्टिव मॉडल के लिए, लेखक एक नई प्रॉपर्टी पेश करते हैं जिसे $\ell_\infty$ -RIP (डेफिनेशन 4) कहा जाता है, जो स्पार्स सब-मैट्रिसेस पर ग्राम मैट्रिक्स $X^\top X - I$ के $\ell_\infty \to \ell_\infty$ ऑपरेटर नॉर्म को बांधती है।

अपर बाउंड (Upper Bound): वे दिखाते हैं कि यदि $X$ , $\ell_\infty$ -RIP को संतुष्ट करता है, तो IHT $\ell_\infty$ एरर $O(\|X^\top \xi\|_\infty)$ तक अभिसरित (converge) होता है। वे सिद्ध करते हैं कि सब-गौसियन मैट्रिसेस $n = \Omega(k^2 \log d)$ के साथ उच्च प्रायिकता के साथ $\ell_\infty$ -RIP को संतुष्ट करते हैं।
लोअर बाउंड (Lower Bound): लेखक एक एडवर्सरियल इंस्टेंस का निर्माण करते हैं ताकि यह सिद्ध किया जा सके कि $n = \Omega(k^2)$ आवश्यक है। निर्माण में एक $k$ -स्पार्स वेक्टर $v$ खोजना शामिल है जिससे $\|v\|_\infty$ बड़ा हो, फिर भी $\|X^\top X v\|_\infty$ छोटा हो (प्रभावी रूप से मेजरमेंट्स द्वारा "मार दिया गया" हो)। यह दिखाने पर निर्भर करता है कि जब $n = o(k^2)$ हो, तो इनवर्स ग्राम मैट्रिक्स का $\ell_\infty$ ऑपरेटर नॉर्म $\Omega(k/\sqrt{n})$ होता है, जिससे एक एडवर्सरी वास्तविक सपोर्ट को छिपा सकता है।

पार्शियली-एडेप्टिव मॉडल (Partially-Adaptive Model)

पेपर एक पार्शियली-एडेप्टिव मॉडल (मॉडल 4) का भी परीक्षण करता है जहाँ नॉइज़ $\xi$ , $X$ से स्वतंत्र है, लेकिन सिग्नल $\theta^\star$ एडेप्टिव हो सकता है। वे एक एल्गोरिदम (एल्गोरिदम 5) प्रस्तावित करते हैं जो एडेप्टिव मेजरमेंट्स (विशेष रूप से, बाद के क्वेरीज में $X$ के विशिष्ट कोऑर्डिनेट्स को "मास्क" या म्यूट करने की क्षमता) का उपयोग करता है। यह एल्गोरिदम पुनरावृत्ति के साथ सपोर्ट एलिमेंट्स की पहचान करता है, उन्हें म्यूट करता है, और दोहराता है, जिससे $n \approx k \log k \log d$ मेजरमेंट्स के साथ वेरिएबल सिलेक्शन प्राप्त होता है।

3. प्रमुख योगदान और परिणाम (Key Contributions and Results)

1. ऑप्टिमल ओब्लिवियस रिकवरी

यह पेपर पहला पॉलीनोमियल-टाइम एल्गोरिदम प्रदान करता है जो $n = O(k \log d)$ सैंपल्स के साथ ओब्लिवियस मॉडल में ऑप्टिमल $\ell_\infty$ एरर प्राप्त करता है।

परिणाम: एक एस्टीमेटर मौजूद है जो उच्च प्रायिकता के साथ लगभग-लीनियर समय में समस्या को हल करता है।
सुधार: यह पूर्व LASSO-आधारित गारंटियों (जैसे, [Wai19]) में सुधार करता है, जिन्हें तुलनीय एरर रेट प्राप्त करने के लिए $n = \Omega(k^2)$ की आवश्यकता होती है।

2. ओब्लिवियस और एडेप्टिव मॉडल्स का पृथक्करण

सबसे महत्वपूर्ण निष्कर्ष $\ell_\infty$ रिकवरी के लिए ओब्लिवियस और एडेप्टिव मॉडल्स के बीच सैंपल कॉम्प्लेक्सिटी में एक प्रमाणिक पृथक्करण है:

ओब्लिवियस: $n = O(k \log d)$ सैंपल्स पर्याप्त हैं।
एडेप्टिव: $n = \Omega(k^2)$ सैंपल्स आवश्यक और पर्याप्त हैं (लॉगैरिद्मिक फैक्टर्स तक)।
विपरीत स्थिति: यह $\ell_2$ सेटिंग के बिल्कुल विपरीत है, जहाँ एडेप्टिव रिकवरी के लिए भी $n \approx k \log d$ सैंपल्स पर्याप्त होते हैं। लेखक स्थापित करते हैं कि अज्ञात मापदंडों के चयन में एडेप्टिविटी $\ell_\infty$ समस्या को सांख्यिकीय रूप से कठिन बनाती है।

3. नया एरर मीट्रिक और बाउंड्स

वे $\|X^\top \xi\|_\infty$ को सही एरर मीट्रिक के रूप में स्थापित करते हैं।

वे इस मीट्रिक के तहत एडेप्टिव मॉडल के लिए मैचिंग अपर और लोअर बाउंड प्रदान करते हैं।
वे दिखाते हैं कि पिछले साहित्य में विचार किए गए अन्य एरर क्वांटिटीज एडेप्टिव मॉडल में प्रमाणिक रूप से अप्राप्य हैं।

4. पार्शियल एडेप्टिविटी (Partial Adaptivity)

पेपर दिखाता है कि एक पार्शियली-एडेप्टिव सेटिंग (जहाँ नॉइज़ बेनिन है) में गैर-तुच्छ (nontrivial) वेरिएबल सिलेक्शन गारंटियां संभव हैं यदि लर्नर को ऑब्जर्वेशन के दौरान कोऑर्डिनेट्स को मास्क करने की अनुमति दी जाए। यह सुझाव देता है कि पूर्णतः एडेप्टिव मॉडल के क्वाड्रेटिक लोअर बाउंड को विशिष्ट स्ट्रक्चरल धारणाओं या इंटरेक्शन क्षमताओं के साथ दरकिनार किया जा सकता है।

4. महत्व और दावे (Significance and Claims)

पेपर दावा करता है कि यह $\ell_\infty$ एरर में स्पार्स लीनियर मॉडल्स सीखने के सांख्यिकीय परिदृश्य से संबंधित मौलिक प्रश्नों को हल करता है। विशेष रूप से:

यह एडेप्टिव $\ell_\infty$ स्पार्स रिकवरी की कम्प्यूटेशनल और सांख्यिकीय जटिलता को सुलझाता है, जो स्पार्सिटी $k$ पर एक क्वाड्रेटिक निर्भरता ( $n \sim k^2$ ) दिखाता है, जो $\ell_2$ रिकवरी में लीनियर निर्भरता से भिन्न है।
यह ओब्लिवियस $\ell_\infty$ रिकवरी के लिए पहला कुशल एल्गोरिदम प्रदान करता है जो $\ell_2$ रिकवरी के ऑप्टिमल सैंपल कॉम्प्लेक्सिटी ( $n \sim k \log d$ ) से मेल खाता है।
यह रेखांकित करता है कि $\ell_\infty$ नॉर्म्स के लिए "सभी के लिए" (एडेप्टिव) गारंटी, "प्रत्येक के लिए" (ओब्लिवियस) गारंटी की तुलना में स्पष्ट रूप से अधिक मांग वाली है, एक ऐसी घटना जो मानक $\ell_2$ सेटिंग में मौजूद नहीं है।

लेखक निष्कर्ष निकालते हैं कि उनका कार्य मानक स्पार्स रिकवरी सिद्धांत के साथ एक आश्चर्यजनक विरोधाभास स्थापित करता है और विभिन्न स्वतंत्रता धारणाओं के तहत वेरिएबल सिलेक्शन के विश्लेषण के लिए एक नया कैनोनिकल फ्रेमवर्क प्रदान करता है। वे $n = o(k^2 \log d/k)$ तक लोअर बाउंड के विस्तार को एक ओपन प्रॉब्लम के रूप में छोड़ देते हैं।