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
משך הזמן: 18 יולי 202124 יולי 2021

סדרות פרסומים

שםProceedings of Machine Learning Research
כרך139

כנס

כנס38th International Conference on Machine Learning, ICML 2021
עירVirtual, Online
תקופה18/07/2124/07/21

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1702???
  • ???subjectarea.asjc.1700.1712???
  • ???subjectarea.asjc.2200.2207???
  • ???subjectarea.asjc.2600.2613???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Dueling Convex Optimization'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי