Random coordinate descent
رینڈمائزڈ (بلاک) کوآرڈینیٹ ڈیسنٹ میتھڈ ایک اصلاحاتی الگورتھم ہے جسے نیسٹروف (2010) اور رچٹرک اور تکاک (2011) نے مقبول کیا۔ اس طریقہ کار کا پہلا تجزیہ، جب ہموار کنویکس فنکشن کو کم سے کم کرنے کے مسئلے پر لاگو ہوتا ہے، تو نیسٹروف (2010) کے ذریعہ انجام دیا گیا تھا۔ نیسٹروف کے تجزیے میں طریقہ کار کو کسی نامعلوم اسکیلنگ فیکٹر کے ساتھ اصل فنکشن کے کواڈریٹک پرٹربیشن پر لاگو کرنے کی ضرورت ہے۔ Richtárik and Takáč (2011) تکرار کی پیچیدگی کی حدود دیتے ہیں جن کے لیے اس کی ضرورت نہیں ہوتی، یعنی طریقہ کار کا اطلاق براہ راست معروضی فعل پر ہوتا ہے۔ مزید برآں، وہ ترتیب کو ایک جامع فنکشن کو کم سے کم کرنے کے مسئلے کے لیے عام کرتے ہیں، یعنی، ایک ہموار کنویکس کا مجموعہ اور ایک (ممکنہ طور پر غیر متزلزل) کنویکس بلاک سے الگ ہونے والا فنکشن: جہاں متغیرات/نقاط کے بلاکس میں تحلیل ہوتا ہے: اور (سادہ) کنویکس افعال ہیں۔ مثال (بلاک ڈکمپزیشن): اگر اور، کوئی اور کا انتخاب کر سکتا ہے۔ مثال (بلاک سے الگ کرنے کے قابل باقاعدگی):، جہاں اور معیاری یوکلیڈین معیار ہے۔ الگورتھم اصلاح کے مسئلے پر غور کریں جہاں ایک کنویکس اور ہموار فنکشن ہے۔ ہموار: ہموار سے ہمارا مطلب مندرجہ ذیل ہے: ہم فرض کرتے ہیں کہ کا میلان ہم آہنگی کے لحاظ سے لپشٹز مستقل کے ساتھ مسلسل ہے۔ یعنی، ہم فرض کرتے ہیں کہ سب کے لیے اور، جہاں متغیر کے حوالے سے جزوی مشتق کی نشاندہی کرتا ہے۔ نیسٹروف، اور رچٹرک اور تاکاک نے دکھایا کہ درج ذیل الگورتھم زیادہ سے زیادہ نقطہ پر یکجا ہوتا ہے: ان پٹ:// ابتدائی نقطہ آؤٹ پٹ: k کے لیے x: = x _ 0 سیٹ کریں: = 1،۔ ہم آہنگی کا انتخاب کریں، یکساں طور پر بے ترتیب اپ ڈیٹ کے اختتام پر کنورجنس ریٹ کے لیے چونکہ اس الگورتھم کے تکرار بے ترتیب ویکٹر ہیں، ایک پیچیدگی کا نتیجہ طریقہ کار کے لیے درکار تکرار کی تعداد پر ایک حد دے گا تاکہ اعلی امکان کے ساتھ ایک تخمینہ حل آؤٹ پٹ کیا جا سکے۔ یہ اس میں دکھایا گیا تھا کہ اگر، جہاں، ایک بہترین حل () ہے، اعتماد کی سطح ہے اور ہدف کی درستگی ہے، تو۔ مخصوص فنکشن پر مثال مندرجہ ذیل شکل سے پتہ چلتا ہے کہ اصول میں تکرار کے دوران کیسے ترقی ہوتی ہے۔ مسئلہ یہ ہے کہ کوآرڈینیٹ کی ترتیب کو روکنے کے لیے توسیع کوئی بھی قدرتی طور پر اس الگورتھم کو نہ صرف کوآرڈینیٹس تک بڑھا سکتا ہے، بلکہ کوآرڈینیٹس کے بلاکس تک بھی بڑھا سکتا ہے۔ فرض کریں کہ ہمارے پاس جگہ ہے۔ اس جگہ کی 5 مربوط سمتیں ہیں، ٹھوس طور پر جس میں بے ترتیب مربوط نزول کا طریقہ حرکت کر سکتا ہے۔ تاہم، کوئی بھی کچھ مربوط سمتوں کو بلاکس میں گروپ کر سکتا ہے اور ہم ان 5 مربوط سمتوں کے بجائے 3 مربوط سمتوں کو بلاک کر سکتے ہیں (تصویر دیکھیں)۔ کوآرڈینیٹ ڈیسنٹ گریڈیئنٹ ڈیسنٹ ریاضیاتی اصلاح حوالہ جات گریڈیئنٹ کے طریقے بھی دیکھیں۔