The famous theorem of Fritz John states that any convex body has a unique maximal volume inscribed ellipsoid, known as the John Ellipsoid. Computing the John Ellipsoid is a fundamental problem in convex optimization. In this paper, we focus on approximating the John Ellipsoid inscribed in a convex and centrally symmetric polytope defined by P:= {x Rd: 1n Ax 1n}, where A Rn d is a rank-d matrix and 1n Rn is the all-ones vector. We develop two efficient algorithms for approximating the John Ellipsoid. The first is a sketchingbased algorithm that runs in nearly input-sparsity time eO(nnz(A)+dω), where nnz(A)denotes the number of nonzero entries in the matrix Aand ω 2.37is the current matrix multiplication exponent. The second is a treewidth-based algorithm that runs in time eO(nτ2), where τ is the treewidth of the dual graph of the matrix A. Our algorithms significantly improve upon the state-of-the-art running time of eO(nd2)achieved by [Cohen, Cousins, Lee, and Yang, COLT 2019].

The VC-dimension is a well-studied and fundamental complexity measure of a set system (or hypergraph) that is central to many areas of machine learning. We establish several new results on the complexity of computing the VC-dimension. In particular, given a hypergraph H = (V,E), we prove that the naive 2O(|V|)-time algorithm is asymptotically tight under the Exponential Time Hypothesis (ETH). We then prove that the problem admits a 1-additive fixed-parameter approximation algorithm when parameterized by the maximum degree of Hand a fixed-parameter algorithm when parameterized by its dimension, and that these are essentially the only such exploitable structural parameters.

The VC-dimension is a well-studied and fundamental complexity measure of a set system (or hypergraph) that is central to many areas of machine learning. We establish several new results on the complexity of computing the VC-dimension.

We study the problem of generating synthetic data under differential privacy. We establish fixed-parameter tractability (FPT) for this problem where the parameter is the treewidth of the query family's incidence graph. Our algorithms attain optimal error rates across all regimes and are realized by two different approaches: the first is based on linear programming (LP) and the FPT of the separation problem for the LP dual; the second is based on a subsampled private multiplicative weights method, where we obtain FPT for sampling from Gibbs distributions. Both approaches are unified by a dynamic programming framework over a tree decomposition.

We investigate the parameterized complexity of Bayesian Network Structure Learn-1 ing (BNSL), a classical problem that has received significant attention in empirical2 but also purely theoretical studies. We follow up on previous works that have3 analyzed the complexity of BNSL w.r.t. the so-called superstructure of the input.4 While known results imply that BNSL is unlikely to be fixed-parameter tractable5 even when parameterized by the size of a vertex cover in the superstructure, here we6 show that a different kind of parameterization--notably by the size of a feedback7 edge set--yields fixed-parameter tractability. We proceed by showing that this8 result can be strengthened to a localized version of the feedback edge set, and9 provide corresponding lower bounds that complement previous results to provide a10 complexity classification of BNSL w.r.t.

We present a method for learning treewidth-bounded Bayesian networks from data sets containing thousands of variables. Bounding the treewidth of a Bayesian network greatly reduces the complexity of inferences. Yet, being a global property of the graph, it considerably increases the difficulty of the learning process. Our novel algorithm accomplishes this task, scaling both to large domains and to large treewidths. Our novel approach consistently outperforms the state of the art on experiments with up to thousands of variables.

Neural Information Processing Systems http://nips.cc/

Neural Information Processing Systems http://nips.cc/