Toward Asymptotic Optimality: Sequential Unsupervised Regression of Density Ratio for Early Classification
Theoretically-inspired sequential density ratio estimation (SDRE) algorithms are proposed for the early classification of time series. Conventional SDRE algorithms can fail to estimate DRs precisely due to the internal overnormalization problem, which prevents the DR-based sequential algorithm, Sequential Probability Ratio Test (SPRT), from reaching its asymptotic Bayes optimality. Two novel SPRT-based algorithms, B2Bsqrt-TANDEM and TANDEMformer, are designed to avoid the overnormalization problem for precise unsupervised regression of SDRs. The two algorithms statistically significantly reduce DR estimation errors and classification errors on an artificial sequential Gaussian dataset and real datasets (SiW, UCF101, and HMDB51), respectively. The code is available at: https://github.com/Akinori-F-Ebihara/LLR_saturation_problem.
Code (1)
Tasks
ClassificationDensity Ratio EstimationEarly ClassificationregressionTime SeriesTime Series AnalysisMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Double Explore-then-Commit: Asymptotic Optimality and Beyond
We study the multi-armed bandit problem with subgaussian rewards. The explore-then-commit (ETC) strategy, which consists of an exploration phase followed by an exploitation phase, is one of the most widely used algorithm…
Optimal sequential tests yield log-optimal e-processes
It has been recently shown that e-processes are sufficient for sequential testing in the following sense: every level-$α$ sequential test can be obtained by thresholding an e-process at $1/α$. However, in the above resul…
Approximate optimality and the risk/reward tradeoff in a class of bandit problems
This paper studies a sequential decision problem where payoff distributions are known and where the riskiness of payoffs matters. Equivalently, it studies sequential choice from a repeated set of independent lotteries. T…
A consistent deterministic regression tree for non-parametric prediction of time series
We study online prediction of bounded stationary ergodic processes. To do so, we consider the setting of prediction of individual sequences and build a deterministic regression tree that performs asymptotically as well a…
PredictionregressionTime SeriesTime Series AnalysisUniversal Asymptotic Optimality of Polyak Momentum
We consider the average-case runtime analysis of algorithms for minimizing quadratic objectives. In this setting, and contrary to the more classical worst-case analysis, non-asymptotic convergence rates and optimal algor…