Search

In information visualization, the position of symbols often encodes associated data values. When visualizing data elements with both a numerical and a categorical dimension, positioning in the categorical axis admits some flexibility. This flexibility can be exploited to reduce symbol overlap, and thereby increase legibility. In this paper we initialize the algorithmic study of optimizing symbol legibility via a limited displacement of the symbols. Specifically, we consider unit square symbols that need to be placed at specified y-coordinates. We optimize the drawing order of the symbols as well as their x-displacement, constrained within a rectangular container, to maximize the minimum visible perimeter over all squares. If the container has width and height at most 2, there is a point that stabs all squares. In this case, we prove that a staircase layout is arbitrarily close to optimality and can be computed in O(n log n) time. If the width is at most 2, there is a vertical line that stabs all squares, and in this case, we give a 2-approximation algorithm (assuming fixed container height) that runs in O(n log n) time. As a minimum visible perimeter of 2 is always trivially achievable, we measure this approximation with respect to the visible perimeter exceeding 2. We show that, despite its simplicity, the algorithm gives asymptotically optimal results for certain instances.

Enclosing depth is a recently introduced depth measure which gives a lower bound to many depth measures studied in the literature. So far, enclosing depth has only been studied from a combinatorial perspective. In this work, we give the first algorithms to compute the enclosing depth of a query point with respect to a data point set in any dimension. In the plane we are able to optimize the algorithm to get a runtime of O(n log n). In constant dimension, our algorithms still run in polynomial time.

We analyze the faces of the dual Koch arrangement, which is the arrangement of $2^s + 1$ lines obtained by projective duality from the Koch chain $K_s$. In particular, we show that this line arrangement does not contain any $k$-gons for $k > 5$, and that the number of pentagons is $3 \cdot 2^{s-1} - 3$.

In information visualization, the position of symbols often encodes associated data values. When visualizing data elements with both a numerical and a categorical dimension, positioning in the categorical axis admits some flexibility. This flexibility can be exploited to reduce symbol overlap, and thereby increase legibility. In this paper we initialize the algorithmic study of optimizing symbol legibility via a limited displacement of the symbols. Specifically, we consider unit square symbols that need to be placed at specified $y$-coordinates. We optimize the drawing order of the symbols as well as their $x$-displacement, constrained within a rectangular container, to maximize the minimum visible perimeter over all squares. If the container has width and height at most $2$, there is a point that stabs all squares. In this case, we prove that a staircase layout is arbitrarily close to optimality and can be computed in $O(n\log n)$ time. If the width is at most $2$, there is a vertical line that stabs all squares, and in this case, we give a 2-approximation algorithm that runs in $O(n\log n)$ time. As a minimum visible perimeter of $2$ is always trivially achievable, we measure this approximation with respect to the visible perimeter exceeding $2$. We show that, despite its simplicity, the algorithm gives asymptotically optimal results for certain instances.

The Matou\v{s}ek LP-type problems were used by Matou\v{s}ek to show that the Sharir-Welzl algorithm may require at least subexponential time. Later, G\"artner translated this result into the language of Unique Sink Orientations (USOs) and introduced the Matou\v{s}ek USOs, the USOs equivalent to Matou\v{s}ek's LP-type problems. He further showed that the Random Facet algorithm only requires quadratic time on the realizable subset of the Matou\v{s}ek USOs, but without characterizing this subset. In this paper, we deliver this missing characterization and also provide concrete realizations for all realizable Matou\v{s}ek USOs. Furthermore, we show that the realizable Matou\v{s}ek USOs are exactly the orientations arising from simple extensions of cyclic-P-matroids., Comment: 17 pages, 5 figures

The ARRIVAL problem is to decide the fate of a train moving along the edges of a directed graph, according to a simple (deterministic) pseudorandom walk. The problem is in $NP \cap coNP$ but not known to be in $P$. The currently best algorithms have runtime $2^{\Theta(n)}$ where $n$ is the number of vertices. This is not much better than just performing the pseudorandom walk. We develop a subexponential algorithm with runtime $2^{O(\sqrt{n}\log n)}$. We also give a polynomial-time algorithm if the graph is almost acyclic. Both results are derived from a new general approach to solve ARRIVAL instances., Comment: 13 pages, 1 figure Added a reference

A unique sink orientation (USO) is an orientation of the hypercube graph with the property that every face has a unique sink. A number of well-studied problems reduce in strongly polynomial time to finding the global sink of a USO; most notably, linear programming (LP) and the P-matrix linear complementarity problem (P-LCP). The former is not known to have a strongly polynomial-time algorithm, while the latter is not known to even have a polynomial-time algorithm, motivating the problem to find the global sink of a USO. Although, every known class of geometric USOs, arising from a concrete problem such as LP, is exponentially small, relative to the class of all USOs. Accordingly, geometric USOs exhibit additional properties that set them apart from general USOs, and it may be advantageous, if not necessary, to leverage these properties to find the global sink of a USO faster. Only a few such properties are known. In this paper, we establish a new combinatorial property of the USOs that arise from symmetric P-LCP, which includes the USOs that arise from linear and simple convex quadratic programming.

