کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5773851 | 1631463 | 2017 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The exact information-based complexity of smooth convex minimization
ترجمه فارسی عنوان
پیچیدگی دقیق مبتنی بر اطلاعات به حداقل رساندن محدب صاف
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
بهینه سازی محدب، پیچیدگی، نرخ همگرایی، پیچیدگی مبتنی بر اطلاعات،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
آنالیز ریاضی
چکیده انگلیسی
We obtain a new lower bound on the information-based complexity of first-order minimization of smooth and convex functions. We show that the bound matches the worst-case performance of the recently introduced Optimized Gradient Method (Drori and Teboulle, 2013; Kim and Fessler, 2015), thereby establishing that the bound is tight and can be realized by an efficient algorithm. The proof is based on a novel construction technique of smooth and convex functions.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Complexity - Volume 39, April 2017, Pages 1-16
Journal: Journal of Complexity - Volume 39, April 2017, Pages 1-16
نویسندگان
Yoel Drori,