Learning With ₁ -Regularizer Based on Markov Resampling

Learning with <tex-math notation="LaTeX">₁ </tex-math> -regularizer has brought about a great deal of research in learning theory community. Previous known results for the learning with <tex-math notation="LaTeX">₁ </tex-math> -regularizer are based on the assumption that samples are independent and identically distributed (i.i.d.), and the best obtained learning rate for the <tex-math notation="LaTeX">₁ </tex-math> -regularization type algorithms is <tex-math notation="LaTeX">O(1/√m) </tex-math> , where <tex-math notation="LaTeX">m </tex-math> is the samples size. This paper goes beyond the classic i.i.d. framework and investigates the generalization performance of least square regression with <tex-math notation="LaTeX">₁ </tex-math> -regularizer ( <tex-math notation="LaTeX">₁ </tex-math> -LSR) based on uniformly ergodic Markov chain (u.e.M.c) samples. On the theoretical side, we prove that the learning rate of <tex-math notation="LaTeX">₁ </tex-math> -LSR for u.e.M.c samples <tex-math notation="LaTeX">₁ </tex-math> -LSR(M) is with the order of <tex-math notation="LaTeX">O(1/m) </tex-math> , which is faster than <tex-math notation="LaTeX">O(1/√m) </tex-math> for the i.i.d. counterpart. On the practical side, we propose an algorithm based on resampling scheme to generate u.e.M.c samples. We show that the proposed <tex-math notation="LaTeX">₁ </tex-math> -LSR(M) improves on the <tex-math notation="LaTeX">₁ </tex-math> -LSR(i.i.d.) in generalization error at the low cost of u.e.M.c resampling.