The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r-1)+1 points in R^d, one can find a partition X=X_1 cup ... cup X_r of X, such that the convex hulls of the X_i, i=1,...,r, all share a common point. In this paper, we prove a strengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span floor[n/3] vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Alvarez-Rebollar et al. guarantees floor[n/6] pairwise crossing triangles. Our result generalizes to a result about simplices in R^d,d >=2.

Consider a community where initially, each individual is positive or negative regarding a reform proposal. In each round, individuals gather randomly in fixed rooms of different sizes, and all individuals in a room agree on the majority opinion in the room (with ties broken in favor of the negative opinion). The Galam model---introduced in statistical physics, specifically sociophysics---approximates this basic random process. We approach the model from a more mathematical perspective and study the threshold behavior and the consensus time of the model.

We study the computational complexity of Arrival, a zero-player game on n-vertex switch graphs introduced by Dohrau, Gärtner, Kohler, Matoušek, and Welzl. They showed that the problem of deciding termination of this game is contained in NP ∩ coNP. Karthik C. S. recently introduced a search variant of Arrival and showed that it is in the complexity class PLS. In this work, we significantly improve the known upper bounds for both the decision and the search variants of Arrival. First, we resolve a question suggested by Dohrau et al. and show that the decision variant of Arrival is in UP ∩ coUP. Second, we prove that the search variant of Arrival is contained in CLS. Third, we give a randomized O(1.4143n)-time algorithm to solve both variants. Our main technical contributions are (a) an e ciently verifiable characterization of the unique witness for termination of the Arrival game, and (b) an e cient way of sampling from the state space of the game. We show that the problem of finding the unique witness is contained in CLS, whereas it was previously conjectured to be FPSPACE-complete. The e cient sampling procedure yields the first algorithm for the problem that has expected runtime O(cn) with c < 2.

We study the behavior of simple principal pivoting methods for the P-matrix linear complementarity problem (P-LCP). We solve an open problem of Morris by showing that Murty's least-index pivot rule (under any fixed index order) leads to a quadratic number of iterations on Morris's highly cyclic P-LCP examples. We then show that on K-matrix LCP instances, all pivot rules require only a linear number of iterations. As the main tool, we employ unique-sink orientations of cubes, a useful combinatorial abstraction of the P-LCP

We introduce unique sink orientations of grids as digraph models for many well-studied problems, including linear programming over products of simplices, generalized linear complementarity problems over P-matrices (PGLCP), and simple stochastic games. We investigate the combinatorial structure of such orientations and develop randomized algorithms for finding the sink. We show that the orientations arising from PGLCP satisfy the Holt-Klee condition known to hold for polytope digraphs, and we give the first expected linear-time algorithms for solving PGLCP with a fixed number of blocks

We investigate the combinatorial structure of linear programs on simple d-polytopes with d + 2 facets. These can be encoded by admissible grid orientations. Admissible grid orientations are also obtained through orientation properties of a planar point configuration or by the dual line arrangement. The point configuration and the polytope corresponding to the same grid are related through an extended Gale transform. The class of admissible grid orientations is shown to contain nonrealizable examples, i.e., there are admissible grid orientations which cannot be obtained from a polytope or a point configuration. It is shown, however, that every admissible grid orientation is induced by an arrangement of pseudolines. This later result is used to prove several nontrivial facts about admissible grid orientations

Tverberg's theorem is one of the cornerstones of discrete geometry. It states that, given a set $X$ of at least $(d+1)(r-1)+1$ points in $\mathbb R^d$, one can find a partition $X=X_1\cup \ldots \cup X_r$ of $X$, such that the convex hulls of the $X_i$, $i=1,\ldots,r$, all share a common point. In this paper, we prove a strengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any $n$ points in the plane in general position span $\lfloor n/3\rfloor$ vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Rebollar et al.\ guarantees $\lfloor n/6\rfloor$ pairwise crossing triangles. Our result generalizes to a result about simplices in $\mathbb R^d,d\ge2$., Comment: 13 pages, 7 figures

We study the computational complexity of ARRIVAL, a zero-player game on $n$-vertex switch graphs introduced by Dohrau, G\"{a}rtner, Kohler, Matou\v{s}ek, and Welzl. They showed that the problem of deciding termination of this game is contained in $\text{NP} \cap \text{coNP}$. Karthik C. S. recently introduced a search variant of ARRIVAL and showed that it is in the complexity class PLS. In this work, we significantly improve the known upper bounds for both the decision and the search variants of ARRIVAL. First, we resolve a question suggested by Dohrau et al. and show that the decision variant of ARRIVAL is in $\text{UP} \cap \text{coUP}$. Second, we prove that the search variant of ARRIVAL is contained in CLS. Third, we give a randomized $\mathcal{O}(1.4143^n)$-time algorithm to solve both variants. Our main technical contributions are (a) an efficiently verifiable characterization of the unique witness for termination of the ARRIVAL game, and (b) an efficient way of sampling from the state space of the game. We show that the problem of finding the unique witness is contained in CLS, whereas it was previously conjectured to be FPSPACE-complete. The efficient sampling procedure yields the first algorithm for the problem that has expected runtime $\mathcal{O}(c^n)$ with $c<2$., Comment: 13 pages, 6 figures

