الملخص
In online inverse linear optimization, a learner recommends an action and then observes the choice of an expert who maximizes a fixed, unknown linear objective on $\mathbb{R}^{d}$; the goal is to learn to optimize this objective without observing it. Sakaue recently obtained the optimal regret $O(\sqrt d)$ with a randomized algorithm making $(dT)^{O(d)}$ linear optimizations per round, and asked whether it can be attained in polynomial time. We answer positively: our deterministic algorithm has regret $O(\sqrt d)$ for every horizon $T$ and runs in time polynomial in $d$ and $T$. It is a variant of the variable-metric algorithms of Sakaue et al.\ and Cai et al., in which a metric update is revoked once the query point moves far enough from where the update was made.
الكلمات المفتاحية
الموضوع
بيانات النشر
- المجلة
- غير متاح
- وصول مفتوح
- وصول مفتوح أخضر
اقتبس هذه المقالة
APA 7
Gupta, A., Guruganesh, G., Lin, H., Mirrokni, V., Leme, R. P., & Woodruff, D. P. (2026). Optimal and Efficient Online Inverse Optimization. https://omanscience.com/ar/articles/optimal-and-efficient-online-inverse-optimization
MLA 9
Gupta, Anupam, et al. "Optimal and Efficient Online Inverse Optimization." https://omanscience.com/ar/articles/optimal-and-efficient-online-inverse-optimization.
شيكاغو (المؤلف–التاريخ)
Gupta, Anupam, Guru Guruganesh, Honghao Lin, Vahab Mirrokni, Renato Paes Leme, and David P. Woodruff. 2026. "Optimal and Efficient Online Inverse Optimization." https://omanscience.com/ar/articles/optimal-and-efficient-online-inverse-optimization.
هارفارد
Gupta, A., Guruganesh, G., Lin, H., Mirrokni, V., Leme, R. P. and Woodruff, D. P. (2026) 'Optimal and Efficient Online Inverse Optimization', Available at: https://omanscience.com/ar/articles/optimal-and-efficient-online-inverse-optimization.
فانكوفر
Gupta A, Guruganesh G, Lin H, Mirrokni V, Leme RP, Woodruff DP. Optimal and Efficient Online Inverse Optimization. https://omanscience.com/ar/articles/optimal-and-efficient-online-inverse-optimization
IEEE
A. Gupta, G. Guruganesh, H. Lin, V. Mirrokni, R. P. Leme, and D. P. Woodruff, "Optimal and Efficient Online Inverse Optimization," https://omanscience.com/ar/articles/optimal-and-efficient-online-inverse-optimization.