📊 statistics

The Price of Hidden Curvature: An $\widetilde{\Omega} (d^{5/4} \sqrt{T})$ Lower Bound for Bandit Convex Optimization

यह शोध पत्र 1-लिप्सचिट्ज़ (1-Lipschitz) फलनों के स्टोकेस्टिक बैंडिट कॉनवेक्स ऑप्टिमाइज़ेशन के लिए $\widetilde{\Omega}(d^{5/4}\sqrt{T})$ का पहला गैर-तुच्छ मिनिमैक्स रिग्रेट लोअर बाउंड (nontrivial minimax regret lower bound) स्थापित करता है, जो यह सिद्ध करता है कि यह समस्या लीनियर बैंडिट्स की तुलना में मौलिक रूप से कठिन है, क्योंकि यह फलनों का एक कठिन वर्ग निर्मित करता है जहाँ एक अज्ञात लीनियर ट्रांसफ़ॉर्मेशन और एक लक्ष्य वेक्टर को सीखना अन्वेषण (exploration) और सूचना एकत्र करने (information gathering) के बीच एक कठिन समझौते की मांग करता है।

मूल लेखक: Nived Rajaraman

प्रकाशित 2026-07-22

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

CC BY 4.0

मूल लेखक: Nived Rajaraman

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

कल्पना कीजिए कि आप एक कंप्यूटर के साथ "सीक्रेट गेस" (गुप्त अनुमान) के एक हाई-स्टेक्स खेल में खेल रहे हैं। आप एक विशाल, बहु-आयामी परिदृश्य (multi-dimensional landscape) में एक सटीक स्थान खोजने की कोशिश कर रहे हैं ताकि एक छिपे हुए स्कोर को कम किया जा सके। हर बार जब आप एक स्थान चुनते हैं, तो कंप्यूटर आपको आपका स्कोर बताता है, लेकिन एक ट्विस्ट के साथ: यह उसमें थोड़ा सा स्टैटिक नॉइज़ (static noise) जोड़ देता है, जैसे रेडियो का स्टेशन थोड़ा सा हट जाना। यह स्टोकेस्टिक बैंडिट कॉनवेक्स ऑप्टिमाइज़ेशन (stochastic bandit convex optimization) की दुनिया है। यह मशीन लर्निंग की एक मौलिक समस्या है जहाँ एक एल्गोरिदम को बिना पूरे मानचित्र को देखे, परीक्षण और त्रुटि (trial and error) के माध्यम से सर्वोत्तम निर्णय लेना सीखना होता है।

वर्षों तक, शोधकर्ताओं का मानना था कि इस खेल की कठिनाई मुख्य रूप से इस बात पर निर्भर करती है कि परिदृश्य में कितने आयाम (dimensions) हैं। उन्हें लगा कि यदि आपके कार्यों और स्कोर के बीच एक रैखिक संबंध (linear relationship) है (जैसे एक सीधी रेखा), तो खेल कठिन है, लेकिन यदि संबंध वक्र (convex) है, तो यह केवल थोड़ा सा अधिक कठिन है। प्रचलित धारणा यह थी कि जीतने के लिए आवश्यक अनुमानों की संख्या आपके द्वारा किए गए कुल समय के वर्गमूल के अनुपात में आयामों की संख्या के साथ बढ़ती है। यह एक आरामदायक, अनुमानित लय थी। लेकिन क्या होगा अगर परिदृश्य केवल एक साधारण वक्र नहीं था? क्या होगा अगर इसमें एक छिपा हुआ, जटिल ज्यामिति (geometry) थी जो इसे किसी के भी अनुमान से कहीं अधिक कठिन बना देती है?

