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. Search for the dark photon in B0 → A′A′, A′ → e+e−, μ+μ−, and π+π− decays at Belle

   https://doi.org/10.1007/JHEP04(2021)191  

   Park, S.-H.; Kwon, Y.-J.; Adachi, I.; Aihara, H.; Al Said, S.; Asner, D. M.; Atmacan, H.; Aushev, T.; Ayad, R.; Babu, V.; et al (April 2021, Journal of High Energy Physics)

   null (Ed.)

   A bstract We present a search for the dark photon A ′ in the B 0 → A ′ A ′ decays, where A ′ subsequently decays to e + e − , μ + μ − , and π + π − . The search is performed by analyzing 772 × 10 6 $$ B\overline{B} $$ B B ¯ events collected by the Belle detector at the KEKB e + e − energy-asymmetric collider at the ϒ(4 S ) resonance. No signal is found in the dark photon mass range 0 . 01 GeV /c 2 ≤ m A ′ ≤ 2 . 62 GeV /c 2 , and we set upper limits of the branching fraction of B 0 → A ′ A ′ at the 90% confidence level. The products of branching fractions, $$ \mathrm{\mathcal{B}}\left({B}^0\to A^{\prime }A^{\prime}\right)\times \mathrm{\mathcal{B}}{\left(A\prime \to {e}^{+}{e}^{-}\right)}^2 $$ ℬ B 0 → A ′ A ′ × ℬ A ′ → e + e − 2 and $$ \mathrm{\mathcal{B}}\left({B}^0\to A^{\prime }A^{\prime}\right)\times \mathrm{\mathcal{B}}{\left(A\prime \to {\mu}^{+}{\mu}^{-}\right)}^2 $$ ℬ B 0 → A ′ A ′ × ℬ A ′ → μ + μ − 2 , have limits of the order of 10 − 8 depending on the A ′ mass. Furthermore, considering A ′ decay rate to each pair of charged particles, the upper limits of $$ \mathrm{\mathcal{B}}\left({B}^0\to A^{\prime }A^{\prime}\right) $$ ℬ B 0 → A ′ A ′ are of the order of 10 − 8 –10 − 5 . From the upper limits of $$ \mathrm{\mathcal{B}}\left({B}^0\to A^{\prime }A^{\prime}\right) $$ ℬ B 0 → A ′ A ′ , we obtain the Higgs portal coupling for each assumed dark photon and dark Higgs mass. The Higgs portal couplings are of the order of 10 − 2 –10 − 1 at $$ {m}_{h\prime}\simeq {m}_{B^0} $$ m h ′ ≃ m B 0 ± 40 MeV /c 2 and 10 − 1 –1 at $$ {m}_{h\prime}\simeq {m}_{B^0} $$ m h ′ ≃ m B 0 ± 3 GeV /c 2 . 

   more » « less