दो ज्यामितियों की कथा: अनुकूली अनुकूलक और गैर-यूक्लिडीय वंश

मूल जानकारी

• पेपर ID: 2511.20584
• शीर्षक: A Tale of Two Geometries: Adaptive Optimizers and Non-Euclidean Descent
• लेखक: Shuo Xie (Toyota Technological Institute at Chicago), Tianhao Wang (UC San Diego), Beining Wu (University of Chicago), Zhiyuan Li (Toyota Technological Institute at Chicago)
• वर्गीकरण: cs.LG (मशीन लर्निंग)
• प्रकाशन समय: 25 नवंबर 2025 (arXiv v1)
• पेपर लिंक: https://arxiv.org/abs/2511.20584

सारांश

यह पेपर अनुकूली अनुकूलकों (जैसे Adam, Shampoo) और सामान्यीकृत सबसे तीव्र वंश (NSD, जैसे Lion, Muon) के दो एल्गोरिदम परिवारों के बीच गैर-यूक्लिडीय ज्यामितीय संरचनाओं के उपयोग में आवश्यक अंतर का व्यवस्थित रूप से अध्ययन करता है। अनुसंधान से पता चलता है कि हालांकि दोनों घातीय गतिशील औसत (EMA) को बंद करने पर समतुल्य हो सकते हैं, लेकिन उनके सैद्धांतिक विश्लेषण विभिन्न ज्यामितीय मान्यताओं पर निर्भर करते हैं: अनुकूली अनुकूलकों को अधिक मजबूत "अनुकूली चिकनाई" (adaptive smoothness) की आवश्यकता होती है, जबकि NSD को केवल मानक चिकनाई की आवश्यकता होती है। यह पेपर अनुकूली चिकनाई सिद्धांत को गैर-उत्तल सेटिंग तक विस्तारित करता है और अनुकूली अनुकूलकों की अभिसरण को सटीक रूप से चिह्नित करता है। अधिक महत्वपूर्ण रूप से, अनुसंधान से पता चलता है कि अनुकूली चिकनाई अनुकूली अनुकूलकों को Nesterov गति के साथ उत्तल सेटिंग में त्वरण (O(T⁻²)) प्राप्त करने में सक्षम बनाती है, जबकि मानक चिकनाई कुछ गैर-यूक्लिडीय ज्यामितियों के तहत इस गारंटी को प्राप्त नहीं कर सकती है। इसके अलावा, पेपर "अनुकूली ढाल विचरण" की अवधारणा प्रस्तुत करता है, जो NSD के लिए आयाम-स्वतंत्र अभिसरण गारंटी प्रदान करता है, जो मानक ढाल विचरण मान्यता के तहत प्राप्य नहीं है।

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

मूल समस्या

यह पेपर दो मौलिक प्रश्नों का उत्तर देने का लक्ष्य रखता है:

1. Q1: क्या अनुकूली विधियां (जैसे Adam, Shampoo) और संबंधित गैर-यूक्लिडीय वंश विधियां (जैसे Lion, Muon) हानि फ़ंक्शन की गैर-यूक्लिडीय ज्यामिति का समान तरीके से उपयोग करती हैं?
2. Q2: क्या अनुकूली विधियों में अधिक मजबूत चिकनाई मान्यता वास्तविक अनुकूलन लाभ ला सकती है?

अनुसंधान का महत्व

• व्यावहारिक मूल्य: Adam जैसे अनुकूली अनुकूलक बड़े पैमाने पर मशीन लर्निंग मॉडल प्रशिक्षण में अपरिहार्य हैं (जैसे LLaMA, DeepSeek आदि), लेकिन हाल ही में Lion, Muon जैसी सरल NSD विधियां आश्चर्यजनक प्रभावशीलता प्रदर्शित करती हैं, जो दोनों विधियों के आवश्यक अंतर के बारे में सोच को प्रेरित करती है।
• सैद्धांतिक कमी: हालांकि Bernstein & Newhouse (2024) ने इंगित किया कि दोनों विधियां EMA को बंद करने पर समतुल्य हैं (जैसे Adam ℓ∞-NSD के बराबर है, Shampoo वर्णक्रमीय मानदंड NSD के बराबर है), लेकिन व्यवस्थित सैद्धांतिक लक्षण वर्णन की कमी है।
• ज्यामितीय दृष्टिकोण: दोनों विधियों की उच्च कार्यक्षमता हानि फ़ंक्शन की गैर-यूक्लिडीय ज्यामिति के उपयोग से संबंधित है, लेकिन उनके सैद्धांतिक विश्लेषण विभिन्न ज्यामितीय मान्यताओं पर निर्भर करते हैं।

मौजूदा विधियों की सीमाएं

