Dueling Convex Optimization

Aadirupa Saha, Tomer Koren, Yishay Mansour

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

We address the problem of convex optimization with preference (dueling) feedback. Like the traditional optimization objective, the goal is to find the optimal point with the least possible query complexity, however, without the luxury of even a zeroth order feedback. Instead, the learner can only observe a single noisy bit which is win-loss feedback for a pair of queried points based on their function values. The problem is certainly of great practical relevance as in many real-world scenarios, such as recommender systems or learning from customer preferences, where the system feedback is often restricted to just one binary-bit preference information. We consider the problem of online convex optimization (OCO) solely by actively querying {0, 1} noisy-comparison feedback of decision point pairs, with the objective of finding a near-optimal point (function minimizer) with the least possible number of queries. For the non-stationary OCO setup, where the underlying convex function may change over time, we prove an impossibility result towards achieving the above objective. We next focus only on the stationary OCO problem, and our main contribution lies in designing a normalized gradient descent based algorithm towards finding a ε-best optimal point. Towards this, our algorithm is shown to yield a convergence rate of Õ(/εν2) (ν being the noise parameter) when the underlying function is β-smooth. Further we show an improved convergence rate of just Õ(/αν2 log1 ε ) when the function is additionally also α-strongly convex.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفProceedings of the 38th International Conference on Machine Learning, ICML 2021
الصفحات9245-9254
عدد الصفحات10
رقم المعيار الدولي للكتب (الإلكتروني)9781713845065
حالة النشرنُشِر - 2021
الحدث38th International Conference on Machine Learning, ICML 2021 - Virtual, Online
المدة: ١٨ يوليو ٢٠٢١٢٤ يوليو ٢٠٢١

سلسلة المنشورات

الاسمProceedings of Machine Learning Research
مستوى الصوت139

!!Conference

!!Conference38th International Conference on Machine Learning, ICML 2021
المدينةVirtual, Online
المدة١٨/٠٧/٢١٢٤/٠٧/٢١

All Science Journal Classification (ASJC) codes

  • !!Artificial Intelligence
  • !!Software
  • !!Control and Systems Engineering
  • !!Statistics and Probability

بصمة

أدرس بدقة موضوعات البحث “Dueling Convex Optimization'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا