रैखिक स्टोकेस्टिक सन्निकटन के लिए सुधारित केंद्रीय सीमा प्रमेय और बूटस्ट्रैप सन्निकटन

मूल जानकारी

• पेपर ID: 2510.12375
• शीर्षक: रैखिक स्टोकेस्टिक सन्निकटन के लिए सुधारित केंद्रीय सीमा प्रमेय और बूटस्ट्रैप सन्निकटन
• लेखक: Bogdan Butyrin, Eric Moulines, Alexey Naumov, Sergey Samsonov, Qi-Man Shao, Zhuo-Song Zhang
• वर्गीकरण: stat.ML cs.LG math.OC math.PR math.ST stat.TH
• प्रकाशन समय: 15 अक्टूबर, 2025 (arXiv प्रीप्रिंट)
• पेपर लिंक: https://arxiv.org/abs/2510.12375

सारांश

यह पेपर रैखिक स्टोकेस्टिक सन्निकटन (LSA) एल्गोरिथ्म में Polyak-Ruppert औसत पुनरावृत्तियों के बहुभिन्न सामान्य सन्निकटन के लिए Berry-Esseen सीमा में सुधार करता है। अनुसंधान Polyak-Juditsky केंद्रीय सीमा प्रमेय द्वारा पूर्वानुमानित सहप्रसरण मैट्रिक्स के गाऊसी वितरण सामान्य सन्निकटन पर विचार करता है, उत्तल दूरी के अर्थ में $n^{-1/3}$ क्रम की अभिसरण दर स्थापित करता है, जहां $n$ एल्गोरिथ्म द्वारा उपयोग किए गए नमूनों की संख्या है। साथ ही, गुणक बूटस्ट्रैप प्रक्रिया की गैर-स्पर्शोन्मुख प्रभावशीलता को औसत LSA अनुमानक के पुनः-मापित त्रुटि वितरण सन्निकटन के लिए सिद्ध किया गया है, $1/\sqrt{n}$ क्रम की सन्निकटन दर स्थापित की गई है, जो Samsonov et al. (2024) के पूर्व परिणामों में महत्वपूर्ण सुधार है।

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

समस्या की पृष्ठभूमि

रैखिक स्टोकेस्टिक सन्निकटन (LSA) एल्गोरिथ्म सांख्यिकी और मशीन लर्निंग में एक मौलिक विधि है, जिसका उपयोग रैखिक समीकरण $\bar{A}\theta^* = \bar{b}$ के अद्वितीय समाधान का सन्निकटन करने के लिए किया जाता है, जहां $\bar{A} \in \mathbb{R}^{d \times d}$ एक गैर-अपक्षयी मैट्रिक्स है। यह एल्गोरिथ्म प्रेक्षण अनुक्रम $\{(A(Z_k), b(Z_k))\}_{k \in \mathbb{N}}$ के आधार पर पुनरावृत्तिमूलक अद्यतन करता है।

मुख्य चुनौतियां

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

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

• LSA एल्गोरिथ्म में केंद्रीय सीमा प्रमेय की अभिसरण दर विश्लेषण में सुधार
• अधिक सटीक बूटस्ट्रैप आत्मविश्वास अंतराल निर्माण विधियों का विकास
• सुदृढ़ीकरण शिक्षा में समय-अंतर (TD) शिक्षा जैसे अनुप्रयोगों के लिए सैद्धांतिक समर्थन प्रदान करना

मुख्य योगदान

1. सुधारित आघूर्ण सीमा: $\sqrt{n}(\bar{\theta}_n - \theta^*)$ की उच्च-क्रम आघूर्ण सीमा स्थापित की गई, $p \geq 2$ के लिए: $E^{1/p}[\|\bar{\theta}_n - \theta^*\|^p] \lesssim \frac{\sqrt{p}\sqrt{\text{Tr}\Sigma_\infty}}{\sqrt{n}} + \frac{p^{3/2}}{n^{5/6}}$
2. Berry-Esseen सीमा में सुधार: उत्तल दूरी के अर्थ में $n^{-1/3}$ क्रम की सामान्य सन्निकटन दर स्थापित की गई, जो पूर्व $n^{-1/4}$ परिणाम में सुधार है
3. गुणक बूटस्ट्रैप की गैर-स्पर्शोन्मुख विश्लेषण: बूटस्ट्रैप प्रक्रिया की प्रभावशीलता सिद्ध की गई, सन्निकटन दर $n^{-1/2}$ तक पहुंचती है, जो मौजूदा परिणामों से काफी बेहतर है
4. तकनीकी नवाचार: $\Sigma_\infty$ के बजाय उपयुक्त सहप्रसरण मैट्रिक्स $\Sigma_n$ का चयन करके सन्निकटन, सीधे गाऊसी तुलना चरण से बचा गया

