Command Palette
Search for a command to run...
تعظيم المخاطر التجريبية للاستدلال العشوائي المحدب: حدود مخاطرة من نوع O(1/n) و O(1/n2)
تعظيم المخاطر التجريبية للاستدلال العشوائي المحدب: حدود مخاطرة من نوع O(1/n) و O(1/n2)
Lijun Zhang; Tianbao Yang; Rong Jin
الملخص
رغم وجود العديد من النظريات حول تقليل المخاطر التجريبية (ERM) في التعلم الإشرافي، فإن الفهم النظري الحالي لتقليل المخاطر التجريبية في مشكلة متعلقة وهي الأمثلة العشوائية المحدبة (SCO) ما زال محدودًا. في هذا البحث، نعزز نطاق تطبيق ERM في SCO من خلال استغلال شروط الانسيابية والحدبية القوية لتحسين حدود المخاطر. أولاً، نثبت حدًا للمخاطر يبلغ O(d/n+F/n) عندما تكون الدالة العشوائية غير سالبة ومحدبة وانسيابة، والدالة المتوقعة متصلة بليبسشيتز، حيث d هي البعدية للمشكلة، n هو عدد العينات، وF_ هي أقل قيمة للمخاطرة. وبالتالي، عندما تكون F∗ صغيرة، نحصل على حد مخاطرة يبلغ O(d/n)، وهو مشابه لمعدل التفاؤل O(1/n) لـ ERM في التعلم الإشرافي.ثانيًا، إذا كانت الدالة الهدف أيضًا محدبة قوية بمقدار λ-strongly convex (محدبة قوية بمقدار λ)، فنثبت حدًا للمخاطر يبلغ O(d/n+κF/n) حيث κ هو رقم الشرط (condition number)، ونحسن هذا الحد إلى O(1/[λn2]+κF/n) عندما يكون n=Ω(κd). نتيجة لذلك، نحصل على حد مخاطرة يبلغ O(κ/n2) تحت شرط أن يكون n كبيرًا وأن تكون F∗ صغيرة، وهو حسب علمنا أفضل حد من نوع O(1/n2) لـ ERM.ثالثًا، نؤكد أن هذه النتائج قد تم إثباتها ضمن إطار موحد يمكننا من اشتقاق حدود مخاطرة جديدة تحت شروط أضعف، مثل عدم الحاجة إلى حدبية الدالة العشوائية أو استمرارية بليبسشيتز للدالة المتوقعة. أخيرًا، نوضح أنه لتحقيق حد مخاطرة يبلغ O(1/[λn2]+κF∗/n) في التعلم الإشرافي، يمكن استبدال شرط Ω(κd) على n بشرط Ω(κ2) الذي لا يعتمد على البعدية.