More Like this

1. Applications of Littlestone Dimension to Query Learning and to Compression

   https://doi.org/10.4230/LIPIcs.MFCS.2024.42  

   Chase, Hunter; Frietag, James; Reyzin, Lev (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Kráľovič, Rastislav; Kučera, Antonín (Ed.)

   In this paper we give several applications of Littlestone dimension. The first is to the model of [Angluin and Dohrn, 2017], where we extend their results for learning by equivalence queries with random counterexamples. Second, we extend that model to infinite concept classes with an additional source of randomness. Third, we give improved results on the relationship of Littlestone dimension to classes with extended d-compression schemes, proving the analog of a conjecture of [Floyd and Warmuth, 1995] for Littlestone dimension. 

   more » « less
2. Response to thermal and hydric regimes point to differential inter- and intraspecific vulnerability of tropical amphibians to climate warming

   https://doi.org/10.1016/j.jtherbio.2021.103148  

   Delgado-Suazo, Peter; Burrowes, Patricia A. (January 2022, Journal of Thermal Biology)
3. To grow and to defend

   https://doi.org/10.1126/science.aau9065  

   Greene, George H.; Dong, Xinnian (September 2018, Science)
4. Three approaches to facilitate invariant neurons and generalization to out-of-distribution orientations and illuminations

   https://doi.org/10.1016/j.neunet.2022.07.026  

   Sakai, A. (July 2022, Neural networks)
5. Learning to Cache and Caching to Learn: Regret Analysis of Caching Algorithms

   https://doi.org/10.1109/TNET.2021.3105880  

   Bura, Archana; Rengarajan, Desik; Kalathil, Dileep; Shakkottai, Srinivas; Chamberland, Jean-Francois (January 2021, IEEE/ACM Transactions on Networking)

   null (Ed.)

   Crucial performance metrics of a caching algorithm include its ability to quickly and accurately learn a popularity distribution of requests. However, a majority of work on analytical performance analysis focuses on hit probability after an asymptotically large time has elapsed. We consider an online learning viewpoint, and characterize the ``regret'' in terms of the finite time difference between the hits achieved by a candidate caching algorithm with respect to a genie-aided scheme that places the most popular items in the cache. We first consider the Full Observation regime wherein all requests are seen by the cache. We show that the Least Frequently Used (LFU) algorithm is able to achieve order optimal regret, which is matched by an efficient counting algorithm design that we call LFU-Lite. We then consider the Partial Observation regime wherein only requests for items currently cached are seen by the cache, making it similar to an online learning problem related to the multi-armed bandit problem. We show how approaching this ``caching bandit'' using traditional approaches yields either high complexity or regret, but a simple algorithm design that exploits the structure of the distribution can ensure order optimal regret. We conclude by illustrating our insights using numerical simulations. 

   more » « less