Bayesian optimization with local search. (arXiv:1911.09159v1 [stat.ML])

Global optimization finds applications in a wide range of real world problems. The multi-start methods are a popular class of global optimization techniques, which are based on the ideas of conducting local searches at multiple starting points, and then sequentially determine the starting points according to some prescribed rules. In this work we propose a…

Deep Active Learning: Unified and Principled Method for Query and Training. (arXiv:1911.09162v1 [cs.LG])

In this paper, we proposed a unified and principled method for both querying and training process in deep batch active learning. We provided the theoretical insights from the intuition of modeling the interactive procedure in active learning as distribution matching, by adopting Wasserstein distance. As a consequence, we derived a new training loss from the…

The Karger-Stein Algorithm is Optimal for $k$-cut. (arXiv:1911.09165v1 [cs.DS])

In the $k$-cut problem, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into $k$ connected components. Algorithms due to Karger-Stein and Thorup showed how to find such a minimum $k$-cut in time approximately $O(n^{2k-2})$. The best lower bounds come from conjectures about the…

Active Learning for Deep Detection Neural Networks. (arXiv:1911.09168v1 [cs.CV])

The cost of drawing object bounding boxes (i.e. labeling) for millions of images is prohibitively high. For instance, labeling pedestrians in a regular urban image could take 35 seconds on average. Active learning aims to reduce the cost of labeling by selecting only those images that are informative to improve the detection network accuracy. In…

Mutating Epidemic Processes Over Time-Varying Networks in Discrete-Time. (arXiv:1911.09175v1 [eess.SY])

This paper studies epidemic processes over discrete-time periodic time-varying networks. Our objective is to find necessary and sufficient conditions for asymptotic convergence to the disease-free equilibrium (DFE). We provide, in terms of the joint spectral radius of a set of matrices, a sufficient condition for global asymptotic stability (GAS) of the DFE. Subsequently, we provide,…

Lower Bounds for Function Inversion with Quantum Advice. (arXiv:1911.09176v1 [quant-ph])

Function inversion is that given a random function $f: [M] \to [N]$, we want to compute some auxiliary information of size $S$ that we can find pre-image of any image with a few queries to the function given as a black box in time $T$. It is a well-studied problem in the classical settings, however,…

Large-scale Multi-view Subspace Clustering in Linear Time. (arXiv:1911.09290v1 [cs.LG])

A plethora of multi-view subspace clustering (MVSC) methods have been proposed over the past few years. Researchers manage to boost clustering accuracy from different points of view. However, many state-of-the-art MVSC algorithms, typically have a quadratic or even cubic complexity, are inefficient and inherently difficult to apply at large scales. In the era of big…

Scalable methods for computing state similarity in deterministic Markov Decision Processes. (arXiv:1911.09291v1 [cs.LG])

We present new algorithms for computing and approximating bisimulation metrics in Markov Decision Processes (MDPs). Bisimulation metrics are an elegant formalism that capture behavioral equivalence between states and provide strong theoretical guarantees on differences in optimal behaviour. Unfortunately, their computation is expensive and requires a tabular representation of the states, which has thus far rendered…

Multi-level scalar structure in complex system analyses. (arXiv:1911.09294v1 [physics.flu-dyn])

The geometrical structure is among the most fundamental ingredients in understanding complex systems. Is there any systematic approach in defining structures quantitatively, rather than illustratively? If yes, what are the basic principles to follow? By introducing the concept of extremal points at different scale levels, a multi-level dissipation element approach has been developed to define…

Patch-level Neighborhood Interpolation: A General and Effective Graph-based Regularization Strategy. (arXiv:1911.09307v1 [cs.LG])

Regularization plays a crucial role in machine learning models, especially for deep neural networks. The existing regularization techniques mainly reply on the i.i.d. assumption and only employ the information of the current sample, without the leverage of neighboring information between samples. In this work, we propose a general regularizer called Patch-level Neighborhood Interpolation~(\textbf{Pani}) that fully…