Forward-Backward Greedy Algorithms for General Convex Smooth Functions over A Cardinality Constraint

We consider forward-backward greedy algorithms for solving sparse feature selection problems with general convex smooth functions. A state-of-the-art greedy method, the Forward-Backward greedy algorithm (FoBa-obj) requires to solve a large number of optimization problems, thus it is not scalable for large-size problems. The FoBa-gdt algorithm, which uses the gradient information for feature selection at each forward iteration, significantly improves the efficiency of FoBa-obj. In this paper, we systematically analyze the theoretical properties of both algorithms. Our main contributions are: 1) We derive better theoretical bounds than existing analyses regarding FoBa-obj for general smooth convex functions; 2) We show that FoBagdt achieves the same theoretical performance as FoBa-obj under the same condition: restricted strong convexity condition. Our new bounds are consistent with the bounds of a special case (least squares) and fills a previously existing theoretical gap for general convex smooth functions; 3) We show that the restricted strong convexity condition is satisfied if the number of independent samples is more than k log d where k is the sparsity number and d is the dimension of the variable; 4)We apply FoBa-gdt (with the conditional random field objective) to the sensor selection problem for human indoor activity recognition and our results show that FoBa-gdt outperforms other methods based on forward greedy selection and L1-regularization.

• Publication year

  2013

• Venue

  International Conference on Machine Learning

• Publication date

  2013-12-31

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1401.0086
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A Multi-Stage Framework for Dantzig Selector and LASSO

  2012cited by this paper
• Adaptive Forward-Backward Greedy Algorithm for Learning Sparse Representations

  2011influential reference
• High-dimensional Sparse Inverse Covariance Estimation using Greedy Methods

  2011cited by this paper
• A General Theory of Concave Regularization for High-Dimensional Sparse Estimation Problems

  2011cited by this paper
• Greedy sparsity-constrained optimization

  2011cited by this paper
• On Learning Discrete Graphical Models using Greedy Methods

  2011influential reference
• Trading Accuracy for Sparsity in Optimization Problems with Sparsity Constraints

  2010cited by this paper
• Introduction to the non-asymptotic analysis of random matrices

  2010cited by this paper
• Sparse Recovery With Orthogonal Matching Pursuit Under RIP

  2010influential reference
• A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers

  2009cited by this paper
• On the Consistency of Feature Selection using Greedy Least Squares Regression

  2009cited by this paper
• Logistic Regression Models

  2009cited by this paper
• High-dimensional covariance estimation by minimizing ℓ1-penalized log-determinant divergence

  2008cited by this paper
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples

  2008cited by this paper
• Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit

  2007cited by this paper
• An Introduction to Conditional Random Fields for Relational Learning

  2007cited by this paper
• An Introduction to Conditional Random Fields for Relational Learning

  2007cited by this paper
• On Model Selection Consistency of Lasso

  2006influential reference
• Boosting for high-dimensional linear models

  2006cited by this paper
• The Dantzig selector: Statistical estimation when P is much larger than n

  2005cited by this paper
• Decoding by linear programming

  2005cited by this paper
• Greed is good: algorithmic results for sparse approximation

  2004influential reference
• Logistic regression.

  2002cited by this paper
• OF LEARNING

  2002influential reference
• Optimal Structure Identification With Greedy Search

  2002cited by this paper
• Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data

  2001cited by this paper
• Regression Shrinkage and Selection via the Lasso

  1996influential reference

• skscope: Fast Sparsity-Constrained Optimization in Python

  2024cites this paper
• Sparsity-Constraint Optimization via Splicing Iteration

  2024influential citation
• BEMS Architecture and Service Modules for Realizing Sophisticated Algorithms

  2023cites this paper
• Sub-exponential time Sum-of-Squares lower bounds for Principal Components Analysis

  2022cites this paper
• Fast Feature Selection with Fairness Constraints

  2022cites this paper
• Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families

  2021cites this paper
• Feature selection using autoencoders with Bayesian methods to high-dimensional data

  2021cites this paper
• Adaptive data-driven nonlinear synchro squeezed transform with single class radial basis function kernel support vector machine applied to wind turbine planetary gearbox fault diagnostics

  2020cites this paper
