More Like this

1. Improve Single-Point Zeroth-Order Optimization Using High-Pass and Low-Pass Filters

   Xin Chen, Yujie Tang (January 2022, Proceedings of the 39 th International Conference on Machine Learning)

   Single-point zeroth-order optimization (SZO) is useful in solving online black-box optimization and control problems in time-varying environments, as it queries the function value only once at each time step. However, the vanilla SZO method is known to suffer from a large estimation variance and slow convergence, which seriously limits its practical application. In this work, we borrow the idea of high-pass and low-pass filters from extremum seeking control (continuous-time version of SZO) and develop a novel SZO method called HLF-SZO by integrating these filters. It turns out that the high-pass filter coincides with the residual feedback method, and the low-pass filter can be interpreted as the momentum method. As a result, the proposed HLF-SZO achieves a much smaller variance and much faster convergence than the vanilla SZO method, and empirically outperforms the residual-feedback SZO method, which are verified via extensive numerical experiments. 

   more » « less
2. Single-pass transcription by T7 RNA polymerase

   https://doi.org/10.1261/rna.076778.120  

   Passalacqua, Luiz F.M.; Dingilian, Armine I.; Lupták, Andrej (November 2020, RNA)

   null (Ed.)
3. Single Pass Entrywise-Transformed Low Rank Approximation

   Jiang, Yifei; Li, Yi; Sun, Yiming; Wang, Jiaxin; Woodruff, David P. (July 2021, Proceedings of Machine Learning Research)
4. Heterogeneous multireference alignment: A single pass approach

   https://doi.org/10.1109/CISS.2018.8362313  

   Boumal, Nicolas; Bendory, Tamir; Lederman, Roy R.; Singer, Amit (March 2018, Information Sciences and Systems (CISS), 2018 52nd Annual Conference on)

   Multireference alignment (MRA) is the problem of estimating a signal from many noisy and cyclically shifted copies of itself. In this paper, we consider an extension called heterogeneous MRA, where K signals must be estimated, and each observation comes from one of those signals, unknown to us. This is a simplified model for the heterogeneity problem notably arising in cryo-electron microscopy. We propose an algorithm which estimates the K signals without estimating either the shifts or the classes of the observations. It requires only one pass over the data and is based on low-order moments that are invariant under cyclic shifts. Given sufficiently many measurements, one can estimate these invariant features averaged over the K signals. We then design a smooth, non-convex optimization problem to compute a set of signals which are consistent with the estimated averaged features. We find that, in many cases, the proposed approach estimates the set of signals accurately despite non-convexity, and conjecture the number of signals K that can be resolved as a function of the signal length L is on the order of √L. 

   more » « less
5. Polynomial pass lower bounds for graph streaming algorithms

   https://doi.org/10.1145/3313276.3316361  

   Assadi, Sepehr; Chen, Yu; Khanna, Sanjeev (January 2019, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019)