ترجمه فارسی مقاله همگرایی زنجیره‌های مارکوف برای نزول گرادیان تصادفی با اندازه گام ثابت با توابع قابل تفکیک

چکیده

Stochastic gradient descent (SGD) is a popular algorithm for minimizing objective functions that arise in machine learning. For constant step-sized SGD, the iterates form a Markov chain on a general state space. Focusing on a class of separable (non-convex) objective functions, we establish a “Doeblin-type decomposition,” in that the state space decomposes into a uniformly transient set and a disjoint union of absorbing sets. Each of the absorbing sets contains a unique invariant measure, with the set of all invariant measures being the convex hull. Moreover the set of invariant measures are shown to be global attractors to the Markov chain with a geometric convergence rate. The theory is highlighted with examples that show: (1) the failure of the diffusion approximation to characterize the long-time dynamics of SGD; (2) the global minimum of an objective function may lie outside the support of the invariant measures (i.e., even if initialized at the global minimum, SGD iterates will leave); and (3) bifurcations may enable the SGD iterates to transition between two local minima. Key ingredients in the theory involve viewing the SGD dynamics as a monotone iterated function system and establishing a “splitting condition” of Dubins and Freedman 1966 and Bhattacharya and Lee 1988.

چکیده به فارسی (ترجمه ماشینی)

نزول شیب تصادفی (SGD) یک الگوریتم محبوب برای به حداقل رساندن عملکردهای عینی است که در یادگیری ماشین بوجود می آید.برای SGD به اندازه گام ثابت ، تکرارها یک زنجیره مارکوف را در یک فضای دولتی عمومی تشکیل می دهند.با تمرکز بر روی یک کلاس از کارکردهای عینی قابل جدا شدن (غیر کنفکس) ، ما یک “تجزیه از نوع doeblin” ایجاد می کنیم ، به این ترتیب که فضای دولت به یک مجموعه یکنواخت گذرا و اتحادیه ای از مجموعه های جذب کننده تجزیه می شود.هر یک از مجموعه های جذب کننده حاوی یک اندازه گیری ثابت منحصر به فرد است که مجموعه ای از تمام اقدامات ثابت ، بدنه محدب است.علاوه بر این ، مجموعه اقدامات ثابت نشان داده شده است که جذب جهانی زنجیره مارکوف با میزان همگرایی هندسی است.این تئوری با مثالهایی برجسته شده است که نشان می دهد: (1) عدم موفقیت تقریب انتشار برای توصیف دینامیک طولانی مدت SGD.(2) حداقل جهانی یک عملکرد عینی ممکن است خارج از حمایت از اقدامات ثابت باشد (یعنی ، حتی اگر در حداقل جهانی اولیه شود ، تکرار SGD ترک می کند).و (3) bifurcations ممکن است تکرار SGD را به انتقال بین دو حداقل محلی تبدیل کند.ترکیبات اصلی این تئوری شامل مشاهده دینامیک SGD به عنوان یک سیستم عملکرد تکراری یکنواخت و ایجاد “شرایط تقسیم” Dubins and Freedman 1966 و Bhattacharya و Le 1988 است.