Structured estimation with atomic norms: General bounds and applications

Sheng Chen, Arindam Banerjee

Research output: Contribution to journalConference articlepeer-review

14 Scopus citations


For structured estimation problems with atomic norms, recent advances in the literature express sample complexity and estimation error bounds in terms of certain geometric measures, in particular Gaussian width of the unit norm ball, Gaussian width of a spherical cap induced by a tangent cone, and a restricted norm compatibility constant. However, given an atomic norm, bounding these geometric measures can be difficult. In this paper, we present general upper bounds for such geometric measures, which only require simple information of the atomic norm under consideration, and we establish tightness of these bounds by providing the corresponding lower bounds. We show applications of our analysis to certain atomic norms, especially k-support norm, for which existing result is incomplete.

Original languageEnglish (US)
Pages (from-to)2908-2916
Number of pages9
JournalAdvances in Neural Information Processing Systems
StatePublished - 2015
Event29th Annual Conference on Neural Information Processing Systems, NIPS 2015 - Montreal, Canada
Duration: Dec 7 2015Dec 12 2015

Bibliographical note

Funding Information:
The research was supported by NSF grants IIS-1447566, IIS-1422557, CCF-1451986, CNS-1314560, IIS-0953274, IIS-1029711, and by NASA grant NNX12AQ39A.


Dive into the research topics of 'Structured estimation with atomic norms: General bounds and applications'. Together they form a unique fingerprint.

Cite this