천천히 변화하는 시퀀스의 동적 추정

우리는 천천히 변화하는 시퀀스(slowly-varying sequence), 즉 위치 $i$와 $i-1$ 사이의 요소 차이의 크기 $α_i$가 작은 시퀀스의 각 요소에 대한 함수를 순차적으로 근사하는 문제를 고려합니다. 암시적 트레이스 추정(implicit trace estimation)에 관한 최근 연구에 따르면, $α_t$가 작을 때 과거 시퀀스 요소에 대한 쿼리를 재사용함으로써 전체 비용을 줄일 수 있음을 보여줍니다 [Dharangutte & Musco, NeurIPS 2021; Woodruff et al., NeurIPS 2022]. 우리는 이를 다양한 벡터 공간에서의 다양한 선형 및 비선형 함수로 일반화하는 프레임워크를 도입하여, 행렬 거듭제곱(matrix powers), 스펙트럼 밀도(spectral densities), 몬테카를로 적분(Monte Carlo integration), 그리고 편미분 방정식(PDEs)의 경계값 문제(boundary value problem)에 대한 새로운 순차적 추정 결과를 얻었습니다. 나아가, 우리는 이 프레임워크와 함께 사용할 수 있는 새로운 알고리즘을 개발하여 $α_t$에 따라 추정 예산(estimation budget)을 국소적으로 조정하며, 길이 $m$인 시퀀스를 추정하는 비용에 대해 $\mathcal{O}(\sum_{i=1}^m α_i)$ 형태의 더 정교한 경로 길이 스타일(path-length-style) 변동 경계(variation bounds)를 얻습니다. 이는 최악의 경우인 $α_i$를 사용하여 쿼리 예산을 고정함으로써 달성되는 기존의 암시적 트레이스 추정 경계인 $\mathcal{O}(m \cdot \max_i α_i)$ [Dharangutte & Musco, NeurIPS 2021]를 개선한 것으로, 기존 방식은 드물게 발생하는 급증(bursts)이 있는 안정적인 시퀀스에 대해 비효율적입니다. 마지막으로, 과거의 모든 연구는 $α_i$에 대한 알려진 경계를 가정하는 반면, 우리는 특정 사례에서 추가 비용이 (거의) 없이 변화를 실시간(on-the-fly)으로 추정할 수 있음을 보여줍니다. 요약하자면, 우리의 프레임워크는 순차적 근사 도구 모음(sequential approximation toolkit)을 범용적이고 적응 가능하게 만드는 동시에, 동적 트레이스 추정(dynamic trace estimation)에 대한 최첨단 보장(state-of-the-art guarantees)을 개선합니다.