Multiscale entropic regularization for MTS on general metric spaces
summary
Shows a concrete algorithm: mirror descent with a multi-scale entropic regularizer run on a constructed DAG over the metric, not on random HSTs. Builds a DAG with extra cross-edges so each leaf has many root-to-leaf paths, keeps the number of source–sink paths polynomial, and proves the online algorithm is O(log^2 n)-competitive for any n-point metric. Uses shifted Shannon entropy, earth-mover movement cost analysis, and succeeds but does not improve the log^2 n bound toward conjectured Θ(log n).
AI-written summary · about