  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.
