صلابة المعاملات لاحتواء الزونوتوب والتحقق من الشبكات العصبية

تُعد الشبكات العصبية التي تستخدم تفعيل ReLU نموذجًا مستخدمًا على نطاق واسع في تعلم الآلة. ولذلك، من المهم أن نفهم بعمق خصائص الدوال التي تحسبها مثل هذه الشبكات. مؤخرًا، زاد الاهتمام بتعقيد الحوسبة (الذي يعتمد على المعلمات) لتحديد هذه الخصائص. في هذا العمل، نقوم بسد عدة ثغرات وحل مشكلة مفتوحة طرحها فرواز وآخرون في مؤتمر COLT '25 بشأن التعقيد المعتمد على المعلمات لمشاكل مختلفة تتعلق بالتحقق من الشبكة. على وجه الخصوص، نثبت أن تحديد إيجابية (ومن ثم شمولية) دالة fᵈ التي تحسبها شبكة ReLU ذات طبقتين هو W1-hard عند المعيار d. تُشير هذه النتيجة أيضًا إلى أن احتواء الزونوتوب (أو عدمه) هو W1-hard بالنسبة لـ d، وهي مشكلة ذات اهتمام مستقل في الهندسة الحاسوبية، ونظرية التحكم، والروبوتات. علاوة على ذلك، نُظهر أن تقدير الحد الأقصى ضمن أي عامل مضاعف في شبكات ReLU ذات الطبقتين، وحساب ثابت Lₚ-Lipschitz لـ p (0, ] في الشبكات ذات الطبقتين، وتقدير ثابت Lₚ-Lipschitz في الشبكات ذات الثلاث طبقات هي NP-hard وW1-hard بالنسبة لـ d. ومن الجدير بالذكر أن نتائج الصعوبة لدينا هي الأقوى المعروفة حتى الآن ونتيجة ذلك أن الأساليب المبنية على التعداد الساذج لحل هذه المشاكل الأساسية جميعها هي في الأساس مثالية تحت فرضية الزمن الأسي.