यह शोध पत्र, जिसका शीर्षक द प्राइस ऑफ हिडन कर्वेचर (The Price of Hidden Curvature) है, इस खेल में कदम रखता है और पुरानी लय को तोड़ देता है। लेखकों ने, निवेद राजरामन (जिन्होंने प्रमाण को परिष्कृत करने के लिए एक उन्नत एआई मॉडल के साथ सहयोग किया), एक विशिष्ट, जटिल प्रकार का वक्र बनाया है जो शिक्षार्थी को पुराने नियमों की तुलना में बहुत अधिक मेहनत करने के लिए मजबूर करता है। वे सिद्ध करते हैं कि कुछ 1-लिप्सचिट्ज़ कॉनवेक्स फंक्शन्स (1-Lipschitz convex functions - ऐसे फंक्शन जो बहुत अधिक नहीं बदलते) के लिए, एक निकट-पूर्ण समाधान खोजने के लिए आवश्यक अनुमानों की संख्या पहले के अनुमान से बहुत तेजी से बढ़ती है। विशेष रूप से, वे दिखाते हैं कि एक निचला स्तर (lower bound) लगभग $d^{5/4}\sqrt{T}$ है, जहाँ $d$ आयामों की संख्या है और $T$ राउंड की संख्या है। यह पिछले सर्वोत्तम अनुमान $d\sqrt{T}$ से एक सख्त सुधार है, जो यह सिद्ध करता है कि स्टोकेस्टिक बैंडिट कॉनवेक्स ऑप्टिमाइज़ेशन अपने रैखिक समकक्ष (linear cousin) की तुलना में मौलिक रूप से कठिन है।

अदृश्य ट्यूब का रहस्य

यह समझने के लिए कि यह इतना कठिन क्यों है, कल्पना कीजिए कि परिदृश्य एक चिकनी पहाड़ी नहीं, बल्कि एक विशाल, बहु-आयामी कमरा है जो एक विशिष्ट प्रकार के जाल से भरा हुआ है। लेखकों ने एक "हार्ड क्लास" के फंक्शन डिज़ाइन किए हैं जो एक सॉफ्ट मैक्सिमम (soft maximum) के रूप में दिखते हैं: एक "ट्यूब" और एक "डिस्टेंस फंक्शन" का मिश्रण।

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

लक्ष्य (जिसे हम $u^*$ कह सकते हैं) इस गलियारे के भीतर एक विशिष्ट बिंदु है जिसे आपको खोजना है। पेच यह है कि आपको नहीं पता कि गलियारा कहाँ है क्योंकि आप गुप्त घुमाव $W^*$ को नहीं जानते हैं। यह एक भूलभुलैया में एक विशिष्ट कमरे को खोजने जैसा है, लेकिन भूलभुलैया स्वयं एक गुप्त कोड के आधार पर अपना आकार बदल रही है।

दो-चरणीय नृत्य (The Two-Step Dance)

शिक्षार्थी एक भयानक दुविधा में फंसा हुआ है, एक "खींचातानी" (tug-of-war) के बीच:

ट्यूब की खोज करें (Explore the Tube): आपको गलियारे के आकार ( $W^*$ ) का अनुमान लगाना होगा ताकि आप जान सकें कि कहाँ चलना है। लेकिन आकार का अनुमान लगाने के लिए, आपको ऐसे कदम उठाने होंगे जो आपको गलियारे से बाहर ले जा सकते हैं, जहाँ आपको कोई जानकारी नहीं मिलेगी।
लक्ष्य को खोजें (Find the Target): एक बार जब आप गलियारे के अंदर होते हैं, तो आप अंततः लक्ष्य $u^*$ को सीखना शुरू कर सकते हैं। लेकिन आप गलियारे के अंदर तब तक नहीं जा सकते जब तक आप यह नहीं जान लेते कि वह कहाँ है।

शोध पत्र दिखाता है कि यह ट्रेड-ऑफ अविश्वसनीय रूप से महंगा है। गलियारे के आकार को इतना सीखने के लिए कि आप उसमें प्रवेश कर सकें, और फिर उसके अंदर लक्ष्य को खोजने के लिए, आपको भारी संख्या में अनुमान लगाने की आवश्यकता होती है। लेखक सिद्ध करते हैं कि प्रत्येक आयाम जोड़ने के साथ, लागत केवल रैखिक रूप से नहीं बढ़ती; यह विस्फोट करती है।

प्रमाण: सूचना का एक खेल

