More Like this

1. An improved lower bound for Folkman's theorem: AN IMPROVED LOWER BOUND FOR FOLKMAN'S THEOREM

   https://doi.org/10.1112/blms.12058  

   Balogh, József ; Eberhard, Sean ; Narayanan, Bhargav ; Treglown, Andrew ; Wagner, Adam Zsolt ( August 2017 , Bulletin of the London Mathematical Society)
2. An Improved Lower Bound for Sparse Reconstruction from Subsampled Hadamard Matrices

   https://doi.org/10.1109/FOCS.2019.00091  

   Blasiok, Jaroslaw ; Lopatto, Patrick ; Luh, Kyle ; Marcinek, Jake ; Rao, Shravas ( November 2019 , 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS))
3. The Age of Evapotranspiration: Lower‐Bound Constraints From Distributed Water Fluxes Across the Continental United States

   https://doi.org/10.1029/2022WR032961  

   Hahm, W. J. ; Lapides, D. A. ; Rempe, D. M. ; McCormick, E. L. ; Dralle, D. N. ( October 2022 , Water Resources Research)
4. A lower bound on the quantitative version of the transversality theorem

   https://doi.org/10.1016/j.jmaa.2023.127539  

   Murdza, Andrew ; Nguyen, Khai T. ( December 2023 , Journal of Mathematical Analysis and Applications)
5. Fully asynchronous stochastic coordinate descent: a tight lower bound on the parallelism achieving linear speedup

   https://doi.org/10.1007/s10107-020-01552-8  

   Cheung, Yun Kuen ; Cole, Richard ; Tao, Yixin ( September 2020 , Mathematical Programming)

   null (Ed.)

   We seek tight bounds on the viable parallelism in asynchronous implementations of coordinate descent that achieves linear speedup. We focus on asynchronous coordinate descent (ACD) algorithms on convex functions which consist of the sum of a smooth convex part and a possibly non-smooth separable convex part. We quantify the shortfall in progress compared to the standard sequential stochastic gradient descent. This leads to a simple yet tight analysis of the standard stochastic ACD in a partially asynchronous environment, generalizing and improving the bounds in prior work. We also give a considerably more involved analysis for general asynchronous environments in which the only constraint is that each update can overlap with at most q others. The new lower bound on the maximum degree of parallelism attaining linear speedup is tight and improves the best prior bound almost quadratically. 

   more » « less