1. अधूरा अभिसरण सिद्धांत: अनुकूली चिकनाई सिद्धांत केवल उत्तल सेटिंग में स्थापित है (Xie et al., 2025b), गैर-उत्तल स्थिति में लक्षण वर्णन की कमी है।
2. अस्पष्ट मान्यता शक्ति: अनुकूली चिकनाई हमेशा मानक चिकनाई से कम नहीं होती है, लेकिन यह अधिक मजबूत मान्यता वास्तविक लाभ लाती है या नहीं यह साबित नहीं हुआ है।
3. आयाम निर्भरता समस्या: NSD को यादृच्छिक अनुकूलन में आयाम निर्भरता समस्या है (जैसे SignGD का √d कारक), अधिक सूक्ष्म शोर मान्यता की कमी है।

मूल योगदान

1. गैर-उत्तल अभिसरण सिद्धांत: अनुकूली चिकनाई सिद्धांत को गैर-उत्तल सेटिंग तक विस्तारित करता है, अनुकूली अनुकूलकों के अभिसरण दर को सटीक रूप से चिह्नित करता है (Theorems C.2, C.7, C.8), इष्टतम Õ(T⁻¹/⁴) गति प्राप्त करता है।
2. त्वरित अभिसरण गारंटी: साबित करता है कि अनुकूली चिकनाई Nesterov गति के साथ अनुकूली अनुकूलकों को उत्तल सेटिंग में Õ(T⁻²) त्वरित दर प्राप्त करने में सक्षम बनाती है (Theorem 4.4), जबकि मानक ℓ∞ चिकनाई के तहत कोई भी अनुकूलक केवल Ω(T⁻¹) प्राप्त कर सकता है (Guzmán & Nemirovski, 2015)।
3. अनुकूली ढाल विचरण: अनुकूली ढाल विचरण की अवधारणा प्रस्तुत करता है (Definition 4.1), साबित करता है कि यह गति के साथ NSD के लिए आयाम-स्वतंत्र अभिसरण गारंटी प्रदान करता है (Theorem 4.6), और निचली सीमा (Theorem 4.9) के माध्यम से साबित करता है कि मानक ढाल विचरण के तहत आयाम निर्भरता अपरिहार्य है।
4. एकीकृत विश्लेषण ढांचा: AdaGrad, AdaGrad-Norm, एकतरफा Shampoo आदि सहित व्यापक अनुकूली विधियों को कवर करने वाला एकीकृत विश्लेषण ढांचा प्रदान करता है, मूल तकनीकी योगदान गैर-क्रमविनिमेय पूर्वशर्त को संभालने के लिए नई मैट्रिक्स असमानताएं हैं (Lemma 3.3, 3.4)।
5. सैद्धांतिक पृथक्करण: दोनों ज्यामितीय मान्यताओं (मानक बनाम अनुकूली) को चिकनाई और शोर दोनों आयामों पर मात्रात्मक रूप से अलग करता है, अनुकूलता के सैद्धांतिक समझ को गहरा करता है।

विधि विवरण

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

अनुकूलन समस्या पर विचार करें: $\min_{x \in \mathbb{R}^d} f(x)$

जहां $f: \mathbb{R}^d \to \mathbb{R}$ संभवतः गैर-उत्तल है। यादृच्छिक सेटिंग में, यादृच्छिक ढाल $\nabla f_t(x)$ के माध्यम से लक्ष्य फ़ंक्शन तक पहुंचा जाता है, जो $\mathbb{E}[\nabla f_t(x)] = \nabla f(x)$ को संतुष्ट करता है।

मूल अवधारणाएं

1. सुसंरचित पूर्वशर्त समुच्चय (Well-structured Preconditioner Set)

परिभाषा 2.1: $\mathcal{H} \subseteq \mathbb{S}_+^d$ को सुसंरचित पूर्वशर्त समुच्चय कहा जाता है, यदि $\mathcal{H} = \mathbb{S}_+^d \cap \mathcal{K}$, जहां $\mathcal{K} \subseteq \mathbb{M}^d$ इकाई मैट्रिक्स युक्त मैट्रिक्स उप-बीजगणित है।

उदाहरण:

• विकर्ण मैट्रिक्स समुच्चय $\mathcal{D}_+^d$ (Adam के अनुरूप)
• पूर्ण PSD मैट्रिक्स $\mathbb{S}_+^d$ (पूर्ण मैट्रिक्स AdaGrad के अनुरूप)
• अदिश मैट्रिक्स $\{cI_d: c>0\}$ (AdaGrad-Norm के अनुरूप)
• Kronecker गुणनफल संरचना $\mathbb{S}_{d_L}^+ \otimes I_{d_R}$ (एकतरफा Shampoo के अनुरूप)

2. प्रेरित मानदंड और द्वैत मानदंड

सुसंरचित पूर्वशर्त समुच्चय $\mathcal{H}$ के लिए, प्रेरित मानदंड को परिभाषित करें: $\|x\|_{\mathcal{H}} := \sup_{H \in \mathcal{H}, \text{Tr}(H) \leq 1} \|x\|_H = \sup_{H \in \mathcal{H}, \text{Tr}(H) \leq 1} \sqrt{x^\top H x}$

