# Jan-Hendrik Lange (PhD Student)

## MSc Jan-Hendrik Lange

- Address
- Max-Planck-Institut für Informatik

Saarland Informatics Campus

Campus E1 4

66123 Saarbrücken - Location
- E1 4 - Room 629
- Phone
- +49 681 9325 2029
- Fax
- +49 681 9325 2099
- Get email via email

# Personal Information

**Research Interests:**

- Combinatorial Optimization
- Applications of Mathematical Optimization in Machine Learning

**Education:**

- Master of Science in Mathematics with Minor in Computer Science, Technische Universität Darmstadt, June 2016
- Since June 2016: PhD Student at Max Planck Institute for Informatics

# Publications

2017

**Analysis and Optimization of Graph Decompositions by Lifted Multicuts**

A. Horňáková, J.-H. Lange and B. Andres

Proceedings of the 34th International Conference on Machine Learning (ICML 2017), 2017

**Decomposition of Trees and Paths via Correlation**

J.-H. Lange and B. Andres

Technical Report, 2017

Abstract

We study the problem of decomposing (clustering) a tree with respect to costs attributed to pairs of nodes, so as to minimize the sum of costs for those pairs of nodes that are in the same component (cluster). For the general case and for the special case of the tree being a star, we show that the problem is NP-hard. For the special case of the tree being a path, this problem is known to be polynomial time solvable. We characterize several classes of facets of the combinatorial polytope associated with a formulation of this clustering problem in terms of lifted multicuts. In particular, our results yield a complete totally dual integral (TDI) description of the lifted multicut polytope for paths, which establishes a connection to the combinatorial properties of alternative formulations such as set partitioning.

**Discrete-Continuous Splitting for Weakly Supervised Learning**

E. Laude, J.-H. Lange, F. R. Schmidt, B. Andres and D. Cremers

Technical Report, 2017

Abstract

This paper introduces a novel algorithm for a class of weakly supervised
learning tasks. The considered tasks are posed as joint optimization problems
in the continuous model parameters and the (a-priori unknown) discrete label
variables. In contrast to prior approaches such as convex relaxations, we
decompose the nonconvex problem into purely discrete and purely continuous
subproblems in a way that is amenable to distributed optimization by the
Alternating Direction Method of Multipliers (ADMM). This approach preserves
integrality of the discrete label variables and, for a reparameterized variant
of the algorithm using kernels, guarantees global convergence to a critical
point. The resulting method implicitly alternates between a discrete and a
continuous variable update, however, it is inherently different from a
discrete-continuous coordinate descent scheme (hard EM). In diverse experiments
we show that our method can learn a classifier from weak supervision that takes
the form of hard and soft constraints on the labeling and outperforms hard EM
in this task.

2016

**Lifting of Multicuts**

B. Andres, A. Fuksova and J.-H. Lange

Technical Report, 2016

Abstract

For every simple, undirected graph $G = (V, E)$, a one-to-one relation exists
between the decompositions and the multicuts of $G$. A decomposition of $G$ is
a partition $\Pi$ of $V$ such that, for every $U \in \Pi$, the subgraph of $G$
induced by $U$ is connected. A multicut of $G$ is an $M \subseteq E$ such that,
for every (chordless) cycle $C \subseteq E$ of $G$, $|M \cap C| \neq 1$. The
multicut related to a decomposition is the set of edges that straddle distinct
components. The characteristic function $x \in \{0, 1\}^E$ of a multicut $M =
x^{-1}(1)$ of $G$ makes explicit, for every pair $\{v,w\} \in E$ of neighboring
nodes, whether $v$ and $w$ are in distinct components. In order to make
explicit also for non-neighboring nodes, specifically, for all $\{v,w\} \in E'$
with $E \subseteq E' \subseteq {V \choose 2}$, whether $v$ and $w$ are in
distinct components, we define a lifting of the multicuts of $G$ to multicuts
of $G' = (V, E')$. We show that, if $G$ is connected, the convex hull of the
characteristic functions of those multicuts of $G'$ that are lifted from $G$ is
an $|E'|$-dimensional polytope in $\mathbb{R}^{E'}$. We establish properties of
trivial facets of this polytope.