Tight Complexity Bounds for Optimizing Composite Objectives Nathan Srebro Toyota Technological Institute at Chicago Toyota Technological Institute at Chicago Chicago, IL, 60637