Joint IOL and COGA research seminar 2020–2021

We study a dynamic traffic assignment model, where agents base their instantaneous routing decisions on real-time delay predictions. We formulate a mathematically concise model and derive properties of the predictors that ensure a dynamic prediction equilibrium exists. We demonstrate the versatility of our framework by showing that it subsumes the well-known full information and instantaneous information models, in addition to admitting further realistic predictors as special cases. We complement our theoretical analysis by an experimental study, in which we systematically compare the induced average travel times of different predictors, including a machine-learning model trained on data gained from previously computed equilibrium flows, both on a synthetic and a real road network.

Methods and applications of Machine Learning have made impressive progress in recent years. One approach is neural network, a brain-inspired learning model that can be trained to perform complex and diverse tasks. In order to deliver good results, the training of such a network is crucial.

Given a neural network, training data, and a threshold, finding weights for the neural network such that the total error is below the threshold is known to be NP-hard. In this talk, we determine the algorithmic complexity of this fundamental problem precisely, by showing that it is complete for the complexity class existential theory of the reals (ER).

This means that, up to polynomial time reductions, the problem is equivalent to deciding whether a system of polynomial equations and inequalities with integer coefficients and real unknowns has a solution. If, as widely expected, ER is strictly larger than NP, our work implies that the problem of training neural networks is not even in NP.

Neural networks are usually trained using some variation of backpropagation. The result of this paper offers an explanation why techniques commonly used to solve big instances of NP-complete problems seem not to be of use for this task. Examples of such techniques are SAT solvers, IP solvers, local search, dynamic programming, to name a few general ones.

The talk is based on joint work with Mikkel Abrahamsen and Tillman Miltzow.

The mathematical approaches for modeling dynamic traffic can roughly be divided into two categories: discrete packet routing models and continuous flow over time models. Despite very vital research activities on models in both categories, the connection between these approaches was poorly understood so far. We build this connection by specifying a (competitive) packet routing model, which is discrete in terms of flow and time, and by proving its convergence to flows over time with deterministic queuing. More precisely, we prove that the limit of the convergence process, when decreasing the packet size and time step length in the packet routing model, constitutes a flow over time with multiple commodities. The convergence result implies the existence of approximate equilibria in the competitive version of the packet routing model. This is of significant interest as exact pure Nash equilibria, similar to almost all other competitive models, cannot be guaranteed in the multi-commodity setting.

Moreover, the introduced packet routing model with deterministic queuing is very application-oriented as it is based on the network loading module of the agent-based transport simulation MATSim. As the present work is the first mathematical formalization of this simulation, it provides a theoretical foundation and an environment for provable mathematical statements for MATSim.

This is joint work with Leon Sering and Theresa Ziemke.

The lecture offers a concise overview of a master’s thesis on the penalised linear regression problem with squared lasso penalty. We derive its dual and optimality conditions and connect it to the well-known lasso problem. Based on the optimality conditions we study the solution path and briefly discuss an exact and an approximate homotopy algorithm.

An elimination tree for a connected graph G is a rooted tree on the vertices of G obtained by choosing a root x and recursing on the connected components of G−x to produce the subtrees of x. Elimination trees appear in many guises in computer science and discrete mathematics, and they are closely related to centered colorings and tree-depth. They also encode many interesting combinatorial objects, such as bitstrings, permutations and binary trees. We apply the recent Hartung-Hoang-Mütze-Williams combinatorial generation framework to elimination trees, and prove that all elimination trees for a chordal graph G can be generated by tree rotations using a simple greedy algorithm. This yields a short proof for the existence of Hamilton paths on graph associahedra of chordal graphs. Graph associahedra are a general class of high-dimensional polytopes introduced by Carr, Devadoss, and Postnikov, whose vertices correspond to elimination trees and whose edges correspond to tree rotations. As special cases of our results, we recover several classical Gray codes for bitstrings, permutations and binary trees, and we obtain a new Gray code for partial permutations. Our algorithm for generating all elimination trees for a chordal graph G can be implemented in time O(m+n) per generated elimination tree, where m and n are the number of edges and vertices of G, respectively. If G is a tree, we improve this to a loopless algorithm running in time O(1) per generated elimination tree. We also prove that our algorithm produces a Hamilton cycle on the graph associahedron of G, rather than just Hamilton path, if the graph G is chordal and 2-connected. Moreover, our algorithm characterizes chordality, i.e., it computes a Hamilton path on the graph associahedron of G if and only if G is chordal. This is joint work with Jean Cardinal (ULB) and Torsten Mütze (Warwick).

An embedding of a graph in a book, called book embedding, consists of a linear ordering of its vertices along the spine of the book and an assignment of its edges to the pages of the book, so that no two edges on the same page cross. The book thickness of a graph is the minimum number of pages over all its book embeddings. For planar graphs, a fundamental result is due to Yannakakis, who proposed an algorithm to compute embeddings of planar graphs in books with four pages. Our main contribution is a technique that generalizes this result to a much wider family of nonplanar graphs, which is characterized by a biconnected skeleton of crossing-free edges whose faces have bounded degree. Notably, this family includes all 1-planar and all optimal 2-planar graphs as subgraphs. We prove that this family of graphs has bounded book thickness, and as a corollary, we obtain the first constant upper bound for the book thickness of optimal 2-planar graphs.

This is joint work with Michael A. Bekos, Giordano Da Lozzo, Martin Gronemann, Fabrizio Montecchiani, and Chrysanthi Raftopoulou.

We consider the problem of maximizing a fractionally subadditive function under a knapsack constraint that grows over time. An incremental solution to this problem is given by an order in which to include the elements of the ground set, and the competitive ratio of an incremental solution is defined by the worst ratio over all capacities relative to an optimum solution of the corresponding capacity. We present an algorithm that finds an incremental solution of competitive ratio at most max{3.293*sqrt{M},2M}, under the assumption that the values of singleton sets are in the range [1,M], and we give a lower bound of max{2.449,M} on the attainable competitive ratio. In addition, we establish that our framework captures potential-based flows between two vertices, and we give a tight bound of 2 for the incremental maximization of classical flows with unit capacities.

We consider a selection problem with stochastic probing. There is a set of items whose values are drawn from independent distributions. The distributions are known in advance. Each item can be tested repeatedly. Each test reduces the uncertainty about the realization of its value. We study a testing model, where the first test reveals if the realized value is smaller or larger than the median of the underlying distribution. Subsequent tests allow to further narrow down the interval in which the realization is located. There is a limited number of possible tests, and our goal is to design near-optimal testing strategies that allow to maximize the expected value of the chosen item. We study both identical and non-identical distributions and develop polynomial-time algorithms with constant approximation factors in both scenarios.

This is joint work with Martin Hoefer and Daniel Schmand.

Deciding how to allocate the seats of a house of representatives is one of the most fundamental problems in the political organization of societies, and has been widely studied over already two centuries. The idea of proportionality is at the core of most approaches to tackle this problem, and this notion is captured by the divisor methods, such as the Jefferson/D’Hondt method. In a seminal work, Balinski and Demange extended the single-dimensional idea of divisor methods to the setting in which the seat allocation is simultaneously determined by two dimensions, and proposed the so-called biproportional apportionment method. The method, currently used in several electoral systems, is however limited to two dimensions and the question of extending it is considered to be an important problem both theoretically and in practice.

In this work we initiate the study of multidimensional proportional apportionment. We first formalize a notion of multidimensional proportionality that naturally extends that of Balinski and Demange. By means of analyzing an appropriate integer linear program we are able to prove that, in contrast to the two-dimensional case, the existence of multidimensional proportional apportionments is not guaranteed and deciding its existence is NP-complete. Interestingly, our main result asserts that it is possible to find approximate multidimensional proportional apportionments that deviate from the marginals by a small amount. The proof arises through the lens of discrepancy theory, mainly inspired by the celebrated Beck-Fiala Theorem. We finally evaluate our approach by using the data from the recent 2021 Chilean Constitutional Convention election.

