Approximating semidefinite programs in sublinear time

Dan Garber, Elad Hazan

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

In recent years semidefinite optimization has become a tool of major importance in various optimization and machine learning problems. In many of these problems the amount of data in practice is so large that there is a constant need for faster algorithms. In this work we present the first sublinear time approximation algorithm for semidefinite programs which we believe may be useful for such problems in which the size of data may cause even linear time algorithms to have prohibitive running times in practice. We present the algorithm and its analysis alongside with some theoretical lower bounds and an improved algorithm for the special problem of supervised learning of a distance metric.

שפה מקוריתאנגלית
כותר פרסום המארחAdvances in Neural Information Processing Systems 24
כותר משנה של פרסום המארח25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011
מוציא לאורNeural Information Processing Systems
מסת"ב (מודפס)9781618395993
סטטוס פרסוםפורסם - 2011
אירוע25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011 - Granada, ספרד
משך הזמן: 12 דצמ׳ 201114 דצמ׳ 2011

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

שםAdvances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011

כנס

כנס25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011
מדינה/אזורספרד
עירGranada
תקופה12/12/1114/12/11

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1710???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Approximating semidefinite programs in sublinear time'. יחד הם יוצרים טביעת אצבע ייחודית.

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