2025-11-22T15:28:16.372787

An Augmented Lagrangian Value Function Method for Lower-level Constrained Stochastic Bilevel Optimization

Nie, Li, Wen
Recently, lower-level constrained bilevel optimization has attracted increasing attention. However, existing methods mostly focus on either deterministic cases or problems with linear constraints. The main challenge in stochastic cases with general constraints is the bias and variance of the hyper-gradient, arising from the inexact solution of the lower-level problem. In this paper, we propose a novel stochastic augmented Lagrangian value function method for solving stochastic bilevel optimization problems with nonlinear lower-level constraints. Our approach reformulates the original bilevel problem using an augmented Lagrangian-based value function and then applies a penalized stochastic gradient method that carefully manages the noise from stochastic oracles. We establish an equivalence between the stochastic single-level reformulation and the original constrained bilevel problem and provide a non-asymptotic rate of convergence for the proposed method. The rate is further enhanced by employing variance reduction techniques. Extensive experiments on synthetic problems and real-world applications demonstrate the effectiveness of our approach.
academic

निम्न-स्तर की बाधित स्टोकेस्टिक द्विस्तरीय अनुकूलन के लिए एक संवर्धित लैग्रेंजियन मान फलन विधि

मूल जानकारी

  • पेपर ID: 2509.24249
  • शीर्षक: निम्न-स्तर की बाधित स्टोकेस्टिक द्विस्तरीय अनुकूलन के लिए एक संवर्धित लैग्रेंजियन मान फलन विधि
  • लेखक: हांताओ नी (बीजिंग विश्वविद्यालय), जियाक्सियांग ली (मिनेसोटा विश्वविद्यालय), जैवेन वेन (बीजिंग विश्वविद्यालय)
  • वर्गीकरण: math.OC (गणितीय अनुकूलन और नियंत्रण)
  • प्रकाशन समय: जनवरी 2025 (arXiv प्रीप्रिंट)
  • पेपर लिंक: https://arxiv.org/abs/2509.24249v2

सारांश

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

अनुसंधान पृष्ठभूमि और प्रेरणा

  1. समस्या की पृष्ठभूमि: निम्न-स्तर की बाधाओं के साथ द्विस्तरीय अनुकूलन (LC-BLO) मशीन लर्निंग क्षेत्र में व्यापक रूप से लागू होता है, जिसमें हाइपरपैरामीटर अनुकूलन, मेटा-लर्निंग, सुदृढ़ शिक्षा आदि शामिल हैं। इस प्रकार की समस्याओं में पदानुक्रमित संरचना होती है, जहां ऊपरी-स्तर की समस्या का समाधान निम्न-स्तर की बाधित अनुकूलन समस्या के इष्टतम समाधान पर निर्भर करता है।
  2. मौजूदा विधियों की सीमाएं:
    • अधिकांश मौजूदा विधियां केवल नियतात्मक मामलों या रैखिक बाधा समस्याओं पर ध्यान केंद्रित करती हैं
    • स्टोकेस्टिक सेटिंग में अरैखिक बाधा समस्याओं के लिए प्रभावी समाधान की कमी है
    • मुख्य चुनौती निम्न-स्तर की समस्या के अनुमानित समाधान से उत्पन्न हाइपरग्रेडिएंट पूर्वाग्रह और विचरण है
  3. तकनीकी चुनौतियां:
    • हाइपर-उद्देश्य फलन की गैर-चिकनाई
    • निम्न-स्तर की समस्या के अनुमानित समाधान से उत्पन्न हाइपरग्रेडिएंट पूर्वाग्रह
    • स्टोकेस्टिक ओरेकल द्वारा लाया गया शोर प्रबंधन
  4. अनुसंधान प्रेरणा: स्टोकेस्टिक अरैखिक बाधित द्विस्तरीय अनुकूलन के सिद्धांत और एल्गोरिदम में अंतराल को भरना, और व्यावहारिक मशीन लर्निंग अनुप्रयोगों के लिए सैद्धांतिक गारंटी के साथ कुशल एल्गोरिदम प्रदान करना।

मुख्य योगदान

  1. नई पुनर्निर्माण विधि: स्टोकेस्टिक संवर्धित लैग्रेंजियन फलन और इसके मोरो लिफाफे के आधार पर द्विस्तरीय समस्या के पुनर्निर्माण का प्रस्ताव, जो निम्न-स्तर की समस्या के अनुमानित समाधान से आने वाले शोर को प्रभावी ढंग से संभालता है
  2. सैद्धांतिक समतुल्यता: स्टोकेस्टिक एकल-स्तरीय पुनर्निर्माण और मूल द्विस्तरीय समस्या के बीच समतुल्यता स्थापित करना, जो एक व्यावहारिक और सैद्धांतिक रूप से ठोस विधि प्रदान करता है
  3. पहला अभिसरण विश्लेषण: अरैखिक LC-BLO के लिए स्टोकेस्टिक सेटिंग में मान फलन विधि का पहला अभिसरण विश्लेषण, Õ(cε⁻²), Õ(cc₁²ε⁻²) का नमूना जटिलता प्रमाणित करता है
  4. विचरण में कमी सुधार: विचरण में कमी की तकनीकों के माध्यम से ऊपरी-स्तर के चर की नमूना जटिलता को Õ(c^1.5ε⁻^1.5) तक सुधारा गया

विधि विवरण

कार्य परिभाषा

स्टोकेस्टिक निम्न-स्तर की बाधित द्विस्तरीय अनुकूलन समस्या पर विचार करें:

निम्न-स्तर की समस्या:

min_{y∈Y} G(x,y) = E_{ξ~D_ξ}[g(x,y;ξ)]
s.t. H_i(x,y) ≤ 0, i = 1,...,p

ऊपरी-स्तर की समस्या:

min_{x∈X} F(x,y*(x)) = E_{ζ~D_ζ}[f(x,y*(x);ζ)]
s.t. y*(x) ∈ arg min_{y∈Y(x)} G(x,y)

जहां Y(x) := {y ∈ Y | H(x,y) ≤ 0} निम्न-स्तर का व्यावहारिक क्षेत्र है।

मॉडल आर्किटेक्चर

1. संवर्धित लैग्रेंजियन पुनर्निर्माण

संवर्धित लैग्रेंजियन दंड पद का परिचय:

A_{γ₁}(x,y,z) = (1/2γ₁)∑ᵢ[γ₁zᵢ + Hᵢ(x,y)]²₊

संवर्धित लैग्रेंजियन फलन को परिभाषित करें:

L_{γ₁}(x,y,z) = G(x,y) + A_{γ₁}(x,y,z)

2. मोरो लिफाफा मान फलन

द्वैत फलन और इसके मोरो लिफाफे का निर्माण:

D_{γ₁}(x,z) = min_{y∈Y} L_{γ₁}(x,y,z)
E^{γ₂}_{γ₁}(x,z) = max_{λ∈ℝ^p₊} {D_{γ₁}(x,λ) - (γ₂/2)||λ-z||²}

3. एकल-स्तरीय पुनर्निर्माण

मूल द्विस्तरीय समस्या को पुनर्निर्मित करें:

min_{(x,y,z)∈X×Y×ℝ^p₊} F(x,y)
s.t. Ĝ(x,y,z;ξ) ≤ ε₁, (1/2)∑ᵢ[Hᵢ(x,y)]²₊ ≤ ε₂²

जहां Ĝ(x,y,z;ξ) = G(x,y) - ℓ_γ(x,z,ŵ(ξ),λ̂(ξ))।

4. दंड विधि

संवर्धित लैग्रेंजियन दंड पुनर्निर्माण को अपनाएं:

min_{(x,y,z)∈X×Y×Z} E_ξ[Ψ(x,y,z;ξ)]

जहां Ψ(x,y,z;ξ) := F(x,y) + c₁Ĝ(x,y,z;ξ) + (c₂/2)∑ᵢHᵢ(x,y)²₊

तकनीकी नवाचार

  1. दोहरे-लूप एल्गोरिदम संरचना:
    • आंतरिक लूप: उप-समस्याओं को हल करने के लिए स्टोकेस्टिक संवर्धित लैग्रेंजियन विधि (SALM) का उपयोग
    • बाहरी लूप: पुनर्निर्मित समस्या पर स्टोकेस्टिक ग्रेडिएंट डिसेंट लागू करें
  2. पूर्वाग्रह नियंत्रण तंत्र: निम्न-स्तर के समाधान की सटीकता को नियंत्रित करके पूर्वाग्रह ग्रेडिएंट समस्या को कम करना
  3. विचरण में कमी की तकनीक: ऊपरी-स्तर के चर की नमूना जटिलता को कम करने के लिए STORM जैसे अपडेट नियम को अपनाएं

प्रयोगात्मक सेटअप

डेटासेट

  1. संश्लेषित समस्याएं: जियांग एट अल. (2012) से परीक्षण उदाहरण, गॉसियन शोर σ = 0.1 जोड़ा गया
  2. SVM हाइपरपैरामीटर अनुकूलन: डायबिटीज और फोरक्लास डेटासेट पर
  3. वजन क्षय ट्यूनिंग: अंक डेटासेट पर दो-स्तरीय MLP का उपयोग करके तंत्रिका नेटवर्क वजन क्षय पैरामीटर अनुकूलन

मूल्यांकन मेट्रिक्स

  • परीक्षण सटीकता
  • अभिसरण समय
  • पुनरावृत्ति संख्या
  • उद्देश्य फलन मान

तुलना विधियां

  • LV-HBA: लैग्रेंजियन मान फलन पर आधारित विधि
  • GAM: ग्रेडिएंट संवर्धन विधि
  • BLOCC: द्विस्तरीय अनुकूलन बाधा नियंत्रण विधि
  • SALVF: इस पेपर द्वारा प्रस्तावित आधार विधि
  • SALVF-VR: इस पेपर द्वारा प्रस्तावित विचरण में कमी संस्करण

कार्यान्वयन विवरण

  • आंतरिक लूप स्टेप साइज: ηⱼ = η/(j+1), ρⱼ = ρ/(j+1)
  • बाहरी लूप स्टेप साइज: αₖ = α < 1/(2L_Ψ)
  • नमूना आकार: rₖ = r, qₖ = q, sₖ = s (स्थिरांक)
  • दंड पैरामीटर: c₁, c₂ सैद्धांतिक विश्लेषण के अनुसार चुने गए

प्रयोगात्मक परिणाम

मुख्य परिणाम

  1. संश्लेषित समस्याएं: SALVF और SALVF-VR दोनों वैश्विक इष्टतम समाधान के पास अभिसरित होते हैं, SALVF-VR का वितरण अधिक केंद्रित है, जो विचरण में कमी के त्वरण प्रभाव को सत्यापित करता है
  2. SVM हाइपरपैरामीटर अनुकूलन:
    • SALVF परीक्षण सटीकता में सभी आधार विधियों से बेहतर है
    • हालांकि BLOCC भी समान शिखर सटीकता तक पहुंच सकता है, लेकिन SALVF की पुनरावृत्ति अधिक समय-कुशल है
    • डायबिटीज डेटासेट पर लगभग 80% परीक्षण सटीकता, फोरक्लास डेटासेट पर लगभग 75% परीक्षण सटीकता प्राप्त करता है
  3. वजन क्षय ट्यूनिंग:
    • सभी द्विस्तरीय विधियां बिना वजन क्षय के आधार से बेहतर प्रदर्शन करती हैं, अधिक-फिटिंग को प्रभावी ढंग से कम करती हैं
    • SALVF समय दक्षता में सर्वोत्तम है, दोहरे-लूप पुनरावृत्ति प्रक्रिया की सरलता के कारण

सैद्धांतिक परिणाम

  1. नमूना जटिलता:
    • SALVF: (Õ(cε⁻²), Õ(cc₁²ε⁻²))
    • SALVF-VR: (Õ(c^1.5ε⁻^1.5), Õ(c^1.5c₁²ε⁻^2.5))
  2. अभिसरण दर:
    • SALVF: Õ(cε⁻¹) पुनरावृत्ति जटिलता
    • SALVF-VR: Õ(c^1.5ε⁻^1.5) पुनरावृत्ति जटिलता

प्रयोगात्मक निष्कर्ष

  1. विचरण में कमी की प्रभावशीलता: SALVF-VR SALVF की तुलना में वितरण केंद्रीकरण और अभिसरण गति दोनों में महत्वपूर्ण सुधार दिखाता है
  2. समय दक्षता लाभ: दोहरे-लूप संरचना तीन-लूप विधियों (जैसे BLOCC) की तुलना में स्पष्ट कम्प्यूटेशनल लाभ है
  3. व्यावहारिकता सत्यापन: वास्तविक मशीन लर्निंग कार्यों में उत्कृष्ट प्रदर्शन, विधि की व्यावहारिक मूल्य को सत्यापित करता है

संबंधित कार्य

मुख्य अनुसंधान दिशाएं

  1. निहित ग्रेडिएंट विधियां (IG): मुख्य रूप से हाइपरग्रेडिएंट की गणना पर ध्यान केंद्रित करती हैं, लेकिन दूसरे-क्रम व्युत्पन्न की आवश्यकता होती है, उच्च कम्प्यूटेशनल लागत
  2. निम्न-स्तर मान फलन विधियां (LLVF): निम्न-स्तर की समस्या मान फलन का परिचय, हेसियन-मुक्त विकल्प के रूप में
  3. दंड विधियां: बाधित समस्याओं को अबाधित समस्याओं में परिवर्तित करके समाधान करना

इस पेपर के लाभ

  1. पहला स्टोकेस्टिक अरैखिक बाधा विश्लेषण: मौजूदा कार्य मुख्य रूप से नियतात्मक या रैखिक बाधा मामलों पर ध्यान केंद्रित करते हैं
  2. सैद्धांतिक गारंटी: गैर-स्पर्शोन्मुख अभिसरण दर विश्लेषण प्रदान करता है
  3. व्यावहारिकता: हेसियन गणना की आवश्यकता नहीं, बड़े पैमाने की समस्याओं के लिए उपयुक्त

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. स्टोकेस्टिक अरैखिक बाधित द्विस्तरीय अनुकूलन की महत्वपूर्ण लेकिन अपर्याप्त रूप से अध्ययन की गई समस्या को सफलतापूर्वक हल किया
  2. प्रस्तावित संवर्धित लैग्रेंजियन मान फलन विधि सिद्धांत और व्यवहार दोनों में उत्कृष्ट प्रदर्शन करती है
  3. विचरण में कमी की तकनीक एल्गोरिदम के प्रदर्शन में प्रभावी ढंग से सुधार करती है

सीमाएं

  1. नमूना जटिलता निर्भरता: निम्न-स्तर के चर की नमूना जटिलता अभी भी अधिक है (O(c₁²ε⁻¹))
  2. पैरामीटर चयन: दंड पैरामीटर c₁, c₂ का चयन समस्या पैरामीटर पर निर्भर करता है, ट्यूनिंग की आवश्यकता हो सकती है
  3. दृढ़ उत्तलता धारणा: निम्न-स्तर की समस्या को दृढ़ उत्तलता धारणा को संतुष्ट करने की आवश्यकता है

