view in publisher's site
- خانه
- لیست مقالات
- چکیده
Efficient Online Linear Optimization with Approximation Algorithms
We revisit the problem of online linear optimization in the case where the set of feasible actions is accessible through an approximated linear optimization oracle with a factor α multiplicative approximation guarantee. This setting in particular is interesting because it captures natural online extensions of well-studied offline linear optimization problems that are NP-hard yet admit efficient approximation algorithms. The goal here is to minimize the α-regret, which is the natural extension to this setting of the standard regret in online learning. We present new algorithms with significantly improved oracle complexity for both the full-information and bandit variants of the problem. Mainly, for both variants, we present α-regret bounds of [Formula: see text], were T is the number of prediction rounds, using only [Formula: see text] calls to the approximation oracle per iteration, on average. These are the first results to obtain both the average oracle complexity of [Formula: see text] (or even polylogarithmic in T) and α -regret bound [Formula: see text] for a constant c > 0 for both variants.
بهینه‌سازی خطی آنلاین کارآمد با الگوریتم های تقریبی
ما مساله بهینه‌سازی خطی آنلاین را در حالتی که مجموعه‌ای از کنش‌های ممکن از طریق یک الگوریتم بهینه‌سازی خطی تقریبی با یک تضمین تقریب میان ضربی در دسترس است، دوباره بررسی می‌کنیم.
این تنظیم به طور خاص جالب است زیرا گسترش‌های آنلاین طبیعی مسایل بهینه‌سازی خطی برون‌خط که به خوبی مورد مطالعه قرار گرفته‌اند را می‌گیرد.
هدف در اینجا به حداقل رساندن پشیمانی آلفا است، که گسترش طبیعی این تنظیم پشیمانی استاندارد در یادگیری آنلاین است.
ما الگوریتم های جدیدی را ارایه می‌دهیم که به طور قابل‌توجهی پیچیدگی الگوریتم بهبود یافته را هم برای انواع کامل اطلاعات و هم برای انواع راهزن مشکل دارند.
به طور کلی، برای هر دو نوع، ما حدود α - پشیمانی از O (T - ۱ / ۳)را نشان می‌دهیم، به طور متوسط، T تعداد دوره‌ای پیش‌بینی است، تنها با استفاده از فراخوانی O (log T)به هر تکرار تصادفی،.
اینها اولین نتایجی هستند که برای به دست آوردن هر دو پیچیدگی متوسط اوراکل O (log T)(یا حتی چند لگاریتمی در T)و a - متاسفانه O (T - c)برای C [ ۰ ] ثابت برای هر دو متغیر به دست می‌آیند.
ترجمه شده با 
- مقاله Computer Science Applications
- ترجمه مقاله Computer Science Applications
- مقاله کاربردهای علوم کامپیوتر
- ترجمه مقاله کاربردهای علوم کامپیوتر
- مقاله General Mathematics
- ترجمه مقاله General Mathematics
- مقاله ریاضیات عمومی
- ترجمه مقاله ریاضیات عمومی
- مقاله Management Science and Operations Research
- ترجمه مقاله Management Science and Operations Research
- مقاله علوم مدیریت و پژوهش عملیاتی
- ترجمه مقاله علوم مدیریت و پژوهش عملیاتی
ترجمه کنید