We develop a variant of the stochastic prox-linear method for minimizing theConditional Value-at-Risk (CVaR) objective. CVaR is a risk measure focused onminimizing worst-case performance, defined as the average of the top quantileof the losses. In machine learning, such a risk measure is useful to train morerobust models. Although the stochastic subgradient method (SGM) is a naturalchoice for minimizing the CVaR objective, we show that our stochasticprox-linear (SPL+) algorithm can better exploit the structure of the objective,while still providing a convenient closed form update. Our SPL+ method alsoadapts to the scaling of the loss function, which allows for easier tuning. Wethen specialize a general convergence theorem for SPL+ to our setting, and showthat it allows for a wider selection of step sizes compared to SGM. We supportthis theoretical finding experimentally.