রৈখিক স্টোকাস্টিক অ্যাপ্রক্সিমেশনের জন্য উন্নত কেন্দ্রীয় সীমা উপপাদ্য এবং বুটস্ট্র্যাপ অ্যাপ্রক্সিমেশন

মৌলিক তথ্য

• পেপার আইডি: 2510.12375
• শিরোনাম: রৈখিক স্টোকাস্টিক অ্যাপ্রক্সিমেশনের জন্য উন্নত কেন্দ্রীয় সীমা উপপাদ্য এবং বুটস্ট্র্যাপ অ্যাপ্রক্সিমেশন
• লেখক: বোগদান বুটিরিন, এরিক মাউলিনেস, অ্যালেক্সি নাউমভ, সার্গে সামসোনভ, কি-ম্যান শাও, ঝুও-সং ঝাং
• শ্রেণীবিভাগ: stat.ML cs.LG math.OC math.PR math.ST stat.TH
• প্রকাশনার সময়: অক্টোবর ১৫, ২০২৫ (arXiv প্রিপ্রিন্ট)
• পেপার লিঙ্ক: https://arxiv.org/abs/2510.12375

সারসংক্ষেপ

এই পেপারটি রৈখিক স্টোকাস্টিক অ্যাপ্রক্সিমেশন (এলএসএ) অ্যালগরিদমে পলিয়াক-রুপার্ট গড়কৃত পুনরাবৃত্তির বহুমাত্রিক সাধারণ বিতরণ অ্যাপ্রক্সিমেশনের বেরি-এসিন সীমানা উন্নত করে। গবেষণা পলিয়াক-জুডিটস্কি কেন্দ্রীয় সীমা উপপাদ্য দ্বারা পূর্বাভাসিত সহভেদ ম্যাট্রিক্সের গাউসীয় বিতরণ সাধারণ অ্যাপ্রক্সিমেশন বিবেচনা করে, উত্তল দূরত্ব অর্থে $n^{-1/3}$ ক্রমের সংগ্রহ হার প্রতিষ্ঠা করে, যেখানে $n$ হল অ্যালগরিদম দ্বারা ব্যবহৃত নমুনা সংখ্যা। একই সাথে গুণক বুটস্ট্র্যাপ পদ্ধতির গড় এলএসএ অনুমানকারীর পুনর্স্কেল করা ত্রুটি বিতরণ অ্যাপ্রক্সিমেশনের অ-অসীম কার্যকারিতা প্রমাণ করে, $1/\sqrt{n}$ ক্রমের অ্যাপ্রক্সিমেশন হার প্রতিষ্ঠা করে, যা সামসোনভ এবং অন্যদের (২০২৪) পূর্ববর্তী ফলাফলকে উল্লেখযোগ্যভাবে উন্নত করে।

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

সমস্যার পটভূমি

রৈখিক স্টোকাস্টিক অ্যাপ্রক্সিমেশন (এলএসএ) অ্যালগরিদম পরিসংখ্যান এবং মেশিন লার্নিংয়ে একটি মৌলিক পদ্ধতি, যা রৈখিক সমীকরণ $\bar{A}\theta^* = \bar{b}$ এর অনন্য সমাধান অ্যাপ্রক্সিমেট করতে ব্যবহৃত হয়, যেখানে $\bar{A} \in \mathbb{R}^{d \times d}$ একটি অ-অবক্ষয়ী ম্যাট্রিক্স। অ্যালগরিদম পর্যবেক্ষণ ক্রম $\{(A(Z_k), b(Z_k))\}_{k \in \mathbb{N}}$ এর উপর ভিত্তি করে পুনরাবৃত্তিমূলক আপডেট সম্পাদন করে।

মূল চ্যালেঞ্জ

১. বিতরণ অ্যাপ্রক্সিমেশন নির্ভুলতা: বিদ্যমান সাধারণ অ্যাপ্রক্সিমেশন ফলাফলের সংগ্রহ হার ধীর, যা ব্যবহারিক প্রয়োগে আত্মবিশ্বাস ব্যবধান নির্মাণের নির্ভুলতা সীমাবদ্ধ করে २. সহভেদ ম্যাট্রিক্স অনুমান: অসীম সহভেদ ম্যাট্রিক্স $\Sigma_\infty$ ব্যবহারিকভাবে অজানা, কার্যকর অনুমান এবং অ্যাপ্রক্সিমেশন পদ্ধতির প্রয়োজন ३. বুটস্ট্র্যাপ কার্যকারিতা: ঐতিহ্যবাহী বুটস্ট্র্যাপ পদ্ধতি অনলাইন শিক্ষা অ্যালগরিদমে তাত্ত্বিক এবং ব্যবহারিক চ্যালেঞ্জের সম্মুখীন হয়

গবেষণা প্রেরণা

• এলএসএ অ্যালগরিদমে কেন্দ্রীয় সীমা উপপাদ্যের সংগ্রহ হার বিশ্লেষণ উন্নত করা
• আরও নির্ভুল বুটস্ট্র্যাপ আত্মবিশ্বাস ব্যবধান নির্মাণ পদ্ধতি বিকাশ করা
• শক্তিশালী শিক্ষায় সময়গত পার্থক্য (টিডি) শিক্ষা ইত্যাদি প্রয়োগের জন্য তাত্ত্বিক সমর্থন প্রদান করা

মূল অবদান

१. উন্নত মুহূর্ত সীমানা: $\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}}$

२. বেরি-এসিন সীমানার উন্নতি: উত্তল দূরত্ব অর্থে $n^{-1/3}$ ক্রমের সাধারণ অ্যাপ্রক্সিমেশন হার প্রতিষ্ঠা করে, পূর্ববর্তী $n^{-1/4}$ ফলাফল উন্নত করে

३. গুণক বুটস্ট্র্যাপের অ-অসীম বিশ্লেষণ: বুটস্ট্র্যাপ পদ্ধতির কার্যকারিতা প্রমাণ করে, অ্যাপ্রক্সিমেশন হার $n^{-1/2}$ এ পৌঁছায়, বিদ্যমান ফলাফলের চেয়ে উল্লেখযোগ্যভাবে উন্নত

४. প্রযুক্তিগত উদ্ভাবন: $\Sigma_\infty$ এর পরিবর্তে উপযুক্ত সহভেদ ম্যাট্রিক্স $\Sigma_n$ নির্বাচনের মাধ্যমে, সরাসরি গাউসীয় তুলনা পদক্ষেপ এড়ায়

পদ্ধতি বিস্তারিত

কাজের সংজ্ঞা

এলএসএ পুনরাবৃত্তি বিবেচনা করুন: $\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^*)$ এর বিতরণ অ্যাপ্রক্সিমেশন বৈশিষ্ট্য বিশ্লেষণ করা।

মূল প্রযুক্তিগত কাঠামো

१. ত্রুটি বিয়োজন কৌশল

এলএসএ ত্রুটিকে ক্ষণস্থায়ী এবং ওঠানামা পদে বিয়োজিত করুন: $\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$ (ওঠানামা পদ)

२. বিঘ্নকারী সম্প্রসারণ পদ্ধতি

ওঠানামা পদকে আরও বিয়োজিত করুন: $\tilde{\theta}_k^{(fl)} = J_k^{(0)} + H_k^{(0)}$ যেখানে $J_k^{(0)}$ রৈখিক প্রধান পদ, $H_k^{(0)}$ উচ্চ-ক্রম অবশিষ্ট পদ।

३. স্টোকাস্টিক ঘনীভবন অসমতা

শাও-ঝাং কাঠামো প্রয়োগ করুন, পরিসংখ্যানকে প্রকাশ করুন: $\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$ এ অর্জিত হয়।

পরীক্ষামূলক সেটআপ

তাত্ত্বিক যাচাইকরণ কাঠামো

পেপারটি প্রধানত তাত্ত্বিক বিশ্লেষণ, নিম্নলিখিত উপায়ে ফলাফল যাচাই করে:

१. অনুমান শর্ত:

• A1: স্বাধীন সমানভাবে বিতরণকৃত পর্যবেক্ষণ ক্রম
• A2: হার্উইটজ ম্যাট্রিক্স শর্ত এবং সীমাবদ্ধ শব্দ
• A3: পদক্ষেপ আকার শর্ত
• A4-A5: নমুনা আকার এবং প্রযুক্তিগত শর্ত

२. প্রয়োগের দৃশ্য: সময়গত পার্থক্য (টিডি) শিক্ষা অ্যালগরিদম গুরুত্বপূর্ণ বিশেষ ক্ষেত্র হিসাবে

মূল্যায়ন মেট্রিক্স

• উত্তল দূরত্ব: $\rho_{Conv}(\mu, \nu) = \sup_{B \in Conv(\mathbb{R}^d)}|\mu(B) - \nu(B)|$
• সংগ্রহ হার: $n$ এর শক্তি দ্বারা প্রকাশিত অ্যাপ্রক্সিমেশন নির্ভুলতা