विधि विवरण

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

LSA पुनरावृत्ति पर विचार करें: $\theta_k = \theta_{k-1} - \alpha_k(A(Z_k)\theta_{k-1} - b(Z_k)), \quad k \geq 1$$\bar{\theta}_n = n^{-1}\sum_{k=0}^{n-1}\theta_k, \quad n \geq 1$

लक्ष्य $\sqrt{n}(\bar{\theta}_n - \theta^*)$ के वितरण सन्निकटन गुणों का विश्लेषण करना है।

मुख्य तकनीकी ढांचा

1. त्रुटि अपघटन तकनीक

LSA त्रुटि को क्षणिक और उतार-चढ़ाव पदों में अपघटित करें: $\theta_k - \theta^* = \tilde{\theta}_k^{(tr)} + \tilde{\theta}_k^{(fl)}$ जहां:

• $\tilde{\theta}_k^{(tr)} = \Gamma_{1:k}(\theta_0 - \theta^*)$ (क्षणिक पद)
• $\tilde{\theta}_k^{(fl)} = -\sum_{\ell=1}^k \alpha_\ell \Gamma_{\ell+1:k}\varepsilon_\ell$ (उतार-चढ़ाव पद)

2. विक्षोभ विस्तार विधि

उतार-चढ़ाव पद को आगे अपघटित करें: $\tilde{\theta}_k^{(fl)} = J_k^{(0)} + H_k^{(0)}$ जहां $J_k^{(0)}$ रैखिक प्रमुख पद है, $H_k^{(0)}$ उच्च-क्रम शेष पद है।

3. यादृच्छिकीकृत सांद्रता असमानता

Shao-Zhang ढांचा लागू करें, सांख्यिकीय मात्रा को इस प्रकार व्यक्त करें: $\sqrt{n}\Sigma_n^{-1/2}(\bar{\theta}_n - \theta^*) = W + D$ जहां $W$ रैखिक सांख्यिकीय है, $D$ गैर-रैखिक शेष पद है।

चरण आकार चयन रणनीति

बहुपद क्षय चरण अपनाएं: $\alpha_k = \frac{c_0}{(k + k_0)^\gamma}, \quad \gamma \in (1/2, 1)$

मुख्य खोज: इष्टतम अभिसरण दर $\gamma = 2/3$ पर प्राप्त होती है।

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

सैद्धांतिक सत्यापन ढांचा

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

1. धारणा शर्तें:
   • A1: स्वतंत्र समान रूप से वितरित प्रेक्षण अनुक्रम
   • A2: Hurwitz मैट्रिक्स स्थिति और सीमित शोर
   • A3: चरण आकार शर्तें
   • A4-A5: नमूना आकार और तकनीकी शर्तें
2. अनुप्रयोग परिदृश्य: समय-अंतर (TD) शिक्षा एल्गोरिथ्म एक महत्वपूर्ण विशेष मामले के रूप में

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

• उत्तल दूरी: $\rho_{Conv}(\mu, \nu) = \sup_{B \in Conv(\mathbb{R}^d)}|\mu(B) - \nu(B)|$
• अभिसरण दर: $n$ की घातों के संदर्भ में व्यक्त सन्निकटन सटीकता

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

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

प्रमेय 1: आघूर्ण सीमा

उपयुक्त धारणाओं के तहत, $p \geq 2$ के लिए: $E^{1/p}[\|\bar{\theta}_n - \theta^*\|^p] \leq \frac{C_{1,1}\sqrt{p}\sqrt{\text{Tr}\Sigma_n}}{\sqrt{n}} + \Delta^{(fl)}(n,p,\gamma) + \frac{C_{1,5}\|\theta_0 - \theta^*\|}{n}$

प्रमेय 2: गाऊसी सन्निकटन

$\rho_{Conv}(\sqrt{n}(\bar{\theta}_n - \theta^*), \Sigma_n^{1/2}\eta) \leq \frac{C_{2,1}}{\sqrt{n}} + \frac{C_{2,2}}{n^{\gamma/2}} + C_{2,3}\phi_n + \frac{C_{2,4}\|\theta_0 - \theta^*\|}{n}$

प्रमेय 3: स्पर्शोन्मुख सन्निकटन

$\rho_{Conv}(\sqrt{n}(\bar{\theta}_n - \theta^*), \Sigma_\infty^{1/2}\eta) \leq \frac{C_{2,1}}{\sqrt{n}} + \frac{C_{2,2}}{n^{\gamma/2}} + C_{2,3}\phi_n + \frac{C_{2,4}\|\theta_0 - \theta^*\|}{n} + \frac{C_3}{n^{1-\gamma}}$

