🤖 machine learning

Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization

यह लेख एक मानक घटना (standard incident) के साथ एक वेरिएंट प्रस्तावित करके नॉइज़ी गॉसियन प्रोसेस बैंडिट ऑप्टिमाइज़ेशन में एक्सपेक्टेड इम्प्रूवमेंट के अभिसरण (convergence) के खुले प्रश्न को हल करता है, जो RKHS नॉर्म या नॉइज़ मापदंडों के पूर्व ज्ञान की आवश्यकता के बिना $\mathcal{O}(\gamma_T\sqrt{T})$ का रिग्रेट बाउंड प्राप्त करता है, और इसके अलावा एक बेहतर एल्गोरिदम पेश करता है जो मौजूदा समकक्षों की तुलना में तेज़ी से अभिसरित होता है।

मूल लेखक: Hung Tran-The, Sunil Gupta, Santu Rana, Svetha Venkatesh

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

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

CC BY 4.0

मूल लेखक: Hung Tran-The, Sunil Gupta, Santu Rana, Svetha Venkatesh

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

कल्पना कीजिए कि आप एक विशाल, धुंधले पर्वत श्रृंखला में सबसे ऊँची चोटी खोजने की कोशिश कर रहे हैं। आप पूरे मानचित्र को नहीं देख सकते, और हर बार जब आप अपनी ऊँचाई की जाँच करने के लिए एक कदम उठाते हैं, तो आपका अल्टीमीटर थोड़ा डगमगाता हुआ, शोर वाला (noisy) माप प्रदान करता है। यह 'गौसियन प्रोसेस बैंडिट ऑप्टिमाइज़ेशन' (Gaussian Process Bandit Optimization) की समस्या है: एक जटिल समस्या के सर्वोत्तम समाधान को खोजने की प्रक्रिया, जब केवल शोर युक्त, अपूर्ण जानकारी उपलब्ध हो।

इसे हल करने के लिए, आपको एक रणनीति की आवश्यकता है। सबसे लोकप्रिय रणनीति को 'एक्सपेक्टेड इम्प्रूवमेंट' (Expected Improvement - EI) कहा जाता है। कल्पना कीजिए कि EI एक ऐसे पर्वतारोही की तरह है जो पूछता है: "यदि मैं इस नए स्थान पर जाता हूँ, तो मेरा दृश्य अब तक देखे गए सबसे अच्छे स्थान की तुलना में कितना बेहतर होगा?"

समस्या: "शोर वाला" पर्वतारोही

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

मुख्य बाधा "इन्कम्बेंट" (incumbent) थी - वह वर्तमान में सबसे अच्छा स्थान जिसे पर्वतारोही याद रखता है।

एक आदर्श दुनिया में (बिना शोर के), पर्वतारोही बस अब तक मिली सबसे ऊँची चोटी को याद रखता है। यह संख्या केवल बढ़ती है, जिससे ट्रैकिंग करना आसान हो जाता है।
शोर वाली दुनिया में, "सबसे अच्छा" स्थान केवल माप की एक भाग्यशाली त्रुटि (lucky error) हो सकता है। यदि पर्वतारोही इस त्रुटिपूर्ण संख्या को अपने संदर्भ के रूप में उपयोग करता है, तो गणित जटिल हो जाता है और ढह जाता है। इसे ठीक करने के पिछले प्रयासों के लिए पर्वतारोही को पर्वत श्रृंखला के बारे में कुछ गुप्त, छिपे हुए नंबरों (जैसे कि ज़मीन कितनी चिकनी है या अल्टीमीटर कितना शोर वाला है) को जानने की आवश्यकता थी। वास्तविक दुनिया में, हालांकि, आमतौर पर व्यक्ति इन रहस्यों को नहीं जानता है।

समाधान: चलने का एक नया तरीका

इस शोध पत्र के लेखकों, हंग ट्रां-थे (Hung Tran-The) और उनकी टीम ने, इस "शोर वाले पर्वतारोही" की समस्या को हल करने के लिए एक नई विधि प्रस्तावित की।

