🤖 machine learning

Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise

यह शोध पत्र हेवी-टेल्ड नॉइज़ (heavy-tailed noise) के तहत नॉनकॉन्वेक्स नॉनस्मूथ ऑप्टिमाइज़ेशन समस्याओं को हल करने के लिए क्लिप्ड टू-पॉइंट ग्रेडिएंट एस्टिमेटर के साथ एक स्टोकेस्टिक ज़ीरो-ऑर्डर एल्गोरिदम प्रस्तावित करता है, जो इष्टतम डायमेंशन-डिपेंडेंट कॉम्प्लेक्सिटी प्राप्त करता है और गोल्डस्टीन स्टेशनरी पॉइंट्स के लिए सर्वोत्तम ज्ञात सटीकता दरों से मेल खाता है।

मूल लेखक: Zhuanghua Liu, Luo Luo

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

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

CC BY 4.0

मूल लेखक: Zhuanghua Liu, Luo Luo

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

कल्पना कीजिए कि आप एक विशाल, धुंधले और ऊबड़-खाबड़ पहाड़ी क्षेत्र में सबसे निचले बिंदु को खोजने की कोशिश कर रहे हैं। यह मशीन लर्निंग की एक सामान्य समस्या है: मॉडल को सटीक भविष्यवाणियां करने के लिए सर्वोत्तम सेटिंग्स खोजना।

एक आदर्श दुनिया में, आपके पास एक मानचित्र और एक दिशा-सूचक यंत्र (ग्रेडिएंट्स) होगा जो आपको ठीक से बताएगा कि नीचे जाने का रास्ता कौन सा है। लेकिन वास्तविक दुनिया में, विशेष रूप से जटिल AI मॉडल्स के साथ, आप अक्सर ढलान को देख नहीं पाते हैं। आप केवल दो स्थानों पर जमीन को टटोल सकते हैं और पूछ सकते हैं, "क्या यह यहाँ ऊँचा है या नीचा?" इसे ज़ेरोथ-ऑर्डर ऑप्टिमाइज़ेशन (Zeroth-Order Optimization) कहा जाता है।

अब, कल्पना कीजिए कि इस पहाड़ी क्षेत्र में मौसम बहुत खराब है। हल्की हवा के बजाय, आप अचानक, विशाल और अप्रत्याशित तूफानों (जिन्हें हेवी-टेल्ड नॉइज़/Heavy-Tailed Noise कहा जाता है) की चपेट में आ जाते हैं। ये तूफान इतने जंगली हैं कि मानक मौसम पूर्वानुमान (जो मानते हैं कि तूफान आमतौर पर छोटे होते हैं) पूरी तरह विफल हो जाते हैं। यदि आप एक ऐसे दिशा-सूचक यंत्र का उपयोग करने की कोशिश करते हैं जो इन विशाल तूफानों के कारण अपने रास्ते से भटक जाता है, तो आप कभी भी तल तक नहीं पहुँच पाएंगे।

यहाँ बताया गया है कि कैसे शोध पत्र "Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise" इस समस्या को हल करता है, जिसे सरल भाषा में समझाया गया है:

1. समस्या: "तूफानी" पहाड़

लेखक एक विशिष्ट प्रकार के पहाड़ के साथ काम कर रहे हैं:

नॉनकॉन्वेक्स (Nonconvex): ज़मीन पहाड़ियों, घाटियों और पठारों से भरी है, न कि केवल एक चिकने कटोरे की तरह।
नॉनस्मूथ (Nonsmooth): ज़मीन ऊबड़-खाबड़ और पथरीली है, कांच की तरह चिकनी नहीं।
हेवी-टेल्ड नॉइज़ (Heavy-Tailed Noise): "हवा" (डेटा नॉइज़) जो आपके मापन को धकेलती है, वह अप्रत्याशित है। कभी-कभी यह एक हल्की हवा होती है, लेकिन कभी-कभी यह एक तूफान होता है जो आपके माप को बेतहाशा गलत दिशा में फेंक देता है। पिछले अधिकांश तरीकों ने माना था कि हवा हमेशा हल्की होती है, जो वास्तविकता में सच नहीं है।

2. समाधान: "क्लिप्ड" कंपास (ZOCOON)

लेखक एक नया एल्गोरिदम प्रस्तावित करते हैं जिसे ZOCOON (Zeroth-Order Clipped Online-to-Nonconvex) कहा जाता है। इसे एक स्मार्ट नेविगेशन रणनीति के रूप में समझें जिसमें दो मुख्य तरकीबें हैं:

तरकीब A: "दो-बिंदु टटोलना" (The Two-Point Poke)
चूंकि आप ढलान नहीं देख सकते, इसलिए एल्गोरिदम दो बिंदुओं को चुनता है जो एक-दूसरे के बहुत करीब हैं और दोनों जगह जमीन को टटोलता है। ऊंचाई के अंतर की तुलना करके, यह ढलान की दिशा का अनुमान लगाता है। बिना मानचित्र के नेविगेट करने का यह मानक तरीका है।

तरकीब B: "तूफान कवच" (The Storm Shield - Clipping)
यह इस शोध पत्र का बड़ा नवाचार है। जब एल्गोरिदम दो टटोलने (pokes) का उपयोग करके ढलान की गणना करता है, तो "तूफान" वाला शोर परिणाम को ऐसा दिखा सकता है जैसे जमीन 90-डिग्री के कोण पर ढल रही हो (जो असंभव है)।

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

3. लक्ष्य: "पर्याप्त अच्छा" स्थान खोजना

क्योंकि पहाड़ इतना ऊबड़-खाबड़ है, यह साबित करना गणितीय रूप से असंभव है कि आपने परफेक्ट निचला बिंदु खोज लिया है। इसलिए, लेखक एक "गोल्डस्टीन स्टेशनरी पॉइंट" (Goldstein Stationary Point) की तलाश करते हैं।

उपमा: पूरी दुनिया के एकमात्र सबसे निचले बिंदु को खोजने के बजाय, वे एक ऐसे स्थान की तलाश करते हैं जहाँ, यदि आप अपने आस-पास एक छोटे घेरे के भीतर जमीन को देखें, तो औसत ढलान समतल हो। यह एक "पर्याप्त अच्छा" विश्राम स्थल है जहाँ आपके और नीचे फिसलने की संभावना नहीं है।

4. परिणाम: यह क्यों काम करता है

यह शोध पत्र गणितीय रूप से सिद्ध करता है कि ZOCOON काम करता है, भले ही "तूफान" बहुत बड़े हों।

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

सारांश

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

तकनीकी सारांश: हैवी-टेल्ड नॉइज़ के साथ ज़ीरोथ-ऑर्डर नॉनकॉन्वेक्स नॉनस्मूथ ऑप्टिमाइज़ेशन

समस्या का स्वरूप (Problem Formulation)
यह शोध पत्र अनकन्स्ट्रेंड स्टोकेस्टिक ऑप्टिमाइज़ेशन समस्या को संबोधित करता है:
$\min_{x \in \mathbb{R}^d} f(x) = \mathbb{E}_{\xi \sim P}[F(x; \xi)]$
जहाँ ऑब्जेक्टिव फंक्शन $f$ नॉनकॉन्वेक्स और नॉनस्मूथ है, लेकिन लिप्सचिट्ज़ कंटीन्यूअस (Lipschitz continuous) है। यह सेटिंग ज़ीरोथ-ऑर्डर (zeroth-order) है, जिसका अर्थ है कि एल्गोरिदम के पास केवल नॉइज़ी फंक्शन इवैल्यूएशन $F(x; \xi)$ तक पहुँच है, न कि ग्रेडिएंट तक।

पूर्ववर्ती कार्यों से एक महत्वपूर्ण विचलन शोर (noise) की धारणा है। जबकि अधिकांश मौजूदा विश्लेषण बाउंडेड वेरिएंस धारणा (सेकंड-ऑर्डर मोमेंट) पर निर्भर करते हैं, यह शोध पत्र हैवी-टेल्ड नॉइज़ (heavy-tailed noise) धारणा के तहत कार्य करता है। विशेष रूप से, स्टोकेस्टिक कंपोनेंट फंक्शन का लिप्सचिट्ज़ कांस्टेंट $L(\xi)$ एक बाउंडेड $p$ -थ मोमेंट कंडीशन को संतुष्ट करता है:
$\mathbb{E}[L(\xi)^p] \leq L^p$
जहाँ $p \in (1, 2]$ है। जब $p < 2$ होता है, तो वेरिएंस अनबाउंडेड हो सकता है, जो हैवी-टेल्ड डिस्ट्रीब्यूशंस (जैसे लेवी $\alpha$ -स्टेबल) की विशेषता है, जो डीप न्यूरल नेटवर्क या रिइन्फोर्समेंट लर्निंग जैसे वास्तविक दुनिया के मशीन लर्निंग अनुप्रयोगों में सामान्यतः देखे जाते हैं।