পরীক্ষামূলক ফলাফল

প্রধান তাত্ত্বিক ফলাফল

উপপাদ্য १: মুহূর্ত সীমানা

উপযুক্ত অনুমানের অধীনে, $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}$

উপপাদ্য २: গাউসীয় অ্যাপ্রক্সিমেশন

$\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}$

উপপাদ্য ३: অসীম অ্যাপ্রক্সিমেশন

$\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}}$

উপপাদ্য ४: বুটস্ট্র্যাপ অ্যাপ্রক্সিমেশন

$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}$

সংগ্রহ হার তুলনা

সম্পর্কিত কাজ

এলএসএ তাত্ত্বিক উন্নয়ন

• অসীম তত্ত্ব: পলিয়াক এবং জুডিটস্কি (१९९२) মৌলিক অসীম সাধারণতা প্রতিষ্ঠা করে
• অ-অসীম বিশ্লেষণ: ডুরমাস এবং অন্যরা (२०२१, २०२५) সীমিত নমুনা সীমানা প্রদান করে
• সাধারণ অ্যাপ্রক্সিমেশন: অ্যানাস্তাসিউ এবং অন্যরা (२०१९) স্টেইন পদ্ধতি ব্যবহার করে

বুটস্ট্র্যাপ পদ্ধতি

• ক্লাসিক্যাল বুটস্ট্র্যাপ: এফ্রন (१९९२) এর যুগান্তকারী কাজ
• গুণক বুটস্ট্র্যাপ: ফ্যাং এবং অন্যরা (२०१८) এসজিডির জন্য অনলাইন বুটস্ট্র্যাপ
• তাত্ত্বিক বিশ্লেষণ: চার্নোজুকভ এবং অন্যরা (२०१३, २०१७) উচ্চ-মাত্রিক তত্ত্ব

প্রযুক্তিগত সরঞ্জাম

• স্টোকাস্টিক ম্যাট্রিক্স পণ্য: হুয়াং এবং অন্যরা (२०२१) এর ঘনীভবন অসমতা
• অ-রৈখিক পরিসংখ্যান: শাও এবং ঝাং (२०२२) এর স্টোকাস্টিক ঘনীভবন পদ্ধতি

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

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

१. সর্বোত্তম সংগ্রহ হার: উত্তল দূরত্বে $n^{-1/3}$ এর বেরি-এসিন সীমানা অর্জন করে, এটি এলএসএ সেটিংয়ে সর্বোত্তম २. বুটস্ট্র্যাপ উন্নতি: বুটস্ট্র্যাপ অ্যাপ্রক্সিমেশন হার $n^{-1/2}$ এ পৌঁছায়, বিদ্যমান $n^{-1/4}$ ফলাফলের চেয়ে উল্লেখযোগ্যভাবে উন্নত ३. প্রযুক্তিগত অগ্রগতি: $\Sigma_\infty$ এর পরিবর্তে $\Sigma_n$ নির্বাচনের মাধ্যমে, প্রযুক্তিগত বাধা এড়ায়

সীমাবদ্ধতা

१. স্বাধীনতা অনুমান: শুধুমাত্র i.i.d. শব্দ বিবেচনা করে, মার্কভ শব্দ ক্ষেত্রে ভবিষ্যত কাজের জন্য রেখে যায় २. পদক্ষেপ আকার সীমাবদ্ধতা: নির্দিষ্ট ফর্মের বহুপদী ক্ষয় পদক্ষেপের প্রয়োজন ३. মাত্রা নির্ভরতা: ধ্রুবকে মাত্রা নির্ভরতা অন্তর্ভুক্ত, উচ্চ-মাত্রিক ক্ষেত্রে সম্ভবত বৃহত্তর

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

१. মার্কভ সম্প্রসারণ: ফলাফলকে মার্কভ শব্দ সেটিংয়ে সাধারণীকরণ করা २. নিম্ন সীমানা মিলান: $\gamma \in (1/2, 2/3)$ ব্যবধানে মিলানো নিম্ন সীমানা প্রতিষ্ঠা করা ३. ব্যবহারিক প্রয়োগ: নির্দিষ্ট শক্তিশালী শিক্ষা এবং অপ্টিমাইজেশন সমস্যায় তাত্ত্বিক পূর্বাভাস যাচাই করা

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

সুবিধা

