📊 statistics

Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems

यह शोध पत्र दोनों स्तरों में मिनिमैक्स संरचनाओं वाले बाइलेवल ऑप्टिमाइज़ेशन के लिए पेनल्टी-आधारित फर्स्ट-ऑर्डर विधियों को प्रस्तुत करता है, जो निचले स्तर की समस्या पर स्ट्रॉन्ग कॉनवेक्सिटी (strong convexity) धारणाओं की आवश्यकता के बिना, नियत (deterministic) सेटिंग्स में $\tilde{O}(\epsilon^{-4})$ और स्टोकेस्टिक (stochastic) सेटिंग्स में $\tilde{O}(\epsilon^{-9})$ के बेहतर ओरैकल कॉम्प्लेक्सिटी बाउंड्स स्थापित करता है।

मूल लेखक: Yiyang Shen, Yutian He, Weiran Wang, Qihang Lin

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

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

CC BY 4.0

मूल लेखक: Yiyang Shen, Yutian He, Weiran Wang, Qihang Lin

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

कल्पना कीजिए कि आप एक बहुत ही जटिल पहेली को हल करने की कोशिश कर रहे हैं, लेकिन जैसे-जैसे आप उसे हल करने का प्रयास करते हैं, पहेली के नियम बदलते रहते हैं। यह बाइलेवल ऑप्टिमाइज़ेशन (Bilevel Optimization) का सार है, जो मशीन लर्निंग में उपयोग किया जाने वाला एक प्रकार का गणितीय प्रश्न है जहाँ एक निर्णय (ऊपरी स्तर/upper level) दूसरे निर्णय (निचले स्तर/lower level) के परिणाम पर निर्भर करता है।

आमतौर पर, निचला स्तर निर्णय एक घाटी के सबसे निचले बिंदु को खोजने (minimization) जैसा होता है। लेकिन यह शोध पत्र एक बहुत ही कठिन परिदृश्य को संबोधित करता है: क्या होगा यदि निचला स्तर एक रस्साकशी (tug-of-war) हो?

मुख्य समस्या: एक पहेली के भीतर "रस्साकशी"

इस शोध पत्र में, लेखक एक विशिष्ट प्रकार की समस्या पर विचार करते हैं जहाँ:

बॉस (ऊपरी स्तर): अपनी लागत को कम करने के लिए एक निर्णय लेना चाहता है।
टीम (निचला स्तर): केवल सबसे निचले बिंदु को खोजने के बजाय, टीम विभाजित है। एक आधा हिस्सा स्कोर को कम (minimize) करना चाहता है, जबकि दूसरा आधा हिस्सा इसे अधिकतम (maximize) करना चाहता है। वे एक-दूसरे के विरुद्ध एक "मिनिमैक्स" (minimax) खेल खेल रहे हैं (जैसे रॉक-पेपर-सिज़र्स या ज़ीरो-सम गेम)।

बॉस को एक ऐसी रणनीति चुननी होती है यह जानते हुए कि टीम तुरंत एक-दूसरे से लड़कर एक "सैडल पॉइंट" (एक ऐसा संतुलन जहाँ कोई भी पक्ष अपनी चाल बदलकर जीत नहीं सकता) खोजने की कोशिश करेगी।

चुनौती: मौजूदा गणितीय उपकरण जो इन पहेलियों को हल करते हैं, आमतौर पर यह मानकर चलते हैं कि टीम केवल एक एकल निम्नतम बिंदु की तलाश कर रही है (जैसे एक पहाड़ी से लुढ़कती गेंद)। जब टीम आपस में लड़ रही होती है, तो ये उपकरण विफल हो जाते हैं। इसके अलावा, कई पुराने उपकरणों के लिए यह आवश्यक था कि "पहाड़ी" पूरी तरह से चिकनी और कटोरे के आकार की (strongly convex) हो, जो कई वास्तविक दुनिया के AI समस्याओं के लिए सच नहीं है।

समाधान: "पेनल्टी" (जुर्माना) रणनीति

लेखक इस समस्या को हल करने के लिए एक नया तरीका प्रस्तावित करते हैं जिसे पेनल्टी-बेस्ड मेथड (Penalty-Based Method) कहा जाता है।

उपमा: सख्त रेफरी (The Strict Referee)
कल्पना कीजिए कि बॉस और टीम एक कमरे में हैं। टीम को एक पूर्ण संतुलन (सैडल पॉइंट) तक पहुँचने की आवश्यकता है, इससे पहले कि बॉस अपना निर्णय ले सके।

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

इस प्रकार, वे एक जटिल दो-स्तरीय समस्या को एक एकल, विशाल "मिन-मैक्स" खेल में बदल देते हैं जिसे मानक कंप्यूटर बहुत तेज़ी से संभाल सकते हैं।

उन्होंने क्या हासिल किया (परिणाम)

शोध पत्र इस "सख्त रेफरी" दृष्टिकोण का उपयोग करके दो बड़ी जीत का दावा करता है:

डिटरमिनिस्टिक केस (शोर रहित) की गति बढ़ाना:
जब गणित सटीक और स्पष्ट होता है (deterministic), तो उनकी विधि लगभग $\tilde{O}(\epsilon^{-4})$ की जटिलता के साथ एक अच्छा समाधान खोज लेती है।
- अनुवाद: यदि आप अपने उत्तर को 10 गुना अधिक सटीक बनाना चाहते हैं, तो आपको 1,000 गुना अधिक काम करने की आवश्यकता नहीं है; आपको केवल लगभग 10,000 गुना अधिक काम करना होगा।
- तुलना: समान समस्याओं के लिए पिछले तरीके (जो बाधाओं के साथ थे) बहुत धीमे थे (लगभग $\epsilon^{-7}$ )। लेखकों ने इसमें महत्वपूर्ण सुधार किया है।
अव्यवस्थित, शोर वाले मामले (Stochastic) को संभालना:
वास्तविक दुनिया में डेटा शोर भरा होता है (जैसे भीड़ भरे कमरे में बातचीत सुनने की कोशिश करना)। लेखकों ने अपने तरीके को इस "स्टोकेस्टिक" सेटिंग को संभालने के लिए विस्तारित किया है।
- उन्होंने सिद्ध किया कि उनका तरीका अभी भी काम करता है, और $\tilde{O}(\epsilon^{-9})$ की जटिलता के साथ एक "लगभग पूर्ण" समाधान खोजता है।
- नोट: हालांकि $\epsilon^{-9}$ सुनने में बहुत अधिक लगता है, लेखक स्वीकार करते हैं कि यह इस विशिष्ट प्रकार की समस्या के लिए एक पहला कदम है और सुझाव देते हैं कि भविष्य के कार्य (वेरिएंस रिडक्शन का उपयोग करके) इसे तेज़ बना सकते हैं।

वास्तविक दुनिया के परीक्षण

लेखकों ने केवल गणित नहीं किया; उन्होंने दो चीज़ों पर इसका परीक्षण किया:

सिंथेटिक लीनियर प्रॉब्लम्स: उन्होंने मौजूदा तरीकों (FOP और SMO) के साथ तुलना करने के लिए नकली गणितीय पहेलियाँ बनाईं। उनकी विधि ने तेज़ी से अभिसरण (converge) किया और बेहतर समाधान खोजे, विशेष रूप से जब उन्होंने "रेफरी" की संवेदनशीलता को ट्यून किया।
मजबूत AI के लिए हाइपरपैरामीटर ट्यूनिंग: उन्होंने इस पद्धति को डिस्ट्रिब्यूशनली रोबस्ट ऑप्टिमाइज़ेशन (DRO) नामक एक वास्तविक दुनिया की समस्या पर लागू किया।
- परिदृश्य: कल्पना कीजिए कि एक AI को पक्षियों को पहचानने के लिए प्रशिक्षित किया जा रहा है। अधिकांश तस्वीरें ज़मीन पर पक्षियों की हैं, लेकिन कुछ पानी पर भी हैं। एक मानक AI पृष्ठभूमि (ज़मीन बनाम पानी) को देखकर धोखा दे सकता है।
- समाधान: लेखकों ने अपने बाइलेवल मेथड का उपयोग AI को इस तरह ट्यून करने के लिए किया ताकि वह "सबसे खराब स्थिति वाले समूह" (जैसे पानी पर पक्षी) पर भी अच्छा प्रदर्शन करे।
- परिणाम: उनके मेथड ने समग्र औसत प्रदर्शन को नुकसान पहुँचाए बिना, मौजूदा तरीकों की तुलना में "सबसे खराब समूह" पर सटीकता में काफी सुधार किया (उदाहरण के लिए, एक डेटासेट पर 41% से बढ़कर 75% तक पहुँचना)।

