효율적인 저차 행렬 추정, 실험 설계 및 팔 세트 의존 저차 밴딧

저차 행렬 트레이스 회귀와 관련된 저차 행렬 밴딧 문제를 연구합니다. 공변량의 분포에 접근할 수 있다고 가정하고, 저차 행렬 추정 방법인 LowPopArt를 제안하며, 여기서 Q는 측정 분포의 공분산 행렬입니다. 이 방법이 몇 가지 문제에서 고전적인 핵 노름 패널티 최소제곱(Koltchinskii et al., 2011)보다 더 엄격한 회복 보장을 제공할 수 있음을 보여줍니다. 주어진 측정 집합 A로부터 제한된 수의 측정으로 효율적인 추정을 수행하기 위해, B(Q)를 계산상 효율적으로 최소화하는 새로운 실험 설계 기준을 제안합니다. 우리는 우리의 새로운 추정기와 실험 설계를 활용하여 개선된 후회의 상한을 누리는 일반 팔 세트에 대한 두 개의 저차 선형 밴딧 알고리즘을 도출합니다. 이는 팔 세트가 단위 공일 경우 또는 효율적인 탐색 분포가 주어진다는 다소 제한적인 가정을 하는 저차 밴딧에 대한 이전 연구들보다 개선된 것입니다. 우리의 실험 설계 기준은 선형 회귀로의 단순한 축소를 넘어 저차 행렬 추정에 맞춰진 첫 번째 기준으로, 독립적인 관심을 가질 수 있습니다.