Mixing predictions for online metric algorithms
A major technique in learning-augmented online algorithms is combining multiple algorithms or predictors. Since the performance of each predictor may vary over time, it is desirable to use not the single best predictor as a benchmark, but rather a dynamic combination which follows different predictors at different times. We design algorithms that combine predictions and are competitive against such dynamic combinations for a wide class of online problems, namely, metrical task systems. Against the best (in hindsight) unconstrained combination of $\ell$ predictors, we obtain a competitive ratio of $O(\ell^2)$, and show that this is best possible. However, for a benchmark with slightly constrained number of switches between different predictors, we can get a $(1+\epsilon)$-competitive algorithm. Moreover, our algorithms can be adapted to access predictors in a bandit-like fashion, querying only one predictor at a time. An unexpected implication of one of our lower bounds is a new structural insight about covering formulations for the $k$-server problem.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Nonparametric Detection of Nonlinearly Mixed Pixels and Endmember Estimation in Hyperspectral Images
Mixing phenomena in hyperspectral images depend on a variety of factors such as the resolution of observation devices, the properties of materials, and how these materials interact with incident light in the scene. Diffe…
Hyperspectral UnmixingregressionNonlinear unmixing of hyperspectral images: models and algorithms
When considering the problem of unmixing hyperspectral images, most of the literature in the geoscience and image processing areas relies on the widely used linear mixing model (LMM). However, the LMM may be not valid an…
validFast Algorithms for Demixing Sparse Signals from Nonlinear Observations
We study the problem of demixing a pair of sparse signals from noisy, nonlinear observations of their superposition. Mathematically, we consider a nonlinear signal observation model, $y_i = g(a_i^Tx) + e_i, \ i=1,\ldots,…
AstronomyModel-Based Deep Autoencoder Networks for Nonlinear Hyperspectral Unmixing
Autoencoder (AEC) networks have recently emerged as a promising approach to perform unsupervised hyperspectral unmixing (HU) by associating the latent representations with the abundances, the decoder with the mixing mode…
DecoderHyperspectral UnmixingHyperspectral Blind Unmixing using a Double Deep Image Prior
With the rise of machine learning, hyperspectral image (HSI) unmixing problems have been tackled using learning-based methods. However, physically meaningful unmixing results are not guaranteed without proper guidance. I…
Hyperspectral UnmixingImage GenerationInterpretable Machine LearningPhysics-informed machine learning