Restricted strong convexity implies weak submodularity
From MaRDI portal
Publication:1990594
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
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
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