🤖 machine learning

The Sharp Tail of Uniform Stability

यह शोध पत्र एक नियत (deterministic), सीमित-हानि (bounded-loss) शिक्षण समस्या का निर्माण करके एक लंबे समय से चले आ रहे खुले प्रश्न को समाप्त करता है जो यूनिफॉर्म स्टेबिलिटी के लिए इष्टतम उच्च-संभाव्यता टेल बाउंड (high-probability tail bound) प्राप्त करता है, और यह सिद्ध करता है कि जनरलाइजेशन गैप केवल स्थिर संभाव्यता के बजाय $\log(1/\delta)$ के रैखिक रूप से स्केल करता है।

मूल लेखक: Pahan Dewasurendra

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

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

CC BY 4.0

मूल लेखक: Pahan Dewasurendra

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

मशीन लर्निंग की दुनिया में, कंप्यूटर उदाहरणों को देखकर, पैटर्न खोजकर और फिर उस नए डेटा पर भविष्यवाणियां करके सीखते हैं जिसे उन्होंने पहले कभी नहीं देखा है। इस क्षेत्र का केंद्रीय वादा यह है कि यदि कोई कंप्यूटर उदाहरणों के एक विशिष्ट सेट से अच्छी तरह सीखता है, तो वह वास्तविक दुनिया में भी उतना ही अच्छा प्रदर्शन करेगा। हालाँकि, इसमें एक सूक्ष्म जोखिम है: कभी-कभी कंप्यूटर एक ऐसा पैटर्न सीख लेता है जो उसे दिए गए उदाहरणों के लिए बहुत विशिष्ट होता है, यानी वह अंतर्निहित नियम को समझने के बजाय प्रशिक्षण डेटा (training data) को रट लेता है। इसे ओवरफिटिंग (overfitting) कहा जाता है, और यह बाद में खराब प्रदर्शन का कारण बनता है। इसे रोकने के लिए, शोधकर्ता 'स्थिरता' (stability) नामक एक अवधारणा का अध्ययन करते हैं। एक लर्निंग एल्गोरिदम की कल्पना एक संवेदनशील तराजू के रूप में करें। यदि आप प्रशिक्षण डेटा के ढेर से केवल एक एकल उदाहरण को हटा देते हैं और कंप्यूटर को पुन: प्रशिक्षित करते हैं, तो एक स्थिर एल्गोरिदम वही परिणाम देगा जो उसने पहले किया था। यदि परिणाम नाटकीय रूप से बदल जाता है, तो एल्गोरिदम अस्थिर है और नए डेटा का सामना करने पर विफल होने की संभावना है। वर्षों से, वैज्ञानिक इस बात के बीच एक सटीक रेखा खींचने की कोशिश कर रहे हैं कि एक एल्गोरिदम कितना स्थिर है और नए डेटा से वास्तविक दुनिया में जाने पर उसके प्रदर्शन में कितनी गिरावट आ सकती है। वे इस संबंध के सामान्य आकार को जानते थे, लेकिन सबसे खराब स्थिति (worst-case scenario) के सटीक विवरण एक रहस्य बने हुए थे।

जॉन्स हॉपकिन्स यूनिवर्सिटी के एक शोधकर्ता ने अब एक विशिष्ट, सबसे खराब स्थिति का निर्माण करके इस रहस्य को सुलझा लिया है, जो इस बात को सिद्ध करता है कि स्थिरता क्या गारंटी दे सकती है उसकी सीमाएं क्या हैं। उन्होंने दिखाया कि भले ही एक एल्गोरिदम गणितीय रूप से स्थिर हो और इसके त्रुटियों को एक निश्चित आकार तक सख्ती से सीमित किया गया हो, फिर भी प्रदर्शन में आश्चर्यजनक रूप से बड़ी गिरावट आने की संभावना होती है। यह गिरावट केवल एक छोटी, यादृच्छिक उतार-चढ़ाव नहीं है; यह एक बहुत ही विशिष्ट, अनुमानित वक्र (curve) का अनुसरण करती है जो इस बात पर निर्भर करती है कि विफलता कितनी दुर्लभ है। शोधकर्ता ने प्रदर्शित किया कि स्थिरता के किसी भी स्तर के लिए, एक ऐसी सीखने की समस्या मौजूद है जहाँ एल्गोरिदम का प्रदर्शन अंतराल उतना ही बड़ा होता है जितना कि सिद्धांत अनुमति देता है, और यह एक सटीक तरीके से घटती जाने वाली प्रायिकता (probability) के साथ होता है। इस कार्य से पहले, यह एक खुला प्रश्न था कि क्या गणितज्ञों द्वारा निकाले गए सैद्धांतिक सीमाएँ वास्तव में एक वास्तविक लर्निंग एल्गोरिदम द्वारा प्राप्त की जा सकती हैं जो निश्चित त्रुटि सीमाओं के भीतर कार्य करता है। नया अध्ययन पुष्टि करता है कि ये सीमाएँ केवल सैद्धांतिक संभावनाएँ नहीं हैं, बल्कि सीखने की प्रक्रिया की वास्तविक, अपरिहार्य विशेषताएं हैं।

यह समझने के लिए कि उन्होंने इस निष्कर्ष तक कैसे पहुँचा, एक को इस समस्या की प्रकृति को देखना चाहिए जिसे उन्होंने बनाया है। शोधकर्ता ने एक ऐसी सीखने की कार्यप्रणाली तैयार की जो सतह पर भ्रामक रूप से सरल है: कंप्यूटर से एक संख्या की भविष्यवाणी करने के लिए कहा जाता है जो हमेशा शून्य होती है। कंप्यूटर को इनपुट का एक सेट दिया जाता है, जिसमें से प्रत्येक में यादृच्छिक संकेतों (random signs) का एक संग्रह होता है, जैसे कि सिर और पूंछ (heads and tails) की एक लंबी सूची। एल्गोरिदम को इन इनपुट के आधार पर निर्णय लेना होता है कि क्या भविष्यवाणी करनी है। शोधकर्ता ने इनपुट को इस तरह से इंजीनियर किया कि उनमें इन यादृच्छिक संकेतों के कई अलग-अलग समूह शामिल हैं, जिनमें से प्रत्येक समूह दुर्लभता के एक अलग पैमाने पर कार्य करता है। अधिकांश समय, एल्गोरिदम संकेतों का एक ऐसा मिश्रण देखता है जो एक-दूसरे को रद्द कर देते हैं, जिससे एक सुरक्षित, औसत भविष्यवाणी होती है। हालाँकि, शोधकर्ता ने इनपुट को इस तरह व्यवस्थित किया कि बहुत कम मामलों में, एक विशिष्ट समूह में एक विशिष्ट संकेत एक चरम आउटलियर (extreme outlier) के रूप में उभर कर आएगा।

इस निर्माण का चतुर हिस्सा यह है कि एल्गोरिदम इस दुर्लभ आउटलियर के प्रति कैसे प्रतिक्रिया करता है। शोधकर्ता ने एल्गोरिदम को इन दुर्लभ घटनाओं के प्रति अत्यंत संवेदनशील बनाया, लेकिन केवल इस तरह से जो स्थिरता के नियमों का उल्लंघन न करे। यदि आप एक प्रशिक्षण उदाहरण को हटा देते, तो एल्गोरिदम का व्यवहार केवल थोड़ा सा बदलता, जो स्थिरता की परिभाषा को संतुष्ट करता है। फिर भी, जब एल्गोरिदम वास्तविक दुनिया में संकेतों के उस विशिष्ट, दुर्लभ संयोजन का सामना करता है, तो वह वास्तविक शून्य मान से काफी अलग भविष्यवाणी करता है। ऐसा इसलिए होता है क्योंकि एल्गोरिदम ने उस दुर्लभ, चरम संकेत को एक बड़ी भविष्यवाणी के साथ जोड़ने के लिए सीखा है। शोधकर्ता ने एक तंत्र का उपयोग किया जहाँ उन्होंने कई ऐसी दुर्लभ संभावनाओं को एक साथ जोड़ा, जैसे कि विभिन्न ऊंचाइयों वाले रैंप (ramps) की एक श्रृंखला। प्रत्येक रैंप दुर्लभता के एक अलग स्तर के अनुरूप है। यदि कोई घटना मध्यम रूपely दुर्लभ है, तो यह एक छोटी त्रुटि को ट्रिगर करती है। यदि कोई घटना अत्यंत दुर्लभ है, तो यह बहुत बड़ी त्रुटि को ट्रिगर करती है। इन रैंपों को एक विशिष्ट ज्यामितीय पैटर्न में व्यवस्थित करके, शोधकर्ता ने यह सुनिश्चित किया कि एल्गोरिदम किसी भी दिए गए विश्वास स्तर (confidence level) के लिए अधिकतम त्रुटि उत्पन्न कर सके।

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

