Dynamic estimation of slowly varying sequences

Prashant Gokhale, Mikhail Khodak, Sandeep Silwal · 2026

Read Dynamic estimation of slowly varying sequences by Prashant Gokhale, Mikhail Khodak, Sandeep Silwal (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-23655.txt.

Description

Gokhale, Khodak, and Silwal develop a general method for estimating properties of a sequence that changes only slightly from step to step, in a 2026 paper on algorithms. Many tasks track a slowly evolving system through limited queries: a drifting data stream, a changing network, or matrices met during optimization. Earlier work showed that reusing past queries saves cost when consecutive elements are close. It covered few targets, though, and charged every step for the worst change seen.

The new framework handles many linear and nonlinear targets on varied spaces. Applications include Monte Carlo integration, matrix powers, and spectral densities, plus a boundary value problem from differential equations. A fresh algorithm scales each step's budget with that step's actual change, so total cost grows with the sum of changes rather than the maximum. In some cases the changes themselves can be estimated on the fly at almost no extra cost.

Catalog record

CREATORPrashant Gokhale, Mikhail Khodak, Sandeep Silwal
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.23655

Browse the full library · About the Tower of Babel