Abstract—This paper is about the relationship between regret
(in online learning) and the rank of an ensemble’s loss matrix Y.
Recently, several new algorithms have been developed to exploit
low rank structure in Y. Unfortunately, each of these is not
known to be order minimax optimal outside of specialized
settings. This paper explores through simulation whether this
apparent difficulty in achieving minimax optimality is because
highly specialized algorithms are required. We observe that a
horizon-adaptive hedge algorithm appears to exploit low rank
structure effectively, suggesting that algorithms do not have to
explicitly work to exploit low rank structure.
Index Terms—Experts, online learning, regret, simulation
study.
Weiqi Yang is with University of Science and Technology of China, China (e-mail: 976237481@qq.com).
Michael Spece is with Carnegie Mellon University, USA.
Cite: Weiqi Yang and Michael Spece, "Implicit Adaptation to Low Rank Structure in Online Learning," International Journal of Machine Learning and Computing vol. 11, no. 5, pp. 339-344, 2021.
Copyright © 2021 by the authors. This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited (CC BY 4.0).