लेखकों ने केवल अनुमान नहीं लगाया; उन्होंने एक गणितीय किला बनाया है। उन्होंने एक "गौसियन प्रायर" (Gaussian prior) का उपयोग किया, जो अनिवार्य रूप से यह कहने का एक तरीका है कि "मान लीजिए कि गुप्त कोड $W^*$ और लक्ष्य $u^*$ एक विशिष्ट वितरण से यादृच्छिक रूप से चुने गए हैं।"

उन्होंने फिर "फिशर इंफॉर्मेशन" (Fisher information) का विश्लेषण किया, जो सूचना मापने का एक शानदार तरीका है कि एक एकल अनुमान आपको छिपे हुए रहस्यों के बारे में कितनी जानकारी देता है। उन्होंने दिखाया कि:

लक्ष्य $u^*$ को सीखने के लिए, आपको कई अलग-अलग दिशाओं में बहुत सारी जानकारी एकत्र करने की आवश्यकता है।
लेकिन आप केवल तभी एक दिशा में जानकारी एकत्र कर सकते हैं जब आप पहले से ही उस दिशा के लिए ट्यूब के अंदर हों।
ट्यूब के अंदर जाने के लिए गुप्त कोड $W^*$ को सीखना आवश्यक है, जो महंगा है।

इन लागतों को संतुलित करके, उन्होंने एक सूत्र निकाला जिससे पता चलता है कि एक अच्छा समाधान खोजने के लिए आवश्यक अनुमानों की कुल संख्या $d^{5/2}/\epsilon^2$ (जहाँ $\epsilon$ पूर्णता से आपकी निकटता है) के रूप में स्केल करती है। जब आप इसे वापस "रिग्रेट" (कुल स्कोर जो आप पूर्णता से खेलने से खो देते हैं) में अनुवादित करते हैं, तो यह $d^{5/4}\sqrt{T}$ हो जाता है।

यह क्यों महत्वपूर्ण है

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

लेखकों ने यह भी जांचा कि क्या उनका निर्माण सबसे अच्छा संभव था। उन्होंने दिखाया कि एक चतुर एल्गोरिदम इस विशिष्ट प्रकार की समस्या को लगभग उतने ही चरणों में हल कर सकता है, जिसका अर्थ है कि उनका निचला स्तर (lower bound) इस विशिष्ट सेटअप के लिए सटीक है। उन्होंने प्रमाण को विस्तारित भी किया ताकि यह दिखाया जा सके कि यह कठिनाई तब भी बनी रहती है जब आप एक बॉल (ball) के भीतर सीमित नहीं हैं और अनंत स्थान में कहीं भी चल सकते हैं।

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

तकनीकी सारांश: छिपी हुई वक्रता की कीमत (The Price of Hidden Curvature)

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

यह शोध पत्र स्टोकेस्टिक बैंडिट कॉनवेक्स ऑप्टिमाइज़ेशन (BCO) की मौलिक सीमाओं को संबोधित करता है। इस सेटिंग में, एक शिक्षार्थी (learner) एक अज्ञात उत्तल फलन (convex function) $f: \mathcal{A} \to \mathbb{R}$ को एक उत्तल क्रिया स्थान (convex action space) $\mathcal{A} \subseteq \mathbb{R}^d$ पर न्यूनतम करने का प्रयास करता है, जहाँ वह क्रमिक रूप से क्रियाएं $a_t$ चुनता है और शोर युक्त अवलोकन (noisy observations) $r_t = f(a_t) + Z_t$ प्राप्त करता है, जहाँ $Z_t$ i.i.d. गॉसियन शोर (Gaussian noise) है। प्रदर्शन मीट्रिक मिनिमैक्स अपेक्षित पछतावा (minimax expected regret) है, जिसे $T$ राउंड के दौरान शिक्षार्थी के संचयी नुकसान और इष्टतम नुकसान के बीच के सबसे खराब मामले के अंतर के रूप में परिभाषित किया गया है।

