OpenRaiser/Intern-Atlas huggingface dataset:
Affine reductions for LPs and SDPs
Venue: arXiv cs.CC 2016
Year: 2016

We define a reduction mechanism for LP and SDP formulations that degrades approximation factors in a controlled fashion. Our reduction mechanism is a minor restriction of classical reductions establishing inapproximability in the context of PCP theorems. As a consequence we establish strong linear programming inapproximability (for LPs with a polynomial number of constraints) for many problems. In particular we obtain a $3/2-\varepsilon$ inapproximability for VertexCover answering an open question in [arXiv:1309.0563] and we answer a weak version of our sparse graph conjecture posed in [arXiv:1311.4001] showing an inapproximability factor of $1/2+\varepsilon$ for bounded degree IndependentSet. In the case of SDPs, we obtain inapproximability results for these problems relative to the SDP-inapproximability of MaxCUT. Moreover, using our reduction framework we are able to reproduce various results for CSPs from [arXiv:1309.0563] via simple reductions from Max-2-XOR.
Distributed Submodular Maximization
Venue: arXiv cs.LG 2016
Year: 2016

Many large-scale machine learning problems--clustering, non-parametric learning, kernel machines, etc.--require selecting a small yet representative subset from a large dataset. Such problems can often be reduced to maximizing a submodular set function subject to various constraints. Classical approaches to submodular optimization require centralized access to the full dataset, which is impractical for truly large-scale problems. In this paper, we consider the problem of submodular function maximization in a distributed fashion. We develop a simple, two-stage protocol GreeDi, that is easily implemented using MapReduce style computations. We theoretically analyze our approach, and show that under certain natural conditions, performance close to the centralized approach can be achieved. We begin with monotone submodular maximization subject to a cardinality constraint, and then extend this approach to obtain approximation guarantees for (not necessarily monotone) submodular maximization subject to more general constraints including matroid or knapsack constraints. In our extensive experiments, we demonstrate the effectiveness of our approach on several applications, including sparse Gaussian process inference and exemplar based clustering on tens of millions of examples using Hadoop.
On the Universality of Jordan Centers for Estimating Infection Sources in Tree Networks
Venue: arXiv cs.SI 2016
Year: 2016

Finding the infection sources in a network when we only know the network topology and infected nodes, but not the rates of infection, is a challenging combinatorial problem, and it is even more difficult in practice where the underlying infection spreading model is usually unknown a priori. In this paper, we are interested in finding a source estimator that is applicable to various spreading models, including the Susceptible-Infected (SI), Susceptible-Infected-Recovered (SIR), Susceptible-Infected-Recovered-Infected (SIRI), and Susceptible-Infected-Susceptible (SIS) models. We show that under the SI, SIR and SIRI spreading models and with mild technical assumptions, the Jordan center is the infection source associated with the most likely infection path in a tree network with a single infection source. This conclusion applies for a wide range of spreading parameters, while it holds for regular trees under the SIS model with homogeneous infection and recovery rates. Since the Jordan center does not depend on the infection, recovery and reinfection rates, it can be regarded as a universal source estimator. We also consider the case where there are k>1 infection sources, generalize the Jordan center definition to a k-Jordan center set, and show that this is an optimal infection source set estimator in a tree network for the SI model. Simulation results on various general synthetic networks and real world networks suggest that Jordan center-based estimators consistently outperform the betweenness, closeness, distance, degree, eigenvector, and pagerank centrality based heuristics, even if the network is not a tree.
Bayesian M-ary Hypothesis Testing: The Meta-Converse and Verdú-Han Bounds are Tight
Venue: arXiv cs.IT 2016
Year: 2016

Two alternative exact characterizations of the minimum error probability of Bayesian M-ary hypothesis testing are derived. The first expression corresponds to the error probability of an induced binary hypothesis test and implies the tightness of the meta-converse bound by Polyanskiy, Poor and Verdú; the second expression is function of an information-spectrum measure and implies the tightness of a generalized Verdú-Han lower bound. The formulas characterize the minimum error probability of several problems in information theory and help to identify the steps where existing converse bounds are loose.
A Field Guide to Forward-Backward Splitting with a FASTA Implementation
Venue: arXiv cs.NA 2016
Year: 2016

Non-differentiable and constrained optimization play a key role in machine learning, signal and image processing, communications, and beyond. For high-dimensional minimization problems involving large datasets or many unknowns, the forward-backward splitting method provides a simple, practical solver. Despite its apparently simplicity, the performance of the forward-backward splitting is highly sensitive to implementation details. This article is an introductory review of forward-backward splitting with a special emphasis on practical implementation concerns. Issues like stepsize selection, acceleration, stopping conditions, and initialization are considered. Numerical experiments are used to compare the effectiveness of different approaches. Many variations of forward-backward splitting are implemented in the solver FASTA (short for Fast Adaptive Shrinkage/Thresholding Algorithm). FASTA provides a simple interface for applying forward-backward splitting to a broad range of problems.
Online Clique Clustering
Venue: arXiv cs.DS 2016
Year: 2016

Clique clustering is the problem of partitioning the vertices of a graph into disjoint clusters, where each cluster forms a clique in the graph, while optimizing some objective function. In online clustering, the input graph is given one vertex at a time, and any vertices that have previously been clustered together are not allowed to be separated. The goal is to maintain a clustering with an objective value close to the optimal solution. For the variant where we want to maximize the number of edges in the clusters, we propose an online strategy based on the doubling technique. It has an asymptotic competitive ratio at most 15.646 and an absolute competitive ratio at most 22.641. We also show that no deterministic strategy can have an asymptotic competitive ratio better than 6. For the variant where we want to minimize the number of edges between clusters, we show that the deterministic competitive ratio of the problem is $n-ω(1)$, where n is the number of vertices in the graph.
Channel Aided Interference Alignment
Venue: arXiv cs.IT 2016
Year: 2016

Interference alignment (IA) techniques mostly attain their degrees of freedom (DoF) benefits as the number of channel extensions tends to infinity. Intuitively, the more interfering signals that need to be aligned, the larger the number of dimensions needed to align them. This requirement poses a major challenge for IA in practical systems. This work evaluates the necessary and sufficient conditions on channel structure of a fully connected interference network with time-varying fading to make perfect IA feasible within limited number of channel extensions. We propose a method based on the obtained conditions on the channel structure to achieve perfect IA. For the case of $3$ user interference channel, it is shown that only one condition on channel coefficients is required to make perfect IA feasible at all receivers. IA feasibility literature have mainly focused on network topology so far. In contrast, derived channel aiding conditions in this work can be considered as the perfect IA feasibility conditions on channel structure.
Optimization-based Alignment for Strapdown Inertial Navigation System Comparison and Extension
Venue: arXiv cs.RO 2016
Year: 2016

In this paper, the optimization-based alignment (OBA) methods are investigated with main focus on the vector observations construction procedures for the strapdown inertial navigation system (SINS). The contributions of this study are twofold. First the OBA method is extended to be able to estimate the gyroscopes biases coupled with the attitude based on the construction process of the existing OBA methods. This extension transforms the initial alignment into an attitude estimation problem which can be solved using the nonlinear filtering algorithms. The second contribution is the comprehensive evaluation of the OBA methods and their extensions with different vector observations construction procedures in terms of convergent speed and steady-state estimate using field test data collected from different grades of SINS. This study is expected to facilitate the selection of appropriate OBA methods for different grade SINS.
Uncovering Droop Control Laws Embedded Within the Nonlinear Dynamics of Van der Pol Oscillators
Venue: arXiv cs.SY 2016
Year: 2016

This paper examines the dynamics of power-electronic inverters in islanded microgrids that are controlled to emulate the dynamics of Van der Pol oscillators. The general strategy of controlling inverters to emulate the behavior of nonlinear oscillators presents a compelling time-domain alternative to ubiquitous droop control methods which presume the existence of a quasi-stationary sinusoidal steady state and operate on phasor quantities. We present two main results in this work. First, by leveraging the method of periodic averaging, we demonstrate that droop laws are intrinsically embedded within a slower time scale in the nonlinear dynamics of Van der Pol oscillators. Second, we establish the global convergence of amplitude and phase dynamics in a resistive network interconnecting inverters controlled as Van der Pol oscillators. Furthermore, under a set of non-restrictive decoupling approximations, we derive sufficient conditions for local exponential stability of desirable equilibria of the linearized amplitude and phase dynamics.
Hashing for statistics over k-partitions
Venue: arXiv cs.DS 2016
Year: 2016

In this paper we analyze a hash function for $k$-partitioning a set into bins, obtaining strong concentration bounds for standard algorithms combining statistics from each bin. This generic method was originally introduced by Flajolet and Martin~[FOCS'83] in order to save a factor $Ω(k)$ of time per element over $k$ independent samples when estimating the number of distinct elements in a data stream. It was also used in the widely used HyperLogLog algorithm of Flajolet et al.~[AOFA'97] and in large-scale machine learning by Li et al.~[NIPS'12] for minwise estimation of set similarity. The main issue of $k$-partition, is that the contents of different bins may be highly correlated when using popular hash functions. This means that methods of analyzing the marginal distribution for a single bin do not apply. Here we show that a tabulation based hash function, mixed tabulation, does yield strong concentration bounds on the most popular applications of $k$-partitioning similar to those we would get using a truly random hash function. The analysis is very involved and implies several new results of independent interest for both simple and double tabulation, e.g. a simple and efficient construction for invertible bloom filters and uniform hashing on a given set.
Guaranteed Matrix Completion via Non-convex Factorization
Venue: arXiv cs.LG 2016
Year: 2016

Matrix factorization is a popular approach for large-scale matrix completion. The optimization formulation based on matrix factorization can be solved very efficiently by standard algorithms in practice. However, due to the non-convexity caused by the factorization model, there is a limited theoretical understanding of this formulation. In this paper, we establish a theoretical guarantee for the factorization formulation to correctly recover the underlying low-rank matrix. In particular, we show that under similar conditions to those in previous works, many standard optimization algorithms converge to the global optima of a factorization formulation, and recover the true low-rank matrix. We study the local geometry of a properly regularized factorization formulation and prove that any stationary point in a certain local region is globally optimal. A major difference of our work from the existing results is that we do not need resampling in either the algorithm or its analysis. Compared to other works on nonconvex optimization, one extra difficulty lies in analyzing nonconvex constrained optimization when the constraint (or the corresponding regularizer) is not "consistent" with the gradient direction. One technical contribution is the perturbation analysis for non-symmetric matrix factorization.
Matchings with lower quotas: Algorithms and complexity
Venue: arXiv cs.DM 2016
Year: 2016

We study a natural generalization of the maximum weight many-to-one matching problem. We are given an undirected bipartite graph $G= (A \cup P, E)$ with weights on the edges in $E$, and with lower and upper quotas on the vertices in $P$. We seek a maximum weight many-to-one matching satisfying two sets of constraints: vertices in $A$ are incident to at most one matching edge, while vertices in $P$ are either unmatched or they are incident to a number of matching edges between their lower and upper quota. This problem, which we call maximum weight many-to-one matching with lower and upper quotas (WMLQ), has applications to the assignment of students to projects within university courses, where there are constraints on the minimum and maximum numbers of students that must be assigned to each project. In this paper, we provide a comprehensive analysis of the complexity of WMLQ from the viewpoints of classic polynomial time algorithms, fixed-parameter tractability, as well as approximability. We draw the line between NP-hard and polynomially tractable instances in terms of degree and quota constraints and provide efficient algorithms to solve the tractable ones. We further show that the problem can be solved in polynomial time for instances with bounded treewidth; however, the corresponding runtime is exponential in the treewidth with the maximum upper quota $u_{max}$ as basis, and we prove that this dependence is necessary unless FPT = W[1]. The approximability of WMLQ is also discussed: we present an approximation algorithm for the general case with performance guarantee $u_{\max}+1$, which is asymptotically best possible unless P = NP. Finally, we elaborate on how most of our positive results carry over to matchings in arbitrary graphs with lower quotas.
An Algorithmic Separating Hyperplane Theorem and Its Applications
Venue: arXiv cs.CC 2016
Year: 2016

We first prove a new separating hyperplane theorem characterizing when a pair of compact convex subsets $K, K'$ of the Euclidean space intersect, and when they are disjoint. The theorem is distinct from classical separation theorems. It generalizes the {\it distance duality} proved in our earlier work for testing the membership of a distinguished point in the convex hull of a finite point set. Next by utilizing the theorem, we develop a substantially generalized and stronger version of the {\it Triangle Algorithm} introduced in the previous work to perform any of the following three tasks: (1) To compute a pair $(p,p') \in K \times K'$, where either the Euclidean distance $d(p,p')$ is to within a prescribed tolerance, or the orthogonal bisecting hyperplane of the line segment $pp'$ separates the two sets; (2) When $K$ and $K'$ are disjoint, to compute $(p,p') \in K \times K'$ so that $d(p,p')$ approximates $d(K,K')$ to within a prescribed tolerance; (3) When $K$ and $K'$ are disjoint, to compute a pair of parallel supporting hyperplanes $H,H'$ so that $d(H,H')$ is to within a prescribed tolerance of the optimal margin. The worst-case complexity of each iteration is solving a linear objective over $K$ or $K'$. The resulting algorithm is a fully polynomial-time approximation scheme for such important special cases as when $K$ and $K'$ are convex hulls of finite points sets, or the intersection of a finite number of halfspaces. The results find many theoretical and practical applications, such as in machine learning, statistics, linear, quadratic and convex programming. In particular, in a separate article we report on a comparison of the Triangle Algorithm and SMO for solving the hard margin problem. In future work we extend the applications to combinatorial and NP-complete problems.
Optimization Algorithms for Faster Computational Geometry
Venue: arXiv cs.CG 2016
Year: 2016

We study two fundamental problems in computational geometry: finding the maximum inscribed ball (MaxIB) inside a bounded polyhedron defined by $m$ hyperplanes, and the minimum enclosing ball (MinEB) of a set of $n$ points, both in $d$-dimensional space. We improve the running time of iterative algorithms on MaxIB from $\tilde{O}(m d α^3 / \varepsilon^3)$ to $\tilde{O}(md + m \sqrt{d} α/ \varepsilon)$, a speed-up up to $\tilde{O}(\sqrt{d} α^2 / \varepsilon^2)$, and MinEB from $\tilde{O}(n d / \sqrt{\varepsilon})$ to $\tilde{O}(nd + n \sqrt{d} / \sqrt{\varepsilon})$, a speed-up up to $\tilde{O}(\sqrt{d})$. Our improvements are based on a novel saddle-point optimization framework. We propose a new algorithm $\mathtt{L1L2SPSolver}$ for solving a class of regularized saddle-point problems, and apply a randomized Hadamard space rotation which is a technique borrowed from compressive sensing. Interestingly, the motivation of using Hadamard rotation solely comes from our optimization view but not the original geometry problem: indeed, it is not immediately clear why MaxIB or MinEB, as a geometric problem, should be easier to solve if we rotate the space by a unitary matrix. We hope that our optimization perspective sheds lights on solving other geometric problems as well.
Problem Theory
Venue: arXiv cs.AI 2016
Year: 2016

The Turing machine, as it was presented by Turing himself, models the calculations done by a person. This means that we can compute whatever any Turing machine can compute, and therefore we are Turing complete. The question addressed here is why, Why are we Turing complete? Being Turing complete also means that somehow our brain implements the function that a universal Turing machine implements. The point is that evolution achieved Turing completeness, and then the explanation should be evolutionary, but our explanation is mathematical. The trick is to introduce a mathematical theory of problems, under the basic assumption that solving more problems provides more survival opportunities. So we build a problem theory by fusing set and computing theories. Then we construct a series of resolvers, where each resolver is defined by its computing capacity, that exhibits the following property: all problems solved by a resolver are also solved by the next resolver in the series if certain condition is satisfied. The last of the conditions is to be Turing complete. This series defines a resolvers hierarchy that could be seen as a framework for the evolution of cognition. Then the answer to our question would be: to solve most problems. By the way, the problem theory defines adaptation, perception, and learning, and it shows that there are just three ways to resolve any problem: routine, trial, and analogy. And, most importantly, this theory demonstrates how problems can be used to found mathematics and computing on biology.
New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs
Venue: arXiv cs.CC 2016
Year: 2016

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain amount of overlap without being in conflict. In one of the most natural generalizations of tolerance graphs with direct applications in the comparison of DNA sequences from different organisms, namely multitolerance graphs, two tolerances are allowed for each interval - one from the left and one from the right side. Several efficient algorithms for optimization problems that are NP-hard in general graphs have been designed for tolerance and multitolerance graphs. In spite of this progress, the complexity status of some fundamental algorithmic problems on tolerance and multitolerance graphs, such as the dominating set problem, remained unresolved until now, three decades after the introduction of tolerance graphs. In this article we introduce two new geometric representations for tolerance and multitolerance graphs, given by points and line segments in the plane. Apart from being important on their own, these new representations prove to be a powerful tool for deriving both hardness results and polynomial time algorithms. Using them, we surprisingly prove that the dominating set problem can be solved in polynomial time on tolerance graphs and that it is APX-hard on multitolerance graphs, solving thus a longstanding open problem. This problem is the first one that has been discovered with a different complexity status in these two graph classes.
Analogue-digital systems with modes of physical behaviour
Venue: arXiv cs.SE 2016
Year: 2016

Complex environments, processes and systems may exhibit several distinct modes of physical behaviour or operation. Thus, for example, in their design, a set of mathematical models may be needed, each model having its own domain of application and representing a particular mode of behaviour or operation of physical reality. The models may be of disparate kinds { discrete or continuous in data, time and space. Furthermore, some physical modes may not have a reliable model. Physical measurements determine modes of operation. We explore the question: What is a mode of behaviour? How do we specify algorithms and software that monitor or govern a complex physical situation with many modes? How do we specify a portfolio of modes, and the computational problem of transitioning from using one mode to another mode as physical modes change? We propose a general definition of an analogue-digital system with modes. We show how any diverse set of modes { with or without models { can be bound together, and how the transitions between modes can be determined, by constructing a topological data type based upon a simplicial complex. We illustrate the ideas of physical modes and our theory by reflecting on simple examples, including driverless racing cars.
Semi-Supervised Learning with Heterophily
Venue: arXiv cs.LG 2016
Year: 2016

We derive a family of linear inference algorithms that generalize existing graph-based label propagation algorithms by allowing them to propagate generalized assumptions about "attraction" or "compatibility" between classes of neighboring nodes (in particular those that involve heterophily between nodes where "opposites attract"). We thus call this formulation Semi-Supervised Learning with Heterophily (SSLH) and show how it generalizes and improves upon a recently proposed approach called Linearized Belief Propagation (LinBP). Importantly, our framework allows us to reduce the problem of estimating the relative compatibility between nodes from partially labeled graph to a simple optimization problem. The result is a very fast algorithm that -- despite its simplicity -- is surprisingly effective: we can classify unlabeled nodes within the same graph in the same time as LinBP but with a superior accuracy and despite our algorithm not knowing the compatibilities.