Structured Learning from Cheap Data