इस कार्य से पूर्व, सामान्य लिप्शिट्ज (Lipschitz) उत्तल फलनों के लिए ज्ञात सबसे मजबूत आयाम-निर्भर निचला बाउंड (dimension-dependent lower bound) $\tilde{\Omega}(d\sqrt{T})$ था, जो लीनियर बैंडिट्स (linear bandits) से विरासत में मिला था। यह सुझाव देता था कि कॉनवेक्स बैंडिट्स, लीनियर बैंडिट्स की तुलना में मौलिक रूप से अधिक कठिन नहीं होंगे। यह शोध पत्र जांच करता है कि क्या यह अंतर्ज्ञान यूक्लिडियन बॉल $\mathcal{A} = B^d_2$ और अनकन्स्ट्रेंड स्पेस $\mathcal{A} = \mathbb{R}^d$ के लिए 1-लिप्शिट्ज उत्तल फलनों के वर्ग पर लागू होता है।

कार्यप्रणाली और निर्माण (Methodology and Construction)

लेखक एक "कठिन" (hard) फलन वर्ग का निर्माण करते हैं जिसे एक छिपी हुई ज्यामितीय संरचना को सीखने और एक लक्ष्य पैरामीटर का अनुमान लगाने के बीच ट्रेड-ऑफ (tradeoff) को मजबूर करने के लिए डिज़ाइन किया गया है। यह निर्माण आयाम $2d$ में संचालित होता है, जो क्रिया $a = (a_1, a_2) \in \mathbb{R}^d \times \mathbb{R}^d$ को विभाजित करता है।

कठिन फलन वर्ग (The Hard Function Class)

ग्राउंड-ट्रुथ फलन $f_{\theta^*}$ एक छिपे हुए लीनियर ट्रांसफॉर्मेशन $W^* \in \mathbb{R}^{d \times d}$ और एक लक्ष्य वेक्टर $u^* \in \mathbb{R}^d$ द्वारा पैरामीटराइज्ड है। फलन को दो शाखाओं के स्केल्ड सॉफ्ट-मैक्सिमम (scaled soft-maximum) के रूप में परिभाषित किया गया है:

ट्यूब शाखा (The Tube Branch): एक स्क्वेर्ड डिस्टेंस टर्म $\frac{1}{r} \| W^* a_1 - \frac{r}{8\varepsilon} a_2 \|^2$ । यह टर्म केवल तभी छोटा होता है जब $a_2 \approx \frac{8\varepsilon}{r} W^* a_1$ हो, जो क्रिया स्थान में एक संकीर्ण "ट्यूब" (tube) को परिभाषित करता है।
लक्ष्य शाखा (The Target Branch): एक स्क्वेर्ड डिस्टेंस टर्म $\frac{1}{2} \| a_1 - u^* \|^2 - \frac{1}{2} \| u^* \|^2$ , जो तब न्यूनतम होता है जब $a_1 \approx u^*$ हो।

फलन औपचारिक रूप से है:
$f_{\theta^*}(a) = \varepsilon \cdot \text{softmax}\left( \frac{1}{r} \left\| W^* a_1 - \frac{r}{8\varepsilon} a_2 \right\|^2, \frac{1}{2} \| a_1 - u^* \|^2 - \frac{1}{2} \| u^* \|^2 \right)$

मुख्य कठिनाई (The Core Difficulty)

कम पछतावा (regret) प्राप्त करने के लिए, शिक्षार्थी को एक ऐसी क्रिया ढूंढनी होगी जहाँ दोनों शाखाएं छोटी हों। इसके लिए आवश्यक है:

$u^*$ (लक्ष्य) का पता लगाना।
ट्यूब बाधा (tube constraint) $a_2 \approx \frac{8\varepsilon}{r} W^* a_1$ को संतुष्ट करना।

महत्वपूर्ण रूप से, ट्यूब शाखा फलन के मान पर हावी रहती है जब तक कि शिक्षार्थी की क्रिया ट्यूब के भीतर न हो। यदि शिक्षार्थी ट्यूब के बाहर की क्रिया चुनता है, तो अवलोकन $u^*$ के बारे में कोई जानकारी प्रदान नहीं करता, चाहे $a_1$ , $u^*$ के कितने भी करीब क्यों न हो। चूंकि $W^*$ अज्ञात है, इसलिए शिक्षार्थी नियत रूप से (deterministically) ट्यूब के भीतर प्रवेश नहीं कर सकता। उन्हें या तो:

$W^*$ को एक्सप्लोर करना होगा: ट्यूब के स्थान की भविष्यवाणी करने के लिए $W^*$ की दिशाओं को सीखने में नमूने (samples) खर्च करने होंगे।
ट्यूब का अनुमान लगाना होगा: $W^* a_1$ का अनुमान लगाकर ट्यूब में प्रवेश करने का प्रयास करना होगा, जो पूर्व ज्ञान के बिना अत्यधिक असंभव है।

यह एक तनाव पैदा करता है: $u^*$ को सीखने के लिए ट्यूब के भीतर होना आवश्यक है, लेकिन ट्यूब को खोजने के लिए $W^*$ को सीखना आवश्यक है।

विश्लेषणात्मक ढांचा (Analytical Framework)

प्रमाण $W^*$ और $u^*$ पर एक गॉसियन प्रायर (Gaussian prior) के साथ एक बेयसियन ढांचे (Bayesian framework) का उपयोग करता है। विश्लेषण दो प्रमुख सूचना-सैद्धांतिक मात्राओं पर निर्भर करता है:

$u^*$ के लिए लाइकलीहुड फिशर इंफॉर्मेशन ( $\mathcal{I}^u_n$ ): यह $u^*$ के बारे में प्राप्त जानकारी को मापता है। पेपर सिद्ध करता है कि $u^*$ का स्थिर त्रुटि (constant error) तक अनुमान लगाने के लिए, $\mathcal{I}^u_n$ के कई बड़े आइगेनवैल्यू (eigenvalues) होने चाहिए।
$W^*$ के लिए पोस्टीरियर फिशर इंफॉर्मेशन ( $K_t$ ): यह छिपे हुए मैप $W^*$ के बारे में प्राप्त जानकारी को मापता है।

केंद्रीय तकनीकी योगदान लेम्मा 2.2 (Lemma 2.2) है, जो इन दोनों मैट्रिसेस के बीच एक "तनाव" स्थापित करता है। यह दिखाता है कि $u^*$ के बारे में पर्याप्त फिशर इंफॉर्मेशन (ताकि $\mathcal{I}^u_n$ में बड़े आइगेनवैल्यू मिल सकें) प्राप्त करने की लागत, $W^*$ को सीखने की लागत द्वारा सीमित है। विशेष रूप से, $W^*$ के फिशर इंफॉर्मेशन एनवेलप के व्युत्क्रम (inverse) का ट्रेस, $u^*$ के बारे में प्राप्त जानकारी द्वारा भारित (weighted), एक सीमा से बंधा हुआ है। यह शिक्षार्थी को $u^*$ को प्रभावी ढंग से सीखने से पहले $W^*$ को सीखने में महत्वपूर्ण नमूने खर्च करने के लिए मजबूर करता है।

मुख्य परिणाम (Key Results)

एस्टीमेशन लोअर बाउंड (Estimation Lower Bound)

थ्योरम 1.1 (Theorem 1.1) एक $\varepsilon$ -इष्टतम क्रिया खोजने के लिए आवश्यक सैंपल कॉम्प्लेक्सिटी पर निचला बाउंड स्थापित करता है। किसी भी एडेप्टिव लर्नर के लिए जो $n$ क्वेरी करता है, यदि $n < c_2 \frac{d^{5/2}}{\varepsilon^2 \log(ed)}$ , तो एक ऐसा फलन मौजूद है जिसमें अपेक्षित उप-इष्टतमता (suboptimality) कम से कम $c_0 \varepsilon$ है।

रिग्रेट लोअर बाउंड (Regret Lower Bound)

कोरोलरी 1.2 (Corollary 1.2) एस्टीमेशन बाउंड को रिग्रेट लोअर बाउंड में अनुवादित करती है। $T \geq C d^3 / \log(ed)$ के लिए, मिनिमैक्स रिग्रेट संतुष्ट करता है:
$\mathfrak{R}^*_T(d; B^d_2) \geq c d^{5/4} \sqrt{\frac{T}{\log(ed)}}$
इस परिणाम को थ्योरम 5.2 के माध्यम से अनकन्स्ट्रेंड सेटिंग $\mathcal{A} = \mathbb{R}^d$ में एक स्मूदनिंग कॉनिक एक्सटेंशन (smoothed conic extension) के माध्यम से विस्तारित किया गया है जो यूनिट बॉल के बाहर भी हार्डनेस गुणों को बनाए रखता है।

