{"id":667467,"date":"2020-06-16T11:09:30","date_gmt":"2020-06-16T18:09:30","guid":{"rendered":"https:\/\/new-cm-edgedigital.pages.dev\/en-us\/research\/?post_type=msr-research-item&p=667467"},"modified":"2020-06-16T11:09:30","modified_gmt":"2020-06-16T18:09:30","slug":"an-improved-cutting-plane-method-for-convex-optimization-convex-concave-games-and-its-applications","status":"publish","type":"msr-research-item","link":"https:\/\/new-cm-edgedigital.pages.dev\/en-us\/research\/publication\/an-improved-cutting-plane-method-for-convex-optimization-convex-concave-games-and-its-applications\/","title":{"rendered":"An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications"},"content":{"rendered":"

Given a separation oracle for a convex set\u00a0K<\/span>\u2282<\/span>R<\/span><\/span><\/span>n<\/span><\/span><\/span><\/span><\/span>\u00a0that is contained in a box of radius\u00a0R<\/span><\/span><\/span><\/span>, the goal is to either compute a point in\u00a0K<\/span><\/span><\/span><\/span>\u00a0or prove that\u00a0K<\/span><\/span><\/span><\/span>\u00a0does not contain a ball of radius\u00a0\u03f5<\/span><\/span><\/span><\/span>. We propose a new cutting plane algorithm that uses an optimal\u00a0O<\/span>(<\/span>n<\/span>log<\/span><\/span>(<\/span>\u03ba<\/span>)<\/span>)<\/span><\/span><\/span><\/span>\u00a0evaluations of the oracle and an additional\u00a0O<\/span>(<\/span>n<\/span>2<\/span><\/span>)<\/span><\/span><\/span><\/span>\u00a0time per evaluation, where\u00a0\u03ba<\/span>=<\/span>n<\/span>R<\/span>\/<\/span><\/span><\/span>\u03f5<\/span><\/span><\/span><\/span>.<\/p>\n