  Memory is a key computational bottleneck when solving large-scale convex
optimization problems such as semidefinite programs (SDPs). In this paper, we
focus on the regime in which storing an $n\times n$ matrix decision variable is
prohibitive. To solve SDPs in this regime, we develop a randomized algorithm
that returns a random vector whose covariance matrix is near-feasible and
near-optimal for the SDP. We show how to develop such an algorithm by modifying
the Frank-Wolfe algorithm to systematically replace the matrix iterates with
random vectors. As an application of this approach, we show how to implement
the Goemans-Williamson approximation algorithm for \textsc{MaxCut} using
$\mathcal{O}(n)$ memory in addition to the memory required to store the problem
instance. We then extend our approach to deal with a broader range of
structured convex optimization problems, replacing decision variables with
random extreme points of the feasible region.
