Timezone: »

Adaptive Forward-Backward Greedy Algorithm for Sparse Learning with Linear Models
Tong Zhang

Wed Dec 10 07:30 PM -- 12:00 AM (PST) @

Consider linear prediction models where the target function is a sparse linear combination of a set of basis functions. We are interested in the problem of identifying those basis functions with non-zero coefficients and reconstructing the target function from noisy observations. Two heuristics that are widely used in practice are forward and backward greedy algorithms. First, we show that neither idea is adequate. Second, we propose a novel combination that is based on the forward greedy algorithm but takes backward steps adaptively whenever beneficial. We prove strong theoretical results showing that this procedure is effective in learning sparse representations. Experimental results support our theory.

Author Information

Tong Zhang (The Hong Kong University of Science and Technology)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors