Stochastic Methods for Convex Optimization with "Difficult" Constraints