روشهای شرکتی اینرسی تصادفی توزیع شده با مشتقات تأخیر برای مشکلات غیر کنفکس توزیع شده است

Stochastic gradient methods (SGMs) are predominant approaches for solving stochastic optimization. On smooth nonconvex problems, a few acceleration techniques have been applied to improve the convergence rate of SGMs. However, little exploration has been made on applying a certain acceleration technique to a stochastic subgradient method (SsGM) for nonsmooth nonconvex problems. In addition, few efforts have been made to analyze an (accelerated) SsGM with delayed derivatives. The information delay naturally happens in a distributed system, where computing workers do not coordinate with each other. In this paper, we propose an inertial proximal SsGM for solving nonsmooth nonconvex stochastic optimization problems. The proposed method can have guaranteed convergence even with delayed derivative information in a distributed environment. Convergence rate results are established for three classes of nonconvex problems: weakly convex nonsmooth problems with a convex regularizer, composite nonconvex problems with a nonsmooth convex regularizer, and smooth nonconvex problems. For each problem class, the convergence rate is $O(1/K^>) $ در ارزش مورد انتظار میدان هنجار شیب ، برای تکرارهای $ $. در یک محیط توزیع شده ، میزان همگرایی روش پیشنهادی با تأخیر اطلاعات کاهش می یابد. با این وجود ، اثر آهسته با تعداد تکرارها برای دو کلاس مشکل دوم پوسیده می شود. ما روش پیشنهادی را در سه برنامه آزمایش می کنیم. نتایج عددی به وضوح مزایای استفاده از شتاب مبتنی بر اینرسی را نشان می دهد. علاوه بر این ، ما سرعت موازی سازی بالاتر را در به روزرسانی های ناهمزمان نسبت به همتای همزمان مشاهده می کنیم ، اگرچه اولی از مشتقات تأخیر استفاده می کند. کد منبع ما در https://github.com/rpi-opt/inertial-sgm در دسترس است.

1. A. Agarwal و J. C. Duchi ، بهینه سازی تصادفی تأخیر توزیع شده ، در پیشرفت در سیستم های پردازش اطلاعات عصبی ، 2011 ، صص 873 - 881. گوگل دانشکده

2. A. Alacaoglu ، Y. Malitsky و V. Cevher ، همگرایی الگوریتم های تطبیقی برای بهینه سازی ضعیف محدود محدب ، preprint ، arxiv: 2006. 06650 ، 2020. گوگل دانشکده

3. Z. Allen-Zhu: اولین شتاب مستقیم روشهای شیب تصادفی ، J. Mach. فرا گرفتن. res، 18 (2017) ، صص 8194 - 8244. محقق isigoogle

4- F. Alvarez ، همگرایی ضعیف یک الگوریتم نقطه ای از طرح ریزی ترکیبی آرام و اینرسی برای عملگرهای حداکثر یکنواخت در فضای هیلبرت ، سیام جی.، 14 (2004) ، صص 773 - 782. محقق Linkisigoogle

5. F. Alvarez و H. Attouch ، یک روش پروگزیمال اینرسی برای حداکثر اپراتورهای یکنواخت از طریق گسسته سازی یک نوسان ساز غیرخطی با میرایی و مقعد با ارزش.، 9 (2001) ، صص 3 - 11. Crossrefisigoogle Scholar

6. K. Bäckström ، M. Papatriantafilou and P. Tsigas ، MindTheStep-Asyncpsgd: نزول شیب موازی موازی ناهمزمان سازگار ، در مجموعه مقالات کنفرانس بین المللی IEEE 2019 در مورد داده های بزرگ ، IEEE ، 2019 ، صص 16-25. گوگل دانشکده

7. E. J. Candès ، X. Li ، Y. Ma و J. Wright ، تجزیه و تحلیل مؤلفه اصلی قوی؟، J. ACM ، 58 (2011) ، صص 1 - 37. Crossrefisigoogle Scholar

8. T. F. Chan. WONG ، تجزیه و تحلیل کور متغیر کل ، IEEE Trans. روند تصویر.، 7 (1998) ، صص 370 - 375. Crossrefisigoogle Scholar

9. V. Chandrasekaran ، S. Sanghavi ، P. A. Parrilo و A. S. Willsky ، ناسازگاری رتبه بندی برای تجزیه ماتریس ، سیام جی.، 21 (2011) ، صص 572 - 596. محقق Linkisigoogle

10. S. Chen, A. Garcia and S. Shahrampour, Distributed Projected Subgradient Method for Weakly Convex Optimization, preprint, arXiv:2004. 13233, 2020. Google Scholar

11. D. Davis و D. Drusvyatskiy، کمینه سازی مبتنی بر مدل تصادفی توابع ضعیف محدب، SIAM J. Optim.، 29 ( 2019 ) ، ص 207 -- 239 ، https://doi.org/10. 1137/18M1178244. LinkISIGoogle Scholar

12. D. Davis, D. Drusvyatskiy and C. Paquette, The nonsmooth landscape ofphase retrieval, IMA J. Numer. مقعدی, 40 ( 2020 ) , ص 2652 -- 2695 . CrossrefGoogle Scholar

13. T. T. Doan، C. L. Beck و R. Srikant، نرخ همگرایی روش های subgradient توزیع شده تحت تأخیرهای ارتباطی، در مجموعه مقالات کنفرانس سالانه کنترل آمریکایی 2018، IEEE، 2018، صفحات 5310 - 5315. Google Scholar

14. D. Drusvyatskiy and C. Paquette، کارایی کمینه سازی ترکیبات توابع محدب و نقشه های صاف، ریاضی. برنامه.، 178 ( 2019 ) ، ص 503 -- 558 . CrossrefISIGoogle Scholar

15. J. Duchi، E. Hazan و Y. Singer، روش های زیرگرایش تطبیقی برای یادگیری آنلاین و بهینه سازی تصادفی، J. Mach. فرا گرفتن. Res., 12 ( 2011 ) ، ص 2121 -- 2159 . ISIGoogle Scholar

16. J. C. Duchi و F. Ruan، حل (بیشتر) مجموعه ای از برابری های درجه دوم: بهینه سازی ترکیبی برای بازیابی فاز قوی، استنتاج اطلاعات، 8 (2019)، صفحات 471 - 529. CrossrefGoogle Scholar

17. Y. C. Eldar and S. Mendelson, Phase retrieval: Stability and recovery garants , Appl. محاسبه کنید. هارمونمقعدی، 36 (2014)، صص 473 - 494. CrossrefISIGoogle Scholar

18. E. Ghadimi، H. R. Feyzmahdavian and M. Johansson، همگرایی جهانی روش توپ سنگین برای بهینه سازی محدب، در مجموعه مقالات کنفرانس کنترل اروپا 2015، IEEE، 2015، صفحات 310 - 315. Google Scholar

19. س. قدیمی و جی. لان، روش های گرادیان شتاب دار برای برنامه ریزی غیرخطی و تصادفی غیر محدب، ریاضی. برنامه.، 156 (1395)، صص 59 - 99. CrossrefISIGoogle Scholar

20. آ. Google Scholar

21. N. Guan، D. Tao، Z. Luo و B. Yuan، فاکتورسازی ماتریس غیر منفی آنلاین با تقریب تصادفی قوی، IEEE Trans. سیستم های یادگیری شبکه های عصبی , 23 ( 2012 ) , صفحات 1087 -- 1099 . CrossrefGoogle Scholar

22. R. Hannah و W. Yin ، در تأخیرهای بی حد و حصر در الگوریتم های موازی موازی ناهمزمان ، J. Sci. محاسبات.، 76 (2018) ، صص 299 - 326. Crossrefisigoogle Scholar

23. Z. Huo و H. Huang ، نزول شیب مینی دسته ای ناهمزمان با کاهش واریانس برای بهینه سازی غیر Convex ، در مجموعه مقالات کنفرانس AAAI در مورد هوش مصنوعی ، 2017. گوگل دانشکده

24. R. Johnson and T. Zhang ، شتاب شیب تصادفی با استفاده از کاهش واریانس پیش بینی ، پیشرفت در سیستم های پردازش اطلاعات عصبی ، 26 (2013) ، صص 315 - 323. گوگل دانشکده

25. A. Krizhevsky ، یادگیری چندین لایه از ویژگی ها از تصاویر کوچک ، 2009 ، http://citeseerx. ist. psu. edu/viewdoc/summary؟doi=10. 1. 1. 222. 9220.، http://citeseerx. ist. psu. edu/viewdoc/summary؟doi=10. 1. 1. 222. 9220. گوگل دانشکده

26. Y. Lecun ، L. Bottou ، Y. Bengio و P. Haffner ، یادگیری مبتنی بر گرادیان که برای تشخیص اسناد اعمال می شود ، Proc. IEEE ، 86 (1998) ، صص 2278 - 2324. Crossrefisigoogle Scholar

27. A. Levin ، Y. Weiss ، F. Durand and W. T. Freeman ، درک الگوریتم های تجزیه نابینا ، IEEE Trans. الگوی مقعد. هوش دستگاه ، 33 (2011) ، صص 2354 - 2367. Crossrefisigoogle Scholar

28. X. Lian ، Y. Huang ، Y. Li and J. Liu ، شیب تصادفی موازی ناهمزمان برای بهینه سازی Nonconvex ، در پیشرفت در سیستم های پردازش اطلاعات عصبی ، 2015 ، صص 2737 - 2745. گوگل دانشکده

29. X. Lian ، W. Zhang ، C. Zhang and J. Liu ، تبار شیب موازی غیر متمرکز غیر متمرکز ، در مجموعه مقالات کنفرانس بین المللی یادگیری ماشین ، 2018 ، صص 3043 - 3052. گوگل دانشکده

30. I. Guyon ، and R. Gaett ، eds. ، Vol. 29 ، Curran Associates ، 2016 ، https://proesings. neurips. cc/paper/2016/file/ea6b2efbdd4255a9f1b3bc6399b58f4-paper. pdf. گوگل دانشکده

31. N. Loizou and P. Richtárik ، روش توپ سنگین تصادفی خطی همگرا برای به حداقل رساندن خطای تعمیم ، preprint ، arxiv: 1710. 10737 ، 2017. گوگل دانشکده

32. N. Loizou و P. Richtárik ، Momentum و Momentum برای شیب تصادفی ، نیوتن ، Proximal Point و Subpace Nexcent Methods ، Comput. بهینهکاربرد، 77 (2020) ، صص 653 - 710. Crossrefisigoogle Scholar

33. V. Mai و M. Johansson، همگرایی یک روش گرادیان تصادفی با تکانه برای بهینه سازی غیرمحدب غیر صاف، در مجموعه مقالات کنفرانس بین المللی یادگیری ماشین، PMLR، 2020، صفحات 6630 - 6639. Google Scholar

34. I. Masubuchi، J. Tsukamoto، T. Wada، R. Morita، T. Asai، Y. Ohta و Y. Fujisaki، بهینه سازی چند عاملی توزیع شده با محدودیت های محلی از طریق یک روش subgradient با اطلاعات تاخیری امکان سنجی، در مجموعه مقالاتبیست و یکمین سمپوزیوم بین المللی نظریه ریاضی شبکه ها و سیستم ها , 2014 , صفحات 23 - 28 . Google Scholar

35. B. McMahan and M. Streeter، الگوریتم های تحمل تاخیر برای یادگیری آنلاین توزیع شده ناهمزمان، در Advances in Neural Information Processing Systems، Z. قهرمانی، M. Welling، C. Cortes، N. Lawrence، و K. Q. Weinberger، ویراستاران.، جلد27، Curran Associates، 2014، https://proceedings. neurips. cc/paper/2014/file/5cce8dede893813f879b873962fb669f-Paper. pdf. Google Scholar

36. J.-J. Moreau، Proximité et dulité dans un espace hilbertien، Bull. Soc. ریاضی. فرانسه، 93 (1965)، ص 273 -- 299، http://www. numdam.org/item? id=BSMF_1965__93__273_0.، http://www. numdam.org/item? id=BSMF_1965__93__273_0. CrossrefGoogle Scholar

37. A. Moudafi و M. Oliny، همگرایی یک روش پروگزیمال اینرسی تقسیم برای عملگرهای یکنواخت، J.comput. Appl. ریاضی., 155 ( 2003 ) , ص 447 -- 454 . CrossrefISIGoogle Scholar

38. S. D. Muruganathan، D. C. Ma، R. I. Bhasin و A. O. Fapojuwo، یک پروتکل مسیریابی متمرکز انرژی کارآمد برای شبکه های حسگر بی سیم، مجله ارتباطات IEEE، 43 (2005)، صفحات S8 - 13. CrossrefGoogle Scholar

39. P. Nazari، D. A. Tarzanagh and G. Michailidis، روش های مرتبه اول و صفر تطبیقی برای مسائل بهینه سازی تصادفی محدب ضعیف، پیش چاپ، arXiv: 2005. 09261، 2020. Google Scholar

40. A. V. Nazin، الگوریتم های نزول آینه اینرسی در مسائل محدب بهینه سازی تصادفی، خودکار. کنترل از راه دور , 79 ( 2018 ) ص 78 -- 88 . CrossrefGoogle Scholar

41. A. Nedić, D. P. Bertsekas and V. S. Borkar, Distributed Asynchronous subgradient incremental methods, Stud. محاسبه کنید. ریاضی.، 8 (2001)، صص 381 - 407. CrossrefGoogle Scholar

42. A. Nemirovski، A. Juditsky، G. Lan و A. Shapiro، رویکرد تقریب تصادفی قوی برای برنامه ریزی تصادفی، SIAM J. Optim., 19 ( 2009 ) , صص 1574 -- 1609 . LinkISIGoogle Scholar

43. Y. E. Nesterov , A method for solving the convex programming problem with convergence rate $O(1/K^>) $ ، dokl. آکادNauk SSSR ، 269 (1983) ، صص 543 - 547. گوگل دانشکده

44. P. OCHS ، همگرایی محلی روش توپ سنگین و Ipiano برای بهینه سازی غیر Convex ، J. Optim. برنامه تئوری.، 177 (2018) ، صص 153 - 180. Crossrefisigoogle Scholar

45. P. Ochs ، T. Brox and T. Gock ، Ipiasco: الگوریتم پروگزیمال اینرسی برای بهینه سازی شدید محدب ، J. Math. تصویربرداری چشم انداز ، 53 (2015) ، صص 171 - 181. Crossrefisigoogle Scholar

46.، 7 (2014) ، صص 1388 - 1419. محقق Linkisigoogle

47. Z. Peng ، Y. Xu ، M. Yan and W. Yin ، در مورد همگرایی تکرار موازی ناهمزمان با تأخیرهای بی حد و حصر ، J. Oper. resSOC. چین ، 7 (2019) ، صص 5 - 42. محقق CrossRefGoogle

48. B. T. Polyak ، برخی از روش های سرعت بخشیدن به همگرایی روش های تکرار ، رایانه اتحاد جماهیر شوروی. ریاضی. ریاضی. فیزیک، 4 (1964) ، صص 1 - 17. محقق CrossRefGoogle

49. B. T. Polyak ، مقدمه ای برای بهینه سازی. بهینه سازی نرم افزار ، شرکت ، بخش انتشارات ، نیویورک ، 1987. گوگل دانشکده

50. B. Recht ، تجزیه و تحلیل CS726-Lyapunov و روش توپ سنگین ، گروه علوم رایانه ، دانشگاه ویسکانسین-مدیسون ، 2010. گوگل دانشکده

51. B. Recht ، C. Re ، S. Wright and F. Niu ، Hogwild: یک رویکرد بدون قفل برای موازی سازی نزول شیب تصادفی ، در پیشرفت در سیستم های پردازش اطلاعات عصبی ، 2011 ، صص 693-701. گوگل دانشکده

52. H. Robbins and S. Monro ، یک روش تقریب تصادفی ، Ann. ریاضی. آمار، 22 (1951) ، صص 400 - 407. Crossrefisigoogle Scholar

53. S. Scardapane ، D.comminiello ، A. Hussain and A. Uncini ، تنظیمات پراکنده گروه برای شبکه های عصبی عمیق ، نوروکومتر ، 241 (2017) ، صص 81 - 89. Crossrefisigoogle Scholar

54. J. V. Shi ، Y. Xu and R. G. Baraniuk ، رگرسیون لجستیک پراکنده Bilinear ، Preprint ، Arxiv: 1404. 4104 ، 2014. گوگل دانشکده

