🤖 machine learning

Quantizing With Randomized Hadamard Transforms: Efficient Heuristic Now Proven

यह शोध पत्र यह सिद्ध करता है कि दो या तीन रैंडमाइज्ड हेडामार्ड ट्रांसफॉर्म्स (RHTs) को संयोजित करना ग्रेडिएंट कम्प्रेशन और वेक्टर क्वांटाइजेशन के लिए क्रमशः यूनिफॉर्म रैंडम रोटेशन्स (URRs) के प्रदर्शन को सैद्धांतिक रूप से मेल खाने के लिए पर्याप्त है, जो गॉसियन कन्वर्जेंस और कोवेरिएंस डिके बाउंड्स स्थापित करके किया गया है, साथ ही यह उपयोग किए जाने वाले ट्रांसफॉर्म्स की संख्या को गतिशील रूप से अनुकूलित करने के लिए एक लीनियर-टाइम रनटाइम चेक भी प्रस्तावित करता है।

मूल लेखक: Ran Ben-Basat, William Kuszmaul, Michael Mitzenmacher, Amit Portnoy, Shay Vargaftik

प्रकाशित 2026-05-08

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

CC BY 4.0

मूल लेखक: Ran Ben-Basat, William Kuszmaul, Michael Mitzenmacher, Amit Portnoy, Shay Vargaftik

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

यहाँ सरल भाषा और रोज़मर्रा के उदाहरणों का उपयोग करके पेपर की व्याख्या दी गई है।

बड़ी तस्वीर: खुरदरे किनारों को चिकना करना (Smoothing the Rough Edges)

कल्पना कीजिए कि आपके पास अलग-अलग आकार की कंचों (marbles) का एक थैला है, और आप उन्हें छोटे बक्सों में छाँटना चाहते हैं। छंटाई को निष्पक्ष और कुशल बनाने के लिए, आप पहले थैले को अच्छी तरह हिलाना चाहते हैं ताकि कंचे पूरी तरह से आपस में मिल जाएँ। कंप्यूटर विज्ञान की दुनिया में, इस "हिलाने" को यूनिफॉर्म रैंडम रोटेशन (Uniform Random Rotation - URR) कहा जाता है। यह डेटा को समान रूप से फैला देता है, जिससे यह एक आदर्श बेल कर्व (Gaussian distribution) की तरह व्यवहार करने लगता है।

हालाँकि, कंप्यूटर पर इस "परफेक्ट शेक" को करना अविश्वसनीय रूप से धीमा और महंगा है, जैसे कि एक छोटी चम्मच से हाथ से विशाल सूप के बर्तन को मिलाने की कोशिश करना।

चीजों को तेज़ करने के लिए, इंजीनियर एक शॉर्टकट का उपयोग करते हैं जिसे रैंडमाइज्ड हेडामर्ड ट्रांसफॉर्म (Randomized Hadamard Transform - RHT) कहा जाता है। RHT को एक "फास्ट मिक्सर" (तेज़ मिलाने वाला) समझें। यह बहुत तेज़ है, लेकिन इसमें एक दोष है: यदि आप इसमें बहुत ही अजीब, ऊबड़-खाबड़ इनपुट डालते हैं (जैसे एक थैला जिसमें एक बहुत बड़ा कंचा और हजारों छोटे कंचे हों), तो यह फास्ट मिक्सर इसे अच्छी तरह से नहीं मिला पाता। परिणाम अभी भी ऊबड़-खाबड़ रहता है, जिससे अंतिम छंटाई (quantization) में त्रुटियाँ होती हैं।

यह पेपर पूछता है: "हमें 'परफेक्ट रिजल्ट' पाने के लिए इस फास्ट मिक्सर को कितनी बार चलाना होगा, जैसा कि धीमे और परफेक्ट मिक्सर से मिलता है?"

समाधान: "डबल" और "ट्रिपल" मिक्सर

लेखकों ने पाया कि उत्तर इस बात पर निर्भर करता है कि आप क्या कर रहे हैं, लेकिन समाधान आश्चर्यजनक रूप से सरल है: बस फास्ट मिक्सर को एक से अधिक बार चलाएं।

1. एकल संख्याओं के लिए (Scalar Quantization): "डबल मिक्सर"

जब लक्ष्य व्यक्तिगत संख्याओं को कंप्रेस करना हो (जैसे DRIVE या QUIC-FL में, जिनका उपयोग AI मॉडल को प्रशिक्षित करने या डेटाबेस खोजने के लिए किया जाता है), तो लेखकों ने पाया कि फास्ट मिक्सर को दो बार चलाना पर्याप्त है।

उदाहरण: कल्पना कीजिए कि आपके पास आटे का एक ऊबड़-खाबड़ टुकड़ा है। यदि आप इसे एक बार मशीन से गुजारते हैं, तो इसमें अभी भी अजीब उभार हो सकते हैं। लेकिन यदि आप इसे दूसरी बार मशीन से गुजारते हैं, तो वे उभार पूरी तरह से खत्म हो जाते हैं।
परिणाम: दो पास के बाद, डेटा सांख्यिकीय रूप से "परफेक्ट शेक" के समान दिखने लगता है। त्रुटियाँ उसी निम्न स्तर तक गिर जाती हैं जो धीमे, परफेक्ट तरीके से मिलती हैं, लेकिन कंप्यूटर फिर भी तेज़ चलता है।
प्रमाण: उन्होंने गणितीय रूप से सिद्ध किया कि किसी भी इनपुट के लिए, दो पास डेटा को एक परफेक्ट बेल कर्व की तरह व्यवहार करने के लिए पर्याप्त हैं। यह उन "वर्स्ट-केस" परिदृश्यों को ठीक करता है जहाँ फास्ट मिक्सर आमतौर पर विफल हो जाता है।

2. संख्याओं के समूहों के लिए (Vector Quantization): "ट्रिपल मिक्सर"

कभी-कभी, कंप्यूटर केवल एकल संख्याओं को नहीं देखते; वे संख्याओं के छोटे समूहों को एक साथ देखते हैं (जैसे खिलाड़ियों की एक टीम)। इसे वेक्टर क्वांटाइजेशन (Vector Quantization - VQ) कहा जाता है।

समस्या: भले ही "डबल मिक्सर" व्यक्तिगत संख्याओं को चिकना बना दे, लेकिन एक समूह के भीतर की संख्याएँ अभी भी एक-दूसरे से बहुत अधिक जुड़ी (correlated) हो सकती हैं। कल्पना कीजिए कि नर्तकों का एक समूह है जो सभी एक ही ताल में चल रहे हैं; वे स्वतंत्र नहीं हैं। यदि वे बहुत अधिक सिंक्रोनाइज़्ड हैं, तो कंप्रेशन एल्गोरिदम भ्रमित हो सकता है।
समाधान: लेखकों ने पाया कि फास्ट मिक्सर को तीन बार चलाना इस अनचाहे संबंध को तोड़ देता है।
उदाहरण: यदि "डबल मिक्सर" आटे को चिकना बनाता है, तो "ट्रिपल मिक्सर" यह सुनिश्चित करता है कि आटे के अंदर की सामग्री एक-दूसरे से पूरी तरह स्वतंत्र हो। यह "लॉकस्टेप" पैटर्न को तोड़ देता है।
परिणाम: तीन पास के साथ, संख्याओं का कोई भी समूह बिल्कुल वैसा ही व्यवहार करता है जैसा कि उसे परफेक्ट, स्लो मिक्सर द्वारा प्रोसेस किया गया हो। यह मानक कंप्रेशन टूल्स को बिना किसी कस्टम डिज़ाइन के इन समूहों पर पूरी तरह से काम करने की अनुमति देता है।

स्मार्ट शॉर्टकट: मिलाने से पहले जाँच करें

पेपर एक समय बचाने का चतुर तरीका भी सुझाता है। आमतौर पर, आप सोच सकते हैं, "मैं सुरक्षित रहने के लिए हमेशा मिक्सर को तीन बार चलाऊंगा।" लेकिन सामान्य डेटा के लिए यह बहुत ज़्यादा है।

विचार: अधिकांश वास्तविक दुनिया का डेटा "ऊबड़-खाबड़" या "अजीब" नहीं होता है। वह पहले से ही काफी चिकना होता है।
जाँच: लेखक एक त्वरित, बिजली की तरह तेज़ जाँच (linear time, $O(d)$ $O (d)$ में) प्रस्तावित करते हैं ताकि मिक्सर शुरू करने से पहले इनपुट डेटा को देखा जा सके।
- यदि डेटा पहले से ही चिकना है, तो आपको केवल एक पास की आवश्यकता है।
- यदि यह थोड़ा ऊबड़-खाबड़ है, तो आपको दो पास की आवश्यकता है।
- यदि यह बहुत अजीब है, तो आपको तीन पास की आवश्यकता है।
लाभ: यह एक "स्मार्ट थर्मोस्टेट" की तरह कार्य करता है। यह डेटा के तापमान की जाँच करता है और केवल उतनी ही ऊर्जा (कंप्यूटिंग पावर) का उपयोग करता है जितनी सख्ती से आवश्यक है, जिससे यह सुनिश्चित होता है कि आपको सटीकता से समझौता किए बिना सर्वोत्तम गति मिले।

उपलब्धियों का सारांश

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

संक्षेप में: फास्ट मिक्सर को केवल एक बार न चलाएं। एकल संख्याओं के लिए इसे दो बार और समूहों के लिए तीन बार चलाएं, या कम से कम करने के लिए डेटा की जाँच करें। यह एक "काफी अच्छा" शॉर्टकट को एक गणितीय रूप से पूर्ण समाधान में बदल देता है।

तकनीकी सारांश: रैंडमाइज्ड हैडामार्ड ट्रांसफॉर्म्स के साथ क्वांटाइजिंग: कुशल ह्यूरिस्टिक अब सिद्ध हुआ

समस्या विवरण

ग्रेडिएंट कंप्रेशन, इन्फरेंस एक्सेलेरेशन और वेक्टर डेटाबेस सर्च के लिए आधुनिक क्वांटाइजेशन फ्रेमवर्क अक्सर प्रीप्रोसेसिंग स्टेप के रूप में यूनिफॉर्म रैंडम रोटेशन्स (URRs) पर निर्भर करते हैं। URRs यह सुनिश्चित करते हैं कि इनपुट वेक्टर का $\ell_2$ नॉर्म सभी कोऑर्डिनेट्स में समान रूप से वितरित हो और उच्च आयामों (high dimensions) में व्यक्तिगत कोऑर्डिनेट्स एक गाऊसी (Gaussian) वितरण की ओर अभिसरित (converge) हों। यह सांख्यिकीय स्मूथिंग स्थिर, लगभग आयाम-मुक्त स्केलर क्वांटाइजेशन डिजाइनों (जैसे, DRIVE, QUIC-FL) को सक्षम बनाती है।

हालाँकि, URRs को कंप्यूट करने के लिए $O(d^2)$ ऑपरेशन्स की आवश्यकता होती है, जो उच्च-आयामी वेक्टर्स के लिए कम्प्यूटेशनल रूप से निषेधात्मक (prohibitive) है। फलस्वरूप, व्यावहारिक सिस्टम URRs को रैंडमाइज्ड हैडामार्ड ट्रांसफॉर्म्स (RHTs) से बदल देते हैं, जो कि स्ट्रक्चर्ड रैंडम रोटेशन्स हैं और जिन्हें $O(d \log d)$ समय में कंप्यूट किया जा सकता है। यद्यपि RHTs कुशल हैं, उनमें वर्स्ट-केस इनपुट्स के लिए URRs जैसी कठोर सैद्धांतिक गारंटी का अभाव है। विशेष रूप से, एक एकल RHT कुछ स्पार्स (sparse) इनपुट्स (जैसे, कम नॉन-जीरो एंट्री वाले यूनिट वेक्टर्स) के लिए गाऊसी जैसी मार्जिनल डिस्ट्रीब्यूशन बनाने में विफल हो सकता है, जिससे क्वांटाइजेशन स्कीम्स का प्रदर्शन गिर जाता है। संबोधित मुख्य समस्या यह है कि क्या दक्षता से समझौता किए बिना URRs की सैद्धांतिक गारंटियों को प्राप्त करने के लिए RHTs को कंपोज़ (compose) किया जा सकता है।

कार्यप्रणाली (Methodology)

लेखक एक इनपुट वेक्टर $x \in \mathbb{R}^d$ पर कई RHTs के कंपोजिशन के सांख्यिकीय गुणों का विश्लेषण करते हैं। वे एक RHT कंपोजिशन $R_k$ को $k$ हैडामार्ड मैट्रिसेस के अनुक्रम के रूप में परिभाषित करते हैं, जिन्हें रैंडम रेडेमिकर साइन्स ( $\pm 1$ ) वाले डायगोनल मैट्रिसेस द्वारा गुणा किया जाता है।

विश्लेषण तीन चरणों में आगे बढ़ता है:

स्केलर मार्जिनल्स (2-RHT): लेखक दो क्रमिक RHTs ( $R_2$ ) लागू करने के बाद एक एकल कोऑर्डिनेट के मार्जिनल डिस्ट्रीब्यूशन की जांच करते हैं। वे कोऑर्डिनेट डिस्ट्रीब्यूशन और एक स्टैंडर्ड गाऊसी डिस्ट्रीब्यूशन के बीच की दूरी को बाउंड करने के लिए बेरी-एस्टीन (Berry-Esseen) प्रमेय का उपयोग करते हैं। यह प्रमाण यह दिखाने पर आधारित है कि पहला RHT इंटरमीडिएट वेक्टर के $\ell_3$ नॉर्म (एक "फ्लैटनेस" का माप) को कम करता है, जिससे दूसरा RHT स्वतंत्र वेरिएबल्स के योग को तेजी से गाऊसी की ओर अभिसरित करने में सक्षम होता है।
वेक्टर क्वांटाइजेशन (3-RHT): वेक्टर क्वांटाइजेशन (VQ) के लिए, जहाँ कोऑर्डिनेट्स के ब्लॉक्स को संयुक्त रूप से क्वांटाइज किया जाता है, केवल मार्जिनल गाऊसियनिटी पर्याप्त नहीं है; कोऑर्डिनेट्स का कमजोर रूप से सह-संबंधित (weakly correlated) होना भी आवश्यक है। लेखक सिद्ध करते हैं कि स्पार्स इनपुट्स को डिकोरिलेट करने के लिए दो RHTs अपर्याप्त हैं क्योंकि उनमें कंडीशनल कोरिलेशन बना रहता है। वे सिद्ध करते हैं कि तीन RHTs ( $R_3$ ) का कंपोजिशन कोऑर्डिनेट्स के बीच कंडीशनल कोवेरिएंस को बाउंड करता है, जो गाऊसी कोडबुक्स के अनुकूल कमजोर निर्भरता सुनिश्चित करता है।
एडाप्टिव वेरिफिकेशन: यह पहचानते हुए कि व्यावहारिक डेटा शायद ही कभी एडवर्सरियल (adversarial) होता है, लेखक एक लीनियर-टाइम $O(d)$ चेक प्रस्तावित करते हैं। यह चेक इनपुट वेक्टर के $\ell_3$ नॉर्म (स्केलर क्वांटाइजेशन के लिए) और $\ell_\infty$ नॉर्म (वेक्टर क्वांटाइजेशन के लिए) का मूल्यांकन करता है ताकि यह निर्धारित किया जा सके कि क्या इनपुट पहले से ही पर्याप्त "फ्लैट" है जिसके लिए कम RHTs की आवश्यकता है।

मुख्य योगदान

1. 2-RHT के साथ यूनिवर्सल स्केलर मार्जिनल्स

पेपर सिद्ध करता है कि किसी भी मनमाने इनपुट वेक्टर $x$ और किसी भी निश्चित कोऑर्डिनेट $i$ के लिए, नॉर्मलाइज्ड कोऑर्डिनेट $\sqrt{d}(R_2 \hat{x})_i$ का डिस्ट्रीब्यूशन एक स्टैंडर्ड गाऊसी $G \sim N(0,1)$ की ओर $O(d^{-1/2})$ एरर बाउंड के साथ अभिसरित होता है। यह दोनों स्थितियों में सत्य है:

कोलमोगोरोव डिस्टेंस ( $d_K$ ): थ्रेशोल्डेड फंक्शन्स के लिए उपयुक्त।
1-वासरस्टीन डिस्टेंस ( $W_1$ ): लिप्सचिट्ज़ फंक्शनल्स के लिए उपयुक्त।

2. स्केलर क्वांटाइज़र के लिए औपचारिक गारंटी

लेखक इन बाउंड्स को अत्याधुनिक स्केलर क्वांटाइजेशन स्कीम्स के विश्लेषण में लागू करते हैं:

DRIVE: वे दिखाते हैं कि 2-RHTs का उपयोग करने से बायस्ड और अनबायस्ड दोनों एस्टिमेटर्स के लिए URR-आधारित नॉर्मलाइज्ड मीन स्क्वेर्ड एरर (vNMSE) बाउंड्स को $O(d^{-1/2})$ के घटते पद तक रिकवर किया जा सकता है। यह उन कमजोर बाउंड्स को समाप्त करता है जो पहले सिंगल RHT से जुड़े थे।
QUIC-FL: वे प्रदर्शित करते हैं कि 2-RHTs सटीक URR-आधारित ट्रांसमिशन बैंडविड्थ थ्रेशोल्ड्स को बहाल करते हैं। विशेष रूप से, यह आउटलियर प्रोबेबिलिटी पर लगने वाले मल्टीप्लिकेटिव पेनल्टी (लगभग $3.2\times$ ) को हटा देता है, जो सिंगल-RHT इम्प्लीमेंटेशन में समस्या थी, जिससे एरर बाउंड्स काफी टाइट हो जाते हैं (उदाहरण के लिए, 1-बिट क्वांटाइजेशन एरर को $\le 4.831$ से घटाकर $\approx 1.520$ करना)।

3. 3-RHT के साथ डिकोरिलेशन और वेक्टर क्वांटाइजेशन

पेपर स्थापित करता है कि जबकि 2-RHTs स्पार्स इनपुट्स को डिकोरिलेट करने में विफल रहते हैं (जो वर्स्ट-केस परिदृश्यों में परफेक्ट कंडीशनल कोरिलेशन की ओर ले जाता है), एक 3-RHT कंपोजिशन यह सुनिश्चित करता है कि कंडीशनल कोवेरिएंस का रूट मीन स्क्वायर (RMS) $O(\sqrt{\frac{\log d}{d}})$ के रूप में घटता है।

कोडबुक यूनिवर्सैलिटी: यह डिकोरिलेशन गारंटी सुनिश्चित करती है कि URRs (या गाऊसी डिस्ट्रीब्यूशन) के लिए अनुकूलित कोई भी फिक्स्ड, बाउंडेड कोडबुक, $d$ बढ़ने के साथ एक एडिटिव टर्म के अलावा, समान अपेक्षित क्वांटाइजेशन एरर प्रदान करेगी।

4. एडाप्टिव लीनियर-टाइम चेक

लेखक एक व्यावहारिक, $O(d)$ वेरिफिकेशन स्टेप प्रस्तावित करते हैं। इनपुट वेक्टर के $\ell_3$ नॉर्म (स्केलर कार्यों के लिए) या $\ell_\infty$ नॉर्म (VQ कार्यों के लिए) की गणना करके, एक सिस्टम यह निर्णय ले सकता है कि क्या 1, 2, या 3 RHTs वास्तव में आवश्यक हैं। यह सिस्टम को "फ्लैट" इनपुट्स पर एम्पिरिकल स्पीड बनाए रखने और एडवर्सरियल इनपुट्स के लिए वर्स्ट-केस गारंटी बनाए रखने की अनुमति देता है।

परिणाम

सैद्धांतिक रिकवरी: दो RHTs का कंपोजिशन स्केलर क्वांटाइजेशन के लिए URRs के एसिम्प्टोटिक प्रदर्शन से मेल खाने के लिए पर्याप्त है, और तीन RHTs वेक्टर क्वांटाइजेशन के लिए पर्याप्त हैं।
एरर बाउंड्स: पेपर स्पष्ट एरर बाउंड्स प्रदान करता है जो दिखाते हैं कि RHT-आधारित तरीकों और URR-आधारित तरीकों के बीच का प्रदर्शन गैप $O(d^{-1/2})$ या $O(\sqrt{\frac{\log d}{d}})$ के रूप में लुप्त हो जाता है।
बैंडविड्थ एफिशिएंसी: QUIC-FL के लिए, 2-RHT दृष्टिकोण सिंगल-RHT वर्स्ट-केस विश्लेषण के लिए आवश्यक कंजर्वेटिव $3.2\times$ बैंडविड्थ ओवर-प्रोविजनिंग की आवश्यकता को समाप्त करता है, जिससे सैद्धांतिक आवश्यकताएं URRs की दक्षता के अनुरूप हो जाती हैं।
कंप्यूटेशनल कॉम्प्लेक्सिटी: प्रस्तावित समाधान RHTs की $O(d \log d)$ जटिलता (या एडाप्टिव चेक के लिए $O(d)$ ) को बनाए रखते हैं, जिससे URRs की $O(d^2)$ लागत से बचा जा सकता है।

महत्व

पेपर का दावा है कि क्वांटाइजेशन फ्रेमवर्क में घने URRs से फास्ट, स्ट्रक्चर्ड RHTs की ओर संक्रमण ने ऐतिहासिक रूप से वर्स्ट-केस इनपुट्स के लिए एक भारी सैद्धांतिक दंड (penalty) उठाया है, जिससे इष्टतम एल्गोरिदम केवल व्यावहारिक ह्यूरिस्टिक्स बनकर रह गए हैं। यह कार्य प्रदर्शित करता है कि यह दंड स्ट्रक्चर्ड मैट्रिसेस की अंतर्निहित सीमा नहीं है, बल्कि पर्याप्त संख्या में ट्रांसफॉर्म्स का उपयोग न करने का परिणाम है।

यह सिद्ध करके कि दो या तीन RHTs का कंपोजिशन URRs के कठोर सांख्यिकीय गुणों को बहाल करता है, लेखक फेडरेटेड लर्निंग और लार्ज-स्केल वेक्टर सर्च जैसे उच्च-जोखिम वाले अनुप्रयोगों में RHTs का उपयोग करने के लिए एक सैद्धांतिक आधार प्रदान करते हैं। यह कार्य सैद्धांतिक इष्टतमता और व्यावहारिक दक्षता के बीच के अंतर को पाटता है, और एक मॉड्यूलर फ्रेमवर्क प्रदान करता है जिसे भविष्य की क्वांटाइजेशन स्कीम्स के लिए अपनाया जा सकता है। इसके अलावा, एडाप्टिव वेरिफिकेशन स्टेप यह सुनिश्चित करता है कि ये मजबूत वर्स्ट-केस गारंटियाँ औसत-केस निष्पादन (average-case execution) पर बोझ न डालें, जिससे सिस्टम इनपुट विशेषताओं के आधार पर प्रदर्शन को गतिशील रूप से अनुकूलित कर सकते हैं।