We study the computational complexity of Arrival, a zero-player game on n-vertex switch graphs introduced by Dohrau, Gärtner, Kohler, Matoušek, and Welzl. They showed that the problem of deciding termination of this game is contained in NP ∩ coNP. Karthik C. S. recently introduced a search variant of Arrival and showed that it is in the complexity class PLS. In this work, we significantly improve the known upper bounds for both the decision and the search variants of Arrival. First, we resolve a question suggested by Dohrau et al. and show that the decision variant of Arrival is in UP ∩ coUP. Second, we prove that the search variant of Arrival is contained in CLS. Third, we give a randomized O(1.4143n)-time algorithm to solve both variants. Our main technical contributions are (a) an e ciently verifiable characterization of the unique witness for termination of the Arrival game, and (b) an e cient way of sampling from the state space of the game. We show that the problem of finding the unique witness is contained in CLS, whereas it was previously conjectured to be FPSPACE-complete. The e cient sampling procedure yields the first algorithm for the problem that has expected runtime O(cn) with c < 2.

We study the computational complexity of Arrival, a zero-player game on n-vertex switch graphs introduced by Dohrau, Gärtner, Kohler, Matousek, and Welzl. They showed that the problem of deciding termination of this game is contained in NP n coNP. Karthik C. S. recently introduced a search variant of Arrival and showed that it is in the complexity class PLS. In this work, we significantly improve the known upper bounds for both the decision and the search variants of Arrival. First, we resolve a question suggested by Dohrau et al. and show that the decision variant of Arrival is in UP n coUP. Second, we prove that the search variant of Arrival is contained in CLS. Third, we give a randomized O(1.4143^n)-time algorithm to solve both variants. Our main technical contributions are (a) an efficiently verifiable characterization of the unique witness for termination of the Arrival game, and (b) an efficient way of sampling from the state space of the game. We show that the problem of finding the unique witness is contained in CLS, whereas it was previously conjectured to be FPSPACE-complete. The efficient sampling procedure yields the first algorithm for the problem that has expected runtime O(c^n) with c<2.

A unique sink orientation (USO) is an orientation of the $n$-dimensional cube graph ($n$-cube) such that every face (subcube) has a unique sink. The number of unique sink orientations is $n^{\Theta(2^n)}$. If a cube orientation is not a USO, it contains a pseudo unique sink orientation (PUSO): an orientation of some subcube such that every proper face of it has a unique sink, but the subcube itself hasn't. In this paper, we characterize and count PUSOs of the $n$-cube. We show that PUSOs have a much more rigid structure than USOs and that their number is between $2^{\Omega(2^{n-\log n})}$ and $2^{O(2^n)}$ which is negligible compared to the number of USOs. As tools, we introduce and characterize two new classes of USOs: border USOs (USOs that appear as facets of PUSOs), and odd USOs which are dual to border USOs but easier to understand., Comment: 22 pages, 10 figures

Consider a graph $G=(V,E)$ and a random initial vertex-coloring, where each vertex is blue independently with probability $p_{b}$, and red with probability $p_r=1-p_b$. In each step, all vertices change their current color synchronously to the most frequent color in their neighborhood and in case of a tie, a vertex conserves its current color; this model is called majority model. If in case of a tie a vertex always chooses blue color, it is called biased majority model. We are interested in the behavior of these deterministic processes, especially in a two-dimensional torus (i.e., cellular automaton with (biased) majority rule). In the present paper, as a main result we prove both majority and biased majority cellular automata exhibit a threshold behavior with two phase transitions. More precisely, it is shown that for a two-dimensional torus $T_{n,n}$, there are two thresholds $0\leq p_1, p_2\leq 1$ such that $p_b \ll p_1$, $p_1 \ll p_b \ll p_2$, and $p_2 \ll p_b$ result in monochromatic configuration by red, stable coexistence of both colors, and monochromatic configuration by blue, respectively in $\mathcal{O}(n^2)$ number of steps

Consider a graph $G=(V,E)$ and an initial random coloring where each vertex $v \in V$ is blue with probability $P_b$ and red otherwise, independently from all other vertices. In each round, all vertices simultaneously switch their color to the most frequent color in their neighborhood and in case of a tie, a vertex keeps its current color. The main goal of the present paper is to analyze the behavior of this basic and natural process on the random $d$-regular graph $\mathbb{G}_{n,d}$. It is shown that for all $\epsilon>0$, $P_b \le 1/2-\epsilon$ results in final complete occupancy by red in $\mathcal{O}(\log_d\log n)$ rounds with high probability, provided that $d\geq c/\epsilon^2$ for a suitable constant $c$. Furthermore, we show that with high probability, $\mathbb{G}_{n,d}$ is immune; i.e., the smallest dynamic monopoly is of linear size. A dynamic monopoly is a subset of vertices that can take over in the sense that a commonly chosen initial color eventually spreads throughout the whole graph, irrespective of the colors of other vertices. This answers an open question of Peleg.

