Acceleration in first-order optimization methods: promenading beyond convexity or smoothness, and applications - Martinez Rubio, D (2021)
Acceleration in optimization is a term that is generally applied to optimization algorithms presenting some common methodology that enjoy convergence rates that improve over other more simple algorithms for the same problem. For example, Nesterov's Accelerated Gradient Descent improves over the gradient descent method for the optimization of smooth and convex functions. In this thesis, we investigate the acceleration phenomenon and its applications for three previously studied research questions in optimization and online learning: geodesically convex accelerated optimization in Riemannian manifolds, approximation of a proportional fair solution under positive linear constraints, also known as the 1-fair packing problem, and regret minimization in a decentralized cooperative stochastic multi-armed bandit problem with no reward collisions. We improve over previously studied approaches by using acceleration as a key element in all of our algorithms: we obtain an accelerated method for some non-convex problems in the first case, we exploit a local decrease condition of our problem in the second case, avoiding the use of poor and non-global smoothness, and in the third problem, we design a solution for which we can effectively apply an accelerated gossip protocol to spread and use information.