  Robust optimization (RO) is a powerful paradigm for decision making under
uncertainty. Existing algorithms for solving RO, including the reformulation
approach and the cutting-plane method, do not scale well, hindering the
application of RO to large-scale decision problems. In this paper, we devise a
first-order algorithm for solving RO based on a novel max-min-max perspective.
Our algorithm operates directly on the model functions and sets through the
subgradient and projection oracles, which enables the exploitation of problem
structures and is especially suitable for large-scale RO. Theoretically, we
prove that the oracle complexity of our algorithm for attaining an
$\varepsilon$-approximate optimal solution is $\mathcal{O}(\varepsilon^{-3})$
or $\mathcal{O}(\varepsilon^{-2})$, depending on the smoothness of the model
functions. The algorithm and its theoretical results are then extended to RO
with projection-unfriendly uncertainty sets. We also show via extensive
numerical experiments that the proposed algorithm outperforms the reformulation
approach, the cutting-plane method and two other recent first-order algorithms.