This is joint work together with José Correa (UChile) and Victor Verdugo (UOH).

We formalize the concept of additive approximation schemes and apply it to load balancing problems on identical machines. Additive approximation schemes compute a solution with an absolute error in the objective of at most εh for some suitable parameter h and any given ε > 0. We consider the problem of assigning jobs to identical machines with respect to common load balancing objectives like makespan minimization, the Santa Claus problem (on identical machines), and the envy-minimizing Santa Claus problem. For these settings we present additive approximation schemes for h = p_max, the maximum processing time of the jobs. Our technical contribution is two-fold. First, we introduce a new relaxation based on integrally assigning slots to machines and fractionally assigning jobs to the slots. We refer to this relaxation as the slot-MILP. While it has a linear number of integral variables, we identify structural properties of (near-)optimal solutions, which allow us to compute those in polynomial time. The second technical contribution is a local-search algorithm which rounds any given solution to the slot-MILP, introducing an additive error on the machine loads of at most εpmax. This is joint work together with Lars Rohwedder (EPFL), Tjark Vredeveld (UM) and Andreas Wiese (UChile).

Propagation of linear constraints has become a crucial sub-routine in modern Mixed-Integer Programming (MIP) solvers. In practice, iterative algorithms with tolerance-based stopping criteria are used to avoid problems with slow or infinite convergence. However, these heuristic stopping criteria can pose difficulties for fairly comparing the efficiency of different implementations of iterative propagation algorithms in a real-world setting. Most significantly, the presence of unbounded variable domains in the problem formulation makes it difficult to quantify the relative size of reductions performed on them. In this work, we develop a method to measure—independently of the algorithmic design—the progress that a given iterative propagation procedure has made at a given point in time during its execution. Our measure makes it possible to study and better compare the behavior of bounds propagation algorithms for linear constraints. We apply the new measure to answer two questions of practical relevance:

1. We investigate to what extent heuristic stopping criteria can lead to premature termination on real-world MIP instances.
2. We compare a GPU-parallel propagation algorithm against a sequential state-of-the-art implementation and show that the parallel version is even more competitive in a real-world setting than originally reported.

The long-standing polynomial Hirsch conjecture asks if the combinatorial diameter of any polyhedron can be bounded by a polynomial of the dimension and number of facets. Inspired by this question, we study the combinatorial diameter of two classes of random polyhedra.

We prove nearly-matching upper and lower bounds, assuming that the number of facets is very large compared to the dimension.

The Quickest Transshipment Problem is to route flow as quickly as possible from sources with supplies to sinks with demands in a network with capacities and transit times on the arcs. It is of fundamental importance for numerous applications in areas such as logistics, production, traffic, evacuation, and finance. More than 25 years ago, Hoppe and Tardos presented the first (strongly) polynomial-time algorithm for this problem. Their approach, as well as subsequently derived algorithms with strongly polynomial running time, are hardly practical as they rely on parametric submodular function minimization via Megiddo‘s method of parametric search. In this talk we present a considerably faster algorithm for the Quickest Transshipment Problem that instead employs a subtle extension of the Discrete Newton Method. This improves the previously best known running time of Õ(m⁴k¹⁴}) to Õ(m²k⁵+m³k³+m³n), where n is the number of nodes, m the number of arcs, and k the number of sources and sinks.

In this talk we will see how to solve a network flow problem by a coarsening technique, and speculate if this technique can be carried over to other optimization problems. Then we will witness the struggles of experimentally evaluating an algorithm with many parameters.

We consider the stochastic scheduling problem of minimizing the expected makespan on m parallel identical machines. While the (adaptive) list scheduling policy achieves an approximation ratio of 2, any (non-adaptive) fixed assignment policy has performance guarantee 𝛺(log m/loglog m). Although the performance of the latter class of policies are worse, there are applications, e.g. in surgery scheduling, in which rather non-adaptive policies are desired.

