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

We consider forward-backward greedy algo-rithms for solving sparse feature selection prob-lems 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 prob-lems, thus it is not scalable for large-size prob-lems. The FoBa-gdt algorithm, which uses the gradient information for feature selection at each forward iteration, significantly improves the ef-ficiency of FoBa-obj. In this paper, we sys-tematically analyze the theoretical properties of both algorithms. Our main contributions are: 1) We derive better theoretical bounds than ex-isting analyses regarding FoBa-obj for general smooth convex functions; 2) We show that FoBa-gdt 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 theoreti-cal gap for general convex smooth functions; 3) We show that the restricted strong convexity con-dition is satisfied if the number of independent samples is more than k ̄ log d where k ̄ is the spar-sity number and d is the dimension of the vari-able; 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 selectio