कार्यप्रणाली: ZOCOON एल्गोरिदम
लेखक Zeroth-Order Clipped Online-to-Nonconvex (ZOCOON) एल्गोरिदम प्रस्तावित करते हैं। यह विधि तीन मुख्य घटकों को एकीकृत करती है:

ऑनलाइन-टू-नॉनकॉन्वेक्स कन्वर्जन फ्रेमवर्क: कटकोस्की एट अल. [9] द्वारा स्थापित और कोर्नोव्स्की और शामिर [25] द्वारा विस्तारित फ्रेमवर्क पर निर्माण करते हुए, यह एल्गोरिदम एक ऑनलाइन लर्निंग समस्या को नॉनकॉन्वेक्स ऑप्टिमाइज़ेशन सॉल्वर में परिवर्तित करता है। इसमें एक स्टेशनरी पॉइंट खोजने के लिए राउंड्स के माध्यम से अपडेट्स का एक क्रम चलाना शामिल है।
टू-पॉइंट स्टोकेस्टिक ग्रेडिएंट एस्टीमेटर: चूंकि ग्रेडिएंट उपलब्ध नहीं हैं, इसलिए एल्गोरिदम स्मूथड सरोगेट फंक्शन $f_{\delta'}(x)$ पर आधारित ज़ीरोथ-ऑर्डर एस्टीमेटर का उपयोग करता है। एक बिंदु $x$ और यूनिट स्फीयर पर एक रैंडम दिशा $w$ के लिए, एस्टीमेटर है:
$\hat{g}(x; w, \xi) = \frac{d}{2\delta'} (F(x + \delta'w; \xi) - F(x - \delta'w; \xi))w$
यह स्मूथड फंक्शन के ग्रेडिएंट का एक अनबायस्ड एस्टीमेट प्रदान करता है।
ग्रेडिएंट क्लिपिंग (Gradient Clipping): हैवी-टेल्ड नॉइज़ के प्रभाव को कम करने के लिए, एल्गोरिदम ग्रेडिएंट एस्टीमेटर पर एक क्लिपिंग ऑपरेटर शामिल करता है। अपडेट स्टेप $\hat{g}_{clipped} = \text{clip}(\hat{g}, \tau)$ का उपयोग करता है, जहाँ $\tau$ एक थ्रेशोल्ड पैरामीटर है। यह बड़े, नॉइज़ी ग्रेडिएंट्स को ऑप्टिमाइज़ेशन प्रक्रिया को अस्थिर करने से रोकता है।

एल्गोरिदम रीस्टार्ट्स के साथ एपोक्स (epochs) में संचालित होता है, जो कन्वर्जेंस गारंटी सुनिश्चित करने के लिए औसत इटरेट के सेट से एक यूनिफॉर्मली रैंडम पॉइंट आउटपुट करता है।

मुख्य योगदान और सैद्धांतिक परिणाम
यह शोध पत्र एक $(\delta, \epsilon)$ -Goldstein स्टेशनरी पॉइंट खोजने के लिए सैद्धांतिक गारंटी स्थापित करता है, जो गोल्डस्टीन $\delta$ -सबडिफरेंशियल के माध्यम से परिभाषित नॉनस्मूथ फंक्शनों के लिए एक परिष्कृत अनुमानित स्टेशनारिटी की धारणा है।

कन्वर्जेंस कॉम्प्लेक्सिटी: ZOCO-ON एल्गोरिदम एक $(\delta, \epsilon)$ -Goldstein स्टेशनरी पॉइंट प्राप्त करता है जिसका स्टोकेस्टिक ज़ीरोथ-ऑर्डर ऑरेकल कॉम्प्लेक्सिटी है:
$O\left( d^{\frac{p}{2(p-1)}} \delta^{-1} \epsilon^{-\frac{2p-1}{p-1}} \right)$
यह परिणाम एक्सपेक्टेशन (expectation) और हाई प्रोबेबिलिटी (high probability) दोनों में मान्य है।
डायमेंशन डिपेंडेंस: डायमेंशन $d$ पर निर्भरता कॉन्वेक्स नॉनस्मूथ सेटिंग में सर्वश्रेष्ठ ज्ञात स्टोकेस्टिक ज़ीरोथ-ऑर्डर ऑप्टिमाइज़ेशन परिणामों से मेल खाती है।
एक्यूरेसी डिपेंडेंस: एक्यूरेसी पैरामीटर्स $\delta$ और $\epsilon$ पर निर्भरता हैवी-टेल्ड नॉइज़ के तहत नॉनकॉन्वेक्स नॉनस्मूथ समस्याओं के लिए सर्वश्रेष्ठ ज्ञात स्टोकेस्टिक फर्स्ट-ऑर्डर एल्गोरिदम के अनुरूप है।
स्मूथ एक्सटेंशन: परिणाम स्वाभाविक रूप से स्मूथ सेटिंग तक विस्तारित होते हैं। $\delta = \epsilon/H$ (जहाँ $H$ स्मूथनेस कांस्टेंट है) सेट करके, विधि एक $\epsilon$ -स्टेशनरी पॉइंट प्राप्त करती है जिसकी कॉम्प्लेक्सिटी स्मूथ नॉनकॉन्वेक्स ऑप्टिमाइज़ेशन के लिए इष्टतम स्टोकेस्टिक फर्स्ट-ऑर्डर विधियों से मेल खाती है।

प्रायोगिक सत्यापन (Experimental Validation)
वास्तविक दुनिया के डेटासेट्स (a9a, covtype, w8a) का उपयोग करके आर्टिफीशियली जोड़े गए हैवी-टेल्ड नॉइज़ (पारेटो डिस्ट्रीब्यूशन) के साथ नॉनकॉन्वेक्स पेनलाइज्ड SVM समस्याओं पर संख्यात्मक प्रयोग किए गए।

बेसलाइन्स: ZOCOON की तुलना GFM [26], GFM+ [5], और ZOO2N [25] से की गई।
निष्कर्ष: ZOCOON, GFM और GFM+ की तुलना में काफी तेजी से अभिसरित (converge) हुआ। ZOCOON ने अधिकांश डेटासेट्स पर ZOO2N की तुलना में अधिक स्थिर प्रदर्शन दिखाया, जो हैवी-टेल्ड नॉइज़ को संभालने में क्लिपिंग मैकेनिज्म की प्रभावशीलता की पुष्टि करता है।

महत्व और दावे
यह शोध पत्र साहित्य में एक महत्वपूर्ण अंतर को भरने का दावा करता है: जबकि हैवी-टेल्ड नॉइज़ व्यवहार में प्रचलित है, मौजूदा ज़ीरोथ-ऑर्डर विधियाँ बाउंडेड वेरिएंस धारणाओं या कॉन्वेक्स सेटिंग्स तक सीमित थीं।

प्रथम प्रकार का (First of its Kind): ZOCOON को हैवी-टेल्ड नॉइज़ के तहत नॉनकॉन्वेक्स नॉनस्मूथ ऑप्टिमाइज़ेशन के लिए पहला कुशल स्टोकेस्टिक ज़ीरोथ-ऑर्डर एल्गोरिदम के रूप में प्रस्तुत किया गया है।
इष्टतमता (Optimality): लेखक नोट करते हैं कि $L, \delta,$ और $\epsilon$ पर निर्भरता इस समस्या वर्ग के लिए हाल ही में स्थापित लोअर बाउंड से मेल खाती है, जो यह सुझाव देती है कि विधि एक्यूरेसी पैरामीटर्स के संबंध में निकट-इष्टतम (near-optimal) है।
मजबूती (Robustness): यह कार्य प्रदर्शित करता है कि ग्रेडिएंट क्लिपिंग, जो फर्स्ट-ऑर्डर विधियों में एक सामान्य तकनीक है, को डायमेंशन-डिपेंडेंट कॉम्प्लेक्सिटी से समझौता किए बिना अनबाउंडेड वेरिएंस को संभालने के लिए ज़ीरोथ-ऑर्डर फ्रेमवर्क में सफलतापूर्वक अनुकूलित किया जा सकता है।

शोध पत्र खुले प्रश्नों को स्वीकार करते हुए समाप्त होता है, विशेष रूप से यह कि क्या डायमेंशन डिपेंडेंस इष्टतम है और क्या इस फ्रेमवर्क को कंस्ट्रेंड ऑप्टिमाइज़ेशन समस्याओं तक विस्तारित किया जा सकता है।

1. समस्या: "तूफानी" पहाड़

2. समाधान: "क्लिप्ड" कंपास (ZOCOON)

3. लक्ष्य: "पर्याप्त अच्छा" स्थान खोजना

4. परिणाम: यह क्यों काम करता है

सारांश

इसी तरह के और पेपर