More Like this

1. Multiplicative Weights Update, Area Convexity and Random Coordinate Descent for Densest Subgraph Problems

   Nguyen, Ta Duy; Ene, Alina (July 2024, International Conference on Machine Learning)

   We study the densest subgraph problem and give algorithms via multiplicative weights update and area convexity that converge in $$O\left(\frac{\log m}{\epsilon^{2}}\right)$$ and $$O\left(\frac{\log m}{\epsilon}\right)$$ iterations, respectively, both with nearly-linear time per iteration. Compared with the work by Bahmani et al. (2014), our MWU algorithm uses a very different and much simpler procedure for recovering the dense subgraph from the fractional solution and does not employ a binary search. Compared with the work by Boob et al. (2019), our algorithm via area convexity improves the iteration complexity by a factor $$\Delta$$ — the maximum degree in the graph, and matches the fastest theoretical runtime currently known via flows (Chekuri et al., 2022) in total time. Next, we study the dense subgraph decomposition problem and give the first practical iterative algorithm with linear convergence rate $$O\left(mn\log\frac{1}{\epsilon}\right)$$ via accelerated random coordinate descent. This significantly improves over $$O\left(\frac{m\sqrt{mn\Delta}}{\epsilon}\right)$$ time of the FISTA-based algorithm by Harb et al. (2022). In the high precision regime $$\epsilon\ll\frac{1}{n}$$ where we can even recover the exact solution, our algorithm has a total runtime of $$O\left(mn\log n\right)$$, matching the state of the art exact algorithm via parametric flows (Gallo et al., 1989). Empirically, we show that this algorithm is very practical and scales to very large graphs, and its performance is competitive with widely used methods that have significantly weaker theoretical guarantees. 

   more » « less
2. Search for the $$ {B}_s^0 $$ → μ+μ−γ decay

   https://doi.org/10.1007/JHEP07(2024)101  

   Aaij, R; Abdelmotteleb, A_S W; Abellan_Beteta, C; Abudinén, F; Ackernley, T; Adefisoye, A A; Adeva, B; Adinolfi, M; Adlarson, P; Agapopoulou, C; et al (July 2024, Journal of High Energy Physics)

   A<sc>bstract</sc> A search for the fully reconstructed$$ {B}_s^0 $$ $B_s^0$→ μ⁺μ⁻γdecay is performed at the LHCb experiment using proton-proton collisions at$$ \sqrt{s} $$ $\sqrt{s}$= 13 TeV corresponding to an integrated luminosity of 5.4 fb⁻¹. No significant signal is found and upper limits on the branching fraction in intervals of the dimuon mass are set$$ {\displaystyle \begin{array}{cc}\mathcal{B}\left({B}_s^0\to {\mu}^{+}{\mu}^{-}\gamma \right)<4.2\times {10}^{-8},& m\left({\mu}^{+}{\mu}^{-}\right)\in \left[2{m}_{\mu },1.70\right]\textrm{GeV}/{c}^2,\\ {}\mathcal{B}\left({B}_s^0\to {\mu}^{+}{\mu}^{-}\gamma \right)<7.7\times {10}^{-8},&\ m\left({\mu}^{+}{\mu}^{-}\right)\in \left[\textrm{1.70,2.88}\right]\textrm{GeV}/{c}^2,\\ {}\mathcal{B}\left({B}_s^0\to {\mu}^{+}{\mu}^{-}\gamma \right)<4.2\times {10}^{-8},& m\left({\mu}^{+}{\mu}^{-}\right)\in \left[3.92,{m}_{B_s^0}\right]\textrm{GeV}/{c}^2,\end{array}} $$ $\begin{array}{cc}B\left(B_s^0\to {\mu }^{+}{\mu }^{-}\gamma \right)<4.2\times {10}^{-8},& m\left({\mu }^{+}{\mu }^{-}\right)\in \left(2m_{\mu },1.70\right)\mathrm{GeV}/c^2,\\ B\left(B_s^0\to {\mu }^{+}{\mu }^{-}\gamma \right)<7.7\times {10}^{-8},& m\left({\mu }^{+}{\mu }^{-}\right)\in \left(\mathrm{1.70,\; 2.88}\right)\mathrm{GeV}/c^2,\\ B\left(B_s^0\to {\mu }^{+}{\mu }^{-}\gamma \right)<4.2\times {10}^{-8},& m\left({\mu }^{+}{\mu }^{-}\right)\in \left(3.92,m_{B_s^0}\right)\mathrm{GeV}/c^2,\end{array}$ at 95% confidence level. Additionally, upper limits are set on the branching fraction in the [2m_μ,1.70] GeV/c²dimuon mass region excluding the contribution from the intermediateϕ(1020) meson, and in the region combining all dimuon-mass intervals. 

   more » « less
3. Memory-Sample Tradeoffs for Linear Regression with Small Error

   Sharan, Vatsal; Sidford, Aaron; Valiant, Gregory (January 2019, Symposium on Theory of Computing (STOC))

   We consider the problem of performing linear regression over a stream of d-dimensional examples, and show that any algorithm that uses a subquadratic amount of memory exhibits a slower rate of convergence than can be achieved without memory constraints. Specifically, consider a sequence of labeled examples (a_1,b_1), (a_2,b_2)..., with a_i drawn independently from a d-dimensional isotropic Gaussian, and where b_i = + \eta_i, for a fixed x in R^d with ||x||= 1 and with independent noise \eta_i drawn uniformly from the interval [-2^{-d/5},2^{-d/5}]. We show that any algorithm with at most d^2/4 bits of memory requires at least \Omega(d \log \log \frac{1}{\epsilon}) samples to approximate x to \ell_2 error \epsilon with probability of success at least 2/3, for \epsilon sufficiently small as a function of d. In contrast, for such \epsilon, x can be recovered to error \epsilon with probability 1-o(1) with memory O\left(d^2 \log(1/\epsilon)\right) using d examples. This represents the first nontrivial lower bounds for regression with super-linear memory, and may open the door for strong memory/sample tradeoffs for continuous optimization. 

   more » « less
4. Super-polynomial accuracy of one dimensional randomized nets using the median of means

   https://doi.org/10.1090/mcom/3791  

   Pan, Zexin; Owen, Art (March 2023, Mathematics of Computation)

   Let $f$be analytic on $[0,1]$with $|f^{\left(k\right)}\left(1/2\right)|⩽<\#comment/>A{\mathrm{\alpha <\#comment/>}}^{k}k!$for some constants $A$and $\mathrm{\alpha <\#comment/>}>2$and all $k⩾<\#comment/>1$. We show that the median estimate of $\mathrm{\mu <\#comment/>}={\int <\#comment/>}_0^{1}f\left(x\right)\mathrm{d}x$under random linear scrambling with $n=2^m$points converges at the rate $O\left(n^{-<\#comment/>c\log <\#comment/>\left(n\right)}\right)$for any $c>3\log <\#comment/>\left(2\right)/{\mathrm{\pi <\#comment/>}}^2\approx <\#comment/>0.21$. We also get a super-polynomial convergence rate for the sample median of $2k-<\#comment/>1$random linearly scrambled estimates, when $k/m$is bounded away from zero. When $f$has a $p$’th derivative that satisfies a $\mathrm{\lambda <\#comment/>}$-Hölder condition then the median of means has error $O\left(n^{-<\#comment/>(p+\mathrm{\lambda <\#comment/>})+\mathrm{ϵ<\#comment/>}}\right)$for any $\mathrm{ϵ<\#comment/>}>0$, if $k\to <\#comment/>\mathrm{\infty <\#comment/>}$as $m\to <\#comment/>\mathrm{\infty <\#comment/>}$. The proof techniques use methods from analytic combinatorics that have not previously been applied to quasi-Monte Carlo methods, most notably an asymptotic expression from Hardy and Ramanujan on the number of partitions of a natural number. 

   more » « less
5. Tight Bounds for ℓ ₁ Oblivious Subspace Embeddings

   https://doi.org/10.1145/3477537  

   Wang, Ruosong; Woodruff, David P. (January 2022, ACM Transactions on Algorithms)

   An \ell _p oblivious subspace embedding is a distribution over r \times n matrices \Pi such that for any fixed n \times d matrix A , \[ \Pr _{\Pi }[\textrm {for all }x, \ \Vert Ax\Vert _p \le \Vert \Pi Ax\Vert _p \le \kappa \Vert Ax\Vert _p] \ge 9/10,\] where r is the dimension of the embedding, \kappa is the distortion of the embedding, and for an n -dimensional vector y , \Vert y\Vert _p = (\sum _{i=1}^n |y_i|^p)^{1/p} is the \ell _p -norm. Another important property is the sparsity of \Pi , that is, the maximum number of non-zero entries per column, as this determines the running time of computing \Pi A . While for p = 2 there are nearly optimal tradeoffs in terms of the dimension, distortion, and sparsity, for the important case of 1 \le p \lt 2 , much less was known. In this article, we obtain nearly optimal tradeoffs for \ell _1 oblivious subspace embeddings, as well as new tradeoffs for 1 \lt p \lt 2 . Our main results are as follows: (1) We show for every 1 \le p \lt 2 , any oblivious subspace embedding with dimension r has distortion \[ \kappa = \Omega \left(\frac{1}{\left(\frac{1}{d}\right)^{1 / p} \log ^{2 / p}r + \left(\frac{r}{n}\right)^{1 / p - 1 / 2}}\right).\] When r = {\operatorname{poly}}(d) \ll n in applications, this gives a \kappa = \Omega (d^{1/p}\log ^{-2/p} d) lower bound, and shows the oblivious subspace embedding of Sohler and Woodruff (STOC, 2011) for p = 1 is optimal up to {\operatorname{poly}}(\log (d)) factors. (2) We give sparse oblivious subspace embeddings for every 1 \le p \lt 2 . Importantly, for p = 1 , we achieve r = O(d \log d) , \kappa = O(d \log d) and s = O(\log d) non-zero entries per column. The best previous construction with s \le {\operatorname{poly}}(\log d) is due to Woodruff and Zhang (COLT, 2013), giving \kappa = \Omega (d^2 {\operatorname{poly}}(\log d)) or \kappa = \Omega (d^{3/2} \sqrt {\log n} \cdot {\operatorname{poly}}(\log d)) and r \ge d \cdot {\operatorname{poly}}(\log d) ; in contrast our r = O(d \log d) and \kappa = O(d \log d) are optimal up to {\operatorname{poly}}(\log (d)) factors even for dense matrices. We also give (1) \ell _p oblivious subspace embeddings with an expected 1+\varepsilon number of non-zero entries per column for arbitrarily small \varepsilon \gt 0 , and (2) the first oblivious subspace embeddings for 1 \le p \lt 2 with O(1) -distortion and dimension independent of n . Oblivious subspace embeddings are crucial for distributed and streaming environments, as well as entrywise \ell _p low-rank approximation. Our results give improved algorithms for these applications. 

   more » « less