  We develop model-based methods for solving stochastic convex optimization
problems, introducing the approximate-proximal point, or aProx, family, which
includes stochastic subgradient, proximal point, and bundle methods. When the
modeling approaches we propose are appropriately accurate, the methods enjoy
stronger convergence and robustness guarantees than classical approaches, even
though the model-based methods typically add little to no computational
overhead over stochastic subgradient methods. For example, we show that
improved models converge with probability 1 and enjoy optimal asymptotic
normality results under weak assumptions; these methods are also adaptive to a
natural class of what we term easy optimization problems, achieving linear
convergence under appropriate strong growth conditions on the objective. Our
substantial experimental investigation shows the advantages of more accurate
modeling over standard subgradient methods across many smooth and non-smooth
optimization problems.