Lemma 2.2: द्वैत मानदंड को संतुष्ट करता है $\|x\|_{\mathcal{H},*} = \inf_{H \in \mathcal{H}, \text{Tr}(H) \leq 1} \|x\|_{H^{-1}}$

यह द्वैत दोनों ज्यामितियों को समझने की कुंजी है: $\|\cdot\|_{\mathcal{H}}$ सभी $\|\cdot\|_H$ का बिंदुवार सर्वोच्च है, जबकि $\|\cdot\|_{\mathcal{H},*}$ संबंधित द्वैत मानदंड का बिंदुवार न्यूनतम है।

3. दो प्रकार की चिकनाई

मानक चिकनाई (Definition 2.3): $L_{\|\cdot\|}(f) := \min\{L: \|\nabla f(x) - \nabla f(y)\|_* \leq L\|x-y\|, \forall x,y\}$

अनुकूली चिकनाई (Definition 2.4): $\Lambda_{\mathcal{H}}(f) := \min_{H \in \mathcal{H}, \text{Tr}(H) \leq 1} L_{\|\cdot\|_H}(f) = \min_{H \in \mathcal{H}, \forall x: -H \preceq \nabla^2 f(x) \preceq H} \text{Tr}(H)$

संबंध (Proposition 2.5): $L_{\|\cdot\|_{\mathcal{H}}}(f) \leq \Lambda_{\mathcal{H}}(f) \leq d \cdot L_{\|\cdot\|_{\mathcal{H}}}(f)$

अनुकूली चिकनाई हमेशा मानक चिकनाई से कम नहीं होती है, लेकिन आयाम कारक $d$ से अधिक नहीं होती है।

एकीकृत अनुकूली अनुकूलक ढांचा (Algorithm 1)

एल्गोरिदम संरचना:

इनपुट: प्रारंभिक बिंदु x₀, सीखने की दर η, पूर्वशर्त समुच्चय H, स्थिरता स्थिरांक ϵ
प्रारंभिकीकरण: M₋₁ = 0
For t = 0, 1, ..., T-1:
    gₜ ← ∇fₜ(xₜ)
    Mₜ ← संचय विधि(Mₜ₋₁, gₜ)  // तीन प्रकार
    Vₜ ← argmin_{H∈H} ⟨Mₜ + ϵI, H⁻¹⟩ + Tr(H)
    xₜ₊₁ ← xₜ - ηVₜ⁻¹gₜ
रिटर्न x_T

तीन संचय प्रकार:

1. संचयी प्रकार (Cumulative): $M_t = M_{t-1} + g_t g_t^\top$ (AdaGrad)
2. EMA प्रकार: $M_t = \beta M_{t-1} + (1-\beta)g_t g_t^\top$ (Adam)
3. भारित प्रकार (Weighted): $M_t = \beta M_{t-1} + g_t g_t^\top$ (एकीकृत विश्लेषण के लिए)

मुख्य अवलोकन: $V_t = \mathcal{P}_{\mathcal{H}}(M_t + \epsilon I)$, जहां $\mathcal{P}_{\mathcal{H}}(M)^2$ $M$ का $\mathcal{H}$ पर प्रक्षेपण है (Lemma A.4)।

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

1. नई मैट्रिक्स असमानता (Lemma 3.4)

धनात्मक निश्चित मैट्रिक्स $X, Y$ के लिए जो $Y \preceq X$ को संतुष्ट करते हैं, किसी भी $0 \leq c \leq C$ के लिए: $X^{-1/2}(X-Y)X^{-1/2} \preceq \frac{3(\log C - \log c)}{\pi^2}(\log X - \log Y) + \left(\frac{12cd}{\pi^2\lambda_{\min}(X)^2} + \frac{12C^{-1}d}{\pi^2}\right)\text{Tr}(X-Y) \cdot I$

महत्व:

• जब मैट्रिक्स क्रमविनिमेय हों, तो लघुगणकीय स्केलिंग का उपयोग करके तंग सीमा प्राप्त की जा सकती है
• गैर-क्रमविनिमेय स्थिति में, दूसरा पद "गैर-क्रमविनिमेय लागत" को मापता है, $\log d$ कारक प्रस्तुत करता है
• मापदंडों को सावधानीपूर्वक चुनकर, लागत को $\log d$ में नियंत्रित किया जाता है

2. द्वितीय-क्रम पद नियंत्रण (Lemma 3.3)

भारित एल्गोरिदम के लिए, $S_T = \sum_{t=0}^{T-1} V_t^{-1}(V_t^2 - \beta V_{t-1}^2)V_t^{-1}$ को परिभाषित करें, तब: $\sum_{t=0}^{T-1} \|V_t^{-1}g_t\|_H^2 \leq \text{Tr}(H) \|S_T\|_{\text{op}}$