१. তাত্ত্বিক গভীরতা: এলএসএ ক্ষেত্রে সবচেয়ে নির্ভুল সংগ্রহ হার বিশ্লেষণ প্রদান করে, উচ্চ প্রযুক্তিগত কঠিনতা २. পদ্ধতি উদ্ভাবন: অ্যাপ্রক্সিমেশন সহভেদ ম্যাট্রিক্স নির্বাচনে চতুরতার সাথে, বিদ্যমান পদ্ধতির সীমাবদ্ধতা অতিক্রম করে ३. ফলাফল সর্বোত্তমতা: একাধিক ফলাফল তাত্ত্বিক সর্বোত্তম সীমানা অর্জন বা কাছাকাছি ४. প্রমাণ কৌশল: একাধিক উন্নত সম্ভাব্যতা সরঞ্জাম একত্রিত, প্রযুক্তিগত পথ স্পষ্ট

অপূর্ণতা

१. পরীক্ষামূলক যাচাইকরণ: বিশুদ্ধ তাত্ত্বিক পেপার হিসাবে, সংখ্যাগত পরীক্ষা তাত্ত্বিক পূর্বাভাস যাচাই করতে অনুপস্থিত २. ব্যবহারিকতা: ধ্রুবক জটিল নির্ভরতা, ব্যবহারিক প্রয়োগে কর্মক্ষমতা আরও গবেষণা প্রয়োজন ३. প্রযোজ্য পরিসীমা: শক্তিশালী অনুমান শর্ত, বাস্তব সমস্যায় প্রযোজ্যতা সীমিত

প্রভাব

१. একাডেমিক মূল্য: স্টোকাস্টিক অ্যাপ্রক্সিমেশন তত্ত্বে গুরুত্বপূর্ণ অগ্রগতি প্রদান করে, ব্যাপকভাবে উদ্ধৃত হওয়ার প্রত্যাশা २. প্রয়োগ সম্ভাবনা: শক্তিশালী শিক্ষা, অনলাইন অপ্টিমাইজেশন ইত্যাদি ক্ষেত্রে তাত্ত্বিক ভিত্তি প্রদান করে ३. পদ্ধতিগত অবদান: প্রযুক্তিগত পদ্ধতি অন্যান্য অ-রৈখিক পরিসংখ্যান সমস্যার গবেষণা অনুপ্রাণিত করতে পারে

প্রযোজ্য দৃশ্য

• শক্তিশালী শিক্ষায় নীতি মূল্যায়ন (টিডি শিক্ষা)
• অনলাইন উত্তল অপ্টিমাইজেশন অ্যালগরিদম বিশ্লেষণ
• নির্ভুল আত্মবিশ্বাস ব্যবধান প্রয়োজনীয় পরিসংখ্যান অনুমান সমস্যা
• বড় আকারের মেশিন লার্নিংয়ে তাত্ত্বিক বিশ্লেষণ

রেফারেন্স

१. পলিয়াক, বি. টি., এবং জুডিটস্কি, এ. বি. (१९९२)। স্টোকাস্টিক অ্যাপ্রক্সিমেশনের ত্বরণ গড়ের মাধ্যমে। এসআইএএম জার্নাল অন কন্ট্রোল এবং অপ্টিমাইজেশন। २. শাও, কিউ. এম., এবং ঝাং, জেড. এস. (२०२२)। বহুমাত্রিক অ-রৈখিক পরিসংখ্যানের জন্য বেরি-এসিন সীমানা এম-অনুমানকারী এবং স্টোকাস্টিক গ্রেডিয়েন্ট ডিসেন্ট অ্যালগরিদমের প্রয়োগ সহ। বার্নুলি। ३. ফ্যাং, ওয়াই., জু, জে., এবং ইয়াং, এল. (२०१८)। স্টোকাস্টিক গ্রেডিয়েন্ট ডিসেন্ট অনুমানকারীর জন্য অনলাইন বুটস্ট্র্যাপ আত্মবিশ্বাস ব্যবধান। জার্নাল অফ মেশিন লার্নিং রিসার্চ। ४. ডুরমাস, এ., মাউলিনেস, ই., নাউমভ, এ., এবং সামসোনভ, এস. (२०२५)। রৈখিক স্টোকাস্টিক অ্যাপ্রক্সিমেশনের পলিয়াক-রুপার্ট গড়কৃত পুনরাবৃত্তির জন্য সীমিত-সময় উচ্চ-সম্ভাবনা সীমানা। অপারেশন গবেষণার গণিত।