2025-11-22T03:37:15.627362

Nonasymptotic Analysis of Accelerated Methods With Inexact Oracle Under Absolute Error Bound

Liu, Tajbakhsh
Performance analysis of first-order algorithms with inexact oracles has gained recent attention due to various emerging applications in which obtaining exact gradients is impossible or computationally expensive. Previous research has demonstrated that the performance of accelerated first-order methods is more sensitive to gradient errors compared with non-accelerated ones. This paper investigates the nonasymptotic convergence bound of two accelerated methods with inexact gradients to solve deterministic smooth convex problems. Performance Estimation Problem (PEP) is used as the primary tool to analyze the convergence bounds of the underlying algorithms. By finding an analytical solution to PEP, we derive novel convergence bounds of Generalized Optimized Gradient Method (GOGM) and Generalized Fast Gradient Method (GFGM) with inexact gradient oracles following the absolute error bound. The derived bounds allow varying oracle inexactness along the iterations; furthermore, their accumulated error terms are independent of the initial condition and any unknown parameters. Furthermore, we analyze the tradeoff between the vanishing term and the accumulated error in the convergence bound that guides finding the optimal stepsize. Finally, we determine the optimal strategy to set the gradient inexactness along iterations (if possible in a given application), ensuring that the accumulated error remains subordinate to the vanishing term.
academic

अत्यधिक त्रुटि के साथत्वरित विधियों का गैर-स्पर्शोन्मुख विश्लेषण

मूल जानकारी

  • पेपर ID: 2408.00720
  • शीर्षक: Nonasymptotic Analysis of Accelerated Methods With Inexact Oracle Under Absolute Error Bound
  • लेखक: यिन लिउ (बीजिंग विश्वविद्यालय), सैम दावनलू ताजबख्श (ओहियो स्टेट विश्वविद्यालय)
  • वर्गीकरण: math.OC (अनुकूलन और नियंत्रण)
  • प्रकाशन समय: 15 अक्टूबर 2025
  • पेपर लिंक: https://arxiv.org/abs/2408.00720

सारांश

यह पेपर अनुपयुक्त ढाल oracle के तहत त्वरित प्रथम-क्रम विधियों की गैर-स्पर्शोन्मुख अभिसरण सीमाओं का अध्ययन करता है। चूंकि कई उभरती हुई अनुप्रयोगों में सटीक ढाल प्राप्त करना असंभव या कम्प्यूटेशनल रूप से महंगा है, अनुपयुक्त oracle के तहत प्रथम-क्रम एल्गोरिदम के प्रदर्शन विश्लेषण को व्यापक ध्यान मिला है। पूर्व अनुसंधान से पता चलता है कि गैर-त्वरित विधियों की तुलना में त्वरित प्रथम-क्रम विधियां ढाल त्रुटि के प्रति अधिक संवेदनशील हैं। यह पेपर प्रदर्शन अनुमान समस्या (PEP) को मुख्य विश्लेषण उपकरण के रूप में उपयोग करता है, PEP के विश्लेषणात्मक समाधान खोजकर, सामान्यीकृत अनुकूलन ढाल विधि (GOGM) और सामान्यीकृत तीव्र ढाल विधि (GFGM) के लिए पूर्ण त्रुटि सीमा के तहत नई अभिसरण सीमाएं प्राप्त की हैं।

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

समस्या परिभाषा

यह पेपर अनुकूलन समस्या पर विचार करता है:

min_{x∈R^d} f(x)

जहां f उत्तल है और Lipschitz सतत ढाल है। व्यावहारिक अनुप्रयोगों में, केवल अनुपयुक्त ढाल अनुमान प्राप्त किए जा सकते हैं:

∇̃f(x) = ∇f(x) + e, ||e|| ≤ b

अनुसंधान प्रेरणा

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

अनुप्रयोग परिदृश्य

  • द्विस्तरीय अनुकूलन: निचली स्तर की समस्या केवल उप-इष्टतम समाधान तक हल की जा सकती है
  • संयोजन अनुकूलन: छोटे बैच नमूनाकरण के माध्यम से अपेक्षा का अनुमान लगाना
  • शून्य-क्रम अनुकूलन: परिमित अंतर या गाऊसी स्मूथिंग के माध्यम से ढाल का अनुमान लगाना

मुख्य योगदान

  1. सैद्धांतिक सफलता: iGOGM और iGFGM के लिए पूर्ण त्रुटि (AE) स्थिति के तहत परिमाणित अभिसरण सीमाएं प्राप्त की, अज्ञात मापदंडों पर निर्भरता को समाप्त किया
  2. विधि नवाचार: PEP तकनीक के माध्यम से विश्लेषणात्मक व्यवहार्य समाधान खोजे, प्रारंभिक स्थिति से स्वतंत्र संचयी त्रुटि शर्तें प्रदान कीं
  3. व्यावहारिक मार्गदर्शन: अभिसरण दर और संचयी त्रुटि के बीच व्यापार-बंद का विश्लेषण किया, इष्टतम चरण आकार चयन रणनीति प्रदान की
  4. इष्टतम शेड्यूलिंग: ढाल अनुपयुक्तता की इष्टतम सेटिंग रणनीति निर्धारित की, कुल कम्प्यूटेशनल लागत को कम किया

विधि विवरण

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

पूर्ण त्रुटि स्थिति के तहत त्वरित ढाल विधियों की अभिसरण का अध्ययन:

  • इनपुट: अनुपयुक्त ढाल oracle जो ||∇̃f(x) - ∇f(x)|| ≤ b_x को संतुष्ट करता है
  • आउटपुट: अभिसरण सीमा f(x_K) - f* की ऊपरी सीमा
  • बाधा: f ∈ F_{0,L} (केवल उत्तल और L-चिकना)

मुख्य एल्गोरिदम

iGOGM एल्गोरिदम (एल्गोरिदम 2)

इनपुट: z_0 = x_0, A_0 = α_0 = 1, चरण आकार पैरामीटर{λ_k}
k = 0 से K-1 तक:
    y_{k+1} = x_k - (1/L)∇̃f(x_k)
    z_{k+1} = z_k - (2/L)α_k∇̃f(x_k)  # मुख्य: गुणांक 2
    α_{k+1} = (λ_{k+1} + √(4λ_{k+1}A_k + λ²_{k+1}))/2
    A_{k+1} = A_k + α_{k+1}
    x_{k+1} = (1 - α_{k+1}/A_{k+1})y_{k+1} + (α_{k+1}/A_{k+1})z_{k+1}

iGFGM एल्गोरिदम (एल्गोरिदम 1)

iGOGM के समान, लेकिन तीसरे चरण में गुणांक 1 है न कि 2।

तकनीकी नवाचार बिंदु

1. PEP विश्लेषणात्मक समाधान

प्रदर्शन अनुमान समस्या के द्वैत रूप के माध्यम से, विश्लेषणात्मक व्यवहार्य समाधान खोजें:

τ = L/(4A_K), v_{i,i+1} = A_i/A_K
u_i = [A_i(1+2α_{i+1})(A_i+2α_iα_{i+1})]/(4LA_K(A_{i+1}-α²_{i+1})) + Σ_{k=i+1}^{K-1} [A_k(1+2α_{k+1})α_iα_{k+1}]/(2LA_K(A_{k+1}-α²_{k+1}))

2. मैट्रिक्स अपघटन तकनीक

Schur पूरक और विकर्ण प्रभावशाली मैट्रिक्स गुणों का उपयोग करके, अर्ध-सकारात्मक निश्चित बाधा सुनिश्चित करें:

  • Gram मैट्रिक्स G = X^T X का निर्माण करें
  • PSD बाधाओं को संभालने के लिए ब्लॉक मैट्रिक्स अपघटन का उपयोग करें
  • साबित करें कि u_i द्वारा दिया गया समाधान व्यवहार्यता शर्तों को संतुष्ट करता है

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

प्रमेय 2.2 (iGOGM अभिसरण सीमा)

f(x_K) - f* - (1/2L)||∇f(x_K)||² ≤ L||x_0-x*||²/(4A_K) + Σ_{k=0}^{K-1} u_k||e_k||²

प्रमेय 2.4 (iGFGM अभिसरण सीमा)

f(x_K) - f* - (1/2L)||∇f(x_K)||² ≤ L||x_0-x*||²/(2A_K) + Σ_{k=0}^{K-1} u_k||e_k||²

मुख्य विशेषताएं:

  • संचयी त्रुटि शर्तें प्रारंभिक स्थिति ||x_0 - x*|| से स्वतंत्र हैं
  • पुनरावृत्ति के साथ भिन्न त्रुटि स्तर b_k की अनुमति देता है
  • गुणांक u_k स्पष्ट रूप से गणना योग्य हैं

प्रायोगिक सेटअप और परिणाम

संख्यात्मक सत्यापन

  1. समाधान का सत्यापन: विश्लेषणात्मक समाधान की सटीकता को सत्यापित करने के लिए संख्यात्मक समाधान के माध्यम से, सापेक्ष त्रुटि <10^{-3}
  2. व्यापार-बंद विश्लेषण: OGM-a (α_i = (i+a)/a) के लिए अभिसरण दर और संचयी त्रुटि के व्यापार-बंद का विश्लेषण
  3. इष्टतम शेड्यूलिंग: निश्चित त्रुटि बनाम इष्टतम परिवर्तनशील त्रुटि की कुल जटिलता की तुलना करें

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

  • जब a=4 हो, तो संचयी त्रुटि O(b²K³/L) परिमाण में है
  • a बढ़ाने से संचयी त्रुटि कम हो सकती है लेकिन अभिसरण दर में कमी आएगी
  • इष्टतम त्रुटि शेड्यूलिंग कुल η-जटिलता को काफी कम कर सकती है

संबंधित कार्य तुलना

त्रुटि स्थितिपरिवर्तनशील त्रुटि की अनुमति?पुनरावृत्ति जटिलतासीमा शर्तें
BIE 8×O(1/A_K + δ)बंधे हुए व्यवहार्य सेट
IFO 12✓O(1/A_K + Σδ_i/A_K)बंधे हुए व्यवहार्य सेट
IFO-q 41×O(1/K² + δ/K^{3q/2-1})उप-ढाल स्थिति
AE 58×O(1/K² + R̃_Kδ + Kδ²)अज्ञात R̃_K
यह पेपर✓O(1/A_K + Σu_kb_k²)कोई अतिरिक्त धारणा नहीं

इष्टतम त्रुटि शेड्यूलिंग

अनुकूलन समस्या

min Σ_{k=0}^{K-1} η_k = Σ_{k=0}^{K-1} h^{-1}(b_k)
s.t. Σ_{k=0}^{K-1} u_kb_k² ≤ LR²/(4A_K)

शक्ति-नियम क्षय स्थिति

h(η) = c₁η^{-c₂} के लिए, इष्टतम समाधान है:

b_k* = √(LR²/(4A_K)) · u_k^{1/(1+2c₂)} / (Σu_j^{1/(1+2c₂)})^{1/2}

घातीय क्षय स्थिति

h(η) = q₁q₂^{-η} के लिए, इष्टतम समाधान है:

b_k* = √(LR²/(4KA_Ku_k))

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

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

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

सीमाएं

  1. सैद्धांतिक परिणामों के लिए α_k² < A_k (कड़ी असमानता) की आवश्यकता है, मानक FGM के α_k² = A_k स्थिति को बाहर करता है
  2. इष्टतम एल्गोरिदम के चरण आकार में पुनरावर्ती संरचना की कमी है, व्यावहारिक कार्यान्वयन कठिन है
  3. विश्लेषण मुख्य रूप से नियतात्मक सेटिंग पर केंद्रित है, यादृच्छिक स्थिति को आगे के अनुसंधान की आवश्यकता है

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

  1. मजबूत उत्तलता और यादृच्छिक सेटिंग तक विस्तार करें
  2. अधिक सामान्य त्रुटि शर्तों का अध्ययन करें
  3. व्यावहारिक स्व-अनुकूल त्रुटि नियंत्रण रणनीति विकसित करें

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

लाभ

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

कमियां

  1. व्यावहारिकता सीमित: इष्टतम एल्गोरिदम की गैर-पुनरावर्ती प्रकृति वास्तविक अनुप्रयोग को सीमित करती है
  2. शर्त सीमाएं: कड़ी α_k² < A_k स्थिति कुछ महत्वपूर्ण स्थितियों को बाहर करती है
  3. प्रयोग अपर्याप्त: वास्तविक अनुकूलन समस्याओं पर संख्यात्मक प्रयोगों की कमी है

प्रभाव

यह पेपर अनुपयुक्त oracle के तहत त्वरित अनुकूलन के लिए महत्वपूर्ण सैद्धांतिक आधार प्रदान करता है, द्विस्तरीय अनुकूलन, संयोजन अनुकूलन आदि अनुप्रयोग क्षेत्रों के लिए मार्गदर्शन मूल्य है। PEP तकनीक का अनुप्रयोग संबंधित विश्लेषण के लिए नई पद्धति भी प्रदान करता है।

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

  • ढाल गणना महंगी बड़े पैमाने पर अनुकूलन समस्याएं
  • द्विस्तरीय अनुकूलन और संयोजन अनुकूलन समस्याएं
  • कम्प्यूटेशनल सटीकता और पुनरावृत्ति संख्या के बीच व्यापार-बंद की आवश्यकता वाले अनुप्रयोग
  • शून्य-क्रम अनुकूलन विधियों का सैद्धांतिक विश्लेषण

संदर्भ

मुख्य संदर्भ साहित्य में Drori & Teboulle की PEP सिद्धांत आधार 18, Kim & Fessler की OGM विधि 32,33, और Devolder आदि की अनुपयुक्त oracle विश्लेषण 12 शामिल हैं।