  Convex risk measures play a foundational role in the area of stochastic
optimization. However, in contrast to risk neutral models, their applications
are still limited due to the lack of efficient solution methods. In particular,
the mean $L_p$ semi-deviation is a classic risk minimization model, but its
solution is highly challenging due to the composition of concave-convex
functions and the lack of uniform Lipschitz continuity. In this paper, we
discuss some progresses on the design of efficient algorithms for $L_p$ risk
minimization, including a novel lifting reformulation to handle the
concave-convex composition, and a new stochastic approximation method to handle
the non-Lipschitz continuity. We establish an upper bound on the sample
complexity associated with this approach and show that this bound is not
improvable for $L_p$ risk minimization in general.