और स्थिरांक $C_1, C_2$ मौजूद हैं जैसे: $\|S_T\|_{\text{op}} \leq C_1\left(1 + \log\left(1 + \frac{d}{\epsilon}\sum_{t=0}^{T-1}\|g_t\|_2^2 + d^2(1-\beta)T\right)\right)\left(\frac{(1-\beta)T}{\beta} + \log\|V_{T-1}^2/\epsilon\|_{\text{op}}\right) + C_2$

विशेष स्थिति: जब $\mathcal{H}$ क्रमविनिमेय हो (जैसे विकर्ण मैट्रिक्स), तो सुधार होता है $\|S_T\|_{\text{op}} \leq (1-\beta)T + \log\|V_{T-1}^2/\epsilon\|_{\text{op}}$।

3. अनुकूली ढाल विचरण (Definition 4.1)

$\sigma_{\mathcal{H}}(\{f_t\})^2 := \min_{H \in \mathcal{H}, \text{Tr}(H) \leq 1} \sup_{t, x} \mathbb{E}[\|\nabla f_t(x) - \mathbb{E}[\nabla f_t(x)]\|_{H^{-1}}^2]$

संबंध (Proposition 4.2): $\sigma_{\|\cdot\|_{\mathcal{H},*}}(\{f_t\})^2 \leq \sigma_{\mathcal{H}}(\{f_t\})^2 \leq d \cdot \sigma_{\|\cdot\|_{\mathcal{H},*}}(\{f_t\})^2$

अंतर्ज्ञान: अनुकूली विचरण सभी पूर्वशर्त-प्रेरित ज्यामितियों में शोर को समान रूप से नियंत्रित करने की आवश्यकता है, जो केवल एक निश्चित मानदंड में नियंत्रण से अधिक मजबूत है।

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

नोट: यह पेपर शुद्ध सैद्धांतिक कार्य है, इसमें प्रायोगिक भाग नहीं है। सभी परिणाम सैद्धांतिक अभिसरण दर और निचली सीमा प्रमाण हैं।

सैद्धांतिक विश्लेषण सेटअप

मान्यता शर्तें

1. चिकनाई:
   • मानक चिकनाई: $\|\nabla f(x) - \nabla f(y)\|_{\mathcal{H},*} \leq L_{\|\cdot\|_{\mathcal{H}}}(f)\|x-y\|_{\mathcal{H}}$
   • अनुकूली चिकनाई: $\Lambda_{\mathcal{H}}(f) = \min_{H \in \mathcal{H}, \text{Tr}(H)\leq 1} L_{\|\cdot\|_H}(f)$
2. शोर मान्यता (Assumption C.1):
   • $\mathbb{E}[\nabla f_t(x)] = \nabla f(x)$
   • $\Sigma \succeq 0$ मौजूद है जैसे $-\Sigma \preceq \nabla f(x)\nabla f(x)^\top - \nabla f_t(x)\nabla f_t(x)^\top \preceq \Sigma$
3. उत्तलता: कुछ परिणाम (त्वरण) $f$ को उत्तल फ़ंक्शन की आवश्यकता है

विश्लेषण विधि

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

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

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

1. गैर-उत्तल अभिसरण दर (Theorem 3.2)

संचयी प्रकार के अनुकूली अनुकूलकों (AdaGrad वर्ग) के लिए, निर्धारणात्मक गैर-उत्तल फ़ंक्शन पर: $\frac{1}{T}\sum_{t=0}^{T-1} \|\nabla f(x_t)\|_{\mathcal{H},*} \leq \frac{1}{\sqrt{T}}\left(\xi + \sqrt{d}\epsilon^{1/4}\sqrt{\xi}\right)$

जहां: $\xi = \tilde{O}\left(\frac{\Delta_0}{\eta} + \eta \cdot \Lambda_{\mathcal{H}}(f) \log^2 d\right)$

$\eta = \sqrt{\frac{\Delta_0}{\Lambda_{\mathcal{H}}(f)\log^2 d}}$ चुनते समय, $\tilde{O}\left(\frac{\sqrt{\Delta_0 \Lambda_{\mathcal{H}}(f)}\log d}{\sqrt{T}}\right)$ प्राप्त होता है।

मुख्य बिंदु:

• अभिसरण दर अनुकूली चिकनाई $\Lambda_{\mathcal{H}}(f)$ पर निर्भर करती है, मानक चिकनाई पर नहीं
• विकर्ण पूर्वशर्त (जैसे Adam) के लिए कोई $\log d$ कारक नहीं
• सामान्य सुसंरचित पूर्वशर्त $\log d$ कारक प्रस्तुत करते हैं (गैर-क्रमविनिमेय लागत)

2. त्वरित अभिसरण दर (Theorem 4.4)

Nesterov गति के साथ अनुकूली अनुकूलकों के लिए (Algorithm 2), उत्तल फ़ंक्शन पर $\alpha_t = \frac{2}{t+2}$ और $\eta = D$ चुनते समय: $\mathbb{E}[f(\bar{x}_T) - f(x^*)] = \tilde{O}\left(\frac{\Lambda_{\mathcal{H}}(f)D^2\log^2 d}{T^2} + \frac{d\sqrt{\epsilon}D}{T^2} + \frac{\sigma_{\mathcal{H}}D\log d}{\sqrt{T}}\right)$