भविष्य की दिशाएं

  1. नमूना जटिलता सुधार: यह पता लगाना कि क्या ऊपरी-स्तर और निम्न-स्तर दोनों चर की नमूना जटिलता को एक साथ कम किया जा सकता है
  2. स्व-अनुकूली पैरामीटर चयन: दंड पैरामीटर चुनने के लिए स्व-अनुकूली रणनीति विकसित करना
  3. गैर-उत्तल विस्तार: निम्न-स्तर की समस्या गैर-उत्तल होने की स्थिति में विस्तार

गहन मूल्यांकन

शक्तियां

  1. महत्वपूर्ण सैद्धांतिक योगदान: स्टोकेस्टिक अरैखिक बाधित द्विस्तरीय अनुकूलन के लिए पहली बार संपूर्ण सैद्धांतिक विश्लेषण
  2. चतुर विधि डिजाइन: संवर्धित लैग्रेंजियन पुनर्निर्माण समस्या समतुल्यता को बनाए रखता है और एल्गोरिदम गुणों में सुधार करता है
  3. व्यापक प्रयोग: संश्लेषित समस्याओं से वास्तविक अनुप्रयोगों तक व्यापक सत्यापन
  4. स्पष्ट लेखन: कठोर गणितीय व्युत्पत्ति, स्पष्ट अभिव्यक्ति

कमियां

  1. कम्प्यूटेशनल जटिलता: दोहरे-लूप संरचना अभी भी उच्च कम्प्यूटेशनल लागत लाती है
  2. धारणा की शर्तें: कई तकनीकी धारणाओं की आवश्यकता (दृढ़ उत्तलता, स्लेटर स्थिति, आदि)
  3. पैरामीटर संवेदनशीलता: एल्गोरिदम प्रदर्शन दंड पैरामीटर चयन के प्रति संवेदनशील हो सकता है

प्रभाव

  1. शैक्षणिक मूल्य: महत्वपूर्ण सैद्धांतिक अंतराल को भरता है, बाद के अनुसंधान के लिए आधार प्रदान करता है
  2. व्यावहारिक मूल्य: मशीन लर्निंग के कई महत्वपूर्ण अनुप्रयोगों में संभावित उपयोग
  3. पुनरुत्पादनीयता: विस्तृत एल्गोरिदम विवरण और सैद्धांतिक विश्लेषण प्रदान करता है

लागू परिदृश्य

  1. हाइपरपैरामीटर अनुकूलन: विशेष रूप से बाधित हाइपरपैरामीटर ट्यूनिंग समस्याएं
  2. मेटा-लर्निंग: बाधा की शर्तों के तहत सीखने की रणनीति सीखने की आवश्यकता
  3. सुदृढ़ शिक्षा: बाधित नीति अनुकूलन समस्याएं
  4. तंत्रिका आर्किटेक्चर खोज: संसाधन बाधाओं के तहत आर्किटेक्चर अनुकूलन

संदर्भ

पेपर 49 संबंधित संदर्भों का हवाला देता है, मुख्य रूप से:

  • द्विस्तरीय अनुकूलन के शास्त्रीय कार्य और नवीनतम प्रगति
  • संवर्धित लैग्रेंजियन विधि की सैद्धांतिक नींव
  • स्टोकेस्टिक अनुकूलन और विचरण में कमी की तकनीकें
  • मशीन लर्निंग में अनुप्रयोग के मामले

समग्र मूल्यांकन: यह एक उच्च-गुणवत्ता वाला सैद्धांतिक और अनुप्रयोग-केंद्रित पेपर है जो एक महत्वपूर्ण लेकिन कठिन समस्या पर वास्तविक प्रगति प्राप्त करता है, स्टोकेस्टिक बाधित द्विस्तरीय अनुकूलन क्षेत्र में महत्वपूर्ण योगदान देता है। विधि नई है, सिद्धांत कठोर है, प्रयोग व्यापक हैं, और इसमें उत्कृष्ट शैक्षणिक मूल्य और व्यावहारिक संभावनाएं हैं।