We present new results for the Frank-Wolfe (also known as the ``conditional gradient") method. Using proof techniques motivated from dual averaging methods, we derive computational guarantees for arbitrary step-size sequences. Our results include guarantees for both duality gaps and the so-called Wolfe gaps. We then examine these guarantees for several different step-size sequences, including those that depend naturally on the warm-start quality of the initial (and subsequent) iterates. Furthermore, we present complexity bounds in the presence of approximate computation of gradients and subproblems.