Author name cluster

Janne H. Korhonen

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

2 author rows

NeurIPS Conference 2021 Conference Paper

Towards Tight Communication Lower Bounds for Distributed Optimisation

Janne H. Korhonen
Dan Alistarh

We consider a standard distributed optimisation setting where $N$ machines, each holding a $d$-dimensional function $f_i$, aim to jointly minimise the sum of the functions $\sum_{i = 1}^N f_i (x)$. This problem arises naturally in large-scale distributed optimisation, where a standard solution is to apply variants of (stochastic) gradient descent. We focus on the communication complexity of this problem: our main result provides the first fully unconditional bounds on total number of bits which need to be sent and received by the $N$ machines to solve this problem under point-to-point communication, within a given error-tolerance. Specifically, we show that $\Omega( Nd \log d / N\varepsilon)$ total bits need to be communicated between the machines to find an additive $\epsilon$-approximation to the minimum of $\sum_{i = 1}^N f_i (x)$. The result holds for both deterministic and randomised algorithms, and, importantly, requires no assumptions on the algorithm structure. The lower bound is tight under certain restrictions on parameter values, and is matched within constant factors for quadratic objectives by a new variant of quantised gradient descent, which we describe and analyse. Our results bring over tools from communication complexity to distributed optimisation, which has potential for further applications.

PDF Details

NeurIPS Conference 2020 Conference Paper

Scalable Belief Propagation via Relaxed Scheduling

Vitalii Aksenov
Dan Alistarh
Janne H. Korhonen

The ability to leverage large-scale hardware parallelism has been one of the key enablers of the accelerated recent progress in machine learning. Consequently, there has been considerable effort invested into developing efficient parallel variants of classic machine learning algorithms. However, despite the wealth of knowledge on parallelization, some classic machine learning algorithms often prove hard to parallelize efficiently while maintaining convergence. In this paper, we focus on efficient parallel algorithms for the key machine learning task of inference on graphical models, in particular on the fundamental belief propagation algorithm. We address the challenge of efficiently parallelizing this classic paradigm by showing how to leverage scalable relaxed schedulers, which reduce parallelization overheads, in this context. We investigate the overheads of relaxation analytically, and present an extensive empirical study, showing that our approach outperforms previous parallel belief propagation implementations both in terms of scalability and in terms of wall-clock convergence time, on a range of practical applications.

PDF Details

STOC Conference 2018 Conference Paper

New classes of distributed time complexity

Alkida Balliu
Juho Hirvonen
Janne H. Korhonen
Tuomo Lempiäinen
Dennis Olivetti
Jukka Suomela

A number of recent papers – e.g. Brandt et al. (STOC 2016), Chang et al. (FOCS 2016), Ghaffari & Su (SODA 2017), Brandt et al. (PODC 2017), and Chang & Pettie (FOCS 2017) – have advanced our understanding of one of the most fundamental questions in theory of distributed computing: what are the possible time complexity classes of LCL problems in the LOCAL model? In essence, we have a graph problem Π in which a solution can be verified by checking all radius- O (1) neighbourhoods, and the question is what is the smallest T such that a solution can be computed so that each node chooses its own output based on its radius- T neighbourhood. Here T is the distributed time complexity of Π. The time complexity classes for deterministic algorithms in bounded-degree graphs that are known to exist by prior work are Θ(1), Θ(log * n ), Θ(log n ), Θ( n 1/ k ), and Θ( n ). It is also known that there are two gaps: one between ω(1) and o (loglog * n ), and another between ω(log * n ) and o (log n ). It has been conjectured that many more gaps exist, and that the overall time hierarchy is relatively simple – indeed, this is known to be the case in restricted graph families such as cycles and grids. We show that the picture is much more diverse than previously expected. We present a general technique for engineering LCL problems with numerous different deterministic time complexities, including Θ(log α n ) for any α ≥ 1, 2 Θ(log α n ) for any α ≤ 1, and Θ( n α ) for any α < 1/2 in the high end of the complexity spectrum, and Θ(log α log * n ) for any α ≥ 1, 2 Θ(log α log * n ) for any α ≤ 1, and Θ((log * n ) α ) for any α ≤ 1 in the low end of the complexity spectrum; here α is a positive rational number.

Details

JAIR Journal 2017 Journal Article

Bayesian Network Structure Learning with Integer Programming: Polytopes, Facets and Complexity

James Cussens
Matti Järvisalo
Janne H. Korhonen
Mark Bartlett

The challenging task of learning structures of probabilistic graphical models is an important problem within modern AI research. Recent years have witnessed several major algorithmic advances in structure learning for Bayesian networks - arguably the most central class of graphical models - especially in what is known as the score-based setting. A successful generic approach to optimal Bayesian network structure learning (BNSL), based on integer programming (IP), is implemented in the GOBNILP system. Despite the recent algorithmic advances, current understanding of foundational aspects underlying the IP based approach to BNSL is still somewhat lacking. Understanding fundamental aspects of cutting planes and the related separation problem is important not only from a purely theoretical perspective, but also since it holds out the promise of further improving the efficiency of state-of-the-art approaches to solving BNSL exactly. In this paper, we make several theoretical contributions towards these goals: (i) we study the computational complexity of the separation problem, proving that the problem is NP-hard; (ii) we formalise and analyse the relationship between three key polytopes underlying the IP-based approach to BNSL; (iii) we study the facets of the three polytopes both from the theoretical and practical perspective, providing, via exhaustive computation, a complete enumeration of facets for low-dimensional family-variable polytopes; and, furthermore, (iv) we establish a tight connection of the BNSL problem to the acyclic subgraph problem.

PDF Details DOI

IJCAI Conference 2017 Conference Paper

Bayesian Network Structure Learning with Integer Programming: Polytopes, Facets and Complexity (Extended Abstract)

James Cussens
Matti Järvisalo
Janne H. Korhonen
Mark Bartlett

Developing accurate algorithms for learning structures of probabilistic graphical models is an important problem within modern AI research. Here we focus on score-based structure learning for Bayesian networks as arguably the most central class of graphical models. A successful generic approach to optimal Bayesian network structure learning (BNSL), based on integer programming (IP), is implemented in the Gobnilp system. Despite the recent algorithmic advances, current understanding of foundational aspects underlying the IP based approach to BNSL is still somewhat lacking. In this paper, we provide theoretical contributions towards understanding fundamental aspects of cutting planes and the related separation problem in this context, ranging from NP-hardness results to analysis of polytopes and the related facets in connection to BNSL.

PDF Details

SAT Conference 2014 Conference Paper

Conditional Lower Bounds for Failed Literals and Related Techniques

Matti Järvisalo
Janne H. Korhonen

Abstract We prove time-complexity lower bounds for various practically relevant probing-based CNF simplification techniques, namely failed literal detection and related techniques. Specifically, we show that improved algorithms for these simplification techniques would give a 2 δn time algorithm for CNF-SAT for some δ < 1, violating the Strong Exponential Time Hypothesis.

Details

MFCS Conference 2013 Conference Paper

On the Parameterized Complexity of Cutting a Few Vertices from a Graph

Fedor V. Fomin
Petr A. Golovach
Janne H. Korhonen

Abstract We study the parameterized complexity of separating a small set of vertices from a graph by a small vertex-separator. That is, given a graph G and integers k, t, the task is to find a vertex set X with | X | ≤ k and | N ( X )| ≤ t. We show that the problem is fixed-parameter tractable (FPT) when parameterized by t but W[1]-hard when parameterized by k, and a terminal variant of the problem, where X must contain a given vertex s, is W[1]-hard when parameterized either by k or by t alone, but is FPT when parameterized by k + t. We also show that if we consider edge cuts instead of vertex cuts, the terminal variant is NP-hard.

Details

SAT Conference 2012 Conference Paper

Finding Efficient Circuits for Ensemble Computation

Matti Järvisalo
Petteri Kaski
Mikko Koivisto
Janne H. Korhonen

Abstract Given a Boolean function as input, a fundamental problem is to find a Boolean circuit with the least number of elementary gates (AND, OR, NOT) that computes the function. The problem generalises naturally to the setting of multiple Boolean functions: find the smallest Boolean circuit that computes all the functions simultaneously. We study an NP-complete variant of this problem titled Ensemble Computation and, especially, its relationship to the Boolean satisfiability (SAT) problem from both the theoretical and practical perspectives, under the two monotone circuit classes: OR-circuits and SUM-circuits. Our main result relates the existence of nontrivial algorithms for CNF-SAT with the problem of rewriting in subquadratic time a given OR-circuit to a SUM-circuit. Furthermore, by developing a SAT encoding for the ensemble computation problem and by employing state-of-the-art SAT solvers, we search for concrete instances that would witness a substantial separation between the size of optimal OR-circuits and optimal SUM-circuits. Our encoding allows for exhaustively checking all small witness candidates. Searching over larger witness candidates presents an interesting challenge for current SAT solver technology.

Details