टाइटनेस (Tightness)

थ्योरम 5.1 एक दो-चरणीय बेयसियन एल्गोरिदम (E2B) प्रस्तुत करता है जो लोअर बाउंड में उपयोग किए गए विशिष्ट गॉसियन प्रायर के लिए $\tilde{O}(d^{5/2}/\varepsilon^2)$ का ऊपरी बाउंड (upper bound) प्राप्त करता है। यह दर्शाता कि लोअर बाउंड उपयोग किए गए विशिष्ट प्रायर के लिए टाइट (tight) है, जिससे पुष्टि होती है कि $d^{5/4}$ फैक्टर प्रमाण तकनीक का एक आर्टिफैक्ट नहीं है, बल्कि इस प्रकार के फलनों का एक मौलिक गुण है।

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

पेपर का दावा है कि यह स्टोकेस्टिक बैंडिट कॉनवेक्स ऑप्टिमाइज़ेशन के लिए पहला गैर-तुच्छ (nontrivial) रिग्रेट लोअर बाउंड स्थापित करता है जो लीनियर बैंडिट बाउंड $\tilde{\Omega}(d\sqrt{T})$ से स्पष्ट रूप से अधिक बढ़ता है।

कॉनवेक्स और लीनियर बैंडिट्स का पृथक्करण: यह परिणाम सिद्ध करता है कि यूक्लिडियन बॉल पर स्टोकेस्टिक बैंडिट कॉनवेक्स ऑप्टिमाइज़ेशन, लीनियर बैंडिट्स की तुलना में मौलिक रूप से कठिन है। जबकि लीनियर बैंडिट्स $d\sqrt{T}$ के रूप में स्केल करते हैं, निर्मित कॉनवेक्स इंस्टेंस $d^{5/4}\sqrt{T}$ के रूप में स्केल करते हैं।
छिपी हुई वक्रता की भूमिका: कठिनाई "छिपी हुई वक्रता" (hidden curvature) से उत्पन्न होती है—सूचना प्रकट करने वाले क्षेत्र (ट्यूब) की ज्यामिति को निर्धारित करने वाले एक छिपे हुए लीनियर ट्रांसफॉर्मेशन ( $W^*$ ) को सीखने की आवश्यकता। यह संरचना मानक लीनियराइजेशन (linearization) तर्कों के उपयोग को रोकता है जो स्मूथ या लीनियर फलनों के लिए काम करते हैं।
वर्तमान अपर बाउंड की सीमाएं: पेपर नोट करता है कि सर्वोत्तम ज्ञात अपर बाउंड $\tilde{O}(d^{3/2}\sqrt{T})$ है। लोअर बाउंड ( $d^{5/4}$ ) और अपर बाउंड ( $d^{3/2}$ ) के बीच का अंतर खुला है। लेखक अनुमान लगाते हैं कि वास्तविक मिनिमैक्स रेट $\tilde{\Theta}(d^{3/2}\sqrt{T})$ है, जो यह सुझाव देता है कि वर्तमान लोअर बाउंड निर्माण, हालांकि अपने विशिष्ट प्रायर के लिए अनुकूल है, सामान्य समस्या की पूरी कठिनाई को कैप्चर नहीं कर सकता है, या अधिक टाइट अपर बाउंड की आवश्यकता है।

लेखक स्पष्ट रूप से कहते हैं कि उनका निर्माण $W^*$ और $u^*$ को सीखने के बीच एक विशिष्ट ट्रेड-ऑफ पर निर्भर करता है, और सरल विस्तार (जैसे अधिक ट्यूब जोड़ना या चौड़ाई बदलना) तुरंत अधिक मजबूत एक्सपोनेंट (exponents) प्रदान नहीं करते हैं, जो इस कठिनाई की विशिष्ट ज्यामितीय प्रकृति को उजागर करता है।