We introduce two classes of policies, namely 𝛿-delay and 𝜏-shift policies, whose degree of adaptivity can be controlled by a parameter. Using the fixed assignment policy induced by LEPT as a basis, we present a policy - belonging to both classes - for which we show that it is an O(loglog m)-approximation for reasonably bounded parameters. In other words, an improvement on the performance of any fixed assignment policy can be achieved when allowing a small degree of adaptivity. Moreover, we provide a matching lower bound for any 𝛿-delay and 𝜏-shift policy when both parameters, respectively, are in the order of the expected makespan of an optimal non-anticipatory policy.

This is joint work with Guillaume Sagnol.

The question whether we can convert a bunch of weak learners into a strong learner arose in the late 80s. It was confirmed by Schapire and led to the most famous approach: AdaBoost. This algorithm is well known for it’s good performance in practice and there are a lot of variants. In this talk, we will look at the application of linear and mixed-integer optimization and we will derive corresponding LP and MIP formulations. In particular, we will look at:

• Properties of AdaBoost including possible drawbacks and approaches to overcome them
• Column generation as an efficient way to solve LP formulations
• LPBoost and IPBoost

Day to day we frequently encounter different kinds of combinatorial objects, e.g., permutations, binary strings, binary trees, spanning trees of a graph, bases of a matroid. Usually, there are three fundamental tasks for these objects: counting, random sampling, and exhaustive generation. Even though for the first two there are powerful well-understood general approaches like generating functions or Markov chains; this has been lacking for exhaustive generation.

In this talk, we will discuss greedy strategies for exhaustive generation. This is a very natural attempt to provide a general approach for exhaustive generation as greedy strategies are a widely used algorithmic paradigm. In particular, we will discuss:

• Various classical examples of Greedy based approaches in exhaustive generation.
• An introduction to the zig-zag framework by Hartung, Hoang, Mütze, and Williams, which provides a common lense for many greedy strategies.
• Some greedy strategies that appear to not fit into the zig-zag framework, including a new greedy approach for generating spanning trees of any given connected graph.

In 1932, Borsuk proved that every 2-dimensional convex body can be divided in three parts with strictly smaller diameter than the original. He also asked if the same would hold for any dimension d: is it true that every d-dimensional convex body can be divided in d+1 pieces of strictly smaller diameter?

The answer to this question is positive in 3 dimensions (Perkal 1947), but in 1993, Kahn and Kalai constructed polytopal counterexamples in dimension 1325. Nowadays, we know that the answer is “no” for all dimensions d≥64 (Bondarenko and Jenrich 2013). It remains open for every dimension between 4 and 63.

In this talk we introduce the problem, and we show the proofs for dimensions 2 and 3 plus computational ideas on how to extend these solutions to dimension 4.

I will talk about how to translate two open problems in the context of ReLU neural network (NN) expressivity into the polytope world:

1. Can constant-depth NNs compute any continuous piecewise linear (CPWL) function? Smallest open special case: Can 3-layer NNs compute the maximum of 5 numbers?
2. Can polynomial-size NNs precisely compute the objective value of the Minimum Spanning Tree problem (or other combinatorial optimization problems) for arbitrary real-valued edge weights?

To achieve these translations, I will introduce an isomorphism between the two semigroups (convex CPWL functions, pointwise addition) and (polytopes, Minkowski sum), known as “support functions” (in convex geometry) and “Newton polytopes” (in tropical geometry). Extending this concept to arbitrary (not necessarily convex) CPWL functions leads to the (in my opinion beautiful) construction of “virtual” polytopes, that is, the group of formal Minkowski differences of two polytopes.

The Moore–Hodgson Algorithm minimizes the number of late jobs on a single machine. That is, it finds an optimal schedule for the classical problem where jobs with given processing times and due dates have to be scheduled on a single machine so as to minimize the number of jobs completing after their due date. Several proofs of the correctness of this algorithm have been published. We present a new short proof.

