THE CONFERENCE
FOR AUTHORS
FOR PARTICIPANTS

Timezone: »

 
Poster
On Approximation Guarantees for Greedy Low Rank Optimization
RAJIV KHANNA · Ethan R. Elenberg · Alexandros Dimakis · Joydeep Ghosh · Sahand Negahban

Wed Aug 09 01:30 AM -- 05:00 AM (PDT) @ Gallery #98
in Posters Wed »

We provide new approximation guarantees for greedy low rank matrix estimation under standard assumptions of restricted strong convexity and smoothness. Our novel analysis also uncovers previously unknown connections between the low rank estimation and combinatorial optimization, so much so that our bounds are reminiscent of corresponding approximation bounds in submodular maximization. Additionally, we provide also provide statistical recovery guarantees. Finally, we present empirical comparison of greedy estimation with established baselines on two important real-world problems.

Author Information

RAJIV KHANNA (UT Austin)
Ethan R. Elenberg (The University of Texas at Austin)
Alexandros Dimakis (UT Austin)

Alex Dimakis is an Associate Professor at the Electrical and Computer Engineering department, University of Texas at Austin. He received his Ph.D. in electrical engineering and computer sciences from UC Berkeley. He received an ARO young investigator award in 2014, the NSF Career award in 2011, a Google faculty research award in 2012 and the Eli Jury dissertation award in 2008. He is the co-recipient of several best paper awards including the joint Information Theory and Communications Society Best Paper Award in 2012. His research interests include information theory, coding theory and machine learning.

Joydeep Ghosh (The University of Texas at Austin)
Sahand Negahban (YALE)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors