  Many recent successes of machine learning went hand in hand with advances in
optimization. The exchange of ideas between these fields has worked both ways,
with machine learning building on standard optimization procedures such as
gradient descent, as well as with new directions in the optimization theory
stemming from machine learning applications. In this thesis, we discuss new
developments in optimization inspired by the needs and practice of machine
learning, federated learning, and data science. In particular, we consider
seven key challenges of mathematical optimization and develop a solution to
each.
  Our first contribution is the resolution of a key open problem in Federated
Learning: we establish the first theoretical guarantees for the famous Local
SGD algorithm in the heterogeneous data regime. As the second challenge, we
close the gap between the upper and lower bounds for the theory of two
algorithms known as Random Reshuffling (RR) and Shuffle-Once that are widely
used in practice, and set as the default data selection strategies for SGD in
modern machine learning software. Our third contribution can be seen as a
combination of our new theory for proximal RR and Local SGD yielding a new
algorithm, which we call FedRR. Unlike Local SGD, FedRR can provably beat
gradient descent in communication complexity in the heterogeneous data regime.
The fourth challenge is related to the class of adaptive methods. In
particular, we present the first parameter-free stepsize rule for gradient
descent that provably works for any locally smooth convex objective. The fifth
challenge is the development of an algorithm for distributed optimization with
quantized updates that preserves linear convergence of gradient descent.
Finally, in our sixth and seventh challenges, we develop new VR mechanisms
applicable to the non-smooth setting based on proximal operators.