इस निष्कर्ष तक पहुँचने के पीछे एक शांत लेकिन गहरा निहितार्थ है कि हम मशीन लर्निंग प्रणालियों पर कैसे भरोसा करते हैं। यह हमें बताता है कि स्थिरता अकेले, यहाँ तक कि जब इसे त्रुटियों के सीमित होने की गारंटी के साथ जोड़ा जाता है, तो उच्च विश्वास के साथ पूर्ण प्रदर्शन सुनिश्चित करने के लिए पर्याप्त नहीं है। यहाँ एक मौलिक ट्रेड-ऑफ (trade-off) है। यदि आप चाहते हैं कि आपका एल्गोरिदम विफल न हो, इसके लिए आपको यह स्वीकार करना होगा कि विफलता का संभावित आकार, जब वह होती है, स्थिरता के साथ एक विशिष्ट, अपरिवर्तनीय तरीके से जुड़ा हुआ है। शोधकर्ता ने मौजूदा एल्गोरिदम में कोई दोष नहीं पाया; बल्कि, उन्होंने उस सीमा को खोजा जो संभव है। उन्होंने दिखाया कि गणितज्ञों द्वारा निकाली गई सैद्धांतिक सीमाएँ केवल अमूर्त ऊपरी सीमाएँ नहीं हैं, बल्कि वास्तव में व्यावहारिक रूप से प्राप्त की जा सकती हैं। इसका अर्थ है कि जब इंजीनियर लर्निंग सिस्टम डिज़ाइन करते हैं, तो वे केवल एल्गोरिदम को ट्यून करके इन सीमाओं को पार करने की उम्मीद नहीं कर सकते। उन्हें यह स्वीकार करना होगा कि किसी भी स्थिर प्रणाली के लिए, दुर्लभ, बड़ी त्रुटियों की एक पूँछ (tail) होती है जिसे समाप्त नहीं किया जा सकता, केवल समझा और प्रबंधित किया जा सकता है।

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

अंत में, यह कार्य लर्निंग एल्गोरिदम के बारे में हमारी समझ के एक लंबे समय से चले आ रहे अंतराल को भरता है। यह पुष्टि करता है कि स्थिरता और सामान्यीकरण त्रुटि (generalization error) के बीच का संबंध ठीक वैसा ही तीक्ष्ण है जैसा कि सबसे अच्छे गणितीय सिद्धांतों ने सुझाव दिया था। शोधकर्ता ने एक प्रश्न का निर्णायक उत्तर दिया है जो वर्षों से बना हुआ था: क्या एक स्थिर एल्गोरिदम जिसमें त्रुटियाँ सीमित हैं, एक ऐसा जनरलाइजेशन गैप प्राप्त कर सकता है जो विश्वास स्तर के लघुगणक (logarithm) के साथ रैखिक रूप से बढ़ता है? उत्तर है हाँ, और यह अपरिहार्य है। इसका मतलब यह नहीं है कि मशीन लर्निंग टूट गई है या हम विश्वसनीय सिस्टम नहीं बना सकते। इसका केवल यह अर्थ है कि अब हम उस जोखिम के सटीक आकार को जानते हैं जिसे हम उठा रहे हैं। हम जानते हैं कि प्रत्येक स्थिरता स्तर के लिए, जोखिम की एक संबंधित पूँछ होती है जिसे काटा नहीं जा सकता। यह स्पष्टता शोधकर्ताओं और चिकित्सकों को अधिक यथार्थवादी अपेक्षाएं निर्धारित करने और अपना प्रयास डेटा की गुणवत्ता या मॉडल आर्किटेक्चर जैसे अन्य पहलुओं पर केंद्रित करने की अनुमति देती है, बजाय इसके कि वे उस जोखिम को समाप्त करने की उम्मीद करें जो उदाहरणों से सीखने की प्रक्रिया में गणितीय रूप से अंतर्निहित है।

तकनीकी सारांश: यूनिफॉर्म स्टेबिलिटी की शार्प टेल (The Sharp Tail of Uniform Stability)

समस्या विवरण (Problem Statement)
यह शोध पत्र $\gamma$ -यूनिफॉर्मली स्टेबल लर्निंग एल्गोरिदम के लिए बाउंडेड लॉस (bounded loss) वाले हाई-प्रोबेबिलिटी जनरलाइजेशन गैप (high-probability generalization gap) के लक्षण वर्णन (characterization) के मौलिक प्रश्न को संबोधित करता है। जबकि ऐसे एल्गोरिदम के लिए एक्सपेक्टेशन गारंटी ( $|E[R(A_S) - R_S(A_S)]| \le \gamma$ ) अच्छी तरह से स्थापित है, उनके हाई-प्रोबेबिलिटी व्यवहार को परिष्कृत करने का कार्य निरंतर जारी रहा है। हालिया ऊपरी सीमाएँ (नेगुएन-कुंग और नेगुएन, 2026) यह स्थापित करती हैं कि $[0, L]$ में लॉस वाले एल्गोरिदम के लिए, जनरलाइजेशन गैप $G_S$ की प्रायिकता $1-\delta$ के साथ:
$G_S = O\left( \gamma \log(1/\delta) + L \sqrt{\frac{\log(1/\delta)}{n}} \right)$
होती है। मोमेंट्स ( $p \ge 2$ ) के संदर्भ में, यह $\|G_S\|_p \lesssim \min\{L, \gamma p + L\sqrt{p/n}\}$ के बराबर है।

खुला हुआ प्रश्न यह था कि क्या लॉस की एक वास्तविक यूनिफॉर्म बाउंड $L$ के लिए यह विशिष्ट $\log(1/\delta)$ पर निर्भरता (या मोमेंट बाउंड में लीनियर डिपेंडेंस $p$ पर) सटीक है। पिछले लोअर बाउंड्स या तो सहायक वीकली डिपेंडेंट वेरिएबल्स पर आधारित थे जिनकी रेंज $n$ के साथ बढ़ती थी (जो यूनिफॉर्म लॉस बाउंड का उल्लंघन करती थी) या केवल कांस्टेंट प्रोबेबिलिटी पर लागू होते थे, जिससे छोटे फेलियर प्रोबेबिलिटी (बड़े $p$ ) पर निर्भरता अनसुलझी रह गई थी।

कार्यप्रणाली (Methodology)
लेखक एक एकल, डिटर्मिनिस्टिक (deterministic), फाईनाइट-डायमेंशनल लर्निंग प्रॉब्लम का निर्माण करते हैं जो सभी कॉन्फिडेंस लेवल्स $e^{-p}$ ( $1 \le p \le cn$ ) के लिए वर्स्ट-केस जनरलाइजेशन गैप को एक साथ साकार करता है। यह निर्माण एक एब्सोल्यूट-लॉस रिग्रेशन समस्या है जिसमें लेबल निरंतर शून्य (constant zero) हैं।

इसका मुख्य तंत्र रेयर रेडमेकर फीचर्स (rare Rademacher features) का एक मल्टीस्केल कलेक्शन है:

फीचर बैंक (Feature Bank): इनपुट स्पेस में ज्यामितीय स्केल्स $p_k$ द्वारा इंडेक्स किए गए स्वतंत्र रेडमेकर कोऑर्डिनेट्स के समूह हैं। समूह $k$ में कोऑर्डिनेट्स की संख्या $d_k \approx e^{-p_k/2}/q_\star$ रखी गई है, जहाँ $q_\star$ $n$ रेडमेकर साइन्स के सम (sum) में एक बड़े विचलन (large deviation) की प्रायिकता है। यह मल्टीप्लिसिटी सुनिश्चित करती है कि एक "रेयर क्रॉसिंग" (एक कोऑर्डिनेट का थ्रेशोल्ड को पार करना) एक नियंत्रित, गैर-नगण्य प्रायिकता के साथ घटित हो।
कोऑर्डिनेटवाइज रैंप (Coordinatewise Ramp): प्रत्येक कोऑर्डिनेट के एम्पिरिकल स्कोर पर एक रैंप फंक्शन $a_{kj}(S)$ लागू किया जाता है। यह रैंप इस तरह डिज़ाइन किया गया है कि यह कोऑर्डिनेट्स की संख्या के बावजूद सुप-नॉर्म (sup-norm) में $\gamma$ -यूनिफॉर्मली स्टेबल रहे। यह केवल तभी सक्रिय होता है जब एक विशिष्ट कोऑर्डिनेट एक उच्च थ्रेशोल्ड को पार करता है, जिससे $\gamma p_k$ का आयाम (amplitude) उत्पन्न होता है।
सिमेट्राइज्ड मैक्सिमम रीडआउट (Symmetrized Maximum Readout): प्रेडिक्टर एक विषम, सिमेट्राइज्ड मैक्सिमम फंक्शन $H_a(x) = \max_j a_j x_j - \max_j (-a_j x_j)$ का उपयोग करता है। यह फंक्शन वेट्स $a$ में सुप-नॉर्म के तहत 2-लिप्सचिट्ज़ (2-Lipschitz) है। जब एक एकल "डोमिनेंट" कोऑर्डिनेट अपने थ्रेशोल्ड को पार करता है, तो $H_a$ इस अद्वितीय चरम फीचर को ग्लोबल लॉस बाउंड $L$ का उल्लंघन किए बिना $\gamma p_k$ के क्रम के जनरलाइजेशन गैप में बदल देता है।
ज्यामितीय अंतराल (Geometric Spacing): रैंप की चौड़ाई को ज्यामितीय रूप से स्पेस करके ( $p_k \propto 4^k$ ), यह निर्माण सुनिश्चित करता है कि किसी भी लक्षित कॉन्फिडेंस लेवल $p$ के लिए, एक ऐसा स्केल $p_k$ मौजूद है जहाँ क्रॉसिंग की घटना एक मानक सैंपलिंग डेविएशन इवेंट के साथ इंटरसेक्ट होती है। यह एक सिंगल लर्नर को सभी $p$ के लिए पूर्ण टेल कर्व $\min\{L, \gamma p + L\sqrt{p/n}\}$ को एक साथ साकार करने की अनुमति देता है।
मेमोरी और सैंपलिंग टर्म्स: एक अलग मेमोरी कंपोनेंट कांस्टेंट-कॉन्फिडेंस रिजीम और उन स्केल्स को संभालता है जहाँ रैंप निष्क्रिय है, जबकि एक स्वतंत्र साइन टर्म स्टैंडर्ड $L\sqrt{p/n}$ सैंपलिंग टेल को अकाउंट करता है।

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

प्रथम बाउंडेड-लॉस लोअर बाउंड: यह पेपर एक बाउंडेड-लॉस ( $[0, L]$ ) यूनिफॉर्मली स्टेबल लर्नर का पहला निर्माण प्रदान करता है जो $\Omega(\gamma \log(1/\delta))$ का हाई-प्रोबेबिलिटी जनरलाइजेशन गैप प्राप्त करता है।
सिमल्टेनियस रियलाइजेशन: पिछले कार्यों के विपरीत, जिन्हें विभिन्न कॉन्फिडेंस लेवल्स के लिए अलग-अलग समस्याओं की आवश्यकता थी, यह एकल डिटर्मिनिस्टिक समस्या सभी $1 \le p \le cn$ के लिए पूर्ण लोअर बाउंड कर्व $\Omega(\min\{L, \gamma p + L\sqrt{p/n}\})$ को एक साथ साकार करती है।
अपरी सीमाओं की शार्पनेस (Sharpness of Upper Bounds): इस लोअर बाउंड को हालिया अपर बाउंड (नेगुएन-कुंग और नेगुएन, 2026) के साथ जोड़कर, यह पेपर स्थापित करता है कि यूनिफॉर्म स्टेबिलिटी की मोमेंट डिपेंडेंस यूनिवर्सल कांस्टेंट्स तक शार्प है। मिनीमैक्स लॉ यह निर्धारित करता है:
$\sup_{(P, A, \ell)} \|G_S\|_p \asymp \min\left\{L, \gamma p + L\sqrt{\frac{p}{n}}\right\}$
डिटर्मिनिस्टिक कंस्ट्रक्शन: परिणाम एक डिटर्मिनिस्टिक एल्गोरिदम के लिए मान्य है, जो यह सिद्ध करता है कि गैप यूनिफॉर्म स्टेबिलिटी कंडीशन की अपनी विशेषता है, न कि एल्गोरिथमिक रैंडमनेस का एक आर्टिफैक्ट।

परिणाम (Results)
मुख्य प्रमेय (थ्योरम 1) बताता है कि प्रत्येक $n, L, \gamma$ के लिए, एक समस्या और एक डिटर्मिनिस्टिक $\gamma$ -यूनिफॉर्मली स्टेबल एल्गोरिदम मौजूद है ताकि:
$P(G_S \ge c_1 \min\{L, \gamma p + L\sqrt{p/n}\}) \ge e^{-p}$
सभी $p \in [1, c_0 n]$ के लिए। यह पुष्टि करता है कि हाई-प्रोबेबिलिटी बाउंड में लॉगरिदमिक फैक्टर आवश्यक है और इसे सामान्य बाउंडेड-लॉस लर्निंग प्रॉब्लम्स के लिए हटाया नहीं जा सकता है।

महत्व (Significance)
यह पेपर दावा करता है कि यह एल्गोरिथमिक स्टेबिलिटी के सिद्धांत में एक महत्वपूर्ण अंतर को पाट देता है। यह प्रदर्शित करता है कि केवल यूनिफॉर्म स्टेबिलिटी कांस्टेंट $\gamma$ और लॉस बाउंड $L$ से प्राप्त 'ब्लैक-बॉक्स' दृष्टिकोण $\gamma \log(1/\delta)$ टर्म से अधिक सटीक हाई-प्रोबेबिलिटी गारंटी नहीं दे सकता है। फलस्वरूप, विशिष्ट ऑप्टिमाइज़र्स के लिए कोई भी शार्पर गारंटी अतिरिक्त स्ट्रक्चरल जानकारी (जैसे कर्वेचर, डेटा-डिपेंडेंट स्टेबिलिटी, या रिप्रेजेंटेशन कंस्ट्रेंट्स) पर निर्भर करनी चाहिए, न कि केवल यूनिफॉर्म स्टेबिलिटी पर। यह निर्माण लॉस के पॉइंटवाइज रेंज को उसके एग्रीगेट टेल साइज से अलग करता है, यह दिखाते हुए कि भले ही लॉस स्ट्रिक्टली बाउंडेड हो, फिर भी दुर्लभ और चरम फीचर्स से बड़े जनरलाइजेशन गैप उत्पन्न हो सकते हैं।

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