论文标题
Oracle模型中凸优化的一种简单方法
A Simple Method for Convex Optimization in the Oracle Model
论文作者
论文摘要
我们提供了一种简单而自然的方法，用于计算大约最佳解决方案，以最大程度地减少凸套$ f $ f $ y seavex set $ k $的$ k $。我们的方法利用了弗兰克 - 沃尔夫算法，对$ k $的有效不平等和$ f $的亚级别的锥体。假设$ f $是$ l $ -lipschitz，并且$ k $包含一个半径$ r $的球，并且包含在原点中心的半径$ r $中，使用$ o（\ frac {（rl）^2} {\ varepsilon^2}}输出一个点$ x \在满足$ f（x）\ leq \ varepsilon + \ min_ {z \ in k} f（z）$中的$ f（x）\ leq \ varepsilon + \ varepsilon + \ varepsilon + x $。 我们的算法易于实现，我们认为它可以作为现有切割平面方法的有用替代方法。作为对此的证据，我们表明，它可以在迭代计数中与基于标准LP的切割平面方法和分析中心切割平面方法进行比较，该方法在组合，半菲尼特和机器学习实例的测试床上进行了比较。
We give a simple and natural method for computing approximately optimal solutions for minimizing a convex function $f$ over a convex set $K$ given by a separation oracle. Our method utilizes the Frank--Wolfe algorithm over the cone of valid inequalities of $K$ and subgradients of $f$. Under the assumption that $f$ is $L$-Lipschitz and that $K$ contains a ball of radius $r$ and is contained inside the origin centered ball of radius $R$, using $O(\frac{(RL)^2}{\varepsilon^2} \cdot \frac{R^2}{r^2})$ iterations and calls to the oracle, our main method outputs a point $x \in K$ satisfying $f(x) \leq \varepsilon + \min_{z \in K} f(z)$. Our algorithm is easy to implement, and we believe it can serve as a useful alternative to existing cutting plane methods. As evidence towards this, we show that it compares favorably in terms of iteration counts to the standard LP based cutting plane method and the analytic center cutting plane method, on a testbed of combinatorial, semidefinite and machine learning instances.
