[AI/ML] الگوریتم Keswani برای بهینه سازی حداقل حداکثر 2 نفره غیر محدب

نویسنده(های): ششوات گوپتا

در ابتدا منتشر شد به سمت هوش مصنوعی.

الگوریتم Keswani یک رویکرد جدید را برای حل مسائل بهینه‌سازی حداقل حداکثر دو نفره غیر محدب معرفی می‌کند، به‌ویژه در بازی‌های متوالی متمایز که در آن توالی اقدامات بازیکن بسیار مهم است. این وبلاگ به بررسی این موضوع می پردازد که چگونه روش کسوانی به چالش های رایج در سناریوهای حداقل حداکثر، با کاربرد در حوزه های مدرن رسیدگی می کند. یادگیری ماشینی مانند GAN ها، آموزش خصمانه، و محاسبات توزیع شده، که جایگزینی قوی برای الگوریتم های سنتی مانند گرادیان نزول صعود (GDA).

تنظیم مشکل:

ما بازی‌های متوالی قابل تمایز را با دو بازیکن در نظر می‌گیریم: یک رهبر که می‌تواند به یک عمل متعهد شود و یک پیرو که پس از مشاهده عمل رهبر پاسخ می‌دهد. به ویژه، ما بر روی حالت حاصل جمع صفر تمرکز می کنیم
مسئله ای که به بهینه سازی مینیمکس نیز معروف است، به عنوان مثال،

بر خلاف بازی های همزمان، بسیاری از آنها عملی هستند یادگیری ماشینی الگوریتم‌ها، از جمله شبکه‌های متخاصم مولد (GAN) [2] [3] ، آموزش خصمانه [4] و یادگیری تقویتی اولیه-دوگانه [5]، به صراحت ترتیب حرکات بین بازیکنان را مشخص کنید و ترتیبی که بازیکن اول عمل می کند برای مشکل بسیار مهم است. به طور خاص، حداقل بهینه سازی حداکثر برای GAN ها ضروری است [2]، آمار، آموزش آنلاین [6]، یادگیری عمیق، و محاسبات توزیع شده [7].

بنابراین، مفهوم کلاسیک تعادل نش محلی از بازی‌های همزمان ممکن است تعریف مناسبی از بهینه محلی برای بازی‌های متوالی نباشد، زیرا مینیمکس به طور کلی با حداکثر برابر نیست. در عوض، ما مفهوم مینیمکس محلی را در نظر می گیریم [8] که ساختار متوالی بهینه سازی مینیمکس را در نظر می گیرد.

مدل ها و روش ها:

الگوریتم وانیل برای حل بهینه سازی حداقلی متوالی است شیب نزول-ascent (GDA)، که در آن هر دو بازیکن به‌روزرسانی گرادیان را به طور همزمان دریافت می‌کنند. با این حال، GDA از دو اشکال شناخته شده است.

1. دارای ویژگی های همگرایی نامطلوب است: نمی تواند به برخی از مینیمکس های محلی همگرا شود و می تواند به نقاط ثابتی همگرا شود که مینیمکس محلی نیستند. [9] [10]
2. GDA چرخش قوی حول نقاط ثابت را نشان می دهد که مستلزم استفاده از نرخ های یادگیری بسیار کوچک است[11] [12] به
   همگرا شوند.

اخیراً علاقه عمیقی به مشکلات حداقل حداکثر وجود داشته است [9] و کارهای بعدی دیگر جین و همکاران [8] در واقع بینش عالی به کار ارائه می دهد.

الگوریتم کسوانی:

الگوریتم اساسا تابع پاسخ را می سازد: حداکثر
y∈{R^m} f (., y) قابل انتقال با انتخاب y-updates (maxplayer) در
روشی حریصانه با محدود کردن انتخاب به روز شده (x,y) به نقاطی در امتداد مجموعه P(x,y) (که به عنوان مجموعه ای از نقاط انتهایی مسیرها تعریف می شود به طوری که f(x,.) غیر کاهشی است). 2 چیز جدید وجود دارد که این الگوریتم برای ساختن آنها انجام می دهد
محاسبات امکان پذیر:

1. P (x, y) را با Pε (x, y) جایگزین کنید (نقاط انتهایی مسیرهایی که f(x,.) با سرعت ε > 0 افزایش می‌یابد (که باعث می‌شود
   به روز رسانی به y توسط هر الگوریتم “طمع” (به عنوان الگوریتم 2) امکان پذیر است)
2. یک شرط احتمالی «نرم» برای توضیح توابع ناپیوسته معرفی کنید.

اثربخشی تجربی:

یک مطالعه [16] انجام شده در EPFL (توسط Shashwat و همکاران)، کارایی الگوریتم Keswani را در پرداختن به محدودیت‌های کلیدی روش‌های سنتی مانند GDA (Gradient Descent Ascent) و OMD (Online Mirror Descent)، به‌ویژه در اجتناب از دوچرخه‌سواری غیرهمگرا تأیید کرد. این مطالعه راه های تحقیقاتی آینده زیر را پیشنهاد کرد:

1. برای بهبود کارایی، محدودیت‌های سخت‌تر را بررسی کنید.
2. برای تعمیم یافته‌ها، دسته‌های عملکرد گسترده‌تر را ترکیب کنید.
3. بهینه سازهای جایگزین را آزمایش کنید تا استحکام الگوریتم را اصلاح کنید.

مطالعه کامل برای توابع مختلف به شرح زیر است:

الگوریتم Keswani برای غیر محدب 2 بازیکن حداقل بهینه سازی حداکثر

الگوریتم Keswani برای غیر محدب 2 بازیکن حداقل بهینه سازی حداکثر –

www.slideshare.net

مراجع:

[1] V. Keswani، O. Mangoubi، S. Sachdeva، و NK Vishnoi، “یک الگوریتم مرتبه اول همگرا و مستقل از ابعاد برای حداقل حداکثر
بهینه سازی،” arXiv preprint arXiv:2006.12376، 2020.
[2] آی. گودفلو، جی. پوگت ابادی، ام. میرزا، بی. ژو، د. وارد فارلی، اس. اوزایر، آ. کورویل و ی. بنژیو، «متخاصم مولد
شبکه‌ها، “ارتباطات ACM، جلد. 63، شماره 11، صفحات 139-144، 2020.
[3] M. Arjovsky, S. Chintala, and L. Bottou, “Wasserstein Generative Adversarial Networks,” صفحات 214-223, 2017.
[4] A. Madry، A. Makelov، L. Schmidt، D. Tsipras و A. Vladu، «به سوی یادگیری عمیق مدل‌های مقاوم در برابر حملات دشمن،” arXiv
پیش چاپ arXiv:1706.06083، 2017.
[5] دبلیو اس چو و ام. وانگ، «یادگیری عمیق اولیه-دوگانه تقویتی: تسریع بازیگر-منتقد با استفاده از دوگانگی بلمن»، پیش چاپ arXiv
arXiv:1712.02467، 2017.
[6] N. Cesa-Bianchi و G. Lugosi، پیش بینی، یادگیری، و بازی. انتشارات دانشگاه کمبریج، 2006.
[7] J. Shamma، کنترل تعاونی سیستم های چند عاملی توزیع شده. وایلی و پسران، گنجانده شده، جان، 2008.
[8] C. Jin، P. Netrapalli، و M. Jordan، “بهینه محلی در بهینه سازی مینیمکس غیر محدب-غیر مقعر چیست؟” صفحات 4880-4889، 2020.
[9] Y. Wang، G. Zhang، و J. Ba، “در حل بهینه سازی حداقل به صورت محلی: رویکردی دنباله دار”، arXiv preprint arXiv:1910.07512،
2019.
[10] C. Daskalakis و I. Panageas، “نقاط حدی نزول گرادیان (خوشبینانه) در بهینه سازی حداقل حداکثر”، پیشرفت در اطلاعات عصبی
سیستم های پردازش، جلد. 31، 2018.
[11] L. Mescheder, S. Nowozin, and A. Geiger, “The numerics of gans,” Advances in neural information processing system, vol. 30, 2017.
[12] D. Balduzzi, S. Racaniere, J. Martens, J. Foerster, K. Tuyls, and T. Graepel, “مکانیک بازی های قابل تمایز با n بازیکن” صفحات 354-363،
2018.
[13] DM Ostroovskii, B. Barazande, and M. Razaviyayn, “Nonconvex-nonconcave Min-Max optimization with a small maximization domain”
پیش چاپ arXiv arXiv:2110.03950، 2021.
[14] جی. یانگ، ن. کیاوش و ن. هی، “همگرایی جهانی و کاهش واریانس برای یک کلاس از مسائل حداقلی غیر محدب-غیر مقعر،”
پیشرفت‌ها در سیستم‌های پردازش اطلاعات عصبی، جلد. 33، صفحات 1153-1165، 2020.
[15] G. Zhang، Y. Wang، L. Lessard، و RB Grosse، “همگرایی محلی نزدیک به بهینه نزول-صعود شیب متناوب برای حداقل
بهینه سازی، صفحات 7659-7679، 2022.
[16] S. Gupta، S. Breguel، M. Jaggi، N. Flammarion “بهینه سازی حداقل حداکثر غیر محدب”، https://vixra.org/pdf/2312.0151v1.pdf

منتشر شده از طریق به سمت هوش مصنوعی