More Like this

1. Mirrorless Mirror Descent: A Natural Derivation of Mirror Descent

   Gunasekar, Suriya; Woodworth, Blake; Srebro, Nathan (January 2021, Proceedings of Machine Learning Research)

   null (Ed.)

   We present a direct (primal only) derivation of Mirror Descent as a “partial” discretization of gradient flow on a Riemannian manifold where the metric tensor is the Hessian of the Mirror Descent potential function. We contrast this discretization to Natural Gradient Descent, which is obtained by a “full” forward Euler discretization. This view helps shed light on the relationship between the methods and allows generalizing Mirror Descent to any Riemannian geometry in Rd, even when the metric tensor is not a Hessian, and thus there is no “dual.” 

   more » « less
2. Hessian Informed Mirror Descent

   https://doi.org/10.1007/s10915-022-01933-5  

   Wang, Li; Yan, Ming (September 2022, Journal of Scientific Computing)
3. Variational Principles for Mirror Descent and Mirror Langevin Dynamics

   https://doi.org/10.1109/LCSYS.2023.3274069  

   Tzen, Belinda; Raj, Anant; Raginsky, Maxim; Bach, Francis (January 2023, IEEE Control Systems Letters)
4. No-regret Caching via Online Mirror Descent

   https://doi.org/10.1145/3605209  

   Si Salem, Tareq; Neglia, Giovanni; Ioannidis, Stratis (December 2023, ACM Transactions on Modeling and Performance Evaluation of Computing Systems)

   We study an online caching problem in which requests can be served by a local cache to avoid retrieval costs from a remote server. The cache can update its state after a batch of requests and store an arbitrarily small fraction of each file. We study no-regret algorithms based on Online Mirror Descent (OMD) strategies. We show that bounds for the regret crucially depend on the diversity of the request process, provided by the diversity ratio R/h , where R is the size of the batch and h is the maximum multiplicity of a request in a given batch. We characterize the optimality of OMD caching policies w.r.t. regret under different diversity regimes. We also prove that, when the cache must store the entire file, rather than a fraction, OMD strategies can be coupled with a randomized rounding scheme that preserves regret guarantees, even when update costs cannot be neglected. We provide a formal characterization of the rounding problem through optimal transport theory, and moreover we propose a computationally efficient randomized rounding scheme. 

   more » « less
5. No-Regret Caching via Online Mirror Descent

   https://doi.org/10.1109/ICC42927.2021.9500487  

   Si Salem, Tareq; Neglia, Giovanni; Ioannidis, Stratis (June 2021, ICC 2021 - IEEE International Conference on Communications)

   null (Ed.)