1.3k citations · 3.8k across the 222 of their papers we have counts for
16 papers · 1 filter
Convergence of the Exponentiated Gradient Method with Armijo Line Search
Yen-Huan Li, Volkan Cevher
Consider the problem of minimizing a convex differentiable function on the probability simplex, spectrahedron, or set of quantum density matrices. We prove that the exponentiated g…
On the linear convergence of the stochastic gradient method with constant step-size
Volkan Cevher, Bang Cong Vu
The strong growth condition (SGC) is known to be a sufficient condition for linear convergence of the stochastic gradient method using a constant step-size (SGM-CS). In this pa…
Smooth Primal-Dual Coordinate Descent Algorithms for Nonsmooth Convex Optimization
Ahmet Alacaoglu, Quoc Tran-Dinh, Olivier Fercoq +1
We propose a new randomized coordinate descent method for a convex optimization template with broad applications. Our analysis relies on a novel combination of four ideas applied t…
Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach
Slobodan Mitrović, Ilija Bogunovic, Ashkan Norouzi-Fard +2
We study the classical problem of maximizing a monotone submodular function subject to a cardinality constraint k, with two additional twists: (i) elements arrive in a streaming fa…
Phase Transitions in the Pooled Data Problem
Jonathan Scarlett, Volkan Cevher
In this paper, we study the pooled data problem of identifying the labels associated with a large collection of items, based on a sequence of pooled tests revealing the counts of e…
Near-Optimal Noisy Group Testing via Separate Decoding of Items
Jonathan Scarlett, Volkan Cevher
The group testing problem consists of determining a small set of defective items from a larger set of items based on a number of tests, and is relevant in applications such as medi…
Combinatorial Penalties: Which structures are preserved by convex relaxations?
Marwa El Halabi, Francis Bach, Volkan Cevher
We consider the homogeneous and the non-homogeneous convex relaxations for combinatorial penalty functions defined on support sets. Our study identifies key differences in the tigh…
Smoothing technique for nonsmooth composite minimization with linear operator
Quang Van Nguyen, Olivier Fercoq, Volkan Cevher
We introduce and analyze an algorithm for the minimization of convex functions that are the sum of differentiable terms and proximable terms composed with linear operators. The met…
Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data
Joel A. Tropp, Alp Yurtsever, Madeleine Udell +1
Several important applications, such as streaming PCA and semidefinite programming, involve a large-scale positive-semidefinite (psd) matrix that is presented as a sequence of line…
Robust Submodular Maximization: A Non-Uniform Partitioning Approach
Ilija Bogunovic, Slobodan Mitrović, Jonathan Scarlett +1
We study the problem of maximizing a monotone submodular function subject to a cardinality constraint , with the added twist that a number of items from the returned set may…
Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
Jonathan Scarlett, Ilijia Bogunovic, Volkan Cevher
In this paper, we consider the problem of sequentially optimizing a black-box function based on noisy samples and bandit feedback. We assume that is smooth in the sense of…
A General Convergence Result for the Exponentiated Gradient Method
Yen-Huan Li, Volkan Cevher
The batch exponentiated gradient (EG) method provides a principled approach to convex smooth minimization on the probability simplex or the space of quantum density matrices. Howev…
Faster Coordinate Descent via Adaptive Importance Sampling
Dmytro Perekrestenko, Volkan Cevher, Martin Jaggi
Coordinate descent methods employ random partial updates of decision variables in order to solve huge-scale convex optimization problems. In this work, we introduce new adaptive ru…
Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage
Alp Yurtsever, Madeleine Udell, Joel A. Tropp +1
This paper concerns a fundamental class of convex matrix optimization problems. It presents the first algorithm that uses optimal storage and provably computes a low-rank approxima…
An Adaptive Sublinear-Time Block Sparse Fourier Transform
Volkan Cevher, Michael Kapralov, Jonathan Scarlett +1
The problem of approximately computing the dominant Fourier coefficients of a vector quickly, and using few samples in time domain, is known as the Sparse Fourier Transform…
Stochastic Three-Composite Convex Minimization
Alp Yurtsever, Bang Cong Vu, Volkan Cevher
We propose a stochastic optimization method for the minimization of the sum of three convex functions, one of which has Lipschitz continuous gradient as well as restricted strong c…