Learning With $\ell _{1}$ -Regularizer Based on Markov Resampling
研究了基于均匀遍历马尔可夫链样本的ℓ1正则化最小二乘回归，证明其学习率可达O(1/m)，优于独立同分布样本的O(1/√m)，并提出了重采样算法。
Learning with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ {\ell _{1}}$ </tex-math></inline-formula> -regularizer has brought about a great deal of research in learning theory community. Previous known results for the learning with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ \boldsymbol {\ell _{1}}$ </tex-math></inline-formula> -regularizer are based on the assumption that samples are independent and identically distributed (i.i.d.), and the best obtained learning rate for the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ {\ell _{1}}$ </tex-math></inline-formula> -regularization type algorithms is <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ {\mathcal {O}({1}/{\sqrt {m}})}$ </tex-math></inline-formula> , where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ {m}$ </tex-math></inline-formula> is the samples size. This paper goes beyond the classic i.i.d. framework and investigates the generalization performance of least square regression with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ {\ell _{1}}$ </tex-math></inline-formula> -regularizer ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ {\ell _{1}}$ </tex-math></inline-formula> -LSR) based on uniformly ergodic Markov chain (u.e.M.c) samples. On the theoretical side, we prove that the learning rate of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ {\ell _{1}}$ </tex-math></inline-formula> -LSR for u.e.M.c samples <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ {\ell _{1}}$ </tex-math></inline-formula> -LSR(M) is with the order of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ {\mathcal {O}({1}/{m})}$ </tex-math></inline-formula> , which is faster than <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ {\mathcal {O}({1}/{\sqrt {m}})}$ </tex-math></inline-formula> 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ {\ell _{1}}$ </tex-math></inline-formula> -LSR(M) improves on the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ {\ell _{1}}$ </tex-math></inline-formula> -LSR(i.i.d.) in generalization error at the low cost of u.e.M.c resampling.