Europt 2024
21st Conference on Advances in
Continuous Optimization

Conservation Laws for Gradient Flows

Understanding the geometric properties of gradient descent dynamics is a key ingredient in deciphering the recent success of very large machine learning models. A striking observation is that trained over-parameterized models retain some properties of the optimization initialization. This "implicit bias" is believed to be responsible for some favorable properties of the trained models and could explain their good generalization properties. In this talk I will first rigorously expose the definition and basic properties of "conservation laws", which are maximal sets of independent quantities conserved during gradient flows of a given model (e.g. of a ReLU network with a given architecture) with any training data and any loss. Then I will explain how to find the exact number of these quantities by performing finite-dimensional algebraic manipulations on the Lie algebra generated by the Jacobian of the model. In the specific case of linear and ReLu networks, this procedure recovers the conservation laws known in the literature, and prove that there are no other laws. The associated paper can be found here and the open source code is here. This is a joint work with Sibylle Marcotte and Rémi Gribonval.

New results on the multi-dimensional linear discriminant analysis problem

Fisher linear discriminant analysis (LDA) is a well-known technique for dimensionality reduction and classification. The method was first formulated in 1936 by Fisher. We present three different formulations of the multi-dimensional problem and show why two of them are equivalent. We then prove a rate of convergence of the form $O(q^{k^2}))$ for solving the third model. Finally, we consider the max-min LDA problem in which the objective function seeks to maximize the minimum separation among all distances between all classes. We show how this problem can be reduced into a quadratic programming problem with nonconvex polyhedral constraints and describe an effective branch and bound method for its solution. Joint work with Raz Sharon.

A Universal Framework for Federated (Convex) Optimization

Federated learning has emerged as an important paradigm in modern large-scale machine learning. Unlike traditional centralized learning, where models are trained using large datasets stored on a central server, federated learning keeps the training data distributed across many clients, such as phones, network sensors, hospitals, or other local information sources. In this setting, communication-efficient optimization algorithms are crucial.

We provide a brief introduction to local update methods developed for federated optimization and discuss their worst-case complexity. Surprisingly, these methods often perform much better in practice than predicted by theoretical analyses using classical assumptions. Recent years have revealed that their performance can be better described using refined notions that capture the similarity among client objectives.

In this talk, we introduce a generic framework based on a distributed proximal point algorithm, which consolidates many of our insights and allows for the adaptation of arbitrary centralized optimization algorithms to the convex federated setting (even with acceleration). Our theoretical analysis shows that the derived methods enjoy faster convergence if the similarity among clients is high.

Based on joint work with Xiaowen Jiang and Anton Rodomanov.

Multiobjective optimization, uncertainty, and a bit of set optimization

In many applications one has to deal with various difficulties at the same time, like uncertain data or several competing objective functions. For instance, for the integration of neighborhood networks into overarching distributing energy networks, a pure optimization of the neighborhood networks under an externally defined weighting of the relevant targets does not adequately model the problem. Moreover, uncertainties in the form of fluctuations or other disturbances can appear and a found solution has to be robust against that. A robust approach to uncertain multiobjective optimization corresponds to solving a set-valued optimization problem. However, it is a very difficult task to solve these optimization problems even for specific cases..

In this talk, we give a short introduction and motivation for multiobjective optimization. In case of uncertainties, a family of parametrized multiobjective optimization problems has to be examined and we discuss approaches on how this is done in the literature. Thereby, basic concepts of set optimization are needed, i.e., of optimization with a set-valued objective function. For that reason, we also provide a short introduction to the main optimality concepts and to new solution approaches used in set optimization. We combine everything for obtaining a solvable reformulation of an uncertain multiobjective problem using a robust approach which extends the classical epigraphical reformulation from single-objective optimization to multiple objectives.