We consider the problem of maximizing the expected revenue from selling k identical items to n unit-demand buyers who arrive sequentially with independent and identically distributed valuations. We show bounds on the gap between the revenue achievable with dynamic prices and that achievable with a static price. These bounds are tight for all values of k and n and vary depending on a regularity property of the underlying distribution. The bound for regular distributions increases in n and tends to 1/(1-k^k/(e^k k!)). Our upper bounds are obtained via a classic relaxation of the pricing problem known as the ex-ante relaxation, and a novel use of Bernstein polynomials to approximate the revenue from static pricing. This technique allows for a uniform and lossless analysis across all parameter values, both in the finite regime and in the limit. (Joint work with Paul Dütting and Felix Fischer)

I present an extension of the Python-embedded optimization modeling language PICOS that makes key results from the fields of robust and distributionally robust optimization available to application developers. While the Python ecosystem already offers multiple frameworks concerned with mathematical optimization, library support for optimization under uncertainty has been sparse in comparison. My talk opens with a brief introduction to the modeling interface provided by PICOS, then leads into a discussion of the recent additions that allow uncertainty in the data to be modelled explicitly and accounted for, assuming worst-case outcomes, during the solution process. In particular, I present an illustrative application in linear signal estimation where distributionally robust optimization can be seen to perform quite well.

From the global strong convexity assumptions to local Łojasiewicz gradient inequalities, functional structures are ubiquitous in Machine Learning. They successfully describe convergence properties of optimization methods, regret bounds of online methods, or generalization bounds. However, much less attention has been dedicated to similar structures in the optimization constraint sets or online learner’s action sets.

Here, we first motivate such an issue from the perspective of projection-free methods (e.g., Conditional Gradients in offline optimization). We then describe how global and local set uniform convexity, i.e., a natural quantitative notion for upper curvature, can help obtain faster convergence rates or regret bounds for online or bandit algorithms. By doing so, we explore some useful characterization of these sets leveraging tools developed to study Banach Spaces. We finally provide some connection between uniform convexity and upper-bound on some Rademacher constants.

Since its invention in 2006, differential privacy (DP) has become the de-facto standard for releasing aggregate information about data in a privacy-preserving way. It has not only found its way into companies such as Google, Microsoft and Apple, but is also used by government agencies such as the U.S. Census Bureau. In this talk, I will give an introduction into the concept of DP. I will further describe the most important building blocks that can be used to construct differentially private machine learning models that are safe against, e.g., training data extraction attacks.

In pandemic times, prohibiting close proximity between people is crucial to control the spread of the virus. This is particularly interesting in test and vaccination centers where each person should keep sufficient distance to other people during their transits to and from their designated rooms to prevent possible infections. To model this as a machine scheduling problem, each job has a transit time before and after its processing time. The task is to find a conflict-free schedule of minimum makespan in which the transit times of no two jobs on machines in close proximity (captured by an undirected graph) intersect. In this talk, we discuss hardness as well as approximation results for the case of identical jobs.

In this short talk, we will discuss some ongoing work on the Min Weighed Sum Bin Packing problem. The goal is to assign n items (with weight w_j and size s_j) to bins, without exceeding the bin capacities, when assigning item j to the i’th bin incurs a cost of i * w_j. This can also be understood as a (batch)-scheduling problem, in which all jobs have unit processing time, the machine can process batches of jobs satisfying a knapsack constraint, and the goal is to minimize the weighted sum of completion time.

A PTAS is known for this problem, but its astronomic running time makes it useless in the practice. Apart from that, the First-Fit algorithm that considers items in non-increasing order of w_j/s_j is known to have a tight performance guarantee of 2, and there is a greedy algorithm with a performance guarantee of 4 for a slight generalization of this problem, in which the feasible batches are given explicitly by a family of subsets of items. We will show that in the considered case (batches defined implicitly by a knapsack constraint), the performance guarantee of the greedy algorithm can be improved to 2.

Differentiable optimization aims at bringing constrained convex optimization to differentiable programming, allowing the computation of solution derivatives with respect to arbitrary input parameters. After an overview of some of the advances in that direction, we will see how to integrate differentiable optimization as a layer in differentiable models and its interplay with automatic differentiation, and conclude with some comparisons with other approaches.