तुलना:

• अनुकूली चिकनाई के तहत: $O(T^{-2})$ त्वरित दर (निर्धारणात्मक भाग)
• मानक ℓ∞ चिकनाई के तहत: Guzmán & Nemirovski (2015) साबित करते हैं कि कोई भी प्रथम-क्रम विधि केवल $\Omega(T^{-1})$ प्राप्त कर सकती है

महत्व: साबित करता है कि अनुकूली चिकनाई का व्यावहारिक लाभ—त्वरण प्राप्त करने की क्षमता, जबकि मानक चिकनाई नहीं कर सकती।

3. आयाम-स्वतंत्र अभिसरण दर (Theorem 4.6)

NSD (Algorithm 3) के लिए अनुकूली ढाल विचरण $\sigma_{\mathcal{H}}$ के तहत: $\mathbb{E}\left[\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla f(x_t)\|_{\mathcal{H},*}\right] \leq \frac{\Delta_0}{\eta T} + \frac{2\eta}{\alpha}L_{\|\cdot\|_{\mathcal{H}}}(f) + \frac{2\sigma_{\mathcal{H}}}{\alpha T} + 2\sigma_{\mathcal{H}}\sqrt{\alpha}$

इष्टतम विकल्प $\alpha = \frac{\sqrt{\Delta_0 L_{\|\cdot\|_{\mathcal{H}}}(f)}}{\sigma_{\mathcal{H}}\sqrt{T}}$ और $\eta = \frac{\Delta_0^{3/4}}{L_{\|\cdot\|_{\mathcal{H}}}(f)^{1/4}\sigma_{\mathcal{H}}^{1/2}}T^{-3/4}$ के साथ: $\text{दर} = O\left(\frac{(\Delta_0 L_{\|\cdot\|_{\mathcal{H}}}(f))^{1/4}\sqrt{\sigma_{\mathcal{H}}}}{T^{1/4}}\right)$

आयाम-स्वतंत्र निर्भरता: Pethick et al. (2025) के $\tilde{O}(\rho\sqrt{d}/T^{1/4})$ की तुलना में (जहां $\rho = \sup_x \frac{\|x\|_{\mathcal{H},*}}{\|x\|_2}$ $\Theta(\sqrt{d})$ तक पहुंच सकता है), यह परिणाम पूरी तरह से आयाम निर्भरता को समाप्त करता है।

4. आयाम निर्भरता निचली सीमा (Theorem 4.9)

मानक ℓ₁ विचरण मान्यता $\mathbb{E}[\|\nabla f_t(x) - \nabla f(x)\|_1^2] \leq \sigma^2$ के तहत, SignGD (ℓ∞-NSD) के लिए कठिन उदाहरण मौजूद हैं जैसे: $\mathbb{E}\left[\min_{t \in [T]}\|\nabla f(x_t)\|_1\right] = \min\left\{e^{-25-\frac{1}{4}}(dL\Delta_0\sigma^2)^{1/4}T^{-1/2}, e^{-25-\frac{1}{2}}\sigma\right\}$

महत्व:

• त्रुटि $\epsilon < e^{-25-1/2}\sigma$ प्राप्त करने के लिए $T = \Omega(\epsilon^{-2}(dL\Delta_0\sigma^2)^{1/2})$ चरणों की आवश्यकता है
• आयाम निर्भरता $\Omega(d^{1/2})$ मानक विचरण मान्यता के तहत अपरिहार्य है
• Theorem 4.6 की आयाम-स्वतंत्र ऊपरी सीमा के साथ विरोधाभास, अनुकूली विचरण की आवश्यक श्रेष्ठता साबित करता है

मुख्य अंतर्दृष्टि

1. ज्यामितीय पृथक्करण का मात्रात्मकीकरण

दोनों प्रकार की चिकनाई और विचरण के बीच संबंध:

• चिकनाई: $L_{\|\cdot\|_{\mathcal{H}}}(f) \leq \Lambda_{\mathcal{H}}(f) \leq d \cdot L_{\|\cdot\|_{\mathcal{H}}}(f)$
• विचरण: $\sigma_{\|\cdot\|_{\mathcal{H},*}}^2 \leq \sigma_{\mathcal{H}}^2 \leq d \cdot \sigma_{\|\cdot\|_{\mathcal{H},*}}^2$

अंतर अधिकतम आयाम $d$ है, लेकिन कुछ स्थितियों में तंग है (जैसे विकर्ण मैट्रिक्स बनाम पूर्ण मैट्रिक्स)।

2. औसत अप्रभावशीलता (Averaging Ineffectiveness)

गैर-यूक्लिडीय ज्यामिति में, औसत प्रभावी रूप से मानदंड को कम नहीं कर सकता:

• ℓ₂: $\|\frac{1}{n}\sum_{i=1}^n x_i\|_2 = O(1/\sqrt{n})$ (प्रभावी)
• ℓ₁: $\|\frac{1}{n}\sum_{i=1}^n x_i\|_1 = O(\sqrt{d}/\sqrt{n})$ (आयाम निर्भर)

यह समझाता है कि क्यों:

• त्वरण को अधिक मजबूत अनुकूली चिकनाई की आवश्यकता है
• गति मानक विचरण के तहत आयाम निर्भरता को समाप्त नहीं कर सकती

3. गैर-क्रमविनिमेय लागत

सामान्य सुसंरचित पूर्वशर्त (जैसे एकतरफा Shampoo) $\log d$ कारक प्रस्तुत करते हैं, जो निम्न से उत्पन्न होता है:

• मैट्रिक्स गैर-क्रमविनिमेयता सीधे दूरबीन योग को रोकती है
• Lemma 3.4 में गैर-क्रमविनिमेय पद: $\frac{12cd}{\pi^2\lambda_{\min}^2}\text{Tr}(X-Y) \cdot I$
• मापदंडों को सावधानीपूर्वक चुनकर, लागत को $\log d$ में नियंत्रित किया जाता है

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

अनुकूली अनुकूलक

1. मैट्रिक्स पूर्वशर्त: Shampoo (Gupta et al., 2018) और इसके प्रकार (SOAP, PolarGrad, AdaMuon)
2. विकर्ण पूर्वशर्त: AdaGrad (Duchi et al., 2011), Adam (Kingma & Ba, 2014)
3. अभिसरण सिद्धांत:
   • उत्तल स्थिति: Xie et al. (2025b) अनुकूली चिकनाई सिद्धांत स्थापित करते हैं
   • विकर्ण स्थिति: Maladkar et al. (2024), Xie et al. (2025a)
4. विचरण अनुकूलता: Frans et al. (2025) मैट्रिक्स श्वेतकरण दृष्टिकोण इंगित करते हैं

सामान्यीकृत सबसे तीव्र वंश (NSD)

1. अभिसरण विश्लेषण:
   • Cutkosky & Mehta (2020): O(T⁻³·⁵) गैर-उत्तल दर
   • Pethick et al. (2025), Kovalev (2025b): सामान्य मानदंड के तहत विश्लेषण
2. समतुल्यता:
   • Lion = ℓ∞-NSD (Sfyraki & Wang, 2025)
   • Muon = वर्णक्रमीय मानदंड-NSD (Chen et al., 2025)
3. आयाम निर्भरता: Jiang et al. (2025) SignGD के लिए सुधार

त्वरित विधियां

1. दर्पण वंश दृष्टिकोण: Kelner et al. (2014), Allen-Zhu & Orecchia (2014)
2. अनुकूली त्वरण: Cutkosky (2019), Kavis et al. (2019), Joulani et al. (2020) विकर्ण/निर्देशांक अनुकूलता के लिए
3. निचली सीमा: Guzmán & Nemirovski (2015) ℓ∞ चिकनाई के तहत Ω(T⁻¹) निचली सीमा साबित करते हैं

इस पेपर का योगदान तुलना

• बनाम Xie et al. (2025b): गैर-उत्तल + यादृच्छिक सेटिंग तक विस्तार
• बनाम Kovalev (2025a): कमजोर मान्यता (Assumption 4 से बचना), व्यापक पूर्वशर्त
• बनाम Pethick et al. (2025): अनुकूली विचरण के माध्यम से आयाम निर्भरता को समाप्त करना
• बनाम मौजूदा त्वरण विधियां: सामान्य सुसंरचित पूर्वशर्त के तहत पहली बार त्वरण साबित करना

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

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

1. ज्यामितीय द्वैत: अनुकूली अनुकूलक और NSD दोनों गैर-यूक्लिडीय ज्यामिति का उपयोग करते हैं, लेकिन आवश्यक रूप से विभिन्न ज्यामितीय मान्यताओं पर निर्भर करते हैं:
   • अनुकूली अनुकूलक: अनुकूली चिकनाई $\Lambda_{\mathcal{H}}(f)$ की आवश्यकता है, स्वचालित रूप से इष्टतम पूर्वशर्त के अनुकूल हो सकते हैं
   • NSD: केवल मानक चिकनाई $L_{\|\cdot\|_{\mathcal{H}}}(f)$ की आवश्यकता है, लेकिन मानदंड को पहले से निर्दिष्ट करने की आवश्यकता है
2. अनुकूलता का मूल्य: अधिक मजबूत अनुकूली मान्यता व्यावहारिक लाभ लाती है:
   • त्वरण: उत्तल स्थिति में O(T⁻²) बनाम मानक मान्यता के तहत Ω(T⁻¹)
   • आयाम-स्वतंत्र: यादृच्छिक स्थिति में आयाम निर्भरता को समाप्त करना
