2025-11-22T18:28:15.174123

Federated Dropout: Convergence Analysis and Resource Allocation

Xie, Wen, Liu et al.
Federated Dropout is an efficient technique to overcome both communication and computation bottlenecks for deploying federated learning at the network edge. In each training round, an edge device only needs to update and transmit a sub-model, which is generated by the typical method of dropout in deep learning, and thus effectively reduces the per-round latency. \textcolor{blue}{However, the theoretical convergence analysis for Federated Dropout is still lacking in the literature, particularly regarding the quantitative influence of dropout rate on convergence}. To address this issue, by using the Taylor expansion method, we mathematically show that the gradient variance increases with a scaling factor of $γ/(1-γ)$, with $γ\in [0, θ)$ denoting the dropout rate and $θ$ being the maximum dropout rate ensuring the loss function reduction. Based on the above approximation, we provide the convergence analysis for Federated Dropout. Specifically, it is shown that a larger dropout rate of each device leads to a slower convergence rate. This provides a theoretical foundation for reducing the convergence latency by making a tradeoff between the per-round latency and the overall rounds till convergence. Moreover, a low-complexity algorithm is proposed to jointly optimize the dropout rate and the bandwidth allocation for minimizing the loss function in all rounds under a given per-round latency and limited network resources. Finally, numerical results are provided to verify the effectiveness of the proposed algorithm.
academic

الانقطاع الموحد: تحليل التقارب وتخصيص الموارد

المعلومات الأساسية

  • معرّف الورقة: 2501.00379
  • العنوان: Federated Dropout: Convergence Analysis and Resource Allocation
  • المؤلفون: Sijing Xie, Dingzhu Wen, Xiaonan Liu, Changsheng You, Tharmalingam Ratnarajah, Kaibin Huang
  • التصنيف: cs.LG cs.IT math.IT
  • تاريخ النشر: 31 ديسمبر 2024
  • رابط الورقة: https://arxiv.org/abs/2501.00379

الملخص

الانقطاع الموحد (Federated Dropout) هو تقنية فعالة للتغلب على اختناقات الاتصالات والحسابات عند نشر التعلم الموحد على حافة الشبكة. في كل جولة تدريب، تحتاج أجهزة الحافة فقط إلى تحديث ونقل نموذج فرعي يتم إنشاؤه من خلال طريقة الانقطاع النموذجية في التعلم العميق، مما يقلل بشكل فعال من التأخير في كل جولة. ومع ذلك، لا تزال الأدبيات تفتقر إلى تحليل نظري للتقارب بشأن الانقطاع الموحد، خاصة فيما يتعلق بالتأثير الكمي لمعدل الانقطاع على التقارب. لمعالجة هذه المشكلة، تستخدم هذه الورقة طريقة تمديد تايلور لإثبات رياضياً أن تباين التدرج ينمو بعامل نسبة γ/(1-γ)، حيث γ∈[0,θ) يمثل معدل الانقطاع و θ هو الحد الأقصى لمعدل الانقطاع الذي يضمن تقليل دالة الخسارة. بناءً على هذا التقريب، توفر الورقة تحليل التقارب للانقطاع الموحد، مما يدل على أنه كلما زاد معدل الانقطاع لكل جهاز، كلما كان التقارب أبطأ. يوفر هذا أساساً نظرياً لتقليل تأخير التقارب من خلال المقارنة بين تأخير كل جولة والعدد الإجمالي لجولات التقارب.

خلفية البحث والدافع

خلفية المشكلة

  1. الطلب المتزايد على الذكاء الاصطناعي على الحافة: انفجار البيانات المحمولة يدفع نشر الذكاء الاصطناعي على حافة الشبكة، حيث أصبح التعلم الموحد على الحافة (FEEL) تقنية واعدة
  2. قيود الموارد الحسابية: تواجه أجهزة الحافة قيوداً شديدة على الموارد الحسابية، بينما تتطلب الشبكات العصبية العميقة الحديثة (DNNs) والنماذج اللغوية الكبيرة (LLMs) قوة حسابية هائلة
  3. قيود الطرق الموجودة:
    • تركز الطرق الفعالة من حيث الاتصالات (ضغط التدرج، جدولة الأجهزة، إلخ) بشكل أساسي على اختناق الاتصالات
    • تتطلب طرق قص النموذج تكاليف اتصالات كبيرة في المراحل المبكرة من التدريب، وعادة ما تقلل من قدرة تمثيل النموذج
    • تفتقر إلى تقليل جوهري للتكاليف الحسابية