We consider the problem of scheduling jobs on parallel machines so as to minimize the sum of weighted job completion times. We assume that each job must be completely processed on one machine and that the time required may depend arbitrarily on the job and the machine. Furthermore, the jobs arrive online over time. In the first part of the talk, we consider preemptive scheduling of deterministic jobs. I will use dual fitting to prove that a simple greedy algorithm for this problem is 4-competitive. The second part is about non-preemptive scheduling of stochastic jobs. Here a similar greedy algorithm for the assignment of jobs to machines, combined with known policies for scheduling the jobs assigned to each machine (Schulz, 2008), leads to stochastic online policies with performance guarantees depending on an upper bound 𝛥 for the squared coefficients of variation of the random variables. These improve upon the previously best known guarantees (Gupta, Moseley, Uetz, & Xie) when 𝛥 is large enough (for the simplest variant considered when 𝛥 ≥ 0.815). This includes the important case of exponentially distributed processing times.

Minimum cost flows have numerous applications, e.g. electrical or gas flows or equilibrium flows in traffic networks. In the classical minimum cost flow problem we are given some flow-dependent cost functions on the edges and demand values on the vertices. In this setting we want to find a flow with minimal costs satisfying the demands. However, in practice, demand and supply values are not constant but may vary or be uncertain. Therefore, we want to analyze the minimum cost flows as a function of the demand values. More specifically, we consider a setting where the demands in the network are given as a function depending on a one-dimensional parameter 𝜆.

We analyze these functions theoretically and use the insights to develop an output-polynomial algorithm that computes the minimum cost flow function explicitly for piecewise-quadratic edge costs and demands that are piecewise-linear functions of 𝜆. Further, we can generalize this approach to compute approximate solutions for arbitrary convex cost functions. The algorithm is tested on real-world gas and traffic networks.

This is joint work with Max Klimm and Per Joachims.

We review classical and modern results in approximation theory of neural networks. First, the density of neural networks within different function spaces under various assumptions on the activation function is considered. Next, lower and upper bounds on the order of approximation with neural networks are given based on the input dimension, the number of neurons and a parameter quantifying the smoothness of the target function. Lastly, a family of compositional target functions for which the curse of dimensionality can be overcome using deep neural networks is examined.

Robust Optimization is a popular paradigm for optimisation under uncertainty. It assumes that the uncertainty is specified by a set and aims to optimise the worst case objective over all elements in the set.

However in many problems the uncertainty changes over time as more information comes in. For this project our goal is to develop an adaptive learning algorithm that can simultaneously learn the uncertainty set and solve the optimisation problem. We achieve this by statistical updates and leveraging online learning algorithms.

This is joint work with Kevin-Martin Aigner, Kristin Braun, Frauke Liers and Sebastian Pokutta.

Since the beginning of Topology, one of the most used approach to study an object was to triangulate it. Many invariants have been introduced in the years, the two most important surely being homotopy and homology. However, the direct computation of these invariants is infeasible for triangulations with a large number of faces. This is why methods to reduce the number of faces of a complex without changing its homology and homotopy type are particularly important. In this talk, we will focus on various ways to see if a complex is contractible, starting from collapsibility and then trying to generalize the concept.

Generic rectangulations are tilings of the unit square by rectangles such that no 4 rectangles share a corner. Generic rectangulations are a fundamental object in computer science: not only appearing in practice (e.g. in VLSI circuit design) and theory (e.g. being closely related to binary search trees); but also within many other fundamental combinatorial objects such as permutations. In this work, we present a versatile algorithmic framework for exhaustively generating a large variety of different classes of generic rectangulations. Our algorithms work under very mild assumptions and apply to a considerable number of interesting rectangulation classes known from the literature, such as generic rectangulations, diagonal rectangulations, S-equivalent rectangulations, 1-sided/area-universal rectangulations, and their guillotine variants. The resulting generation algorithms are efficient, in most interesting cases even loopless or constant amortized time, i.e., each new rectangulation is generated in constant time in the worst case or on average, respectively.

In this talk we will show:

• A simple introduction to rectangulations and some of its interesting classes,
• Our algorithmic generation framework for rectangulation classes and
• Correctness proof (sketch) of the framework by relating rectangulations to permutations.

This is joint work with Torsten Mütze.

Fast domain propagation of linear constraints has become a crucial component of today’s best algorithms and solvers for mixed integer programming and pseudo-boolean optimization to achieve peak solving performance. Irregularities in the form of dynamic algorithmic behaviour, dependency structures, and sparsity patterns in the input data make efficient implementations of domain propagation on GPUs and, more generally, on parallel architectures challenging. This is one of the main reasons why domain propagation in state-of-the-art solvers is single thread only. In this paper, we present a new algorithm for domain propagation which (a) avoids these problems and allows for an efficient implementation on GPUs, and is (b) capable of running propagation rounds entirely on the GPU, without any need for synchronization or communication with the CPU. We present extensive computational results which demonstrate the effectiveness of our approach and show that ample speedups are possible on practically relevant problems: on state-of-the- art GPUs, our geometric mean speed-up for reasonably-large instances is around 10x to 20x and can be as high as 195x on favorably-large instances.

Conditional gradients (CG) constitute a class of projection-free first-order algorithms for smooth convex optimization. As such, they are frequently used in solving smooth convex optimization problems over polytopes, for which the computational cost of projections is prohibitive. We will discuss two topics in this talk. First of all, CG algorithms do not enjoy the optimal convergence rates achieved by projection-based first-order accelerated methods; achieving such globally-accelerated rates is information-theoretically impossible. To address this issue, we present Locally Accelerated Conditional Gradients – an algorithmic framework that couples accelerated steps with conditional gradient steps to achieve local acceleration on smooth strongly convex problems. Our approach does not require projections onto the feasible set, but only on (typically low-dimensional) simplices, thus keeping the computational cost of projections at bay. Further, it achieves optimal accelerated local convergence.

The second topic in this talk deals with the setting where first and second-order information about the function is costly to compute, and so we would like to make as much primal progress as possible per oracle call. Constrained second-order convex optimization algorithms are the method of choice when a high accuracy solution to a problem is needed, due to their local quadratic convergence. These algorithms require the solution of a constrained quadratic subproblem at every iteration. In this setting, we present the Second-Order Conditional Gradient Sliding (SOCGS) algorithm, which uses a projection-free algorithm to solve the constrained quadratic subproblems inexactly and uses inexact Hessian oracles (subject to an accuracy requirement). When the feasible region is a polytope, and a lower bound on the primal gap is known, the algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations. Once in the quadratic regime the SOCGS algorithm requires O(log log (1/ε)) first-order and inexact Hessian oracle calls and O(log (1 / ε) ⋅ log log (1/ε)) linear minimization oracle calls to achieve an ε-optimal solution.

We consider a general class of binary packing problems with multiple convex quadratic knapsack constraints. We present three constant-factor approximation algorithms based upon three different algorithmic techniques: (1) a rounding technique tailored to a convex relaxation in conjunction with a non-convex relaxation; (2) a greedy strategy; and (3) a randomized rounding method. The practical performance is tested by a computational study of the empirical approximation of these algorithms for problem instances arising in the context of real-world gas transport networks.

The learning of relations, dynamics, and governing equations from (sampled) data is a prevalent problem in various scientific fields. In the absence of noise, this task can often be solved using the Buchberger-Möller Algorithm, see Möller and Buchberger (1982). In general, however, when we do not have direct access to aforementioned equations, we have access to them indirectly only via noisy sampling. Known methods which extract relations from noisy data are the Approximate Vanishing Ideal Algorithm (AVI) and Vanishing Component Analysis (VCA), see Heldt et al. (2009) and Livni et al. (2013), respectively. These algorithms are often computationally inefficient and only allow for restricted recovery of relations from data. We present a new AVI algorithm and two variants utilizing Conditional Gradient Descent or the Frank-Wolfe Algorithm, see, e.g., Frank and Wolfe (1956) or Levitin and Polyak (1966). Our method is more general, easily regularizable, and can also extract non-homogeneous relations. We then present the efficacy and versatility of our approach for three learning problems: reconstruction of governing equations from data, classification, and regression.

This talk is a basic overview over my PhD projects. I focus on a project on making neural networks interpretable. If a neural network outputs a classification result for a high-dimensional input, we would like to know whether a small set of the input parameters was already decisive for the classification. This problem is formalised by introducing a probabilistic variant of prime implicants. We show that this problem is hard for the class NP^PP and remains NP-hard for any non-trivial approximation. We present a heuristic solution strategy for real-world applications that is build on Assumed Density Filtering: A technique to propagate multivariate normal distributions through neural networks. To justify the use of this heuristic we show that in fact no sensible family of distributions can be invariant under ReLu-neural network layers.

In Computer Vision, algorithms are now capable of “intelligent” automatic processing of the images. And these possibilities have been recently recycled in many creative processes by A.I. artists, which outputs sometimes reached hammer prizes in art auctions. This emergence of A.I. art looks like an artification, i.e., a societal process by which a practice becomes commonly acknowledged as an art form. Art history abounds with such examples, e.g., the transitioning from craftmanship to solo painters in the Renaissance.

Hence, rather than assessing the artist’s narratives, this point of view allows understanding A.I. art as a figurehead of the broader ecosystem of the creative industry. The latter indeed highly benefited from recent advances in Computer Vision.

We discuss here the possible intertwinements between A.I. art, the use of Computer Vision in the next generation of creative software, the creative industry, and broader societal consequences.

This is ongoing work with Louis Thiry and Léa Saint-Raymond at Ecole Normale Supérieure in Paris.

During the COGA Retreat 2019 we started research on the Symmetric Rendezvous-on-the-Line-Problem with Unknown Initial Distance: Two robots are placed on the real line with unknown initial distance. They do not know the location of the other robot and do not necessarily share the same sense of “left” and “right” on the line. They move with constant speed over the line and try to achieve rendez-vous using the same (randomized) search strategy in as little time as possible.

In a March 2020 talk (given in the COGA Research Seminar) we presented a family of search strategies that performed well in simulations without being able to determine their exact competitive ratio. During this talk we will present a novel family of search strategies whose precise competitive ratio can be computed using generating functions.

This is WIP by Guillaume, Khai Van, Martin, and Max.

This talk deals with an open problem concerning the expressivity of feedforward neural networks (NNs) with rectified linear unit (ReLU) activations. While it has been shown that every continuous, piecewise linear (CPWL) function can be exactly represented by such an NN with logarithmic depth (with respect to the input dimension), it is still unknown whether there exists any CPWL function that cannot be represented with three layers. Based on a yet unproven theoretical assumption, we show a computer-aided proof of non-existence of a 3-layer ReLU NN that computes the maximum of five scalar input numbers. We achieve this partial result by converting the existence question into a linear programming feasibility problem. This is joint work in progress with Amitabh Basu, Marco Di Summa, and Martin Skutella.

The Frank-Wolfe algorithm has become a popular constrained optimization algorithm for it is simple and projection-free, and it has been successfully applied to a variety of real-world problems. Its main drawback however lies in its convergence rate, which can be excessively slow due to naive descent directions. In this talk, we provide a brief review and propose two methods significantly improving its performance: one for minimizing a convex objective and one for minimizing a (non)convex finite-sum objective. The first method speeds up the Frank-Wolfe algorithm by better aligning the descent direction with that of the negative gradient via a matching pursuit-style subroutine. Although the idea is reasonably natural, its advantage over the state-of-the-art Frank-Wolfe algorithms is quite considerable. The second method blends stochastic Frank-Wolfe algorithms with adaptive gradients, which set entry-wise step-sizes that automatically adjust to the geometry of the problem. Computational experiments on convex and nonconvex objectives demonstrate the advantage of our approach.