We study high-dimensional estimators with the trimmed $l_1$ penalty, which leaves the $h$ largest parameter entries penalty-free. While optimization techniques for this non-convex penalty have been studied, the statistical properties have not yet been analyzed. We present the first statistical analyses for M-estimation, and characterize support recovery, $l_{\infty}$ and $l_2$ error of the trimmed $l_1$ estimates as a function of the trimming parameter h. Our results show different regimes based on how h compares to the true support size. Our second contribution is a new algorithm for the trimmed regularization problem, which has the same theoretical convergence rate as difference of convex (DC) algorithms, but in practice is faster and finds lower objective values. Empirical evaluation of $l_1$ trimming for sparse linear regression and graphical model estimation indicate that trimmed $l_1$ can outperform vanilla $l_1$ and non-convex alternatives. Our last contribution is to show that the trimmed penalty is beneficial beyond M-estimation, and yields promising results for two deep learning tasks: input structures recovery and network sparsification.
이 논문에서는 가장 큰 h개의 파라미터는 페널티를 받지 않는 가지친 $l_1$ 정규화를 이용한 고차원 데이터 분석 방법을 제안한다. 이전에 최적화 관점에서 가지친 $l_1$ 정규화 방법에 대해 연구된 바가 있지만 아직까지 그것이 가진 통계적인 특징에 대해서는 분석된 적이 없다. 우리는 처음으로 가지친 $l_1$ 정규화가 가지는
통계적인 특징에 대해 분석하며, 파라미터 h에 따라 서포트 복구와 추정된 파라미터의 $l_1$, $l_2$ 에러를 특징 짓는다. 우리의 결과는 h의 크기가 달라짐에 따라 다른 결과를 보여준다. 두 번째로 우리는 가지친 정규화 방법에 대한 새로운 최적화 방법을 제시한다. 우리의 방법은 이론적으로는 컨벡스 함수의 차이 구조에 기반한 기존의 방법과 같은 속도를 보이지만 실제 예시에서는 더 빠르고 보다 작은 목표값을 얻을 수 있다. 실제로 많이 쓰이는 두 가지 예시인 희소 선형 회귀와 희소 그래프 모형에 대해 가지친 $l_1$ 정규화 방법은 기존의 $l_1$ 과 다른 볼록하지 않은 정규화 방법들에 비해 훨씬 더 좋은 성능을 나타낸다. 마지막으로 우리는 가지친 $l_1$ 정규화 방법이 딥 러닝 문제 중 (i) 네트워크의 인풋-히든 파라미터의 서포트 구조 복구와 (ii) 깊은 네트워크의 희소화 작업에 대해 가지친 $l_1$ 이 효과적임을 보인다.