सारांश

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

तकनीकी सारांश: मिनमैक्स और बाधात्मक लोअर-लेवल समस्याओं के लिए पेनल्टी-आधारित फर्स्ट-ऑर्डर मेथड्स

समस्या का निरूपण (Problem Formulation)

यह शोध पत्र बाइलेवल ऑप्टिमाइज़ेशन (bilevel optimization) की एक श्रेणी को संबोधित करता है जहाँ ऊपरी-स्तर (upper-level) और निचले-स्तर (lower-level) दोनों ही मिनमैक्स संरचना प्रदर्शित करते हैं। सामान्य निरूपण को इस प्रकार परिभाषित किया गया है:
$\min_{x_1, y_1, y_2} \left\{ \max_{x_2} f(x_1, x_2, y_1, y_2) \mid (y_1, y_2) \in \arg\min_{z_1} \max_{z_2} \tilde{f}(x_1, z_1, z_2) \right\}$
जहाँ $(y_1, y_2)$ लोअर-लेवल फंक्शन $\tilde{f}$ के सैडल-पॉइंट (saddle-point) को दर्शाता है। लेखक विशिष्ट संरचनात्मक गुणों को मानते हैं: $f$ और $\tilde{f}$ को स्मूथ घटकों और उचित क्लोज्ड कॉन्वेक्स (proper closed convex) फलनों में विभाजित किया जा सकता है, जिसमें उनके संबंधित चरों के संबंध में विशिष्ट कॉनवेक्सिटी/कॉनकेविटी गुण (जैसे, $x_1, z_1$ के संबंध में $\tilde{f}$ कॉनवेक्स है और $z_2$ के संबंध में कॉनकेव है) होते हैं।