3. एकीकृत सैद्धांतिक ढांचा: एकतरफा Shampoo सहित व्यापक अनुकूली विधियों के लिए पहली बार गैर-उत्तल अभिसरण सिद्धांत स्थापित करता है, मूल तकनीक गैर-क्रमविनिमेय पूर्वशर्त को संभालने के लिए नई मैट्रिक्स असमानता है।
4. तंगता: निचली सीमा साबित करते हैं कि:
   • मानक विचरण मान्यता के तहत आयाम निर्भरता अपरिहार्य है (Theorem 4.9)
   • अनुकूली विचरण की श्रेष्ठता केवल तकनीकी मान्यता नहीं है, बल्कि आवश्यक अंतर है

सीमाएं

1. सैद्धांतिक कार्य: सैद्धांतिक भविष्यवाणियों को सत्यापित करने के लिए प्रयोग की कमी (जैसे विभिन्न ज्यामितियों के तहत वास्तविक अभिसरण व्यवहार)
2. स्थिरांक कारक:
   • गैर-विकर्ण पूर्वशर्त $\log d$ कारक प्रस्तुत करते हैं (व्यावहार में महत्वहीन हो सकता है)
   • त्वरण एल्गोरिदम को $D = \max_t \|x_t - x^*\|_{\mathcal{H}}$ ज्ञात होने की आवश्यकता है (प्रक्षेपण संस्करण द्वारा कम किया जाता है)
3. मान्यता शर्तें:
   • Assumption C.1 (बिंदुवार सहप्रसरण ऊपरी सीमा) मानक मान्यता से अधिक मजबूत है
   • त्वरण परिणाम उत्तलता और ज्ञात $D$ की आवश्यकता है
4. प्रयोज्यता सीमा:
   • अनुकूली विचरण मान्यता व्यावहार में कैसे सत्यापित करें?
   • कौन सी वास्तविक समस्याएं अनुकूली चिकनाई को संतुष्ट करती हैं?
5. EMA विश्लेषण: EMA प्रकार को $\beta = 1 - \Theta(\frac{\log d}{T})$ चुनने की आवश्यकता है, व्यावहार में अक्सर निश्चित $\beta$ (जैसे 0.9, 0.999) का उपयोग किया जाता है

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

1. प्रायोगिक सत्यापन:
   • वास्तविक गहन शिक्षा कार्यों में अनुकूली चिकनाई मान्यता सत्यापित करना
   • विभिन्न ज्यामितियों के तहत अनुभवजन्य अभिसरण व्यवहार की तुलना करना
2. मान्यता को कमजोर करना:
   • अधिक कमजोर शोर मान्यता की खोज (जैसे केवल अपेक्षा बंधी)
   • गैर-उत्तल स्थिति में त्वरण की संभावना
3. एल्गोरिदम सुधार:
   • पूर्वशर्त संरचना $\mathcal{H}$ को अनुकूली रूप से चुनना
   • अनुकूली चिकनाई के साथ नए अनुकूलन एल्गोरिदम
4. अन्य ज्यामितियां:
   • Bregman विचलन, Riemannian ज्यामिति तक विस्तार
   • अन्य संरचित पूर्वशर्त (जैसे विरल, निम्न-रैंक)
5. निचली सीमा सुधार:
   • अनुकूली चिकनाई के तहत निचली सीमा (वर्तमान में केवल मानक चिकनाई के तहत)
   • गैर-उत्तल स्थिति में अधिक तंग निचली सीमा

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

शक्तियां

1. सैद्धांतिक गहराई:
   • दोनों ज्यामितीय मान्यताओं के बीच मात्रात्मक पृथक्करण का पहली बार व्यवस्थित स्थापन
   • मूल मैट्रिक्स असमानता (Lemma 3.4) में स्वतंत्र मूल्य है, अन्य मैट्रिक्स विश्लेषण समस्याओं पर लागू हो सकता है
   • प्रमाण तकनीक परिष्कृत है, विशेष रूप से गैर-क्रमविनिमेयता को संभालने की विधि
2. एकीकरण:
   • AdaGrad, Adam, Shampoo आदि व्यापक विधियों को कवर करता है
   • तीन संचय विधियों (संचयी, EMA, भारित) की समतुल्यता विश्लेषण स्पष्ट है
   • चिकनाई और विचरण का समानांतर उपचार गहरी संरचना प्रकट करता है
3. पूर्णता:
   • ऊपरी सीमा + निचली सीमा तंगता साबित करते हैं
   • निर्धारणात्मक + यादृच्छिक, उत्तल + गैर-उत्तल पूर्ण कवरेज
   • तकनीकी परिशिष्ट विस्तृत (48 पृष्ठ), पुनरुत्पादनीयता मजबूत है
4. अंतर्दृष्टि:
   • "औसत अप्रभावशीलता" आयाम निर्भरता के मूल को समझाता है
   • द्वैत (सर्वोच्च बनाम न्यूनतम) की ज्यामितीय अंतर्ज्ञा
   • गैर-क्रमविनिमेय लागत का सटीक मात्रात्मकीकरण
