Restricted strong convexity implies weak submodularity

DOI10.1214/17-AOS1679zbMath1401.68262arXiv1612.00804OpenAlexW2962827663MaRDI QIDQ1990594

Rajiv Khanna, Ethan R. Elenberg, Alexandros G. Dimakis, Sahand N. Negahban

Publication date: 25 October 2018

Published in: The Annals of Statistics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1612.00804

zbMATH Keywords

subset selectiongreedy algorithmssubmodular functionsrestricted strong convexity

Mathematics Subject Classification ID

Analysis of algorithms (68W40) General nonlinear regression (62J02) Learning and adaptive systems in artificial intelligence (68T05) Approximation algorithms (68W25)

Related Items

Greedy Variable Selection for High-Dimensional Cox Models, Sparse approximation over the cube, Maximization of nonsubmodular functions under multiple constraints with applications, Greedy guarantees for non-submodular function maximization under independent system constraint with applications, Unnamed Item, Weakly Submodular Function Maximization Using Local Submodularity Ratio., Unnamed Item, Approximating Robust Parameterized Submodular Function Maximization in Large-Scales, Fast algorithms for maximizing monotone nonsubmodular functions, Subset Selection in Sparse Matrices, Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms

Uses Software

• RCV1
• CoSaMP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exponential screening and optimal rates of sparse estimation
• A new perspective on boosting in linear regression via subgradient optimization and relatives
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• High-dimensional generalized linear models and the lasso
• Approximation and learning by greedy algorithms
• Submodular functions and optimization.
• An analysis of approximations for maximizing submodular set functions—I
• Deterministic Algorithms for Submodular Maximization Problems
• Sparse Approximate Solutions to Linear Systems
• Sparse Recovery With Orthogonal Matching Pursuit Under RIP
• Learning with Submodular Functions: A Convex Optimization Perspective
• Greedy Sparsity-Constrained Optimization
• Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima
• A unified framework for high-dimensional analysis of \(M\)-estimators with decomposable regularizers