In general dimension, there is no known total polynomial algorithm for either convex hull or vertex enumeration, i.e. an algorithm whose complexity depends polynomially on the input and output sizes. It is thus important to identify problems and polytope representations for which total polynomial-time algorithms can be obtained. We offer the first total polynomial-time algorithm for computing the edge-skeleton-including vertex enumeration-of a polytope given by an optimization or separation oracle, where we are also given a superset of its edge directions. We also offer a space-efficient variant of our algorithm by employing reverse search. All complexity bounds refer to the (oracle) Turing machine model. There is a number of polytope classes naturally defined by oracles; for some of them neither vertex nor facet representation is obvious. We consider two main applications, where we obtain (weakly) total polynomial-time algorithms: Signed Minkowski sums of convex polytopes, where polytopes can be subtracted provided the signed sum is a convex polytope, and computation of secondary, resultant, and discriminant polytopes. Further applications include convex combinatorial optimization and convex integer programming, where we offer a new approach, thus removing the complexity's exponential dependence in the dimension., SCOPUS: ar.j, info:eu-repo/semantics/published

In general dimension, there is no known total polynomial algorithm for either convex hull or vertex enumeration, i.e. an algorithm whose complexity depends polynomially on the input and output sizes. It is thus important to identify problems and polytope representations for which total polynomial-time algorithms can be obtained. We offer the first total polynomial-time algorithm for computing the edge-skeleton-including vertex enumeration-of a polytope given by an optimization or separation oracle, where we are also given a superset of its edge directions. We also offer a space-efficient variant of our algorithm by employing reverse search. All complexity bounds refer to the (oracle) Turing machine model. There is a number of polytope classes naturally defined by oracles; for some of them neither vertex nor facet representation is obvious. We consider two main applications, where we obtain (weakly) total polynomial-time algorithms: Signed Minkowski sums of convex polytopes, where polytopes can be subtracted provided the signed sum is a convex polytope, and computation of secondary, resultant, and discriminant polytopes. Further applications include convex combinatorial optimization and convex integer programming, where we offer a new approach, thus removing the complexity's exponential dependence in the dimension., SCOPUS: ar.j, info:eu-repo/semantics/published

Random Edge is the most natural randomized pivot rule for the simplex algorithm. Considerable progress has been made recently towards fully understanding its behavior. Back in 2001, Welzl introduced the concepts of reachmaps and niceness of Unique Sink Orientations (USO), in an effort to better understand the behavior of Random Edge. In this paper, we initiate the systematic study of these concepts. We settle the questions that were asked by Welzl about the niceness of (acyclic) USO. Niceness implies natural upper bounds for Random Edge and we provide evidence that these are tight or almost tight in many interesting cases. Moreover, we show that Random Edge is polynomial on at least n^{Omega(2^n)} many (possibly cyclic) USO. As a bonus, we describe a derandomization of Random Edge which achieves the same asymptotic upper bounds with respect to niceness.

Random sampling is a classical tool in constrained optimization. Under favorable conditions, the optimal solution subject to a small subset of randomly chosen constraints violates only a small subset of the remaining constraints. Here we study the following variant that we call random sampling with removal: suppose that after sampling the subset, we remove a fixed number of constraints from the sample, according to an arbitrary rule. Is it still true that the optimal solution of the reduced sample violates only a small subset of the constraints? The question naturally comes up in situations where the solution subject to the sampled constraints is used as an approximate solution to the original problem. In this case, it makes sense to improve cost and volatility of the sample solution by removing some of the constraints that appear most restricting. At the same time, the approximation quality (measured in terms of violated constraints) should remain high. We study random sampling with removal in a generalized, completely abstract setting where we assign to each subset R of the constraints an arbitrary set V(R) of constraints disjoint from R; in applications, V(R) corresponds to the constraints violated by the optimal solution subject to only the constraints in R. Furthermore, our results are parametrized by the dimension d, i.e., we assume that every set R has a subset B of size at most d with the same set of violated constraints. This is the first time this generalized setting is studied. In this setting, we prove matching upper and lower bounds for the expected number of constraints violated by a random sample, after the removal of k elements. For a large range of values of k, the new upper bounds improve the previously best bounds for LP-type problems, which moreover had only been known in special cases. We show that this bound on special LP-type problems, can be derived in the much more general setting of violator spaces, and with very elementary proofs.

We propose a new framework for deriving screening rules for convex optimization problems. Our approach covers a large class of constrained and penalized optimization formulations, and works in two steps. First, given any approximate point, the structure of the objective function and the duality gap is used to gather information on the optimal solution. In the second step, this information is used to produce screening rules, i.e. safely identifying unimportant weight variables of the optimal solution. Our general framework leads to a large variety of useful existing as well as new screening rules for many applications. For example, we provide new screening rules for general simplex and $L_1$-constrained problems, Elastic Net, squared-loss Support Vector Machines, minimum enclosing ball, as well as structured norm regularized problems, such as group lasso.

Random Edge is the most natural randomized pivot rule for the simplex algorithm. Considerable progress has been made recently towards fully understanding its behavior. Back in 2001, Welzl introduced the concepts of \emph{reachmaps} and \emph{niceness} of Unique Sink Orientations (USO), in an effort to better understand the behavior of Random Edge. In this paper, we initiate the systematic study of these concepts. We settle the questions that were asked by Welzl about the niceness of (acyclic) USO. Niceness implies natural upper bounds for Random Edge and we provide evidence that these are tight or almost tight in many interesting cases. Moreover, we show that Random Edge is polynomial on at least $n^{\Omega(2^n)}$ many (possibly cyclic) USO. As a bonus, we describe a derandomization of Random Edge which achieves the same asymptotic upper bounds with respect to niceness and discuss some algorithmic properties of the reachmap., Comment: An extended abstract appears in the proceedings of Approx/Random 2016

Suppose that a train is running along a railway network, starting from a designated origin, with the goal of reaching a designated destination. The network, however, is of a special nature: every time the train traverses a switch, the switch will change its position immediately afterwards. Hence, the next time the train traverses the same switch, the other direction will be taken, so that directions alternate with each traversal of the switch. Given a network with origin and destination, what is the complexity of deciding whether the train, starting at the origin, will eventually reach the destination? It is easy to see that this problem can be solved in exponential time, but we are not aware of any polynomial-time method. In this short paper, we prove that the problem is in NP $\cap$ coNP. This raises the question whether we have just failed to find a (simple) polynomial-time solution, or whether the complexity status is more subtle, as for some other well-known (two-player) graph games., Comment: 6 pages, 3 figures; final version is due to be published in the collection of papers "A Journey through Discrete Mathematics. A Tribute to Ji\v{r}\'i Matou\v{s}ek" edited by Martin Loebl, Jaroslav Ne\v{s}et\v{r}il and Robin Thomas, due to be published by Springer

A function $f: \mathbb{R}^d \rightarrow \mathbb{R}$ is a Sparse Additive Model (SPAM), if it is of the form $f(\mathbf{x}) = \sum_{l \in \mathcal{S}}\phi_{l}(x_l)$ where $\mathcal{S} \subset [d]$, $|\mathcal{S}| \ll d$. Assuming $\phi$'s, $\mathcal{S}$ to be unknown, there exists extensive work for estimating $f$ from its samples. In this work, we consider a generalized version of SPAMs, that also allows for the presence of a sparse number of second order interaction terms. For some $\mathcal{S}_1 \subset [d], \mathcal{S}_2 \subset {[d] \choose 2}$, with $|\mathcal{S}_1| \ll d, |\mathcal{S}_2| \ll d^2$, the function $f$ is now assumed to be of the form: $\sum_{p \in \mathcal{S}_1}\phi_{p} (x_p) + \sum_{(l,l^{\prime}) \in \mathcal{S}_2}\phi_{(l,l^{\prime})} (x_l,x_{l^{\prime}})$. Assuming we have the freedom to query $f$ anywhere in its domain, we derive efficient algorithms that provably recover $\mathcal{S}_1,\mathcal{S}_2$ with finite sample bounds. Our analysis covers the noiseless setting where exact samples of $f$ are obtained, and also extends to the noisy setting where the queries are corrupted with noise. For the noisy setting in particular, we consider two noise models namely: i.i.d Gaussian noise and arbitrary but bounded noise. Our main methods for identification of $\mathcal{S}_2$ essentially rely on estimation of sparse Hessian matrices, for which we provide two novel compressed sensing based schemes. Once $\mathcal{S}_1, \mathcal{S}_2$ are known, we show how the individual components $\phi_p$, $\phi_{(l,l^{\prime})}$ can be estimated via additional queries of $f$, with uniform error bounds. Lastly, we provide simulation results on synthetic data that validate our theoretical findings., Comment: To appear in Information and Inference: A Journal of the IMA. Made following changes after review process: (a) Corrected typos throughout the text. (b) Corrected choice of sampling distribution in Section 5, see eqs. (5.2), (5.3). (c) More detailed comparison with existing work in Section 8. (d) Added Section B in appendix on roots of cubic equation

A function $f: \mathbb{R}^d \rightarrow \mathbb{R}$ is referred to as a Sparse Additive Model (SPAM), if it is of the form $f(\mathbf{x}) = \sum_{l \in \mathcal{S}}\phi_{l}(x_l)$, where $\mathcal{S} \subset [d]$, $|\mathcal{S}| \ll d$. Assuming $\phi_l$'s and $\mathcal{S}$ to be unknown, the problem of estimating $f$ from its samples has been studied extensively. In this work, we consider a generalized SPAM, allowing for second order interaction terms. For some $\mathcal{S}_1 \subset [d], \mathcal{S}_2 \subset {[d] \choose 2}$, the function $f$ is assumed to be of the form: $$f(\mathbf{x}) = \sum_{p \in \mathcal{S}_1}\phi_{p} (x_p) + \sum_{(l,l^{\prime}) \in \mathcal{S}_2}\phi_{(l,l^{\prime})} (x_{l},x_{l^{\prime}}).$$ Assuming $\phi_{p},\phi_{(l,l^{\prime})}$, $\mathcal{S}_1$ and, $\mathcal{S}_2$ to be unknown, we provide a randomized algorithm that queries $f$ and exactly recovers $\mathcal{S}_1,\mathcal{S}_2$. Consequently, this also enables us to estimate the underlying $\phi_p, \phi_{(l,l^{\prime})}$. We derive sample complexity bounds for our scheme and also extend our analysis to include the situation where the queries are corrupted with noise -- either stochastic, or arbitrary but bounded. Lastly, we provide simulation results on synthetic data, that validate our theoretical findings., Comment: 23 pages, to appear in Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS) 2016

