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, أسبانيا
المدة: ١٢ ديسمبر ٢٠١١١٤ ديسمبر ٢٠١١

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

الاسمAdvances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011

!!Conference

!!Conference25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011
الدولة/الإقليمأسبانيا
المدينةGranada
المدة١٢/١٢/١١١٤/١٢/١١

All Science Journal Classification (ASJC) codes

  • !!Information Systems

بصمة

أدرس بدقة موضوعات البحث “Approximating semidefinite programs in sublinear time'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا