Combinatorial Optimization
Jun 12, 2019
Speakers
Abolfazl Hashemi
Speaker · 1 follower
Alan Kuhnle
Speaker · 0 followers
Amin Karbasi
Speaker · 2 followers
Eduardo Laber
Speaker · 0 followers
Ehsan Kazemi
Speaker · 0 followers
F. Bruce Shepherd
Speaker · 0 followers
Ferdinando Cicalese
Speaker · 0 followers
Haris Vikalo
Speaker · 0 followers
Joan Bruna
Speaker · 4 followers
Kaito Fujii
Speaker · 0 followers
Lucas Murtinho
Speaker · 0 followers
Mahsa Ghasemi
Speaker · 0 followers
Manish Purohit
Speaker · 0 followers
Manish Raghavan
Speaker · 0 followers
Marko Mitrovic
Speaker · 0 followers
Mohammad Hossein Bateni
Speaker · 0 followers
Mohsen Ghaffari
Speaker · 0 followers
Morteza Zadimoghaddam
Speaker · 0 followers
Richard Santiago
Speaker · 0 followers
Sepehr Assadi
Speaker · 0 followers
Shinsaku Sakaue
Speaker · 0 followers
Silvio Lattanzi
Speaker · 0 followers
Slobodan Mitrović
Speaker · 0 followers
Sreenivas Gollapudi
Speaker · 0 followers
Thomas Frerix
Speaker · 0 followers
Ufuk Topcu
Speaker · 0 followers
Vahab Mirrokni
Speaker · 0 followers
Victoria Crawford
Speaker · 0 followers
About
Distributed Weighted Matching via Randomized Composable Coresets Maximum weight matching is one of the most fundamental combinatorial optimization problems with a wide range of applications in data mining and bioinformatics. Developing distributed weighted matching algorithms has been challenging due to the sequential nature of efficient algorithms for this problem. In this paper, we develop a simple distributed algorithm for the problem on general graphs with approximation guarantee of 2 + eps that (nearly) matches that of the sequential greedy algorithm. A key advantage of this algorithm is that it can be easily implemented in only two rounds of computation in modern parallel computation frameworks such as MapReduce. We also demonstrate the efficiency of our algorithm in practice on various graphs (some with half a trillion edges) by achieving objective values always close to what is achievable in the centralized setting. Multivariate Submodular Optimization Submodular functions have found a wealth of new applications in data science and machine learning models in recent years. This has been coupled with many algorithmic advances in the area of submodular optimization Beyond Adaptive Submodularity: Approximation Guarantees of Greedy Policy with Adaptive Submodularity Ratio We propose a new concept named adaptive submodularity ratio to study the greedy policy for sequential decision making. While the greedy policy is known to perform well for a wide variety of adaptive stochastic optimization problems in practice, its theoretical properties have been analyzed only for a limited class of problems. We narrow the gap between theory and practice by using adaptive submodularity ratio, which enables us to prove approximation guarantees of the greedy policy for a substantially wider class of problems. Examples of newly analyzed problems include important applications such as adaptive influence maximization and adaptive feature selection. Our adaptive submodularity ratio also provides bounds of adaptivity gaps. Experiments confirm that the greedy policy performs well with the applications being considered compared to standard heuristics. Approximating Orthogonal Matrices with Effective Givens Factorization We develop effective approximation methods for unitary matrices. In our formulation, a unitary matrix is represented as a product of rotations in two-dimensional subspaces, so-called Givens rotations. Instead of the quadratic dimension dependence when applying a dense matrix, applying such an approximation scales with the number factors, each of which can be implemented efficiently. Consequently, in settings where an approximation is once computed and then applied many times, such an effective representation becomes advantageous. Although efficient Givens factorizations are not possible for generic unitary operators, we show that minimizing a sparsity-inducing objective with a coordinate descent algorithm on the unitary group yields good factorizations for structured matrices. Canonical applications of such a setup are orthogonal basis transforms. We demonstrate that our methods improve the approximate representation of the graph Fourier transform, the matrix obtained when diagonalizing a graph Laplacian. New results on information theoretic clustering An impurity measure I is a function that assigns a vector v to a non-negative value so that the more homogeneous v, with respect to the values of its components, the larger its impurity. We study the problem of optimizing the clustering of a set of vectors when the quality of the clustering is measured by the Entropy or the Gini impurity. Notwithstanding the wide use in relevant applications of this type of clustering, what is known in terms of optimal (approximation) algorithms and/or related complexity limitations (inapproximability) is still limited. Our results improve the state of the art both in terms of best known approximation guarantees and inapproximability bounds: (i) we give the first polynomial time algorithm for Entropy impurity based clustering with approximation guarantee independent of the number of vectors and (ii) we show that the problem of clustering based on entropy impurity does not admit a PTAS. This also implies on an inapproximability result in information theoretic clustering for probability distributions closing a problem left open in [Chaudhury and McGregor, COLT08] and [Ackermann et al., ECCC11]. We also report experiments on a novel clustering method based on the theoretical tools leading to the above results. Tested for word clustering, our implementation produces clusterings with impurity close to those given by state of the art algorithms with the advantage of running up to 3 orders of magnitude faster. Improved Parallel Algorithms for Density-Based Network Clustering Clustering large-scale networks is a central topic in unsupervised learning with many applications in machine learning and data mining. A classic approach to cluster a network is to identify regions of high edge density. In literature this approach is captured by two fundamental problems: the densest subgraph and the k-core decomposition problems. We design massively parallel computation (MPC) algorithms for these problems that are considerably faster than prior work. In the case of k-core decomposition, our work improves exponentially on the algorithm provided by Esfandiari et al.~(ICML'18). Compared to the prior work on densest subgraph presented by Bahmani et al.~(VLDB'12, '14), our result requires quadratically fewer MPC rounds. We complement our analysis with an experimental scalability analysis of our techniques. Submodular Observation Selection and Information Gathering for Quadratic Models We study the problem of selecting a subset of observations that enable accurate prediction of unknown parameters, i.e., the task of choosing the most informative observations from a potentially significantly larger set. This problem arises in a variety of settings in machine learning and signal processing including feature selection, phase retrieval, and target localization. For quadratic measurement models, the moment matrix is generally unknown and the practice of optimizing the so-called alphabetical selection criteria no longer guarantees selection of a near-optimal subset. Majority of prior work resorts to approximation techniques such as linearization of the measurement model to optimize the utility of an approximate moment matrix. In contrast, by exploiting a connection to the classical Van Trees' inequality, we derive new alphabetical optimality criteria without distorting the relational structure of the measurement model. We further show that under certain conditions on parameters of the problem these optimality criteria are monotone and (weak) submodular set functions. These results enable us to develop an efficient greedy observation selection algorithm uniquely tailored for quadratic models, and provide theoretical bounds on its achievable utility. Extensive numerical experiments demonstrate efficacy of the proposed framework. Submodular Cost Submodular Cover with an Approximate Oracle In this work, we study the Submodular Cost Submodular Cover problem, which is to minimize the submodular cost required to ensure that the submodular benefit function exceeds a given threshold. Existing approximation ratios for the greedy algorithm assume a value oracle to the benefit function. However, access to a value oracle is not a realistic assumption for many applications of this problem, where the benefit function is difficult to compute. We present two incomparable approximation ratios for this problem with an approximate value oracle and demonstrate that the ratios take on empirically relevant values through a case study with the Influence Threshold problem in online social networks. Submodular Streaming in All Its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity Streaming algorithms are generally judged by the quality of their solution, memory footprint, and computational complexity. In this paper, we study the problem of maximizing a monotone submodular function in the streaming setting with a cardinality constraint k. We first propose SIEVE-STREAMING++, which requires just one pass over the data, keeps only O(k) elements and achieves the tight 12-approximationguarantee.The best previously known streaming algorithms either achieve a suboptimal 14-approximation with Θ(k) memory or the optimal 12-approximation with O(klogk)memory.Next, we showthat by buffering a small fraction of the stream and applying a careful filtering procedure, one can heavily reduce the number of adaptive computational rounds, thus substantially lowering thecomputationalcomplexity of SIEVE-STREAMING++. We then generalize our results to the more challenging multi-source streaming setting. We show how one can achieve the tight 12-approximation guarantee with O(k) shared memory, while minimizing not only the rounds of computations but also the total number of communicated bits. Finally, we demonstrate the efficiency of our algorithms on real-world data summarization tasks for multi-source streams of tweets and of YouTube videos. Hiring Under Uncertainty n this paper we introduce the hiring under uncertainty problem to model the questions faced by hiring committees in large enterprises and universities alike. Given a set of n eligible candidates, the decision maker needs to choose the sequence of candidates to make offers so as to hire the k best candidates. However, candidates may choose to reject an offer (for instance, due to a competing offer) and the decision maker has a time limit by which all positions must be filled. Given an estimate of the probabilities of acceptance for each candidate, the hiring under uncertainty problem is to design a strategy of making offers so that total expected value of all candidates hired by the time limit is maximized.Distributed Weighted Matching via Randomized Composable Coresets Maximum weight matching is one of the most fundamental combinatorial optimization problems with a wide range of applications in data mining and bioinformatics. Developing distributed weighted matching algorithms has been challenging due to the sequential nature of efficient algorithms for this problem. In this paper, we develop a simple distributed algorithm for the problem on general graphs with approximation guarantee of 2 + eps…
Categories
Mathematics
Category · 2.4k presentations
AI & Data Science
Category · 10.8k presentations
About ICML 2019
The International Conference on Machine Learning (ICML) is the premier gathering of professionals dedicated to the advancement of the branch of artificial intelligence known as machine learning. ICML is globally renowned for presenting and publishing cutting-edge research on all aspects of machine learning used in closely related areas like artificial intelligence, statistics and data science, as well as important application areas such as machine vision, computational biology, speech recognition, and robotics. ICML is one of the fastest growing artificial intelligence conferences in the world. Participants at ICML span a wide range of backgrounds, from academic and industrial researchers, to entrepreneurs and engineers, to graduate students and postdocs.
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Personalized Visualization of the Impact of Climate Change
Watch later
Deep Learning on the 2-Dimensional Ising Model to Extract the Crossover Region
Watch later
Reinforcement Learning Theory
Watch later
General ML
Watch later
Learning Representations for Continual Learning
Watch later
