On Matching Pursuit and Coordinate Descent

Two popular examples of first-order optimization methods over linear spaces are coordinate descent and matching pursuit algorithms, with their randomized variants. While the former targets the optimization by moving along coordinates, the latter considers a generalized notion of directions. Exploiting the connection between the two algorithms, we present a unified analysis of both, providing affine invariant sublinear O(1/t) rates on smooth objectives and linear convergence on strongly convex objectives. As a byproduct of our affine invariant analysis of matching pursuit, our rates for steepest coordinate descent are the tightest known. Furthermore, we show the first accelerated convergence rate O(1/t^2) for matching pursuit and steepest coordinate descent on convex objectives.

Adaptation in Stochastic Algorithms: From Nonsmooth Optimization to Min-Max Problems and Beyond

Ahmet Alacaoglu

Stochastic gradient descent (SGD) and randomized coordinate descent (RCD) are two of the workhorses for training modern automated decision systems. Intriguingly, convergence properties of these methods are not well-established as we move away from the specific case of smooth minimization. In this dissertation, we focus on related problems of nonsmooth optimization and min-max optimization to improve the theoretical understanding of stochastic algorithms.First, we study SGD-based adaptive algorithms and propose a regret analysis framework overcoming the limitations of the existing ones in the convex case. In the nonconvex case, we prove convergence of an adaptive gradient algoritm for solving constrained weakly convex optimization, generalizing the previously known results on unconstrained smooth optimization. We also propose an algorithm combining Nesterov's smoothing with SGD to solve convex problems with infinitely many linear constraints, with optimal rates.Then, we move on to convex-concave min-max problems with bilinear coupling and analyze primal-dual coordinate descent (PDCD) algorithms. We obtain the first PDCD methods with the optimal

\mathcal{O}(1/k)

rate on the the standard optimality measure expected primal-dual gap, which was an open question since 2014. Our analysis also aims to explain the practical behavior of these algorithms by showing that the last iterate enjoys adaptive linear convergence without altering the parameters, depending on a certain error bound condition. Furthermore, we propose an algorithm combining the favorable properties of two branches of PDCD methods: the new method uses large step sizes with dense data and its per-iteration cost depends on the number of nonzeros of the data matrix. Thanks to these unique properties, this method enjoys compelling practical performance complementing its rigorous theoretical guarantees.Next, we consider monotone variational inequalities that generalize convex-concave min-max problems with nonbilinear coupling. We introduce variance reduced algorithms that converge under the same set of assumptions as their deterministic counterparts and improve the best-known complexities for solving convex-concave min-max problems with finite-sum structure. Optimality of our algorithms for this problem class is established in a recent work via matching lower bounds. Finally, we show our preliminary results on policy optimization methods for solving two player zero-sum Markov games for competitive reinforcement learning (RL). Even though this is a nonconvex-nonconcave min-max problem in general, thanks to the special structure, it is tractable to find an approximate Nash equilibrium. We introduce an algorithm that improves the best-known sample complexity of policy gradient methods. This development combines tools from RL and stochastic primal-dual optimization, showing the importance of techniques from convex-concave optimization.

EPFL2021

Convex Optimization using Sparsified Stochastic Gradient Descent with Memory

Jean-Baptiste Francis Marie Juliette Cordonnier

The interest for distributed stochastic optimization has raised to train complex Machine Learning models with more data on distributed systems. Increasing the computation power speeds up the training but it faces a communication bottleneck between workers which hurts the scale-up of these distributed algorithms. Previous work tried to address this issue through quantization by broadcasting low precision updates (Seide et al., 2014; Alistarh et al., 2017) or through sparsification by sharing only the most important coordinates to update (Aji and Heafield, 2017; Lin et al., 2018). Even though the sparsifica- tion method works well in practice, it lacked a theoretical proof until now. We propose a sparsification scheme for SGD where only a small constant number of coordinates are applied at each iteration. The amount of data to be communicated is drastically reduced while the O(1/T ) convergence rate of vanilla SGD is preserved. Our concise proof extends to parallel setting and gains a linear speed up in the number of workers. We exper- iment with sparsified SGD with memory in C++ and Python, and show the excellent convergence properties for top-k and random-k operators. Our scheme outperforms QSGD in progress per number of bits sent. It also opens the path to using lock-free asynchronous parallelization (e.g. Hogwild! Niu et al. (2011)) on dense problems as the sparsity of the gradient updates is enforced.

2018

Uncooperative Rendezvous in Space: Design of an Electronic Architecture for High Performance Avionic with Multi Sensor Input and Intensive Data Rate.

Michaël Yannick Juillard

Active Debris Removal missions consist of sending a satellite in space and removing one or more debris from their current orbit. A key challenge is to obtain information about the uncooperative target. By gathering the velocity, position, and rotation of the desired object, the satellite is able to plan its trajectory and define the sequence of approach. It requires the use of a variety of sensors with often a high data rate. For this task, a dedicated payload computer is envisioned with the responsibility of processing the information from the various rendezvous sensors. This component has the goal to provide meaningful information to the main satellite computer about the targeted debris. The focus of this work is on the data processing, the number of elements, and the electrical energy with constraints due to internal communication.First, an avionic testbench was built at the EPFL Space Center to assess early hardware and software architectures. The goal is to enable Hardware-In-the-Loop testing while developing the payload computer. A communication data bus has been implemented between the Platform and the Payload On-Board Computer. Emphasis was placed on the reliability of the high-level protocol and multiple concepts for improvement were analyzed.In a second phase, the testbench has been extended to support other data buses. The aim was to develop a reliable and efficient backup or fall-back data bus in case of failure in the main link. Four data buses have been tested with extensive analyses on their resilience to error and the efficiency of their data exchange.In parallel, extensive work has been performed to develop a simulation and optimization tool. Its goal is to support the design of payload avionic architectures for ADR missions by providing trade-offs and analyses. In the first iteration, a simulator has been created with instances of various high-level elements modeled.The second iteration introduced the additional dimension of optimization. It is trying to determine the best set of instruments and algorithms to use. With this capability, numerous analyses have been conducted on the influence of various parameters linked to the general optimizer behavior. It allows us to better understand the strength and limitations of the tool.The third step regarding the tool was to start its verification. The task has been to develop an Hardware-In-the-Loop architecture to compare its behavior with the results of the optimizer. The implementation of various mock-up algorithms enables the verification of their models in the tool. These analyses guarantee the feasibility of the outputted solution.The last part was dedicated to the creation and analysis of a realistic payload avionic architecture. The goal was to test the capability of the tool with hardware elements inspired by actual components. This work has shown the procedure to efficiently use the tool in the design phase of a mission.In conclusion, the work on the communication between the Payload and the Platform On-Board Computer has brought valuable lessons and experiences to the projects. They can now be used for the establishment of the high-level protocol into ClearSpace-1 flight software. In addition, the optimizer created allows tackling the design of complex payload avionic architecture where mass saving and processing resources are crucial. It is an essential point to develop a highly efficient payload computer for an Active Debris Removal satellite.

EPFL2022