Search

In an instance of the minimum eigenvalue problem, we are given a collection of $n$ vectors $v_1,\ldots, v_n \subset {\mathbb{R}^d}$, and the goal is to pick a subset $B\subseteq [n]$ of given vectors to maximize the minimum eigenvalue of the matrix $\sum_{i\in B} v_i v_i^{\top} $. Often, additional combinatorial constraints such as cardinality constraint $\left(|B|\leq k\right)$ or matroid constraint ($B$ is a basis of a matroid defined on $[n]$) must be satisfied by the chosen set of vectors. The minimum eigenvalue problem with matroid constraints models a wide variety of problems including the Santa Clause problem, the E-design problem, and the constructive Kadison-Singer problem. In this paper, we give a randomized algorithm that finds a set $B\subseteq [n]$ subject to any matroid constraint whose minimum eigenvalue is at least $(1-\epsilon)$ times the optimum, with high probability. The running time of the algorithm is $O\left( n^{O(d\log(d)/\epsilon^2)}\right)$. In particular, our results give a polynomial time asymptotic scheme when the dimension of the vectors is constant. Our algorithm uses a convex programming relaxation of the problem after guessing a rescaling which allows us to apply pipage rounding and matrix Chernoff inequalities to round to a good solution. The key new component is a structural lemma which enables us to "guess'' the appropriate rescaling, which could be of independent interest. Our approach generalizes the approximation guarantee to monotone, homogeneous functions and as such we can maximize $\det(\sum_{i\in B} v_i v_i^\top)^{1/d}$, or minimize any norm of the eigenvalues of the matrix $\left(\sum_{i\in B} v_i v_i^\top\right)^{-1} $, with the same running time under some mild assumptions. As a byproduct, we also get a simple algorithm for an algorithmic version of Kadison-Singer problem.

In an instance of the weighted Nash Social Welfare problem, we are given a set of $m$ indivisible items, $\mathscr{G}$, and $n$ agents, $\mathscr{A}$, where each agent $i \in \mathscr{A}$ has a valuation $v_{ij}\geq 0$ for each item $j\in \mathscr{G}$. In addition, every agent $i$ has a non-negative weight $w_i$ such that the weights collectively sum up to $1$. The goal is to find an assignment $\sigma:\mathscr{G}\rightarrow \mathscr{A}$ that maximizes $\prod_{i\in \mathscr{A}} \left(\sum_{j\in \sigma^{-1}(i)} v_{ij}\right)^{w_i}$, the product of the weighted valuations of the players. When all the weights equal $\frac1n$, the problem reduces to the classical Nash Social Welfare problem, which has recently received much attention. In this work, we present a $5\cdot\exp\left(2\cdot D_{\text{KL}}(\mathbf{w}\, ||\, \frac{\vec{\mathbf{1}}}{n})\right) = 5\cdot\exp\left(2\log{n} + 2\sum_{i=1}^n w_i \log{w_i}\right)$-approximation algorithm for the weighted Nash Social Welfare problem, where $D_{\text{KL}}(\mathbf{w}\, ||\, \frac{\vec{\mathbf{1}}}{n})$ denotes the KL-divergence between the distribution induced by $\mathbf{w}$ and the uniform distribution on $[n]$. We show a novel connection between the convex programming relaxations for the unweighted variant of Nash Social Welfare presented in \cite{cole2017convex, anari2017nash}, and generalize the programs to two different mathematical programs for the weighted case. The first program is convex and is necessary for computational efficiency, while the second program is a non-convex relaxation that can be rounded efficiently. The approximation factor derives from the difference in the objective values of the convex and non-convex relaxation.

Determinant maximization provides an elegant generalization of problems in many areas, including convex geometry, statistics, machine learning, fair allocation of goods, and network design. In an instance of the determinant maximization problem, we are given a collection of vectors $v_1,\ldots, v_n \in \mathbb{R}^d$, and the goal is to pick a subset $S\subseteq [n]$ of given vectors to maximize the determinant of the matrix $\sum_{i \in S} v_iv_i^\top$, where the picked set of vectors $S$ must satisfy some combinatorial constraint such as cardinality constraint ($|S| \leq k$) or matroid constraint ($S$ is a basis of a matroid defined on $[n]$). In this work, we give a combinatorial algorithm for the determinant maximization problem under a matroid constraint that achieves $O(d^{O(d)})$-approximation for any matroid of rank $r\geq d$. This complements the recent result of~\cite{BrownLPST22} that achieves a similar bound for matroids of rank $r\leq d$, relying on a geometric interpretation of the determinant. Our result matches the best-known estimation algorithms~\cite{madan2020maximizing} for the problem, which could estimate the objective value but could not give an approximate solution with a similar guarantee. Our work follows the framework developed by~\cite{BrownLPST22} of using matroid intersection based algorithms for determinant maximization. To overcome the lack of a simple geometric interpretation of the objective when $r \geq d$, our approach combines ideas from combinatorial optimization with algebraic properties of the determinant. We also critically use the properties of a convex programming relaxation of the problem introduced by~\cite{madan2020maximizing}.

