Abstract: 

Classical complexity theory characterizes the difficulty of optimization problems through global worst-case parameters---Lipschitz constants, smoothness, dimension---and derives bounds that are tight over the entire problem class. Yet algorithms routinely outperform these predictions in practice, prompting the question of which other structural properties may determine algorithm efficiency. In this talk, I will present a line of research showing that local structural properties of optimization problems can reveal tractability hidden by worst-case analysis. I will discuss two interconnected threads. The first develops a new complexity framework based on local subgradient variation, which captures when optimization is substantially easier than global bounds suggest. A striking consequence is that parallelization can provably accelerate convex optimization for broad problem classes---including those underlying classical lower bounds---overturning long-standing conventional wisdom. The second thread applies a similar "closer look" philosophy to robust learning: I will discuss how local geometric structure enables polynomial-time algorithms with best-possible error guarantees for learning generalized linear and single-index models under adversarial noise and distributional shifts. I will close with future directions toward a broader theory of optimization that explains efficiency beyond the worst case.