इस कार्य का एक महत्वपूर्ण हिस्सा उन बाइलेवल समस्याओं पर केंद्रित है जहाँ लोers-लेवल एक कॉन्वेक्स मिनिमाइजेशन समस्या है जिसमें कॉनवेक्स नॉनलीन इनइक्वैलिटी कंस्ट्रेंट्स (constraints) हैं:
$\min_{x_1, y_1} \left\{ f(x_1, y_1) \mid y_1 \in \arg\min_{z_1} \{ \bar{f}(x_1, z_1) \mid \bar{g}(x_1, z_1) \leq 0 \} \right\}$
स्लेटर की स्थिति (Slater's condition) के तहत, इस बाधित (constrained) समस्या को लैग्रेंजियन डुअलिटी (Lagrangian duality) के माध्यम से सामान्य मिनमैक्स बाइलेवल फ्रेमवर्क के एक विशेष मामले के रूप में पुनर्गठित किया जाता है।

मौजूदा साहित्य मुख्य रूप से उन बाइलेवल ऑप्टिमाइज़ेशन पर केंद्रित है जहाँ लोers-लेवल एक सिंगल-ऑब्जेक्टिव मिनिमाइजेशन (अक्सर स्ट्रॉन्गली कॉनवेक्स) है। हाइपरग्रेडिएंट्स या इमप्लीसिट डिफरेंशिएशन (implicit differentiation) पर निर्भर विधियाँ अक्सर विफल हो जाती हैं जब लोers-लेवल केवल कॉनवेक्स, नॉन-कॉनवेक्स, या मिनमैक्स संरचना वाला होता है। यह कार्य बिना स्ट्रॉन्ग कॉनवेक्सिटी की आवश्यकता के मिनमैक्स लोers-लेवल सेटिंग के लिए फर्स्ट-ऑर्डर मेथड्स विकसित करके इस अंतर को भरने का लक्ष्य रखता है।

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

प्रस्तावित दृष्टिकोण एक वैल्यू-फंक्शन पेनल्टी पुनर्गठन (value-function penalty reformulation) का उपयोग करता है। बाधित बाइलेवल समस्या को एक पेनल्टी पैरामीटर $\rho$ पेश करके एक अनकंस्ट्रेंड (या सरल कंस्ट्रेंड) मिनमैक्स समस्या में बदल दिया जाता है।

नियतिवादी सेटिंग (Deterministic Setting)

पेनल्टी पुनर्गठन: मूल समस्या को एक सिंगल-लेवल मिनमैक्स समस्या में पुनर्गठित किया जाता है:
$\min_{x_1, y_1, y_2} \max_{x_2, z_1, z_2} P_\rho(x_1, x_2, y_1, y_2, z_1, z_2)$
जहाँ $P_\rho$ , ऑब्जेक्टिव फंक्शन और पेनल्टी टर्म $\rho(p(x_1, y_1) - d(x_1, y_2))$ को शामिल करता है, जो लोers-लेवल समस्या के डुअलिटी गैप (duality gap) को दर्शाता है।
एल्गोरिदम: लेखक एक इनएक्सैक्ट प्रॉक्सिमल पॉइंट मेथड (inexact proximal point method) का प्रस्ताव करते हैं। बाहरी लूप प्राइमल-डुअल चरों को स्ट्रॉन्गली-कॉनवेक्स-स्ट्रॉन्गली-कॉनकेव (SCSC) सब-प्रॉब्लम्स के एक अनुक्रम को हल करके अपडेट करता है।
सब-प्रॉब्लम सॉल्वर: प्रत्येक सब-प्रॉब्लम को एक इष्टतम फर्स्ट-ऑर्डर मेथड (विशेष रूप से, लू और मेई [52] या कोवालेव और गासनिकोव [37] द्वारा विकसित विधि का एक संस्करण) का उपयोग करके हल किया जाता है, जिसे OptFOM कहा जाता है।
जटिलता (Complexity): यह विधि एक $\epsilon$ -KKT पॉइंट को $\tilde{O}(\epsilon^{-4})$ के ऑरेकल कॉम्प्लेक्सिटी के साथ खोजती है।

स्टोकेस्टिक सेटिंग (Stochastic Setting)

जब केवल स्टोकेस्टिक ग्रेडिएंट ऑरेकल्स स्मूथ घटकों के लिए उपलब्ध होते हैं:

एल्गोरिदम: आंतरिक सब-प्रब्लम्स को हल करने के लिए नियतिवादी प्रॉक्सिमल पॉइंट मेथड को स्टोकेस्टिक एक्सीलरेटेड प्राइमल-डुअल (SAPD) मेथड (विशेष रूप से झांग एट अल. [75] द्वारा SAPD+) का उपयोग करने के लिए अनुकूलित किया गया है।
अभिसरण (Convergence): यह विधि एक "लगभग" $\epsilon$ -KKT पॉइंट (जहाँ समाधान एक सटीक $\epsilon$ -KKT पॉइंट के $\epsilon$ दूरी के भीतर है) को $\tilde{O}(\epsilon^{-9})$ की स्टोकेस्टिक ऑरेकल कॉम्प्लेक्सिटी के साथ खोजती है।

बाधित लोers-लेवल समस्याओं के लिए अनुप्रयोग

बाधित कॉनवेक्स लोers-लेवल वाले बाइलेवल ऑप्टिमाइज़ेशन (समस्या 4) के विशिष्ट मामले के लिए, लेखक दिखाते हैं कि स्लेटर की स्थिति के तहत, लैग्रेंज मल्टीप्लायर्स $[0, B]^l$ बॉक्स के भीतर सीमित हैं। यह अनुमत करता है कि बाधित समस्या को डुअल चरों को स्पष्ट ऑप्टिमाइज़ेशन चरों के रूप में और बॉक्स कंस्ट्रेंट्स के साथ पेश करके, सामान्य मिनमैक्स बाइलेवल समस्या (समस्या 1) के रूप में पुनर्गठित किया जा सके। यह पुनर्गठन आंतरिक बाधाओं के लिए दूसरे पेनल्टी पैरामीटर के उपयोग से बचता है, जिससे पिछले कार्यों की तुलना में बेहतर कॉम्प्लेक्सिटी बाउंड्स प्राप्त होते हैं।

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

बाइलेवल मिनमैक्स के लिए प्रथम कॉम्प्लेक्सिटी परिणाम: यह शोध पत्र बाइलेवल ऑप्टिमाइज़ेशन के लिए पहले फर्स्ट-ऑर्डर मेथड्स के कॉम्प्लेक्सिटी बाउंड्स स्थापित करता है जहाँ लोers-लेवल एक मिनमैक्स समस्या है।
- नियतिवादी जटिलता: $\tilde{O}(\epsilon^{-4})$ ।
- स्टोकेस्टिक जटिलता: $\tilde{O}(\epsilon^{-9})$ ।
बाधित बाइलेवल समस्याओं के लिए बेहतर बाउंड्स: प्रस्तावित मिनमैक्स फ्रेमवर्क के उदाहरण के रूप में बाधित कॉनवेक्स लोers-लेवल वाली बाइलेवल समस्याओं को पुनर्गठित करके, लेखक $\tilde{O}(\epsilon^{-4})$ की जटिलता प्राप्त करते हैं। यह [53] में $\tilde{O}(\epsilon^{-7})$ (केवल कॉनवेक्स लोers-लेवल के लिए) और [51] में $\tilde{O}(\epsilon^{-6})$ (स्ट्रॉन्गली कॉनवेक्स लोers-लेवल के लिए) के मौजूदा परिणामों में सुधार करता है। यह सुधार आंतरिक बाधाओं के लिए दूसरे पेनल्टी पैरामीटर के उपयोग से बचने से आता है, जो पहले उच्च स्मूथनेस पैरामीटर्स का कारण बनता था।
अनुभवजन्य सत्यापन (Empirical Validation):
- सिंथेटिक डेटा: बाधित लीनियर बाइलेवल समस्याओं पर, प्रस्तावित विधि मौजूदा पेनल्टी-आधारित विधियों (FOP और SMO) के मुकाबले प्रतिस्पर्धी अभिसरण गति प्रदर्शित करती है, विशेष रूप से जब लिप्सचिट्ज़ स्थिरांक (Lipschitz constant) को ट्यून किया जाता है।
- वास्तविक दुनिया का अनुप्रयोग: विधि को डीप लर्निंग में डिस्ट्रिब्यूशनली रोबस्ट ऑप्टिमाइज़ेशन (DRO) के लिए हाइपरपैरामीटर ट्यूनिंग पर लागू किया गया है। CelebA और Waterbirds डेटासेट पर, प्रस्तावित स्टोकेस्टिक बाइलेवल दृष्टिकोण औसत सटीकता को बनाए रखते हुए वर्स्ट-ग्रुप एक्यूरेसी (worst-group accuracy) के मामले में मानक DRO विधियों से बेहतर प्रदर्शन करता है।

परिणाम और महत्व (Results and Significance)

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

सैद्धांतिक महत्व: यह कार्य बाइलेवल ऑप्टिमाइज़ेशन और मिनमैक्स ऑप्टिमाइज़ेशन के बीच के अंतर को पाटता है, जो लोers-लेवल के लिए स्ट्रॉन्ग कॉनवेक्सिटी धारणाओं पर निर्भर किए बिना कठोर अभिसरण गारंटी प्रदान करता है। बाधित लोers-लेवल के लिए कॉम्प्लेक्सिटी को $\tilde{O}(\epsilon^{-7})$ से घटाकर $\tilde{O}(\epsilon^{-4})$ करना एक महत्वपूर्ण सैद्धांतिक प्रगति के रूप में प्रस्तुत किया गया है।
व्यावहारिक महत्व: DRO में अनुप्रयोग वितरण बदलाव (distribution shifts) और ग्रुप फेयरनेस (group fairness) से जुड़े मशीन लर्निंग परिदृश्यों में विधि की उपयोगिता को प्रदर्शित करता है। CelebA और Waterbirds डेटासेट पर परिणाम दिखाते हैं कि विधि बेसलाइन DRO विधियों की तुलना में वर्स्ट-ग्रुप एक्यूरेसी प्राप्त करके वर्स्ट-ग्रुप ऑप्टिमाइज़ेशन चुनौती को प्रभावी ढंग से संभाल सकती है।

लेखक सीमाओं को स्वीकार करते हैं, जिनमें कॉम्पैक्ट फिक्सेबल डोमेन की आवश्यकता, KKT परिभाषाओं के लिए लिफ्टेड स्पेस का उपयोग, और स्टोकेस्टिक केस की उच्च जटिलता ( $\tilde{O}(\epsilon^{-9})$ ) शामिल है, यह नोट करते हुए कि वेरिएंस रिडक्शन तकनीकें भविष्य के कार्य के लिए एक दिशा हो सकती हैं।