1.3k citations · 3.8k across the 222 of their papers we have counts for
12 papers · 1 filter
An Efficient Streaming Algorithm for the Submodular Cover Problem
Ashkan Norouzi-Fard, Abbas Bazzi, Marwa El Halabi +3
We initiate the study of the classical Submodular Cover (SC) problem in the data streaming model which we refer to as the Streaming Submodular Cover (SSC). We show that any single…
Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation
Ilija Bogunovic, Jonathan Scarlett, Andreas Krause +1
We present a new algorithm, truncated variance reduction (TruVaR), that treats Bayesian optimization (BO) and level-set estimation (LSE) with Gaussian processes in a unified fashio…
Practical sketching algorithms for low-rank matrix approximation
Joel A. Tropp, Alp Yurtsever, Madeleine Udell +1
This paper describes a suite of algorithms for constructing low-rank approximations of an input matrix from a random linear image of the matrix, called a sketch. These methods can…
Lower Bounds on Active Learning for Graphical Model Selection
Jonathan Scarlett, Volkan Cevher
We consider the problem of estimating the underlying graph associated with a Markov random field, with the added twist that the decoding algorithm can iteratively choose which subs…
Convex block-sparse linear regression with expanders -- provably
Anastasios Kyrillidis, Bubacarr Bah, Rouzbeh Hasheminezhad +3
Sparse matrices are favorable objects in machine learning and optimization. When such matrices are used, in place of dense ones, the overall complexity requirements in optimization…
A single-phase, proximal path-following framework
Quoc Tran-Dinh, Anastasios Kyrillidis, Volkan Cevher
We propose a new proximal, path-following framework for a class of constrained convex problems. We consider settings where the nonlinear---and possibly non-smooth---objective part…
On the Difficulty of Selecting Ising Models with Approximate Recovery
Jonathan Scarlett, Volkan Cevher
In this paper, we consider the problem of estimating the underlying graph associated with an Ising model given a number of independent and identically distributed samples. We adopt…
Partial Recovery Bounds for the Sparse Stochastic Block Model
Jonathan Scarlett, Volkan Cevher
In this paper, we study the information-theoretic limits of community detection in the symmetric two-community stochastic block model, with intra-community and inter-community edge…
Converse Bounds for Noisy Group Testing with Arbitrary Measurement Matrices
Jonathan Scarlett, Volkan Cevher
We consider the group testing problem, in which one seeks to identify a subset of defective items within a larger set of items based on a number of noisy tests. While matching achi…
Learning Data Triage: Linear Decoding Works for Compressive MRI
Yen-Huan Li, Volkan Cevher
The standard approach to compressive sampling considers recovering an unknown deterministic signal with certain known structure, and designing the sub-sampling pattern and recovery…
Frank-Wolfe Works for Non-Lipschitz Continuous Gradient Objectives: Scalable Poisson Phase Retrieval
Gergely Odor, Yen-Huan Li, Alp Yurtsever +4
We study a phase retrieval problem in the Poisson noise model. Motivated by the PhaseLift approach, we approximate the maximum-likelihood estimator by solving a convex program with…
Time-Varying Gaussian Process Bandit Optimization
Ilija Bogunovic, Jonathan Scarlett, Volkan Cevher
We consider the sequential Bayesian optimization problem with bandit feedback, adopting a formulation that allows for the reward function to vary with time. We model the reward fun…