1. मानक समाधान (GP-EI):
उन्होंने सिद्ध किया कि एक मानक, सरल संदर्भ मान (मानचित्र से प्राप्त सर्वोत्तम अनुमानित औसत ऊँचाई, न कि शोर वाला कच्चा माप) का उपयोग किया जा सकता है और फिर भी यह गारंटी दी जा सकती है कि पर्वतारोही अंततः चोटी को खोज लेगा।

परिणाम: उन्होंने गणितीय रूप से दिखाया कि यह विधि अभिसरित (converge) होती है (चोटी को खोज लेती है) और उन्होंने एक "रिग्रेट बाउंड" (regret bound) प्रदान किया। पर्वतारोही की शब्दावली में, "रिग्रेट" वह कुल ऊँचाई है जो उसने वास्तविक चोटी पर खड़े न होने के कारण खो दी। उन्होंने सिद्ध किया कि उनके पर्वतारोही का रिग्रेट इतनी धीरे बढ़ता है कि पर्वतारोही कुशल रहता है।
बोनस: पिछले तरीकों के विपरीत, उनके पर्वतारोही को पर्वत श्रृंखला के गुप्त "चिकनापन" (smoothness) या अल्टीमीटर के "शोर" (shakiness) को जानने की आवश्यकता नहीं है। वे बस चढ़ाई शुरू कर देते हैं।

2. सुपर-फास्ट समाधान (Improved-GP-EI):
उन्होंने महसूस किया कि बहुत जटिल पर्वत श्रृंखलाओं (उच्च आयामों/dimensions) के लिए, पहला तरीका अभी भी लंबा समय ले सकता है क्योंकि पर्वतारोही एक ही क्षेत्रों की बार-बार जाँच कर सकता है।
इसलिए, उन्होंने Improved-GP-EI बनाया।

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

प्रमाण: पर्वतारोही पर भरोसा क्यों करें?

यह शोध पत्र गणितीय रूप से भारी है, लेकिन मुख्य तर्क इस प्रकार है:

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

परीक्षण (The Test Drive)

यह सुनिश्चित करने के लिए कि उनका सिद्धांत केवल एक सुंदर गणितीय युक्ति नहीं है, उन्होंने कंप्यूटर सिमुलेशन पर इसका परीक्षण किया:

सिंथेटिक पर्वत: उन्होंने नकली, जटिल गणितीय परिदृश्य (जैसे हार्टमैन और एक्ली फंक्शन) बनाए और अपने एल्गोरिदम को चोटी खोजने के लिए छोड़ा।
प्रतिस्पर्धा: उन्होंने अपने "Improved-GP-EI" पर्वतारोही की तुलना अन्य प्रसिद्ध पर्वतारोहियों (जैसे GP-UCB और Standard-GP-EI) के साथ की।
परिणाम: उनका Improved-GP-EI पर्वतारोही अन्य पर्वतारोहियों की तुलना में अधिक तेज़ी से और अधिक विश्वसनीयता के साथ चोटियों को खोज पाया, विशेष रूप से तब जब "गुप्त पैरामीटर" (जैसे कि सटीक शोर का स्तर) अज्ञात थे।

सारांश

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

यहाँ पेपर "Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह पेपर गॉसियन-प्रोसेस-(GP-)बैंडिट ऑप्टिमाइजेशन की समस्या को संबोधित करता है, विशेष रूप से एक नॉन-बायेसियन सेटिंग (जहाँ फलन निश्चित है लेकिन अज्ञात है और एक रिप्रोड्यूसिंग कर्नेल हिल्बर्ट स्पेस या RKHS में स्थित है) में। इसका लक्ष्य एक महंगे ब्लैक-बॉक्स फलन $f(x)$ को अधिकतम करने के लिए अनुक्रमिक रूप से बिंदुओं $x_t$ का चयन करना है, जो शोर युक्त अवलोकनों $y_t = f(x_t) + \epsilon_t$ पर आधारित होते हैं।

प्रदर्शन को संचयी रिग्रेट (cumulative regret) $R_T = \sum_{t=1}^T (f(x^*) - f(x_t^+))$ द्वारा मापा जाता है, जहाँ $x^*$ वैश्विक इष्टतम (global optimum) है और $x_t^+$ एल्गोरिदम द्वारा इटरेशन $t$ तक रिपोर्ट किया गया सबसे अच्छा बिंदु है।

मुख्य चुनौती:
यद्यपि अपनी सरलता के कारण एक्स्पेक्टेड इम्प्रूवमेंट (Expected Improvement - EI) एल्गोरिदम बायेसियन ऑप्टिमाइजेशन के लिए एक लोकप्रिय ह्यूरिस्टिक है, लेकिन नॉइजी सेटिंग (noisy setting) में इसके सैद्धांतिक अभिसरण (convergence) गुणों पर प्रश्न बना हुआ था।

शोर-मुक्त (noise-free) सेटिंग्स में, "इन्कंबेंट" (वर्तमान सर्वोत्तम मान) केवल देखा गया अधिकतम मान होता है, जो कि एक मोनोटोनिक (monotonic) होता है।
नॉइजी सेटिंग्स में, इन्कंबेंट आमतौर पर GP प्रेडिक्टिव मीन ( $\mu_t^+$ ) का अधिकतम या नॉइजी ऑब्जर्वेशन ( $y_t^+$ ) का अधिकतम होता है।
$\pi$ -GP-UCB जैसे पिछले कार्यों के विपरीत, यहाँ GP प्रेडिक्टिव मीन $\mu_t^+$ समय के साथ मोनोटोनिक नहीं होता है। यह कमी मानक सैद्धांतिक विश्लेषण को अत्यंत कठिन बना देती है जो इन्कंबेंट की मोनोटोनिसिटी पर निर्भर करता है। पिछले कार्यों में या तो अज्ञात मापदंडों (जैसे RKHS नॉर्म बाउंड $B$ और सब-गॉसियन प्रॉपर्टी $R$ ) के ज्ञान की आवश्यकता थी या उन्होंने गैर-मानक इन्कंबेंट्स का उपयोग किया था जिनमें महंगे ग्लोबल ऑप्टिमाइजेशन स्टेप्स की आवश्यकता होती थी।

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

लेखक इन सैद्धांतिक और व्यावहारिक अंतरालों को भरने के लिए दो मुख्य एल्गोरिदम प्रस्तावित करते हैं।

A. स्टैंडर्ड GP-EI (Standard Incumbent के साथ)

पहला योगदान एक मानक GP-EI एल्गोरिदम का कठोर विश्लेषण है, जहाँ इन्कंबेंट को देखे गए बिंदुओं पर GP प्रेडिक्टिव मीन के अधिकतम के रूप में परिभाषित किया गया है:
$\xi_t = \mu_t^+ = \max_{x_i \in D_{t-1}} \mu_{t-1}(x_i)$

एक्विजिशन फंक्शन (Acquisition Function): एल्गोरिदम अगले बिंदु $x_t$ को एक्सपेक्टेड इम्प्रूवमेंट को अधिकतम करके चुनता है:
$\alpha_{EI}(x) = \mathbb{E}[\max\{0, f(x) - \mu_t^+\} | D_t]$
इसे फलन $\rho(u, v) = u\Phi(u/v) + v\phi(u/v)$ का उपयोग करके क्लोज्ड फॉर्म में कंप्यूट किया जाता है।
टाइम-वेरिंग स्केलिंग फैक्टर (Time-Varying Scaling Factor): शोर को संभालने और RKHS नॉर्म ( $B$ ) या शोर पैरामीटर ( $R$ ) के ज्ञान के बिना अभिसरण सुनिश्चित करने के लिए, एल्गोरिदम एक समय-परिवर्तित स्केलिंग पैरामीटर $\omega_t = \sqrt{\gamma_{t-1} + 1 + \ln(1/\delta)}$ का उपयोग करता है, जहाँ $\gamma_t$ अधिकतम इंफॉर्मेशन गेन है।
प्रमुख सैद्धांतिक नवाचार: लेखक $\mu_t^+$ की नॉन-मोनोटोनिसिटी को वैरिएंस फंक्शन की मोनोटोनिसिटी ( $\sigma_t(x)$ बढ़ने के साथ घटता है) का लाभ उठाकर दूर करते हैं। वे इंस्टेंटेनियस रिग्रेट को डिकम्पोज़ करते हैं और इस वैरिएंस प्रॉपर्टी का उपयोग करके "इम्प्रूवमेंट टर्म्स" के योग को बाउंड करते हैं, एक ऐसी तकनीक जिसे पहले इस तरह से GP बैंडिट ऑप्टिमाइजेशन में लागू नहीं किया गया था।

B. इम्प्रूव्ड-GP-EI (Improved-GP-EI)

स्टैंडर्ड GP-EI की सीमाओं (विशेष रूप से, यह तथ्य कि मैटर्न कर्नेल के लिए रिग्रेट बाउंड हमेशा सबलीनियर नहीं होता है और $\omega_t$ बहुत तेज़ी से बढ़ता है, जिससे अनावश्यक एक्सप्लोरेशन होता है) को दूर करने के लिए, लेखक Improved-GP-EI प्रस्तावित करते हैं।

प्रेरणा: इसे $\pi$ -GP-UCB एल्गोरिदम (Janz et al., 2020) से अनुकूलित किया गया है।
पार्टीशनिंग स्ट्रैटेजी (Partitioning Strategy): सर्च स्पेस को हाइपरक्यूब्स (एक कवरिंग) में विभाजित किया जाता है। प्रत्येक हाइपरक्यूब पर, केवल स्थानीय डेटा का उपयोग करके एक स्वतंत्र GP फिट किया जाता है।
ग्लोबल स्केलिंग: एक टाइम-वेरिंग $\omega_t$ के बजाय, एक फिक्स्ड ग्लोबल स्केलिंग $\omega_T = \sqrt{\ln(T)\ln\ln(T)}$ का उपयोग किया जाता है, जो केवल पॉलीलॉगारिदमिक रूप से बढ़ता है।
मैकेनिज्म: प्रत्येक चरण में, एल्गोरिदम वर्तमान सर्वोत्तम उम्मीदवार वाले विशिष्ट हाइपरक्यूब के भीतर EI को अधिकतम करके एक बिंदु चुनता है, जिससे प्रभावी रूप से लोकलाइजेशन (localization) होता है।

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

स्टैंडर्ड GP-EI के लिए प्रथम सैद्धांतिक गारंटी:
यह पेपर यह सिद्ध करने वाला पहला प्रमाण प्रदान करता है कि नॉइजी सेटिंग में स्टैंडर्ड इन्कंबेंट ( $\xi = \mu_t^+$ ) के साथ GP-EI अभिसरित (converge) होता है।
- रिग्रेट बाउंड: संचयी रिग्रेट $O(\gamma_T \sqrt{T})$ द्वारा बाउंड है।
- पैरामीटर स्वतंत्रता: महत्वपूर्ण रूप से, इस एल्गोरिदम को RKHS नॉर्म बाउंड ( $B$ ) या शोर के सब-गॉसियन पैरामीटर ( $R$ ) के ज्ञान की आवश्यकता नहीं है, जो वास्तविक दुनिया के अनुप्रयोगों में अज्ञात होते हैं।
Improved-GP-EI एल्गोरिदम:
एक नया वेरिएंट जो मैटर्न कर्नेल के लिए तेज़ कन्वर्जेंस रेट प्राप्त करता है।
- रिग्रेट बाउंड: मैटर्न कर्नेल्स के लिए स्मूथनेस $\nu > 1$ के साथ, रिग्रेट $\tilde{O}(T^{\frac{d(2d+3)+2\nu}{d(2d+4)+4\nu}})$ है। यह सभी $\nu > 1$ और $d \geq 1$ के लिए सबलीनियर है, जो स्टैंडर्ड GP-EI की सीमाओं में सुधार करता है।
- दक्षता: एक पार्टीशनिंग स्ट्रैटेजी और पॉलीलॉगारिदमिक स्केलिंग पैरामीटर का उपयोग करके, यह अनावश्यक एक्सप्लोरेशन को रोकता है और पिछले तरीकों में देखे गए तेजी से बढ़ते वैरिएंस स्केल से बचता है।
नवीन प्रमाण तकनीकें (Novel Proof Techniques):
लेखक एक ऐसी प्रमाण रणनीति पेश करते हैं जो GP प्रेडिक्टिव मीन इन्कंबेंट की नॉन-मोनोटोनिसिटी को संभालने के लिए GP वैरिएंस फंक्शन की घटती मोनोटोनिसिटी का लाभ उठाती है।

4. परिणाम (Results)

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

Standard GP-EI: $O(\gamma_T \sqrt{T})$ का रिग्रेट प्राप्त करता है। स्क्वेयर्ड एक्सपोनेंशियल (SE) कर्नेल्स के लिए, यह सबलीनियर है। मैटर्न कर्नेल्स के लिए, यह सबलीनियर है यदि $2\nu > d$ हो।
Improved-GP-EI: एक टाइट रिग्रेट बाउंड प्राप्त करता है जो सभी $\nu > 1$ के लिए सबलीनियर है। यह $\pi$ -GP-UCB के रिग्रेट रेट से मेल खाता है लेकिन $B$ और $R$ के ज्ञान की आवश्यकता को समाप्त करता है।

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

लेखकों ने सिंथेटिक फंक्शन्स (Hartmann3, Shekel, Hartmann6, Ackley) और RKHS स्पेस से उत्पन्न फंक्शन्स पर अपने एल्गोरिदम का परीक्षण किया।

प्रदर्शन: Improved-GP-EI लगातार स्टैंडर्ड GP-EI, मॉडिफाइड-GP-EI और स्टेट-ऑफ-द-आर्ट $\pi$ -GP-UCB से बेहतर प्रदर्शन करता है।
मजबूती (Robustness): $\pi$ -GP-UCB के विपरीत, जिसे अज्ञात मापदंडों ( $B$ और $R$ ) के ह्यूरिस्टिक ट्यूनिंग की आवश्यकता होती है और जो गलत अनुमान लगाने पर खराब प्रदर्शन करता है, Improved-GP-EI इन बाउंड्स के संबंध में पैरामीटर-फ्री है और बेहतर स्थिरता प्रदर्शित करता है।
दक्षता: Improved-GP-EI में पार्टीशनिंग स्ट्रैटेजी ने कम्प्यूटेशनल जटिलता को कम किया। उदाहरण के लिए, Hartmann3 पर प्रति इटरेशन औसत रनटाइम Improved-GP-EI के लिए 1.21 मिनट था, जबकि स्टैंडर्ड GP-EI के लिए यह 1.37 मिनट था; बड़े हॉरिज़न्स पर यह अंतर बढ़ जाता है क्योंकि यह छोटे लोकल मैट्रिसेस को इनवर्ट करता है।

5. महत्व (Significance)

यह पेपर गॉसियन प्रोसेस बैंडिट्स के लिए एक्सपेक्टेड इम्प्रूवमेंट के सैद्धांतिक विश्लेषण के एक लंबे समय से खुले प्रश्न को हल करता है।

सिद्धांत और व्यवहार को जोड़ना: यह सिद्ध करता है कि सबसे लोकप्रिय ह्यूरिस्टिक (EI) बिना किसी 'ओरेकल-लाइक' ज्ञान (जैसे फंक्शन स्मूथनेस या नॉइज़ लेवल) के नॉइजी वातावरण में सैद्धांतिक रूप से सुदृढ़ है।
व्यावहारिक प्रयोज्यता: अज्ञात मापदंडों ( $B$ और $R$ ) पर निर्भरता को समाप्त करके, प्रस्तावित एल्गोरिदम वास्तविक दुनिया के परिदृश्यों (जैसे रोबोटिक्स, हाइपरपैरामीटर ट्यूनिंग) के लिए तुरंत लागू करने योग्य हैं, जहाँ इन मानों का अनुमान लगाना कठिन या असंभव है।
एल्गोरिद्मिक प्रगति: Improved-GP-EI UCB-आधारित तरीकों के लिए एक मजबूत, पैरामीटर-फ्री विकल्प प्रदान करता है और यह दर्शाता है कि EI-आधारित रणनीतियाँ कर्नेल चयन और पैरामीटर अनिश्चितता के प्रति अधिक मजबूत होते हुए भी इष्टतम रिग्रेट रेट प्राप्त कर सकती हैं।