Stochastic Block-Coordinate Gradient Projection Algorithms for Submodular Maximization
المؤلفون المشاركون
Wu, Qingtao
Zheng, Ruijuan
Zhang, Mingchuan
Zhu, Junlong
Li, Zhigang
Zhang, Qikun
المصدر
العدد
المجلد 2018، العدد 2018 (31 ديسمبر/كانون الأول 2018)، ص ص. 1-11، 11ص.
الناشر
Hindawi Publishing Corporation
تاريخ النشر
2018-12-05
دولة النشر
مصر
عدد الصفحات
11
التخصصات الرئيسية
الملخص EN
We consider a stochastic continuous submodular huge-scale optimization problem, which arises naturally in many applications such as machine learning.
Due to high-dimensional data, the computation of the whole gradient vector can become prohibitively expensive.
To reduce the complexity and memory requirements, we propose a stochastic block-coordinate gradient projection algorithm for maximizing continuous submodular functions, which chooses a random subset of gradient vector and updates the estimates along the positive gradient direction.
We prove that the estimates of all nodes generated by the algorithm converge to some stationary points with probability 1.
Moreover, we show that the proposed algorithm achieves the tight (pmin/2F⁎-ϵ) approximation guarantee after O(1/ϵ2) iterations for DR-submodular functions by choosing appropriate step sizes.
Furthermore, we also show that the algorithm achieves the tight (γ2/1+γ2pminF⁎-ϵ) approximation guarantee after O(1/ϵ2) iterations for weakly DR-submodular functions with parameter γ by choosing diminishing step sizes.
نمط استشهاد جمعية علماء النفس الأمريكية (APA)
Li, Zhigang& Zhang, Mingchuan& Zhu, Junlong& Zheng, Ruijuan& Zhang, Qikun& Wu, Qingtao. 2018. Stochastic Block-Coordinate Gradient Projection Algorithms for Submodular Maximization. Complexity،Vol. 2018, no. 2018, pp.1-11.
https://search.emarefa.net/detail/BIM-1133310
نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)
Li, Zhigang…[et al.]. Stochastic Block-Coordinate Gradient Projection Algorithms for Submodular Maximization. Complexity No. 2018 (2018), pp.1-11.
https://search.emarefa.net/detail/BIM-1133310
نمط استشهاد الجمعية الطبية الأمريكية (AMA)
Li, Zhigang& Zhang, Mingchuan& Zhu, Junlong& Zheng, Ruijuan& Zhang, Qikun& Wu, Qingtao. Stochastic Block-Coordinate Gradient Projection Algorithms for Submodular Maximization. Complexity. 2018. Vol. 2018, no. 2018, pp.1-11.
https://search.emarefa.net/detail/BIM-1133310
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references
رقم السجل
BIM-1133310
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر