📊 statistics

Randomized Subspace Nesterov Accelerated Gradient

यह शोधपत्र स्मूथ कॉनवेक्स (smooth convex) और स्ट्रॉन्गली कॉनवेक्स (strongly convex) ऑप्टिमाइज़ेशन के लिए रैंडमाइज्ड-सबस्पेस नेस्टरोव एक्सीलरेटेड ग्रेडिएंट मेथड्स पेश करता है जो एक्सीलरेटेड ओरकल कॉम्प्लेक्सिटी प्राप्त करने के लिए मैट्रिक्स स्मूथनेस और स्केच डिस्ट्रीब्यूशन का लाभ उठाते हैं, जो संभावित रूप से फुल-डायमेंशनल नेस्टरोव एक्सीलरेशन से बेहतर प्रदर्शन कर सकते हैं।

मूल लेखक: Gaku Omiya, Pierre-Louis Poirion, Akiko Takeda

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

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

CC BY 4.0

मूल लेखक: Gaku Omiya, Pierre-Louis Poirion, Akiko Takeda

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

कल्पना कीजिए कि आप एक विशाल, धुंधली घाटी (एक जटिल गणितीय समस्या का "इष्टतम समाधान") में सबसे निचले बिंदु को खोजने की कोशिश कर रहे हैं। आप पूरी घाटी को देख नहीं सकते, इसलिए आपको अपने पैरों के ठीक नीचे की ढलान के आधार पर कदम उठाने होंगे। यह इस तरह है जैसे कंप्यूटर आधुनिक एआई (AI) में विशाल अनुकूलन (optimization) समस्याओं को हल करते हैं।

आमतौर पर, यह जानने के लिए कि "नीचे" की दिशा कौन सी है, आपको एक साथ हर दिशा में ढलान की जांच करने की आवश्यकता होती है। यदि घाटी में 1,000 आयाम (dimensions) हैं (जो आधुनिक एआई का एक सामान्य आकार है), तो इसका मतलब है कि हर एक कदम के लिए 1,000 माप लेने होंगे। यह सटीक है, लेकिन धीमा और महंगा है, जैसे कि यह बताने के लिए कि आपको किस दिशा में चलना है, 1,000 स्काउट्स (जासूसों) को काम पर रखना।

समस्या: बहुत अधिक स्काउट्स
चीजों को तेज करने के लिए, शोधकर्ता "रैंडमाइज्ड सबस्पेस" (Randomized Subspace) विधियों का उपयोग करते हैं। केवल 1,000 स्काउट्स को काम पर रखने के बजाय, वे केवल कुछ ही (मान लीजिए 10) को नियुक्त करते हैं ताकि घाटी के एक यादृच्छिक (random), कम-आयामी हिस्से में ढलान की जांच की जा सके। यह बहुत सस्ता और तेज़ है। हालांकि, इसमें एक पेंच है: सामान्य "स्मार्ट" चलने की तकनीकें (जिन्हें नेस्टरोव एक्सेलेरेशन कहा जाता है) जो आमतौर पर आपको तेजी से नीचे ले जाने में मदद करती हैं, जब आपके पास केवल कुछ ही स्काउट्स होते हैं, तो वे अच्छी तरह से काम नहीं करती हैं। यदि आप केवल कुछ ही स्काउट्स के साथ "स्मार्ट" तकनीक का उपयोग करने का प्रयास करते हैं, तो गणित बिगड़ जाता है, और आपको वह गति नहीं मिलती जिसकी आपने अपेक्षा की थी।

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

यहाँ मुख्य विचार सरल भाषा में समझाया गया है:

पुराना तरीका (दो-चरणीय नृत्य): पारंपरिक एक्सेलेरेशन दो चलते हुए हिस्सों का उपयोग करता है: आपकी वर्तमान स्थिति और एक "मोमेंटम" (momentum) स्थिति। यह एक डांसर की तरह है जो आगे बढ़ने के लिए दीवार से धक्का देकर फिसल रहा है। लेकिन जब आपके पास केवल आंशिक जानकारी (कुछ स्काउट्स) होती है, तो यह दो-चरणीय नृत्य भ्रमित हो जाता है और लड़खड़ाने लगता है।
नया तरीका (तीन-चरणीय नृत्य): लेखकों ने महसूस किया कि उन्हें इस नृत्य में एक तीसरे साथी की आवश्यकता है। उन्होंने एक तीन-अनुक्रम (three-sequence) संरचना पेश की।
- अनुक्रम 1: आपकी वर्तमान स्थिति।
- अनुक्रम 2: आपकी "मोमेंटम" स्थिति (जहाँ आप लक्ष्य बना रहे हैं)।
- अनुक्रम 3: एक विशेष "सहायक" स्थिति जो एक पुल (bridge) के रूप में कार्य करती है।

यह तीसरा अनुक्रम रैंडम स्काउट्स के "शोर" (noise) और अपूर्णता को संभालने के लिए तैयार किया गया है। यह एक सुरक्षा जाल की तरह कार्य करता है जो एल्गोरिदम को बिना खाई में गिरे, बड़े और आत्मविश्वासी कदम उठाने की अनुमति देता है, भले ही वह परिदृश्य के केवल एक छोटे से हिस्से को देख रहा हो।

"स्केच" की उपमा
स्काउट्स को घाटी के एक स्केच के रूप में सोचें।

फुल ग्रेडिएंट: आपको पूरी घाटी की एक हाई-रिज़ॉल्यूशन फोटो मिलती है। (महंगा, धीमा)।
रैंडमाइज्ड सबस्पेस: आपको केवल कुछ पहाड़ियों का एक त्वरित, लो-रिज़ॉल्यूशन स्केच मिलता है। (सस्ता, तेज़)।

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

मुख्य निष्कर्ष सरल अंग्रेजी में

यह चिकनी पहाड़ियों के लिए काम करता है: उन्होंने गणितीय रूप से सिद्ध किया कि यह विधि दो प्रकार की घाटियों के लिए काम करती है: जो केवल "चिकनी" (convex) हैं और जो "चिकनी और कटोरे के आकार की" (strongly convex) हैं।
यह तेज़ है: "ओरेकल कॉम्प्लेक्सिटी" (एक फैंसी तरीका यह गिनने का कि आपको स्काउट्स से कितनी बार ढलान पूछनी पड़ती है) के मामले में, उनकी विधि पुराने गैर-एक्सेलेरेटेड रैंडम तरीकों की तुलना में काफी तेज़ है।
"सर्वश्रेष्ठ" स्केच का आकार: उन्होंने स्काउट्स को चुनने के विभिन्न तरीकों (Haar, Coordinate, और Gaussian sketches) का परीक्षण किया। उन्होंने पाया कि, आश्चर्यजनक रूप से, सबसे छोटी टीम (केवल 1 स्काउट) का उपयोग करना अक्सर काम को कम समय में पूरा करने का सबसे कुशल तरीका है।
वास्तविक दुनिया के परीक्षण: उन्होंने वास्तविक दुनिया के डेटा (जैसे कैंसर की भविष्यवाणी करना या छवियों को वर्गीकृत करना) पर इसका परीक्षण किया। परिणाम दिखाते हैं कि उनकी नई विधि लगातार मानक विधियों से बेहतर प्रदर्शन करती है, विशेष रूप से जब विशिष्ट डेटा के लिए सही प्रकार के "स्केच" का उपयोग किया जाता है।

निष्कर्ष
यह शोध पत्र एक लंबे समय से चले आ रहे पहेली को सुलझाता है: "हम अनुकूलन एल्गोरिदम को कैसे तेज़ (प्रति चरण कम डेटा का उपयोग करके) और स्मार्ट (एक्सेलेरेशन का उपयोग करके) बना सकते हैं?"

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

यहाँ ओमिया, पोइरियन और ताकेडा के शोध पत्र "Randomized Subspace Nesterov Accelerated Gradient" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र स्मूथ कॉन्वेक्स (smooth convex) और स्मूथ स्ट्रॉन्गली कॉन्वेक्स (smooth strongly convex) समस्याओं के लिए रैंडमाइज्ड सबस्पेस ऑप्टिमाइजेशन विधियों (randomized subspace optimization methods) को त्वरित करने की चुनौती का समाधान करता है।

संदर्भ: उच्च-आयामी अनुकूलन (high-dimensional optimization) (जैसे, मशीन लर्निंग) में, पूर्ण ग्रेडिएंट $\nabla f(x) \in \mathbb{R}^d$ की गणना करना महंगा होता है। रैंडमाइज्ड सबस्पेस विधियाँ एक स्केच मैट्रिक्स $P_k \in \mathbb{R}^{d \times r}$ (जहाँ $r \ll d$ ) का उपयोग करके एक निम्न-आयामी रैंडम सबस्पेस के साथ अपडेट करके लागत को कम करती हैं। यह अपडेट आमतौर पर $x_{k+1} = x_k - \alpha P_k P_k^\top \nabla f(x_k)$ के रूप में होता है।
अंतराल (The Gap): जबकि नेस्टरोव एक्सेलेरेटेड ग्रेडिएंट (NAG) फुल-ग्रेडिएंट और कोऑर्डिनेट-डिसेंट विधियों के लिए अच्छी तरह से समझा गया है, सामान्य रैंडमाइज्ड सबस्पेस स्केचेस (general randomized subspace sketches) तक त्वरण (acceleration) का विस्तार करना गैर-तुच्छ (non-trivial) है।
ओरेकल मॉडल (The Oracle Model): लेखक एक ओरेकल कॉम्प्लेक्सिटी मॉडल पर ध्यान केंद्रित करते हैं जो फॉरवर्ड-मोड ऑटोमैटिक डिफरेंशिएशन (forward-mode automatic differentiation) और कम्युनिकेशन-लिमिटेड डिस्ट्रीब्यूटेड सेटिंग्स के लिए प्रासंगिक है। इस मॉडल में, एक पूर्ण ग्रेडिएंट की लागत $d$ ओरेकल कॉल (डायरेक्शनल डेरिवेटिव्स) है, जबकि एक प्रोजेक्टेड ग्रेडिएंट $P_k^\top \nabla f(x)$ की लागत केवल $r$ कॉल है। लक्ष्य $\epsilon$ -सटीक समाधान तक पहुँचने के लिए आवश्यक कुल ओरेकल कॉल्स की संख्या को कम करना है।
चुनौती: नेस्टरोव एक्सेलरेशन के साथ सबस्पेस अपडेट्स का एक सीधा संयोजन (एक डायरेक्ट टू-सीक्वेंस स्कीम) सामान्य स्केच डिस्ट्रीब्यूशन के तहत त्वरित अभिसरण गारंटी (accelerated convergence guarantees) प्रदान करने में विफल रहता है, क्योंकि मानक प्रमाण तकनीकें (एस्टीमेट सीक्वेंस) सीधे स्टोकेस्टिक सबस्पेस सेटिंग में लागू नहीं होती हैं।

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

लेखक दोनों कॉन्वेक्स और स्ट्रॉन्गली कॉन्वेक्स सेटिंग्स के लिए रैंडमाइज्ड सबस्पेस नेस्टरोव एक्सेलेरेटेड ग्रेडिएंट (RS-NAG) विधियों का प्रस्ताव करते हैं।

मुख्य तकनीकी नवाचार: थ्री-सीक्वेंस फॉर्मूलेशन (Three-Sequence Formulation)

मानक NAG के विपरीत, जो दो-अनुक्रम पुनरावृत्ति ( $x_k, y_k$ ) का उपयोग करता है, प्रस्तावित विधि एक तीन-अनुक्रम फॉर्मूलेशन ( $x_k, y_k, z_k$ ) पेश करती है जो मैट्रिक्स स्मूथनेस (matrix smoothness) के लिए तैयार की गई है।

मैट्रिक्स स्मूथनेस: केवल एक स्केलर लिप्सचिट्ज़ स्थिरांक $L$ मानने के बजाय, यह शोध पत्र मानता है कि फलन एक मैट्रिक्स स्मूथनेस स्थिति को संतुष्ट करता है:
$f(y) \le f(x) + \langle \nabla f(x), y-x \rangle + \frac{1}{2}(y-x)^\top L (y-x)$
जहाँ $L \succeq 0$ एक निश्चित मैट्रिक्स है।
स्केच मोमेंट धारणाएँ (Sketch Moment Assumptions): रैंडम स्केच मैट्रिसेस $P_k$ $P_{k}$ को i.i.d. माना गया है और वे $\omega$ $ω$ और $\ell$ $ℓ$ स्थिरांकों वाले विशिष्ट मोमेंट कंडीशंस को संतुष्ट करते हैं:
1. अनबायस्डनेस (Unbiasedness): $\mathbb{E}[P_k P_k^\top] = I_d$
2. सेकंड-मोमेंट बाउंड (Second-moment bound): $\mathbb{E}[(P_k P_k^\top)^2] \preceq \omega I_d$
3. मैट्रिक्स स्मूथनेस इंटरैक्शन: $\mathbb{E}[P_k P_k^\top L P_k P_k^\top] \preceq \ell L$

एल्गोरिदम (Algorithms)

RS-NAG-C (Convex): यह $m = 1/(2L\ell)$ से प्राप्त वेट्स $A_k$ और स्टेप साइज़ की एक श्रृंखला का उपयोग करता है। इसमें एक स्केच्ड ग्रेडिएंट स्टेप और एक सहायक अनुक्रम $z_k$ शामिल है जो ग्रेडिएंट्स को संचित करता है।
RS-NAG-SC (Strongly Convex): यह एक कॉन्ट्रैक्शन पैरामीटर $\theta = \sqrt{\mu / (L\omega\ell)}$ का उपयोग करता है। पुनरावृत्ति (recursion) वर्तमान इटरैट, सहायक अनुक्रम और स्केच्ड ग्रेडिएंट को मिलाती है ताकि लीनियर कन्वर्जेंस प्राप्त किया जा सके।

दोनों एल्गोरिदम शास्त्रीय नेस्टरोव विधियों में बदल जाते हैं जब $r=d$ और $P_k P_k^\top = I_d$ हो।

3. मुख्य योगदान (Key Contributions)

सामान्य रैंडमाइज्ड सबस्पेस स्केचेस के लिए पहला एक्सेलेरेटेड फ्रेमवर्क: यह शोध पत्र सामान्य रैंडमाइज्ड सबस्पेस ग्रेडिएंट विधियों के लिए पहला एक्सेलेरेटेड मेथड प्रदान करता है जो गैर-एक्सेलेरेटेड सबस्पेस विधियों और मानक फुल-डायमेंशनल NAG की तुलना में ओरेकल कॉम्प्लेक्सिटी के मामले में बेहतर है।
नया थ्री-सीक्वेंस एनालिसिस: लेखक एक तीन-अनुक्रम लियापुनोव फंक्शन (three-sequence Lyapunov function) का उपयोग करके एक नया अभिसरण विश्लेषण ढांचा विकसित करते हैं। यह शास्त्रीय दो-अनुक्रम नेस्टरोव प्रमाणों को सीधे सबस्पेस अपडेट्स पर लागू करने की सीमाओं को दूर करता है, जिसके लिए पहले प्रतिबंधात्मक "नियर-फुल-डायमेंशनल" धारणाओं की आवश्यकता थी।
ओरेकल कॉम्प्लेक्सिटी गारंटी: शोध पत्र स्पष्ट अभिसरण दरें (convergence rates) प्राप्त करता है जो स्केच डिस्ट्रीब्यूशन पैरामीटर्स ( $\omega, \ell$ $ω, ℓ$ ) और मैट्रिक्स स्मूथनेस ( $L$ $L$ ) पर निर्भर करती हैं।
- कॉन्वेक्स केस: फंक्शन वैल्यू में $O(1/N^2)$ अभिसरण प्राप्त करता है, जिससे $O\left( \sqrt{\omega \ell r^2} \frac{R_0 \sqrt{L}}{\sqrt{\epsilon}} \right)$ की ओरेकल कॉम्प्लेक्सिटी मिलती है।
- स्ट्रॉन्गली कॉन्वेक्स केस: लीनियर कन्वर्जेंस प्राप्त करता है, जिससे $O\left( \sqrt{\omega \ell r^2} \sqrt{\frac{L}{\mu}} \log \frac{\Delta_0}{\epsilon} \right)$ की ओरेकल कॉम्प्लेक्सिटी मिलती है।
स्केच तुलना और अनुकूलन: लेखक इष्टतम सबस्पेस डायमेंशन $r$ $r$ निर्धारित करने के लिए तीन मानक स्केच परिवारों (Haar, Coordinate, और Gaussian) का विश्लेषण करते हैं।
- वे सिद्ध करते हैं कि इन स्केचेस के लिए, ओरेकल कॉम्प्लेक्सिटी फैक्टर $\sqrt{\omega \ell r^2}$ $r=1$ पर न्यूनतम होता है।
- वे स्पष्ट स्थिरांक ( $Q_H, Q_C, Q_G$ ) निकालते हैं जो दिखाते हैं कि अनुकूल परिस्थितियों के तहत (जैसे, कम प्रभावी रैंक या विशिष्ट डायगोनल संरचना), $r=1$ के साथ सबस्पेस एक्सेलरेशन, फुल-डायमेंशनल नेस्टरोव एक्सेलरेशन (फैक्टर $d$ ) से लगभग $\sqrt{d}$ के फैक्टर से बेहतर प्रदर्शन कर सकता है।

4. परिणाम (Results)

सैद्धांतिक परिणाम (Theoretical Results)

अभिसरण (Convergence): प्रमेय 3.3 और 4.3 स्थापित करते हैं कि RS-NAG त्वरित दरें प्राप्त करता है। कॉम्प्लेक्सिटी बाउंड्स स्पष्ट रूप से दिखाते हैं कि कैसे स्केच पैरामीटर्स $\omega$ और $\ell$ , मैट्रिक्स स्मूथनेस $L$ के साथ इंटरैक्ट करते हैं।
तुलना: पेपर की टेबल 1 दर्शाती है कि RS-NAG, कॉन्वेक्स केस में फंक्शन वैल्यू के लिए $1/\epsilon$ (RS-GD के लिए) से $1/\sqrt{\epsilon}$ (RS-NAG के लिए) में सुधार करता है, और स्ट्रॉन्गली कॉन्वेक्स केस में कंडीशन नंबर डिपेंडेंस को $L/\mu$ से $\sqrt{L/\mu}$ में सुधार करता है।
स्केच चयन: प्रपोजिशन 5.2 दिखाता है कि Haar, Coordinate, और Gaussian स्केचेस के लिए, इष्टतम सबस्पेस डायमेंशन $r=1$ $r = 1$ है।
- Haar Sketch: $Q_H \approx d \sqrt{\frac{r_{eff}}{d}}$ ।
- Coordinate Sketch: $Q_C \approx d \sqrt{\delta_{diag}}$ ।
- Gaussian Sketch: $Q_G \approx \sqrt{d \cdot r_{eff}}$ ।
- कई मामलों में, ये कारक $d$ से काफी छोटे हैं, जो फुल-डायमेंशनल नेस्टरोव एक्सेलरेशन (फैक्टर $d$ ) की तुलना में स्पीडअप का संकेत देते हैं।

अनुभवजन्य परिणाम (Empirical Results)

क्वाड्रेटिक प्रयोग: सिंथेटिक क्वाड्रेटिक समस्याओं पर प्रयोग पुष्टि करते हैं कि $r=1$ अक्सर इष्टतम होता है। प्रदर्शन सैद्धांतिक स्थिरांक $Q$ के अनुरूप है। उदाहरण के लिए, छोटे प्रभावी रैंक वाले डायगोनल मैट्रिसेस पर, Haar और Gaussian स्केचेस, कोऑर्डिनेट स्केचेस और फुल-डायमेंशनल NAG से बेहतर प्रदर्शन करते हैं।
लॉजिस्टिक रिग्रेशन: वास्तविक दुनिया के डेटासेट्स (जैसे, colon-cancer, leukemia, gisette) पर परीक्षणों से पता चलता है कि RS-NAG-SC लगातार स्टैंडर्ड ग्रेडिएंट डिसेंट (GD) से बेहतर प्रदर्शन करता है और अक्सर फुल-डायमेंशनल NAG से भी बेहतर होता है। स्केच प्रकारों का सापेक्ष प्रदर्शन (Haar बनाम Coordinate बनाम Gaussian) डेटासेट-डिपेंडेंट मात्राओं ( $r_{eff}, \delta_{diag}$ ) के आधार पर सैद्धांतिक भविष्यवाणियों से मेल खाता है।

5. महत्व (Significance)

सिद्धांत और व्यवहार को जोड़ना: यह पेपर रैंडमाइज्ड सबस्पेस विधियों के त्वरण के संबंध में एक लंबे समय से चली आ रही सैद्धांतिक कमी को दूर करता है। यह एक कठोर ढांचा प्रदान करता है जो न्यायसंगत बनाता है कि सबस्पेस एक्सेलरेशन कब और क्यों काम करता है।
उच्च आयामों में दक्षता: यह सिद्ध करके कि $r=1$ अक्सर इष्टतम होता है, यह कार्य सुझाव देता है कि अत्यंत निम्न-आयामी प्रोजेक्शन, गणना/कम्युनिकेशन लागत और अभिसरण गति के बीच सबसे अच्छा संतुलन प्रदान कर सकते हैं। यह बड़े पैमाने पर डिस्ट्रीब्यूटेड लर्निंग और मेमोरी बाधाओं वाले सेटिंग्स (फॉरवर्ड-मोड AD) के लिए महत्वपूर्ण है।
एकीकृत ढांचा (Unified Framework): मैट्रिक्स स्मूथनेस धारणा विभिन्न कंप्रेशन और स्केचिंग तकनीकों के विश्लेषण को एकीकृत करती है, जिससे विभिन्न स्केच डिस्ट्रीब्यूशन की उनके हेसियन स्ट्रक्चर (Hessian structure) के साथ इंटरैक्शन के आधार पर सीधी तुलना संभव होती है।
व्यावहारिक मार्गदर्शन: प्राप्त स्थिरांक ( $Q_H, Q_C, Q_G$ ) अभ्यासकर्ताओं को अनुकूलन एल्गोरिदम चलाने से पहले विशिष्ट डेटासेट के लिए सबसे अच्छा स्केच डिस्ट्रीब्यूशन चुनने के लिए एक व्यावहारिक ह्यूरिस्टिक प्रदान करते हैं।

संक्षेप में, यह कार्य सफलतापूर्वक रैंडमाइज्ड सबस्पेस रिजीम में नेस्टरोव एक्सेलरेशन को विस्तारित करता है, और यह सिद्ध करता है कि सही थ्री-सीक्वेंस फॉर्मूलेशन और मैट्रिक्स-स्मूथनेस विश्लेषण के साथ, एक इष्टतम ओरेकल कॉम्प्लेक्सिटी प्राप्त की जा सकती है जो अक्सर फुल-डायमेंशनल एक्सेलरेशन से बेहतर होती है।