• Feature Selection for Neural Networks Using Group Lasso Regularization

  2020cites this paper
• Sparse Convex Optimization via Adaptively Regularized Hard Thresholding

  2020cites this paper
• A Statistically Efficient and Scalable Method for Exploratory Analysis of High-Dimensional Data

  2020influential citation
• Discrimination-Aware Network Pruning for Deep Model Compression

  2020cites this paper
• An Empirical Study on Distributed Bayesian Approximation Inference of Piecewise Sparse Linear Models

  2019cites this paper
• Anomaly detection via adaptive greedy model

  2019cites this paper
• Distributed Inexact Newton-type Pursuit for Non-convex Sparse Learning

  2019cites this paper
• Exclusive feature selection and multi-view learning for Alzheimer's Disease

  2019cites this paper
• An efficient adaptive forward–backward selection method for sparse polynomial chaos expansion

  2019cites this paper
• Robust Health Score Prediction from Pyro-Sensor Activity Data based on Greedy Feature Selection

  2019cites this paper
• Discrimination-aware Channel Pruning for Deep Neural Networks

  2018cites this paper
• A Robust AUC Maximization Framework With Simultaneous Outlier Detection and Feature Selection for Positive-Unlabeled Classification

  2018influential citation
• Nonlinear Structured Signal Estimation in High Dimensions via Iterative Hard Thresholding

  2018cites this paper
• Dantzig Selector with an Approximately Optimal Denoising Matrix and its Application to Reinforcement Learning

  2018cites this paper
• Mixed Causal Structure Discovery with Application to Prescriptive Pricing

  2018cites this paper
• An Interactive Greedy Approach to Group Sparsity in High Dimensions

  2017influential citation
• A Machine Learning Approach for Brain Tissue Recognition of Human Brain Slice Images

  2017cites this paper
• Feature Selection Based on Structured Sparsity: A Comprehensive Study

  2017cites this paper
• Submitted to the Annals of Statistics RESTRICTED STRONG CONVEXITY IMPLIES WEAK SUBMODULARITY By

  2017cites this paper
• Distributed Bayesian piecewise sparse linear models

  2017cites this paper
• Adaptive Greedy Dictionary Selection for Web Media Summarization

  2017cites this paper
• Piecewise sparse linear classification via factorized asymptotic bayesian inference

  2016cites this paper
• Restricted Strong Convexity Implies Weak Submodularity

  2016cites this paper
• Dantzig Selector with an Approximately Optimal Denoising Matrix and its Application in Sparse Reinforcement Learning

  2016cites this paper
• On Benefits of Selection Diversity via Bilevel Exclusive Sparsity

  2016cites this paper
• Activity recognition in monitored environments using utility meter disaggregation

  2016cites this paper
• Accelerated Stochastic Block Coordinate Gradient Descent for Sparsity Constrained Nonconvex Optimization

  2016cites this paper
• Atom Decomposition with Adaptive Basis Selection Strategy for Matrix Completion

  2016cites this paper
• Forward Backward Greedy Algorithms for Multi-Task Learning with Faster Rates

  2016cites this paper
• Density Corrected Sparse Recovery when R.I.P. Condition Is Broken

  2015cites this paper
• OPTIMAL ROUTE SERVICE SELECTION IN AD-HOC MOBILE E-MARKETPLACES WITH DYNAMIC PROGRAMMING ALGORITHM USING TSP APPROACH

  2015cites this paper
• Simple Atom Selection Strategy for Greedy Matrix Completion

  2015cites this paper
• Conflict intensity estimation from speech using Greedy forward-backward feature selection

  2015cites this paper
• Exclusive Feature Learning on Arbitrary Structures via \ell_{1, 2}-norm

  2014cites this paper
• Efficient Sparse Recovery via Adaptive Non-Convex Regularizers with Oracle Property

  2014cites this paper
• Fully-Automatic Bayesian Piecewise Sparse Linear Models

  2014cites this paper
• Forward–Backward Greedy Algorithms for Atomic Norm Regularization

  2014cites this paper
• On Iterative Hard Thresholding Methods for High-dimensional M-Estimation

  2014cites this paper