Publications de Marwa El Halabi

Learning with Structured Sparsity: From Discrete to Convex and Back

In modern-data analysis applications, the abundance of data makes extracting meaningful information from it challenging, in terms of computation, storage, and interpretability. In this setting, exploiting sparsity in data has been essential to the developm ...

EPFL2018

Combinatorial Penalties: Which structures are preserved by convex relaxations?

Volkan Cevher, Marwa El Halabi

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 tightness of the resulting relaxations through the notion of the lower combinato ...

2017

General Proximal Gradient Method: A Case for Non-Euclidean Norms

Volkan Cevher, Marwa El Halabi, Ya-Ping Hsieh, Cong Bang Vu, Van Quang Nguyen

In this paper, we consider composite convex minimization problems. We advocate the merit of considering Generalized Proximal gradient Methods (GPM) where the norm employed is not Euclidean. To that end, we show the tractability of the general proximity ope ...

2017

An Efficient Streaming Algorithm for the Submodular Cover Problem

Volkan Cevher, Ilija Bogunovic, Marwa El Halabi, Abbas Bazzi, Ashkan Norouzi Fard, Ya-Ping Hsieh

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 pass streaming algorithm using sublinear memory in the size of the stream wi ...

2016

Frank-Wolfe Works for Non-Lipschitz Continuous Gradient Objectives: Scalable Poisson Phase Retrieval

Volkan Cevher, Marwa El Halabi, Yen-Huan Li, Quoc Tran Dinh, Alp Yurtsever, Ya-Ping Hsieh, Gergely Odor

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 a nuclear norm constraint. While the Frank-Wolfe algorithm, together with t ...

Ieee2016

A totally unimodular view of structured sparsity

Volkan Cevher, Marwa El Halabi

This paper describes a simple framework for structured sparse recovery based on convex optimization. We show that many interesting structured sparsity models can be naturally represented by linear matrix inequalities on the support of the unknown parameter ...

2015

MAP Estimation for Bayesian Mixture Models with Submodular Priors

Volkan Cevher, Marwa El Halabi, Luca Baldassarre

We propose a Bayesian approach where the signal structure can be represented by a mixture model with a submodular prior. We consider an observation model that leads to Lipschitz functions. Due to its combinatorial nature, computing the maximum a posteriori ...

2014

To Convexify or Not? Regression with Clustering Penalties on Graphs

Volkan Cevher, Marwa El Halabi, Luca Baldassarre

We consider minimization problems that are compositions of convex functions of a vector

\x \in\reals^N

with submodular set functions of its support (i.e., indices of the non-zero coefficients of

\x

). Such problems are in general difficult for large

N

...

IEEE2013