Determinant maximization problem gives a general framework that models problems arising in as diverse fields as statistics \cite{pukelsheim2006optimal}, convex geometry \cite{Khachiyan1996}, fair allocations\linebreak \cite{anari2016nash}, combinatorics \cite{AnariGV18}, spectral graph theory \cite{nikolov2019proportional}, network design, and random processes \cite{kulesza2012determinantal}. In an instance of a determinant maximization problem, we are given a collection of vectors $U=\{v_1,\ldots, v_n\} \subset \RR^d$, and a goal is to pick a subset $S\subseteq U$ of given vectors to maximize the determinant of the matrix $\sum_{i\in S} v_i v_i^\top $. Often, the set $S$ of picked vectors must satisfy additional combinatorial constraints such as cardinality constraint $\left(|S|\leq k\right)$ or matroid constraint ($S$ is a basis of a matroid defined on the vectors). In this paper, we give a polynomial-time deterministic algorithm that returns a $r^{O(r)}$-approximation for any matroid of rank $r\leq d$. This improves previous results that give $e^{O(r^2)}$-approximation algorithms relying on $e^{O(r)}$-approximate \emph{estimation} algorithms \cite{NikolovS16,anari2017generalization,AnariGV18,madan2020maximizing} for any $r\leq d$. All previous results use convex relaxations and their relationship to stable polynomials and strongly log-concave polynomials. In contrast, our algorithm builds on combinatorial algorithms for matroid intersection, which iteratively improve any solution by finding an \emph{alternating negative cycle} in the \emph{exchange graph} defined by the matroids. While the $\det(.)$ function is not linear, we show that taking appropriate linear approximations at each iteration suffice to give the improved approximation algorithm.

We study a unified approach and algorithm for constructive discrepancy minimization based on a stochastic process. By varying the parameters of the process, one can recover various state-of-the-art results. We demonstrate the flexibility of the method by deriving a discrepancy bound for smoothed instances, which interpolates between known bounds for worst-case and random instances.

The Gibbs Sampler is a general method for sampling high-dimensional distributions, dating back to Turchin, 1971. In each step of the Gibbs Sampler, we pick a random coordinate and re-sample that coordinate from the distribution induced by fixing all other coordinates. While it has become widely used over the past half-century, guarantees of efficient convergence have been elusive. We show that for a convex body $K$ in $\mathbb{R}^{n}$ with diameter $D$, the mixing time of the Coordinate Hit-and-Run (CHAR) algorithm on $K$ is polynomial in $n$ and $D$. We also give a lower bound on the conductance of CHAR, showing that it is strictly worse than hit-and-run or the ball walk in the worst case.

We show that the volume of a convex body in $\mathbb{R}^{n}$ in the general membership oracle model can be computed to within relative error $\varepsilon$ using $\widetilde{O}(n^{3.5}\psi^{2} + n^3/\varepsilon^{2})$ oracle queries, where $\psi$ is the KLS constant. With the current bound of $\psi=\widetilde{O}(1)$, this gives an $\widetilde{O}(n^{3.5} + n^3/\varepsilon^{2})$ algorithm, improving on the Lov\'{a}sz-Vempala $\widetilde{O}(n^{4}/\varepsilon^{2})$ algorithm from 2003. The main new ingredient is an $\widetilde{O}(n^{3}\psi^{2})$ algorithm for isotropic transformation of a well-rounded convex body; we apply this iteratively to isotropicize a general convex body. Following this, we can apply the $\widetilde{O}(n^{3}/\varepsilon^{2})$ volume algorithm of Cousins and Vempala for well-rounded convex bodies. We also give an efficient implementation of the new algorithm for convex polytopes defined by $m$ inequalities in $\mathbb{R}^{n}$: polytope volume can be estimated in time $\widetilde{O}(mn^{c}/\varepsilon^{2})$ where $c<3.7$ depends on the current matrix multiplication exponent and improves on the previous best bound., Comment: 21 pages, 1 figure; updated with corrected proofs

Motivated by the Dikin walk, we develop aspects of an interior-point theory for sampling in high dimension. Specifically, we introduce a symmetric parameter and the notion of strong self-concordance. These properties imply that the corresponding Dikin walk mixes in $\tilde{O}(n\bar{\nu})$ steps from a warm start in a convex body in $\mathbb{R}^{n}$ using a strongly self-concordant barrier with symmetric self-concordance parameter $\bar{\nu}$. For many natural barriers, $\bar{\nu}$ is roughly bounded by $\nu$, the standard self-concordance parameter. We show that this property and strong self-concordance hold for the Lee-Sidford barrier. As a consequence, we obtain the first walk to mix in $\tilde{O}(n^{2})$ steps for an arbitrary polytope in $\mathbb{R}^{n}$. Strong self-concordance for other barriers leads to an interesting (and unexpected) connection -- for the universal and entropic barriers, it is implied by the KLS conjecture.