Continuous optimization has become a prevalent tool across the sciences and engineering. Modern applications have displayed steady growth in problem sizes. Such sizes often prohibit the use of classical algorithmic solutionsthat heavily rely on costly operations, such as matrix inversion, and do not scale well. To counter this phenomenon practitioners have turned their focus to simpler first-order heuristics, such as gradient descent, that are often highly successful, yet are not well-understood. In this thesis, we study a few nonsmooth settings where simple algorithms are provably convergent. We start with the problem of detecting infeasibility of large-scale linear programming problems using the primal-dual hybrid gradient method of Chambolle and Pock (2011). The literature on PDHG has focused chiefly on feasible problems. When the problem is not feasible, the iterates of the algorithm do not converge. In this scenario, we show that the iterates diverge at a controlled rate towards a well-defined ray. Leveraging this fact, we design a simple scheme to extract certificates of infeasibility from the iterates. We then turn to unconstrained convex optimization and consider the classic {proximal bundle methods}, an algorithmic family dating back to the 70s. We prove convergence rates for bundle methods under a variety of assumptions. In particular, we show that these algorithms automatically adapt to problem regularity, exhibiting faster convergence rates. We complement these findings with a new parallelizable variant of the bundle method that attains near-optimal rates without prior knowledge of function parameters. These results improve on the limited existing convergence rates and provide a unified approach across problem settings and algorithmic details. After that, we study rapid local convergence guarantees for nonconvex formulations of low-rank matrix recovery problems, a problem family that includes phase retrieval, blind deconvolution, matrix completion, and robust PCA. Standard approaches for solving these problems use smooth penalty functions and often exhibit an undesirable phenomenon: the condition number, classically defined, scales poorly with the dimension. In contrast, we show that natural nonsmooth penalty formulations have two clear advantages: (1) they do not suffer from the same type of ill-conditioning, and (2) they are robust against noise and gross outliers. Consequently, we prove that off-the-shelf algorithms for nonsmooth optimization converge at a rapid dimension-independent rate when initialized close to the solution, even when a constant fraction of the measurements are adversarially corrupted. To complement these local convergence guarantees, we turn to the question of escaping saddle points of nonsmooth functions. Recent work has shown that stochastically perturbed gradient methods can efficiently strict saddle points of smooth functions. We extend this body of work to nonsmooth optimization, by analyzing an inexact analogue of a stochastically perturbed gradient method applied to the Moreau envelope. The main conclusion is that a variety of algorithms can escape strict saddle points of the Moreau envelope at a controlled rate.