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

নিম্ন-স্তরের সীমাবদ্ধতাযুক্ত স্টোকাস্টিক দ্বিস্তরীয় অপ্টিমাইজেশনের জন্য একটি বর্ধিত লাগ্রেঞ্জিয়ান মূল্য ফাংশন পদ্ধতি

মৌলিক তথ্য

  • পেপার আইডি: 2509.24249
  • শিরোনাম: An Augmented Lagrangian Value Function Method for Lower-level Constrained Stochastic Bilevel Optimization
  • লেখক: Hantao Nie (পিকিং বিশ্ববিদ্যালয়), Jiaxiang Li (মিনেসোটা বিশ্ববিদ্যালয়), Zaiwen Wen (পিকিং বিশ্ববিদ্যালয়)
  • শ্রেণীবিভাগ: math.OC (গাণিতিক অপ্টিমাইজেশন এবং নিয়ন্ত্রণ)
  • প্রকাশনার সময়: ২০২৫ সালের জানুয়ারি (arXiv প্রিপ্রিন্ট)
  • পেপার লিংক: https://arxiv.org/abs/2509.24249v2

সারসংক্ষেপ

এই পেপারটি অরৈখিক নিম্ন-স্তরের সীমাবদ্ধতা সহ স্টোকাস্টিক দ্বিস্তরীয় অপ্টিমাইজেশন সমস্যার জন্য একটি উদ্ভাবনী স্টোকাস্টিক বর্ধিত লাগ্রেঞ্জিয়ান মূল্য ফাংশন পদ্ধতি প্রস্তাব করে। এই পদ্ধতিটি বর্ধিত লাগ্রেঞ্জিয়ান মূল্য ফাংশনের মাধ্যমে মূল দ্বিস্তরীয় সমস্যাটি পুনর্গঠন করে এবং স্টোকাস্টিক অরাকেল থেকে আসা শব্দ সাবধানে পরিচালনা করতে শাস্তিমূলক স্টোকাস্টিক গ্রেডিয়েন্ট পদ্ধতি প্রয়োগ করে। লেখকরা স্টোকাস্টিক একক-স্তরের পুনর্গঠন এবং মূল সীমাবদ্ধ দ্বিস্তরীয় সমস্যার মধ্যে সমতা প্রতিষ্ঠা করেন এবং অ-অ্যাসিম্পটোটিক সংবেদনশীলতা হার বিশ্লেষণ প্রদান করেন। ভেরিয়েন্স হ্রাস কৌশলের মাধ্যমে সংবেদনশীলতা হার আরও উন্নত করা হয়েছে। সিন্থেটিক সমস্যা এবং বাস্তব প্রয়োগে ব্যাপক পরীক্ষা-নিরীক্ষা পদ্ধতির কার্যকারিতা যাচাই করেছে।

গবেষণা পটভূমি এবং প্রেরণা

  1. সমস্যার পটভূমি: নিম্ন-স্তরের সীমাবদ্ধতা সহ দ্বিস্তরীয় অপ্টিমাইজেশন (LC-BLO) মেশিন লার্নিং ক্ষেত্রে ব্যাপকভাবে প্রয়োগ করা হয়, যার মধ্যে রয়েছে হাইপারপ্যারামিটার অপ্টিমাইজেশন, মেটা-লার্নিং এবং শক্তিশালী শিক্ষা। এই ধরনের সমস্যাগুলির একটি স্তরযুক্ত কাঠামো রয়েছে, যেখানে উপরের স্তরের সমস্যার সমাধান নিম্ন-স্তরের সীমাবদ্ধ অপ্টিমাইজেশন সমস্যার সর্বোত্তম সমাধানের উপর নির্ভর করে।
  2. বিদ্যমান পদ্ধতির সীমাবদ্ধতা:
    • বেশিরভাগ বিদ্যমান পদ্ধতি শুধুমাত্র নির্ধারণীয় ক্ষেত্রে বা রৈখিক সীমাবদ্ধতা সমস্যায় মনোনিবেশ করে
    • স্টোকাস্টিক ক্ষেত্রে অরৈখিক সীমাবদ্ধতা সমস্যার জন্য কার্যকর সমাধানের অভাব রয়েছে
    • প্রধান চ্যালেঞ্জ হল নিম্ন-স্তরের সমস্যার অনির্ভুল সমাধান থেকে উদ্ভূত হাইপারগ্রেডিয়েন্ট পক্ষপাত এবং ভেরিয়েন্স
  3. প্রযুক্তিগত চ্যালেঞ্জ:
    • হাইপার-উদ্দেশ্য ফাংশনের অ-মসৃণতা
    • নিম্ন-স্তরের সমস্যার অনির্ভুল সমাধান থেকে উদ্ভূত হাইপারগ্রেডিয়েন্ট পক্ষপাত
    • স্টোকাস্টিক অরাকেল দ্বারা আনা শব্দ পরিচালনা
  4. গবেষণার প্রেরণা: স্টোকাস্টিক অরৈখিক সীমাবদ্ধ দ্বিস্তরীয় অপ্টিমাইজেশনের তত্ত্ব এবং অ্যালগরিদমের ফাঁক পূরণ করা, বাস্তব মেশিন লার্নিং প্রয়োগের জন্য তাত্ত্বিক গ্যারান্টি সহ দক্ষ অ্যালগরিদম প্রদান করা।

মূল অবদান

  1. উদ্ভাবনী পুনর্গঠন পদ্ধতি: স্টোকাস্টিক বর্ধিত লাগ্রেঞ্জিয়ান ফাংশন এবং এর Moreau এনভেলপের উপর ভিত্তি করে দ্বিস্তরীয় সমস্যার পুনর্গঠন প্রস্তাব করে, যা নিম্ন-স্তরের সমস্যার অনির্ভুল সমাধান থেকে আসা শব্দ কার্যকরভাবে পরিচালনা করে
  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} নিম্ন-স্তরের সম্ভাব্য অঞ্চল।

মডেল আর্কিটেকচার

১. বর্ধিত লাগ্রেঞ্জিয়ান পুনর্গঠন

বর্ধিত লাগ্রেঞ্জিয়ান শাস্তি পদ প্রবর্তন করুন:

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

বর্ধিত লাগ্রেঞ্জিয়ান ফাংশন সংজ্ঞায়িত করুন:

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

২. Moreau এনভেলপ মূল্য ফাংশন

দ্বৈত ফাংশন এবং এর Moreau এনভেলপ তৈরি করুন:

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

३. একক-স্তরের পুনর্গঠন

মূল দ্বিস্তরীয় সমস্যাটি পুনর্গঠন করুন:

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,ŵ(ξ),λ̂(ξ))।

४. শাস্তি পদ্ধতি

বর্ধিত লাগ্রেঞ্জিয়ান শাস্তি পুনর্গঠন গ্রহণ করুন:

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. সিন্থেটিক সমস্যা: Jiang et al. (2012) থেকে পরীক্ষার উদাহরণ, গাউসিয়ান শব্দ σ = 0.1 যোগ করা হয়েছে
  2. SVM হাইপারপ্যারামিটার অপ্টিমাইজেশন: Diabetes এবং Fourclass ডেটাসেটে সম্পাদিত
  3. ওজন ক্ষয় টিউনিং: digit ডেটাসেটে দুই-স্তরের 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 এর পুনরাবৃত্তি আরও সময় দক্ষ
    • Diabetes ডেটাসেটে প্রায় 80% পরীক্ষা নির্ভুলতা এবং Fourclass ডেটাসেটে প্রায় 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): নিম্ন-স্তরের সমস্যা মূল্য ফাংশন প্রবর্তন করে, Hessian-মুক্ত বিকল্প হিসাবে কাজ করে
  3. শাস্তি পদ্ধতি: সীমাবদ্ধ সমস্যাকে অসীমাবদ্ধ সমস্যায় রূপান্তরিত করে সমাধান করে

এই পেপারের সুবিধা

  1. প্রথম স্টোকাস্টিক অরৈখিক সীমাবদ্ধতা বিশ্লেষণ: বিদ্যমান কাজ প্রধানত নির্ধারণীয় বা রৈখিক সীমাবদ্ধতা ক্ষেত্রে মনোনিবেশ করে
  2. তাত্ত্বিক গ্যারান্টি: অ-অ্যাসিম্পটোটিক সংবেদনশীলতা হার বিশ্লেষণ প্রদান করে
  3. ব্যবহারিকতা: Hessian গণনার প্রয়োজন নেই, বড় আকারের সমস্যার জন্য উপযুক্ত

উপসংহার এবং আলোচনা

প্রধান উপসংহার

  1. স্টোকাস্টিক অরৈখিক সীমাবদ্ধ দ্বিস্তরীয় অপ্টিমাইজেশন এই গুরুত্বপূর্ণ কিন্তু অপর্যাপ্তভাবে অধ্যয়ন করা সমস্যা সফলভাবে সমাধান করেছে
  2. প্রস্তাবিত বর্ধিত লাগ্রেঞ্জিয়ান মূল্য ফাংশন পদ্ধতি তত্ত্ব এবং অনুশীলন উভয় ক্ষেত্রেই চমৎকার পারফরম্যান্স প্রদর্শন করে
  3. ভেরিয়েন্স হ্রাস কৌশল অ্যালগরিদম পারফরম্যান্স কার্যকরভাবে উন্নত করে

সীমাবদ্ধতা

  1. নমুনা জটিলতা নির্ভরতা: নিম্ন-স্তরের ভেরিয়েবলের নমুনা জটিলতা এখনও বেশি (O(c₁²ε⁻¹))
  2. প্যারামিটার নির্বাচন: শাস্তি প্যারামিটার c₁, c₂ এর নির্বাচন সমস্যা প্যারামিটারের উপর নির্ভর করে, সম্ভবত টিউনিং প্রয়োজন
  3. শক্তিশালী উত্তলতা অনুমান: নিম্ন-স্তরের সমস্যা শক্তিশালী উত্তলতা অনুমান পূরণ করতে হবে

ভবিষ্যত দিকনির্দেশনা

  1. নমুনা জটিলতা উন্নতি: উপরের এবং নিম্ন-স্তরের ভেরিয়েবলের নমুনা জটিলতা একযোগে হ্রাস করা যায় কিনা তা অন্বেষণ করুন
  2. স্বয়ংক্রিয় প্যারামিটার নির্বাচন: শাস্তি প্যারামিটার নির্বাচনের জন্য স্বয়ংক্রিয় কৌশল বিকাশ করুন
  3. অ-উত্তল সম্প্রসারণ: নিম্ন-স্তরের সমস্যা অ-উত্তল ক্ষেত্রে সম্প্রসারণ করুন

গভীর মূল্যায়ন

সুবিধা

  1. উল্লেখযোগ্য তাত্ত্বিক অবদান: স্টোকাস্টিক অরৈখিক সীমাবদ্ধ দ্বিস্তরীয় অপ্টিমাইজেশনের জন্য প্রথমবার সম্পূর্ণ তাত্ত্বিক বিশ্লেষণ প্রদান করে
  2. চতুর পদ্ধতি ডিজাইন: বর্ধিত লাগ্রেঞ্জিয়ান পুনর্গঠন সমস্যা সমতা বজায় রাখে এবং অ্যালগরিদম বৈশিষ্ট্য উন্নত করে
  3. ব্যাপক পরীক্ষা-নিরীক্ষা: সিন্থেটিক সমস্যা থেকে বাস্তব প্রয়োগ পর্যন্ত সম্পূর্ণ যাচাইকরণ
  4. স্পষ্ট লেখা: গাণিতিক ডেরিভেশন কঠোর, অভিব্যক্তি স্পষ্ট

অপূর্ণতা

  1. গণনা জটিলতা: দ্বৈত-লুপ কাঠামো এখনও উচ্চ গণনা খরচ নিয়ে আসে
  2. অনুমান শর্ত: একাধিক প্রযুক্তিগত অনুমান প্রয়োজন (শক্তিশালী উত্তলতা, Slater শর্ত ইত্যাদি)
  3. প্যারামিটার সংবেদনশীলতা: অ্যালগরিদম পারফরম্যান্স শাস্তি প্যারামিটার নির্বাচনের প্রতি সংবেদনশীল হতে পারে

প্রভাব

  1. একাডেমিক মূল্য: গুরুত্বপূর্ণ তাত্ত্বিক ফাঁক পূরণ করে, পরবর্তী গবেষণার ভিত্তি প্রদান করে
  2. ব্যবহারিক মূল্য: মেশিন লার্নিংয়ের একাধিক গুরুত্বপূর্ণ প্রয়োগে সম্ভাব্য ব্যবহার রয়েছে
  3. পুনরুৎপাদনযোগ্যতা: বিস্তারিত অ্যালগরিদম বর্ণনা এবং তাত্ত্বিক বিশ্লেষণ প্রদান করে

প্রযোজ্য পরিস্থিতি

  1. হাইপারপ্যারামিটার অপ্টিমাইজেশন: বিশেষত সীমাবদ্ধ হাইপারপ্যারামিটার টিউনিং সমস্যা
  2. মেটা-লার্নিং: সীমাবদ্ধ শর্তে শিক্ষা কৌশল শিখতে হবে
  3. শক্তিশালী শিক্ষা: সীমাবদ্ধ নীতি অপ্টিমাইজেশন সমস্যা
  4. নিউরাল আর্কিটেকচার সার্চ: সম্পদ সীমাবদ্ধতার অধীনে আর্কিটেকচার অপ্টিমাইজেশন

রেফারেন্স

পেপারটি 49টি সম্পর্কিত রেফারেন্স উদ্ধৃত করে, যার মধ্যে প্রধানত রয়েছে:

  • দ্বিস্তরীয় অপ্টিমাইজেশনের ক্লাসিক কাজ এবং সর্বশেষ অগ্রগতি
  • বর্ধিত লাগ্রেঞ্জিয়ান পদ্ধতির তাত্ত্বিক ভিত্তি
  • স্টোকাস্টিক অপ্টিমাইজেশন এবং ভেরিয়েন্স হ্রাস কৌশল
  • মেশিন লার্নিংয়ে প্রয়োগ কেস

সামগ্রিক মূল্যায়ন: এটি একটি উচ্চ-মানের তত্ত্ব এবং প্রয়োগ উভয়ই জোর দেওয়া পেপার, যা গুরুত্বপূর্ণ কিন্তু কঠিন সমস্যায় উল্লেখযোগ্য অগ্রগতি অর্জন করেছে, স্টোকাস্টিক সীমাবদ্ধ দ্বিস্তরীয় অপ্টিমাইজেশন ক্ষেত্রে গুরুত্বপূর্ণ অবদান রেখেছে। পদ্ধতি উদ্ভাবনী, তত্ত্ব কঠোর, পরীক্ষা-নিরীক্ষা ব্যাপক, চমৎকার একাডেমিক মূল্য এবং ব্যবহারিক সম্ভাবনা রয়েছে।