प्रमेय 4: बूटस्ट्रैप सन्निकटन

$1-1/n$ की संभावना के साथ: $\sup_{B \in Conv(\mathbb{R}^d)}|P^b(\sqrt{n}(\bar{\theta}_n^b - \bar{\theta}_n) \in B) - P(\sqrt{n}(\bar{\theta}_n - \theta^*) \in B)| \leq \frac{C_4\|\theta_0 - \theta^*\| + \Delta_{4,1}}{\sqrt{n}} + \frac{\Delta_{4,2}}{n^{\gamma/2}} + \Delta_{4,3}\phi_n + \frac{\Delta_{4,4}}{n}$

अभिसरण दर तुलना

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

LSA सिद्धांत विकास

• स्पर्शोन्मुख सिद्धांत: Polyak & Juditsky (1992) ने मौलिक स्पर्शोन्मुख सामान्यता स्थापित की
• गैर-स्पर्शोन्मुख विश्लेषण: Durmus et al. (2021, 2025) आदि ने परिमित नमूना सीमा प्रदान की
• सामान्य सन्निकटन: Anastasiou et al. (2019) ने Stein विधि का उपयोग किया

बूटस्ट्रैप विधियां

• शास्त्रीय बूटस्ट्रैप: Efron (1992) का अग्रणी कार्य
• गुणक बूटस्ट्रैप: Fang et al. (2018) SGD के लिए ऑनलाइन बूटस्ट्रैप
• सैद्धांतिक विश्लेषण: Chernozhukov et al. (2013, 2017) का उच्च-आयामी सिद्धांत

तकनीकी उपकरण

• यादृच्छिक मैट्रिक्स उत्पाद: Huang et al. (2021) की सांद्रता असमानता
• गैर-रैखिक सांख्यिकी: Shao & Zhang (2022) की यादृच्छिकीकृत सांद्रता विधि

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

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

1. इष्टतम अभिसरण दर: उत्तल दूरी में $n^{-1/3}$ की Berry-Esseen सीमा प्राप्त करता है, जो LSA सेटिंग में इष्टतम है
2. बूटस्ट्रैप सुधार: बूटस्ट्रैप सन्निकटन दर $n^{-1/2}$ तक पहुंचती है, मौजूदा $n^{-1/4}$ परिणाम से काफी बेहतर है
3. तकनीकी सफलता: $\Sigma_\infty$ के बजाय $\Sigma_n$ को सन्निकटन सहप्रसरण के रूप में चुनकर, तकनीकी बाधाओं से बचा गया

सीमाएं

1. स्वतंत्रता धारणा: केवल i.i.d. शोर पर विचार करता है, Markov शोर मामला भविष्य के कार्य के लिए छोड़ा गया है
2. चरण आकार बाधा: विशिष्ट रूप के बहुपद क्षय चरण की आवश्यकता है
3. आयाम निर्भरता: स्थिरांक में आयाम निर्भरता शामिल है, उच्च-आयामी मामलों में बड़ा हो सकता है

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

1. Markov विस्तार: परिणामों को Markov शोर सेटिंग तक सामान्यीकृत करना
2. निचली सीमा मिलान: $\gamma \in (1/2, 2/3)$ अंतराल में मिलान करने वाली निचली सीमा स्थापित करना
3. व्यावहारिक अनुप्रयोग: विशिष्ट सुदृढ़ीकरण शिक्षा और अनुकूलन समस्याओं में सैद्धांतिक भविष्यवाणियों को सत्यापित करना

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

लाभ

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

कमियां

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

प्रभाव

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

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

• सुदृढ़ीकरण शिक्षा में नीति मूल्यांकन (TD शिक्षा)
• ऑनलाइन उत्तल अनुकूलन एल्गोरिथ्म विश्लेषण
• सटीक आत्मविश्वास अंतराल की आवश्यकता वाली सांख्यिकीय अनुमान समस्याएं
• बड़े पैमाने पर मशीन लर्निंग में सैद्धांतिक विश्लेषण

संदर्भ

1. Polyak, B. T., & Juditsky, A. B. (1992). Acceleration of stochastic approximation by averaging. SIAM journal on control and optimization.
2. Shao, Q. M., & Zhang, Z. S. (2022). Berry–Esseen bounds for multivariate nonlinear statistics with applications to M-estimators and stochastic gradient descent algorithms. Bernoulli.
3. Fang, Y., Xu, J., & Yang, L. (2018). Online bootstrap confidence intervals for the stochastic gradient descent estimator. Journal of Machine Learning Research.
4. Durmus, A., Moulines, E., Naumov, A., & Samsonov, S. (2025). Finite-time high-probability bounds for Polyak–Ruppert averaged iterates of linear stochastic approximation. Mathematics of Operations Research.