55. J. T. Springenberg ، A. Dosovitskiy ، T. Brox and M. Riedmiller ، در تلاش برای سادگی: همه شبکه های حلقوی ، preprint ، arxiv: 1412. 6806 ، 2014. گوگل دانشکده

56. S. SRA ، S. Nowozin و S. J. Wright ، بهینه سازی برای یادگیری ماشین ، MIT Press ، کمبریج ، MA ، 2012. گوگل دانشکده

57. S. SRA ، A. W. Yu ، M. Li and A. Smola ، Adadelay: بهینه سازی تصادفی توزیع تطبیقی توزیع شده ، در مجموعه مقالات هوش مصنوعی و آمار ، 2016 ، صص 957 - 965. گوگل دانشکده

58. T. Sun، D. Li، Z. Quan، H. Jiang، S. Li و Y. Dou، الگوریتم های توپ سنگین همیشه از نقاط زینی فرار می کنند، در مجموعه مقالات بیست و هشتمین کنفرانس مشترک بین المللی هوش مصنوعی، 2019، ص. 3520 -- 3526 2019 /488.، https://doi.org/10. 24963/ijcai. 2019/488. Google Scholar

59. تی سان و ال. کیائو. لی، پیچیدگی غیرنرگودیک نزول های گرادیان اینرسی پروگزیمال، IEEE Trans. سیستم های یادگیری شبکه های عصبی , 32 ( 2021 ) , صفحات 4613 -- 4626 . CrossrefGoogle Scholar

60. T. Sun، P. Yin، D. Li، C. Huang، L. Guan and H. Jiang، تحلیل همگرایی غیرارگودیکی الگوریتم های توپ سنگین، در مجموعه مقالات کنفرانس AAAI در زمینه هوش مصنوعی، جلد. 33 , 2019 , صفحات 5033 -- 5040 . CrossrefGoogle Scholar

61. I. Sutskever, J. Martens, G. Dahl and G. Hinton, On the Importance of Initialization and Momentum in Deep Leaing, در مجموعه مقالات کنفرانس بین المللی یادگیری ماشینی, PMLR, 2013, صفحات 1139-1147. Google Scholar

62. Q. Tran-Dinh، N. H. Pham، D. T. Phan، و L. M. Nguyen، یک چارچوب بهینه سازی تصادفی ترکیبی برای بهینه سازی غیر محدب مرکب، ریاضی. برنامه.، برای ظاهر شدن. Google Scholar

63. P. Tseng، روش گرادیان افزایشی (-projection) با ترم تکانه و قانون اندازه گام تطبیقی، SIAM J. Optim.، 8 ( 1998 ) ، ص 506 -- 531 . LinkISIGoogle Scholar

64. H. Wang، X. Liao و T. Huang. Li، Cooperative بهینه سازی را در شبکه های چند عاملی با تاخیر توزیع کرد، IEEE Trans. Systems Man Cybeetics Systems , 45 ( 2014 ) , صفحات 363 -- 369 . CrossrefGoogle Scholar

65. Y. Xu، روش گرادیان تصادفی تقلیل یافته واریانس مبتنی بر تکانه برای بهینه سازی تصادفی غیرمحدب مرکب، پیش چاپ، arXiv:2006. 00425، 2020. Google Scholar

66. Y. Xu، Y. Xu، Y. Yan، C. Sutcher-Shepard، L. Grinberg و J. Chen، روشهای گرادیان تصادفی تطبیقی ناهمزمان موازی و توزیع شده، پیش چاپ، arXiv:2002. 09095، 2020. Google Scholar

67. Y. Yan، T. Yang، Z. Li، Q. Lin و Y. Yang، تجزیه و تحلیل یکپارچه روش های تکانه تصادفی برای یادگیری عمیق، در مجموعه مقالات بیست و هفتمین کنفرانس بین المللی مشترک هوش مصنوعی، 2018، ص 2955-- 2961 2018 /410.، https://doi.org/10. 24963/ijcai. 2018/410. Google Scholar

68. S. Zavriev و F. Kostyuk، روش توپ سنگین در مسائل بهینه سازی غیر محدب، محاسبات. ریاضی. مدل.، 4 (1993)، صص 336 - 341. CrossrefGoogle Scholar