زمان همگرایی قدم‌زدن تصادفی (ارائه درس گسترگراف)

دریافت

جانشین محدب

یک قسمتی از اثبات وجود تعادل نش این است که با قضیه‌ی بروئر ثابت می‌کنند که نقطه ثابت یک تابع، تعادل نش است. حالا ایده‌ی من این بود که اگر به جای اینکه فقط به صورت وجودی از این قضیه استفاده کنیم برای پیدا کردن تعادل نش ازش استفاده کنیم. این کار هم انجام شده بود (یا حداقل کارهای شبیه‌اش).
یک چیزی که امروز در ارائه‌ی یکی از بچه‌ها بود «جایگزین محدب» بود. در بهینه‌سازی روی یک مجموعه‌ی خاص، به جای یک تابع می‌شود از یک تابع دیگر استفاده کرد و همچنان جواب همان قبلی به دست می‌آید. حالا به نظرم می‌شود همین کار را برای تعادل نش هم انجام داد.

حالا به قیافه‌ی این مقاله می‌خورد که برای پیدا کردن بهترین جواب از این تابع جانشین محدب‌ها استفاده کرده باشد، اما قول نمی‌دهم همین باشد! :))

https://papers.nips.cc/paper/5686-adversarial-prediction-games-for-multivariate-losses.pdf

http://drops.dagstuhl.de/opus/volltexte/2016/6811/pdf/LIPIcs-ISAAC-2016-41.pdf

http://www.jmlr.org/proceedings/papers/v28/mairal13.pdf

تنک‌کننده‌ها

http://www.cs.cmu.edu/afs/cs/user/glmiller/public/Scientific-Computing/F-11/RelatedWork/HarveySparsify.pdf

دریافت

دریافت

دریافت

یک راه حل دیگر هم اینجا ارائه شده:

https://simons.berkeley.edu/talks/alexandr-andoni-2014-12-02

که فیلمش در سایت دانشگاه هم هست.

ابزار بهبود واژگان

حس کردم یک نفر که زبانش خوب نیست نوشته‌هایش لغت‌های خوبی دارند. یاد این افتادم که مثلاً مترجم گوگل این امکان را دارد که یک لغت را تایپ کنید و لغت‌های مترادف پیشنهاد بدهد. دنبال یک ابزار خوب هستم که بیشتر از یک لغت بگیرد و اشتراک‌های آنها را بدهد. از نظر لغت مترجم گوگل از همه بهتر است چون از بین کلمات مترادف پیشنهاد می‌دهد.

Dynamics on Unimodular Random Graphs

https://arxiv.org/pdf/1608.05940v1.pdf
ارائه‌اش چهارشنبه بود یادم رفت برم. گفتم به یک دلیلی می‌خواستم بمونم دانشگاه ولی یادم نیومد! :| :|
http://mehr.sharif.edu/~combinatorics/seminars9501/khezeli.pdf

تعمیم نتایج اقلیدسی به متریک‌های دوبرابر شونده

http://www.cs.cmu.edu/~anupamg/adfocs/Gupta-lec3.pdf

local doubling dimension

http://cccg.ca/proceedings/2015/03.pdf

Expanders via Local Edge Flips

https://arxiv.org/abs/1510.07768

متاالگوریتم پیش‌بینی وضع هوا

http://www.cs.ubc.ca/~amehrabi/Articles/weather_forecast_problem_feb16.pdf
گفته یکی از کاربردهای متاالگوریتم‌ها حل تقریبی بازی‌های مجموع-صفر است. به نظر می‌رسد که ترکیب الگوریتم‌های یادگیری است با الگوریتم تقریبی است.
خودش گفته ترجمه‌ی این است:
http://thl.epfl.ch/gems/notes/lecture1.pdf

انواع دیگر گراف تصادفی

http://www.albany.edu/~ravi/pdfs/part_07.pdf