Given a Boolean Circuit with n inputs and n outputs, we want to decide if it represents a Unique Sink Orientation (USO). USOs are useful combinatorial objects that serve as abstraction of many relevant optimization problems. We prove that recognizing a USO is coNP-complete. However, the situation appears to be more complicated for recognizing acyclic USOs. Firstly, we give a construction to prove that there exist cyclic USOs where the smallest cycle is of superpolynomial size. This implies that the straightforward representation of a cycle (i.e. by a list of vertices) does not make up for a coNP certificate. Inspired by this fact, we investigate the connection of recognizing an acyclic USO to PSPACE and we prove that the problem is PSPACE-complete.

The problem of detecting and removing redundant constraints is fundamental in optimization. We focus on the case of linear programs (LPs) in dictionary form, given by n equality constraints in n+d variables, where the variables are constrained to be nonnegative. A variable x_r is called redundant, if after removing its nonnegativity constraint the LP still has the same feasible region. The time needed to solve such an LP is denoted by LP(n,d). It is easy to see that solving n+d LPs of the above size is sufficient to detect all redundancies. The currently fastest practical method is the one by Clarkson: it solves n+d linear programs, but each of them has at most s variables, where s is the number of nonredundant constraints. In the first part we show that knowing all of the finitely many dictionaries of the LP is sufficient for the purpose of redundancy detection. A dictionary is a matrix that can be thought of as an enriched encoding of a vertex in the LP. Moreover - and this is the combinatorial aspect - it is enough to know only the signs of the entries, the actual values do not matter. Concretely we show that for any variable x_r one can find a dictionary, such that its sign pattern is either a redundancy or nonredundancy certificate for x_r. In the second part we show that considering only the sign patterns of the dictionary, there is an output sensitive algorithm of running time of order d (n+d) s^{d-1} LP(s,d) + d s^{d} LP(n,d) to detect all redundancies. In the case where all constraints are in general position, the running time is of order s LP(n,d) + (n+d) LP(s,d), which is essentially the running time of the Clarkson method. Our algorithm extends naturally to a more general setting of arrangements of oriented topological hyperplane arrangements.

We study randomized algorithms for constrained optimization, in abstract frameworks that include, in strictly increasing generality: convex programming; LP-type problems; violator spaces; and a setting we introduce, consistent spaces. Such algorithms typically involve a step of finding the optimal solution for a random sample of the constraints. They exploit the condition that, in finite dimension $\delta$, this sample optimum violates a provably small expected fraction of the non-sampled constraints, with the fraction decreasing in the sample size~$r$. We extend such algorithms by considering the technique of removal, where a fixed number $k$ of constraints are removed from the sample according to a fixed rule, with the goal of improving the solution quality. This may have the effect of increasing the number of violated non-sampled constraints. We study this increase, and bound it in a variety of general settings. This work is motivated by, and extends, results on removal as proposed for chance-constrained optimization. For many relevant values of $r$, $\delta$, and $k$, we prove matching upper and lower bounds for the expected number of constraints violated by a random sample, after the removal of $k$ constraints. For a large range of values of $k$, the new upper bounds improve the previously best bounds for LP-type problems, which moreover had only been known in special cases, and not in the generality we consider. Moreover, we show that our results extend from finite to infinite spaces, for chance-constrained optimization.

In general dimension, there is no known total polynomial algorithm for either convex hull or vertex enumeration, i.e. an algorithm whose complexity depends polynomially on the input and output sizes. It is thus important to identify problems (and polytope representations) for which total polynomial-time algorithms can be obtained. We offer the first total polynomial-time algorithm for computing the edge-skeleton (including vertex enumeration) of a polytope given by an optimization or separation oracle, where we are also given a superset of its edge directions. We also offer a space-efficient variant of our algorithm by employing reverse search. All complexity bounds refer to the (oracle) Turing machine model. There is a number of polytope classes naturally defined by oracles; for some of them neither vertex nor facet representation is obvious. We consider two main applications, where we obtain (weakly) total polynomial-time algorithms: Signed Minkowski sums of convex polytopes, where polytopes can be subtracted provided the signed sum is a convex polytope, and computation of secondary, resultant, and discriminant polytopes. Further applications include convex combinatorial optimization and convex integer programming, where we offer a new approach, thus removing the complexity's exponential dependence in the dimension., Comment: 22 pages, 2 figures

The problem of detecting and removing redundant constraints is fundamental in optimization. We focus on the case of linear programs (LPs) in dictionary form, given by $n$ equality constraints in $n+d$ variables, where the variables are constrained to be nonnegative. A variable $x_r$ is called redundant, if after removing $x_r \geq 0$ the LP still has the same feasible region. The time needed to solve such an LP is denoted by $LP(n,d)$. It is easy to see that solving $n+d$ LPs of the above size is sufficient to detect all redundancies. The currently fastest practical method is the one by Clarkson: it solves $n+d$ linear programs, but each of them has at most $s$ variables, where $s$ is the number of nonredundant constraints. In the first part we show that knowing all of the finitely many dictionaries of the LP is sufficient for the purpose of redundancy detection. A dictionary is a matrix that can be thought of as an enriched encoding of a vertex in the LP. Moreover - and this is the combinatorial aspect - it is enough to know only the signs of the entries, the actual values do not matter. Concretely we show that for any variable $x_r$ one can find a dictionary, such that its sign pattern is either a redundancy or nonredundancy certificate for $x_r$. In the second part we show that considering only the sign patterns of the dictionary, there is an output sensitive algorithm of running time $\mathcal{O}(d \cdot (n+d) \cdot s^{d-1} \cdot LP(s,d) + d \cdot s^{d} \cdot LP(n,d))$ to detect all redundancies. In the case where all constraints are in general position, the running time is $\mathcal{O}(s \cdot LP(n,d) + (n+d) \cdot LP(s,d))$, which is essentially the running time of the Clarkson method. Our algorithm extends naturally to a more general setting of arrangements of oriented topological hyperplane arrangements.

We consider a stochastic continuum armed bandit problem where the arms are indexed by the $\ell_2$ ball $B_{d}(1+\nu)$ of radius $1+\nu$ in $\mathbb{R}^d$. The reward functions $r :B_{d}(1+\nu) \rightarrow \mathbb{R}$ are considered to intrinsically depend on $k \ll d$ unknown linear parameters so that $r(\mathbf{x}) = g(\mathbf{A} \mathbf{x})$ where $\mathbf{A}$ is a full rank $k \times d$ matrix. Assuming the mean reward function to be smooth we make use of results from low-rank matrix recovery literature and derive an efficient randomized algorithm which achieves a regret bound of $O(C(k,d) n^{\frac{1+k}{2+k}} (\log n)^{\frac{1}{2+k}})$ with high probability. Here $C(k,d)$ is at most polynomial in $d$ and $k$ and $n$ is the number of rounds or the sampling budget which is assumed to be known beforehand., Comment: Changes from previous version: (a) Corrected typos throughout. (b) In earlier version, regret was defined as a conditional expectation (and hence bounded w.h.p); this is changed to an expectation now resulting in minor changes in statements of Lemma 1, Theorems 1,2 and Corollary 1. See Remark 1. (c) Added Remark 3, and corrected statement of Proposition 3

The $d$-dimensional Goldfarb cube is a polytope with the property that all its $2^d$ vertices appear on some \emph{shadow} of it (projection onto a 2-dimensional plane). The Goldfarb cube is the solution set of a system of 2d linear inequalities with at most 3 variables per inequality. We show in this paper that the $d$-dimensional Klee-Minty cube --- constructed from inequalities with at most 2 variables per inequality --- also has a shadow with $2^d$ vertices. In contrast, with one variable per inequality, the size of the shadow is bounded by 2d., Comment: 10 pages

We consider the stochastic and adversarial settings of continuum armed bandits where the arms are indexed by [0,1]^d. The reward functions r:[0,1]^d -> R are assumed to intrinsically depend on at most k coordinate variables implying r(x_1,..,x_d) = g(x_{i_1},..,x_{i_k}) for distinct and unknown i_1,..,i_k from {1,..,d} and some locally Holder continuous g:[0,1]^k -> R with exponent 0 < alpha <= 1. Firstly, assuming (i_1,..,i_k) to be fixed across time, we propose a simple modification of the CAB1 algorithm where we construct the discrete set of sampling points to obtain a bound of O(n^((alpha+k)/(2*alpha+k)) (log n)^((alpha)/(2*alpha+k)) C(k,d)) on the regret, with C(k,d) depending at most polynomially in k and sub-logarithmically in d. The construction is based on creating partitions of {1,..,d} into k disjoint subsets and is probabilistic, hence our result holds with high probability. Secondly we extend our results to also handle the more general case where (i_1,...,i_k) can change over time and derive regret bounds for the same., Comment: (1) Appeared in proceedings of 11th Workshop on Approximation and Online Algorithms (WAOA 2013). (2) Corrected minor typos in previous version (3) 17 pages

We consider unconstrained randomized optimization of convex objective functions. We analyze the Random Pursuit algorithm, which iteratively computes an approximate solution to the optimization problem by repeated optimization over a randomly chosen one-dimensional subspace. This randomized method only uses zeroth-order information about the objective function and does not need any problem-specific parametrization. We prove convergence and give convergence rates for smooth objectives assuming that the one-dimensional optimization can be solved exactly or approximately by an oracle. A convenient property of Random Pursuit is its invariance under strictly monotone transformations of the objective function. It thus enjoys identical convergence behavior on a wider function class. To support the theoretical results we present extensive numerical performance results of Random Pursuit, two gradient-free algorithms recently proposed by Nesterov, and a classical adaptive step-size random search scheme. We also present an accelerated heuristic version of the Random Pursuit algorithm which significantly improves standard Random Pursuit on all numerical benchmark problems. A general comparison of the experimental results reveals that (i) standard Random Pursuit is effective on strongly convex functions with moderate condition number, and (ii) the accelerated scheme is comparable to Nesterov's fast gradient method and outperforms adaptive step-size strategies. The appendix contains additional supporting online material., Comment: 35 pages, 5 figures, 8 algorithms, 21 tables, submitted to journal The appendix contains additional supporting online material, not contained in the journal version

We give a polynomial-time dynamic programming algorithm for solving the linear complementarity problem with tridiagonal or, more generally, Hessenberg P-matrices. We briefly review three known tractable matrix classes and show that none of them contains all tridiagonal P-matrices., Comment: 4 pages, 3 figures

Unique-sink orientations (USOs) are an abstract class of orientations of the n-cube graph. We consider some classes of USOs that are of interest in connection with the linear complementarity problem. We summarise old and show new lower and upper bounds on the sizes of some such classes. Furthermore, we provide a characterisation of K-matrices in terms of their corresponding USOs., Comment: 13 pages; v2: proof of main theorem expanded, plus various other corrections. Now 16 pages; v3: minor corrections

Clarksons algorithm is a two-staged randomized algorithm for solving linear programs. This algorithm has been simplified and adapted to fit the framework of LP-type problems. In this framework we can tackle a number of non-linear problems such as computing the smallest enclosing ball of a set of points in R^d . In 2006, it has been shown that the algorithm in its original form works for violator spaces too, which are a proper general- ization of LP-type problems. It was not clear, however, whether previous simplifications of the algorithm carry over to the new setting. In this paper we show the following theoretical results: (a) It is shown, for the first time, that Clarksons second stage can be simplified. (b) The previous simplifications of Clarksons first stage carry over to the violator space setting. (c) Furthermore, we show the equivalence of violator spaces and partitions of the hypercube by hypercubes., Comment: 21 pages

For a wide variety of regularization methods, algorithms computing the entire solution path have been developed recently. Solution path algorithms do not only compute the solution for one particular value of the regularization parameter but the entire path of solutions, making the selection of an optimal parameter much easier. Most of the currently used algorithms are not robust in the sense that they cannot deal with general or degenerate input. Here we present a new robust, generic method for parametric quadratic programming. Our algorithm directly applies to nearly all machine learning applications, where so far every application required its own different algorithm. We illustrate the usefulness of our method by applying it to a very low rank problem which could not be solved by existing path tracking methods, namely to compute part-worth values in choice based conjoint analysis, a popular technique from market research to estimate consumers preferences on a class of parameterized options., Comment: 7 Pages, 1 Figure

For a variety of regularized optimization problems in machine learning, algorithms computing the entire solution path have been developed recently. Most of these methods are quadratic programs that are parameterized by a single parameter, as for example the Support Vector Machine (SVM). Solution path algorithms do not only compute the solution for one particular value of the regularization parameter but the entire path of solutions, making the selection of an optimal parameter much easier. It has been assumed that these piecewise linear solution paths have only linear complexity, i.e. linearly many bends. We prove that for the support vector machine this complexity can be exponential in the number of training points in the worst case. More strongly, we construct a single instance of n input points in d dimensions for an SVM such that at least \Theta(2^{n/2}) = \Theta(2^d) many distinct subsets of support vectors occur as the regularization parameter changes., Comment: Journal version, 28 Pages, 5 Figures

Given a set of n unit squares in the plane, the goal is to rank them in space in such a way that only few squares see each other vertically. We prove that ranking the squares according to the lexicographic order of their centers results in at most 3n-7 pairwise visibilities for n at least 4. We also show that this bound is best possible, by exhibiting a set of n squares with at least 3n-7 pairwise visibilities under any ranking., Comment: 4 pages, 2 EPS-figures

Sharir and Welzl introduced an abstract framework for optimization problems, called LP-type problems or also generalized linear programming problems, which proved useful in algorithm design. We define a new, and as we believe, simpler and more natural framework: violator spaces, which constitute a proper generalization of LP-type problems. We show that Clarkson's randomized algorithms for low-dimensional linear programming work in the context of violator spaces. For example, in this way we obtain the fastest known algorithm for the P-matrix generalized linear complementarity problem with a constant number of blocks. We also give two new characterizations of LP-type problems: they are equivalent to acyclic violator spaces, as well as to concrete LP-type problems (informally, the constraints in a concrete LP-type problem are subsets of a linearly ordered ground set, and the value of a set of constraints is the minimum of its intersection)., Comment: 28 pages, 5 figures, extended abstract was presented at ESA 2006; author spelling fixed

We introduce unique sink orientations of grids as digraph models for many well-studied problems, including linear programming over products of simplices, generalized linear complementarity problems over P-matrices (PGLCP), and simple stochastic games. We investigate the combinatorial structure of such orientations and develop randomized algorithms for finding the sink. We show that the orientations arising from PGLCP satisfy the Holt-Klee condition known to hold for polytope digraphs, and we give the first expected linear-time algorithms for solving PGLCP with a fixed number of blocks

We investigate the combinatorial structure of linear programs on simple d-polytopes with d + 2 facets. These can be encoded by admissible grid orientations. Admissible grid orientations are also obtained through orientation properties of a planar point configuration or by the dual line arrangement. The point configuration and the polytope corresponding to the same grid are related through an extended Gale transform. The class of admissible grid orientations is shown to contain nonrealizable examples, i.e., there are admissible grid orientations which cannot be obtained from a polytope or a point configuration. It is shown, however, that every admissible grid orientation is induced by an arrangement of pseudolines. This later result is used to prove several nontrivial facts about admissible grid orientations

We study the behavior of simple principal pivoting methods for the P-matrix linear complementarity problem (P-LCP). We solve an open problem of Morris by showing that Murty's least-index pivot rule (under any fixed index order) leads to a quadratic number of iterations on Morris's highly cyclic P-LCP examples. We then show that on K-matrix LCP instances, all pivot rules require only a linear number of iterations. As the main tool, we employ unique-sink orientations of cubes, a useful combinatorial abstraction of the P-LCP