5. लेखन गुणवत्ता:
   • संरचना स्पष्ट है, Adam/SignGD उदाहरणों से अवधारणाएं प्रस्तुत करता है
   • चित्र 1 द्वैत को सहज रूप से दिखाता है
   • तकनीकी विवरण और अंतर्ज्ञान अच्छी तरह संतुलित हैं

कमियां

1. व्यावहारिक प्रासंगिकता:
   • सैद्धांतिक भविष्यवाणियों को सत्यापित करने के लिए प्रयोग की कमी
   • वास्तविक समस्याओं में अनुकूली चिकनाई की सार्वभौमिकता अज्ञात है
   • $\log d$ कारक व्यावहार में महत्वपूर्ण है या नहीं?
2. मान्यता शक्ति:
   • Assumption C.1 मानक मान्यता से अधिक मजबूत है (लगभग हर जगह सत्य)
   • त्वरण एल्गोरिदम उत्तलता और ज्ञात $D$ की आवश्यकता है
   • EMA को $\beta = 1 - \Theta(\log d / T)$ की आवश्यकता है, व्यावहार से असंगत
3. तकनीकी सीमाएं:
   • विकर्ण स्थिति बनाम सामान्य स्थिति का अंतर ($\log d$) समाप्त किया जा सकता है?
   • गैर-उत्तल त्वरण की असंभवता साबित नहीं हुई है
   • अनुकूली चिकनाई की निचली सीमा अनुपस्थित है
4. अभिव्यक्ति विवरण:
   • Õ संकेतन कई मापदंडों पर लघुगणकीय निर्भरता छिपाता है (केवल $d$ नहीं)
   • कुछ स्थिरांक ($C_1, C_2$) स्पष्ट नहीं हैं
   • Lemma 3.4 में $c, C$ चयन रणनीति अधिक स्पष्ट हो सकती है
5. संबंधित कार्य:
   • Kovalev & Borodich (2025) समानांतर कार्य से अंतर अधिक विस्तृत हो सकता है
   • शास्त्रीय दर्पण वंश सिद्धांत के साथ संबंध गहरा हो सकता है

प्रभाव

1. सैद्धांतिक योगदान:
   • अनुकूली अनुकूलन सिद्धांत को नया दृष्टिकोण प्रदान करता है (ज्यामितीय मान्यता का पदानुक्रम)
   • मैट्रिक्स असमानता तकनीक संबंधित क्षेत्रों को प्रभावित कर सकती है (जैसे मैट्रिक्स विश्लेषण, क्वांटम सूचना)
   • एकीकृत ढांचा भविष्य विश्लेषण का मानक बन सकता है
2. व्यावहारिक मूल्य:
   • अनुकूलक चयन को निर्देशित करता है: कब अनुकूली विधि बनाम NSD?
   • नए एल्गोरिदम डिजाइन को प्रेरित करता है (जैसे $\mathcal{H}$ को अनुकूली रूप से चुनना)
   • हाइपरपैरामीटर ट्यूनिंग के लिए सैद्धांतिक आधार प्रदान करता है (जैसे $\beta$ चयन)
3. पुनरुत्पादनीयता:
   • शुद्ध सैद्धांतिक कार्य, परिणाम सत्यापन योग्य हैं
   • प्रमाण तकनीक विस्तृत है, अन्य सेटिंग्स तक विस्तारित हो सकती है
   • परिभाषाएं स्पष्ट हैं, बाद के अनुसंधान के लिए उद्धरण सुविधाजनक है
4. सीमाएं:
   • प्रयोग की कमी तत्काल प्रभाव को सीमित करती है
   • मान्यता शर्तों का सत्यापन बाद के कार्य की आवश्यकता है
   • व्यावहार के साथ अंतर को पाटने की आवश्यकता है

प्रयोज्य परिदृश्य

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

संदर्भ (प्रमुख साहित्य का चयन)

1. Xie et al. (2025b): "Structured Preconditioners in Adaptive Optimization: A Unified Analysis" - इस पेपर का उत्तल स्थिति आधार
2. Guzmán & Nemirovski (2015): "On lower complexity bounds for large-scale smooth convex optimization" - ℓ∞ चिकनाई के तहत निचली सीमा
3. Pethick et al. (2025): "Training deep learning models with norm-constrained lmos" - NSD का नवीनतम विश्लेषण
4. Kovalev (2025a): "SGD with Adaptive Preconditioning: Unified Analysis and Momentum Acceleration" - समानांतर कार्य
5. Bernstein & Newhouse (2024): "Old optimizer, new norm: An anthology" - Adam और NSD की समतुल्यता
6. Gupta et al. (2017): "A unified approach to adaptive regularization" - अनुकूली अनुकूलक ढांचा
7. Lieb (1973): "Convex trace functions and the wigner-yanase-dyson conjecture" - Lemma A.7 की अवतलता आधार

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