دافع البحث

  1. الفجوة النظرية: على الرغم من أن إطار FedDrop عملي، إلا أنه يفتقر إلى تحليل نظري صارم للتقارب
  2. متطلبات التحسين: الحاجة إلى إرشادات نظرية لتحسين التصميم المشترك لمعدل الانقطاع وتخصيص الموارد
  3. التطبيقات العملية: توفير أساس نظري وخوارزميات عملية للتعلم الموحد في البيئات محدودة الموارد

المساهمات الأساسية

  1. تحليل النظرية الرياضية للتقارب:
    • إثبات باستخدام تمديد تايلور أن متجه التدرج للشبكة الفرعية هو تقدير محدود التباين لمتجه التدرج الأصلي للشبكة العصبية العميقة
    • إثبات رياضي بأن تباين التدرج يتناسب مع γ/(1-γ)
    • إنشاء علاقة كمية بين معدل الانقطاع وسرعة التقارب
  2. تقليل دالة الخسارة في كل جولة:
    • بناءً على التحليل النظري، توصيف تقليل خسارة التعلم في أي جولة
    • تحت قيود عرض النطاق الترددي للنظام وتأخير إكمال المهمة وميزانية الطاقة للجهاز، تعظيم تقليل خسارة التعلم
  3. خوارزمية التحسين المشترك:
    • اقتراح تصميم مشترك لمعدل الانقطاع التكيفي وتخصيص عرض النطاق الترددي
    • الحصول على حل بصيغة مغلقة من خلال شروط KKT
    • تعقيد الخوارزمية هو فقط O(K²)
  4. تقييم الأداء:
    • إجراء تجارب رقمية في سيناريوهات نقص التجهيز والإفراط في التجهيز
    • التحقق من صحة التحليل النظري

شرح الطريقة

تعريف المهمة

الإدخال: K جهاز حافة، كل جهاز k يحتفظ بمجموعة بيانات محلية Dk الهدف: تقليل دالة الخسارة العامة: F(w)=∑k=1K∣Dk∣∣D∣fk(w^k;Dk)F(w) = \sum_{k=1}^K \frac{|D_k|}{|D|} f_k(\hat{w}_k; D_k) حيث w^k\hat{w}_k هي الشبكة الفرعية المولدة من الانقطاع المقابلة للجهاز k، و fkf_k هي دالة الخسارة المحلية للجهاز k.

معمارية النموذج

1. إطار العمل للانقطاع الموحد

يتضمن إطار FedDrop خمس خطوات:

  1. مرحلة الإنشاء: ينشئ الخادم شبكة فرعية لكل جهاز
  2. مرحلة الدفع: يقوم الجهاز بتنزيل الشبكة الفرعية المقابلة
  3. مرحلة الحساب: يقوم الجهاز بتحديث الشبكة الفرعية بناءً على البيانات المحلية
  4. مرحلة السحب: يقوم الجهاز برفع الشبكة الفرعية المحدثة
  5. مرحلة التجميع: يقوم الخادم بتجميع جميع تحديثات الشبكة الفرعية وتحديث النموذج العام

2. آلية الانقطاع

بالنسبة للجهاز k بمعدل انقطاع γk، يتم تعريف الشبكة الفرعية على النحو التالي: w^k=w∘mk\hat{w}_k = w \circ m_k حيث العنصر j من قناع الانقطاع mk يُعرّف على النحو التالي:

\frac{1}{1-\gamma_k}, & \text{بالاحتمالية} (1-\gamma_k) \\ 0, & \text{بالاحتمالية} \gamma_k \end{cases}$$ #### 3. نموذج التأخير واستهلاك الطاقة إجمالي التأخير في كل جولة: $$T_{k,t} = T^{com,dl}_{k,t} + T^{cmp}_{k,t} + T^{com,ul}_{k,t}$$ إجمالي استهلاك الطاقة: $$E_{k,t} = E^{com,ul}_{k,t} + E^{cmp}_{k,t} + \xi_k$$ ### نقاط الابتكار التقني #### 1. نظرية تحديد تباين التدرج **اللمة 1**: تحت الافتراضات المعطاة، متجه التدرج للشبكة الفرعية هو تقدير محدود التباين: $$E_{m_k^{(t)}}[\hat{g}_k(\hat{w}_k^{(t)})] = \tilde{g}_k(w^{(t)})$$ $$D_{m_k^{(t)}}[\hat{g}_k(\hat{w}_k^{(t)})] \leq (AG)^2 \cdot \frac{\gamma_{k,t}}{1-\gamma_{k,t}}$$ #### 2. تحليل التقارب **النظرية 1**: بالنظر إلى معدل التعلم η = 1/(3√TL)، يتقارب متجه التدرج الأساسي إلى: $$\lim_{T→+∞} \frac{1}{T} \sum_{t=0}^{T-1} \|g(w^{(t)})\|^2 ≤ G_T = 0$$ الاكتشاف الرئيسي: تنخفض سرعة التقارب مع زيادة معدل الانقطاع. #### 3. مشكلة التحسين المشترك $$\min_{\{\gamma_{k,t}, \rho_{k,t}\}} \sum_{k=1}^K \frac{|D_k|}{|D|} \frac{1}{1-\gamma_{k,t}}$$ تحت القيود: - C1: قيد التأخير في كل جولة - C2: قيد استهلاك الطاقة - C3: قيد تخصيص عرض النطاق الترددي - C4: قيد معدل الانقطاع ## إعداد التجارب ### مجموعات البيانات - **CIFAR-100**: للتدريب على LeNet و AlexNet - **توزيع البيانات**: - التوزيع المستقل والموزع بشكل متطابق (IID) - التوزيع غير المستقل والموزع بشكل غير متطابق (Non-IID) باستخدام توزيع Dirichlet(0.1) ### تكوين النموذج 1. **LeNet** (سيناريو نقص التجهيز): - طبقتا التفاف + طبقتا متصلتان بالكامل - حجم نواة الالتفاف: 5×5 - دالة التفعيل: Tanh 2. **AlexNet** (سيناريو الإفراط في التجهيز): - 5 طبقات التفاف + طبقتا متصلتان بالكامل - حجم نواة الالتفاف: 3×3 - دالة التفعيل: ReLU ### مؤشرات التقييم - عدد جولات التقارب - دقة الاختبار - تكاليف الحساب والاتصالات ### الطرق المقارنة 1. **المخطط المقترح**: الحل الأمثل للخوارزمية 1 2. **المخطط الواعي لعرض النطاق الترددي**: تخصيص عشوائي لعرض النطاق الترددي، تحسين معدل الانقطاع 3. **المخطط بدون انقطاع**: معيار مثالي، بدون الأخذ في الاعتبار الانقطاع ## نتائج التجارب ### النتائج الرئيسية #### 1. تأثير معدل الانقطاع على الأداء - **سيناريو نقص التجهيز**: تنخفض دقة الاختبار مع زيادة معدل الانقطاع - **سيناريو الإفراط في التجهيز**: يحقق معدل انقطاع معتدل (0.15) أفضل أداء، وتنخفض الأداء مع معدل انقطاع أعلى #### 2. تأثير موارد الشبكة على أداء التعلم **تأثير التأخير في كل جولة**: - يتفوق المخطط المقترح باستمرار على المخطط الواعي لعرض النطاق الترددي - مع زيادة التأخير في كل جولة، ينخفض عدد جولات التقارب - عند زيادة التأخير، يضيق الفارق في الأداء مع المخطط بدون انقطاع **تأثير عرض النطاق الترددي للنظام**: - مع زيادة عرض النطاق الترددي للنظام، ينخفض عدد جولات التقارب - يتفوق المخطط المقترح على طرق الأساس في جميع ظروف عرض النطاق الترددي #### 3. النتائج الكمية وفقاً للجدول II، عند نفس درجة الندرة: - على LeNet، ينخفض معدل الدقة في FedDrop على بيانات Non-IID من 25.19% (γ=0) إلى 19.09% (γ=0.4) - على AlexNet، يرتفع معدل الدقة في FedDrop على بيانات Non-IID ثم ينخفض، ويصل إلى ذروته 32.77% عند γ=0.15 ### تجارب الاستئصال من خلال مقارنة الإعدادات الموحدة بمعدلات انقطاع مختلفة، تم التحقق من: 1. معدلات الانقطاع الأصغر تؤدي إلى تقارب أسرع 2. صحة التحليل النظري 3. تأثير التنظيم للانقطاع في سيناريو الإفراط في التجهيز ### النتائج التجريبية 1. **التحقق النظري**: تتطابق نتائج التجارب مع التحليل النظري، مما يثبت الارتباط السلبي بين معدل الانقطاع وسرعة التقارب 2. **المقارنة بين الموارد**: تسمح موارد الشبكة الأكثر بمعدلات انقطاع أقل، مما يحسن الأداء 3. **التكيف مع السيناريو**: يتفوق المخطط المقترح على المخطط بدون انقطاع في سيناريو الإفراط في التجهيز ## الأعمال ذات الصلة ### التعلم الموحد الفعال من حيث الاتصالات - متوسط التدرج الجزئي، ضغط التدرج، إدارة الموارد، جدولة الأجهزة، الحساب الجوي، تقطير المعرفة، وغيرها ### الطرق الفعالة من حيث الحساب - التعلم الموحد مع قص النموذج (PruneFL) - قص النموذج التكيفي - إطار عمل تدريب الشبكة الفرعية: المخططات الثابتة والمتداول والموجهة بالأهمية ### مميزات هذه الورقة 1. **تعقيد التصميم المنخفض**: يتطلب فقط عملية الانقطاع 2. **التكيف متعدد الوظائف**: يمكن لمعدل الانقطاع أن يتكيف مع قدرات الجهاز وظروف الشبكة 3. **تنوع النموذج العالي**: العشوائية تجلب تنوعاً في التدريب 4. **قوة النموذج القوية**: تعزز قوة النموذج وتزيل الاعتماديات البسيطة بين الخلايا العصبية ## الخلاصة والمناقشة ### الاستنتاجات الرئيسية 1. توفير تحليل نظري صارم للتقارب في FedDrop لأول مرة 2. إنشاء علاقة كمية بين معدل الانقطاع وسرعة التقارب 3. اقتراح خوارزمية تحسين مشترك منخفضة التعقيد 4. التحقق التجريبي من صحة التحليل النظري والخوارزمية ### القيود 1. **شروط الافتراض**: التحليل يعتمد على افتراض معدل انقطاع صغير 2. **نطاق النموذج**: يركز بشكل أساسي على DNNs، مع ترك LLMs للبحث المستقبلي 3. **نموذج القناة**: يفترض قناة غير انتقائية في التردد 4. **الهدف الأمثل**: استخدام الحد الأعلى لدالة الخسارة بدلاً من القيمة الدقيقة ### الاتجاهات المستقبلية 1. التوسع إلى النماذج اللغوية الكبيرة (LLMs) 2. الجمع بين تقنيات الضغط والحساب الجوي 3. الأخذ في الاعتبار نماذج قنوات أكثر تعقيداً 4. استراتيجيات تكيفية في بيئات الشبكة الديناميكية ## التقييم المتعمق ### المميزات 1. **مساهمة نظرية كبيرة**: توفير تحليل صارم للتقارب في FedDrop لأول مرة، ملء فجوة نظرية مهمة 2. **استنتاج رياضي دقيق**: استخدام تمديد تايلور وشروط KKT، مع إثبات رياضي كامل وموثوق 3. **قيمة عملية عالية**: خوارزمية بتعقيد O(K²) مناسبة للنشر العملي 4. **تجارب شاملة**: تغطي سيناريوهات نقص التجهيز والإفراط في التجهيز، مع تحقق كافٍ 5. **كتابة واضحة**: هيكل منظم، تعبير دقيق عن التفاصيل التقنية ### أوجه القصور 1. **قيود الافتراض**: قد يحد افتراض معدل الانقطاع الصغير من نطاق التطبيقات العملية 2. **قيود النموذج**: التحقق على شبكات نسبياً بسيطة فقط، مع نقص التجارب على نماذج واسعة النطاق 3. **تبسيط البيئة**: نموذج شبكة أحادي الخلية، بينما البيئات الفعلية أكثر تعقيداً 4. **مقارنة محدودة**: المقارنة مع طرق تدريب الشبكة الفرعية الأخرى غير كافية ### التأثير 1. **القيمة الأكاديمية**: توفير أساس نظري لتقنية الانقطاع في التعلم الموحد 2. **الأهمية العملية**: توفير حل قابل للتطبيق للتعلم الموحد في بيئات الحوسبة الطرفية 3. **قابلية التكرار**: وصف خوارزمي مفصل، إعدادات معاملات واضحة، سهولة التكرار ### السيناريوهات المطبقة 1. **أجهزة الحافة محدودة الموارد**: أجهزة إنترنت الأشياء ذات قدرات حسابية واتصالات محدودة 2. **شبكات محدودة عرض النطاق الترددي**: بيئات الشبكات اللاسلكية التي تحتاج إلى تقليل تكاليف الاتصالات 3. **التطبيقات الحساسة للتأخير**: تطبيقات الذكاء الاصطناعي على الحافة الحساسة للتأخير 4. **النشر على نطاق واسع**: أنظمة التعلم الموحد التي تحتاج إلى دعم عدد كبير من الأجهزة المشاركة ## المراجع تستشهد الورقة بـ 50 مرجعاً ذا صلة، تغطي التعلم الموحد والحوسبة الطرفية وتخصيص الموارد وضغط النموذج وغيرها من المجالات ذات الصلة، مما يوفر أساساً نظرياً متيناً للبحث. --- **التقييم الإجمالي**: هذه ورقة بحثية ذات مساهمة مهمة في تحليل النظرية الرياضية للتعلم الموحد. يقدم المؤلفون للمرة الأولى تحليلاً صارماً للتقارب في FedDrop، ويؤسسون علاقة كمية بين معدل الانقطاع وأداء التقارب، ويقترحون خوارزمية تحسين مشترك عملية. الاستنتاج الرياضي دقيق، والتحقق التجريبي شامل، وله أهمية كبيرة في تعزيز تطبيق التعلم الموحد في بيئات الحوسبة الطرفية.