-
Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem
Authors:
Yann Disser,
Svenja M. Griesbach,
Max Klimm,
Annette Lutz
Abstract:
We consider an incremental variant of the rooted prize-collecting Steiner-tree problem with a growing budget constraint. While no incremental solution exists that simultaneously approximates the optimum for all budgets, we show that a bicriterial $(α,μ)$-approximation is possible, i.e., a solution that with budget $B+α$ for all $B \in \mathbb{R}_{\geq 0}$ is a multiplicative $μ$-approximation comp…
▽ More
We consider an incremental variant of the rooted prize-collecting Steiner-tree problem with a growing budget constraint. While no incremental solution exists that simultaneously approximates the optimum for all budgets, we show that a bicriterial $(α,μ)$-approximation is possible, i.e., a solution that with budget $B+α$ for all $B \in \mathbb{R}_{\geq 0}$ is a multiplicative $μ$-approximation compared to the optimum solution with budget $B$. For the case that the underlying graph is a tree, we present a polynomial-time density-greedy algorithm that computes a $(χ,1)$-approximation, where $χ$ denotes the eccentricity of the root vertex in the underlying graph, and show that this is best possible. An adaptation of the density-greedy algorithm for general graphs is $(γ,2)$-competitive where $γ$ is the maximal length of a vertex-disjoint path starting in the root. While this algorithm does not run in polynomial time, it can be adapted to a $(γ,3)$-competitive algorithm that runs in polynomial time. We further devise a capacity-scaling algorithm that guarantees a $(3χ,8)$-approximation and, more generally, a $\smash{\bigl((4\ell - 1)χ, \frac{2^{\ell + 2}}{2^{\ell}-1}\bigr)}$-approximation for every fixed $\ell \in \mathbb{N}$.
△ Less
Submitted 5 July, 2024;
originally announced July 2024.
-
A Privacy Preserving System for Movie Recommendations Using Federated Learning
Authors:
David Neumann,
Andreas Lutz,
Karsten Müller,
Wojciech Samek
Abstract:
Recommender systems have become ubiquitous in the past years. They solve the tyranny of choice problem faced by many users, and are utilized by many online businesses to drive engagement and sales. Besides other criticisms, like creating filter bubbles within social networks, recommender systems are often reproved for collecting considerable amounts of personal data. However, to personalize recomm…
▽ More
Recommender systems have become ubiquitous in the past years. They solve the tyranny of choice problem faced by many users, and are utilized by many online businesses to drive engagement and sales. Besides other criticisms, like creating filter bubbles within social networks, recommender systems are often reproved for collecting considerable amounts of personal data. However, to personalize recommendations, personal information is fundamentally required. A recent distributed learning scheme called federated learning has made it possible to learn from personal user data without its central collection. Consequently, we present a recommender system for movie recommendations, which provides privacy and thus trustworthiness on multiple levels: First and foremost, it is trained using federated learning and thus, by its very nature, privacy-preserving, while still enabling users to benefit from global insights. Furthermore, a novel federated learning scheme, called FedQ, is employed, which not only addresses the problem of non-i.i.d.-ness and small local datasets, but also prevents input data reconstruction attacks by aggregating client updates early. Finally, to reduce the communication overhead, compression is applied, which significantly compresses the exchanged neural network parametrizations to a fraction of their original size. We conjecture that this may also improve data privacy through its lossy quantization stage.
△ Less
Submitted 16 May, 2024; v1 submitted 7 March, 2023;
originally announced March 2023.
-
Using Deep Learning to Find the Next Unicorn: A Practical Synthesis
Authors:
Lele Cao,
Vilhelm von Ehrenheim,
Sebastian Krakowski,
Xiaoxue Li,
Alexandra Lutz
Abstract:
Startups often represent newly established business models associated with disruptive innovation and high scalability. They are commonly regarded as powerful engines for economic and social development. Meanwhile, startups are heavily constrained by many factors such as limited financial funding and human resources. Therefore, the chance for a startup to eventually succeed is as rare as "spotting…
▽ More
Startups often represent newly established business models associated with disruptive innovation and high scalability. They are commonly regarded as powerful engines for economic and social development. Meanwhile, startups are heavily constrained by many factors such as limited financial funding and human resources. Therefore, the chance for a startup to eventually succeed is as rare as "spotting a unicorn in the wild". Venture Capital (VC) strives to identify and invest in unicorn startups during their early stages, hoping to gain a high return. To avoid entirely relying on human domain expertise and intuition, investors usually employ data-driven approaches to forecast the success probability of startups. Over the past two decades, the industry has gone through a paradigm shift moving from conventional statistical approaches towards becoming machine-learning (ML) based. Notably, the rapid growth of data volume and variety is quickly ushering in deep learning (DL), a subset of ML, as a potentially superior approach in terms of capacity and expressivity. In this work, we carry out a literature review and synthesis on DL-based approaches, covering the entire DL life cycle. The objective is a) to obtain a thorough and in-depth understanding of the methodologies for startup evaluation using DL, and b) to distil valuable and actionable learning for practitioners. To the best of our knowledge, our work is the first of this kind.
△ Less
Submitted 10 June, 2024; v1 submitted 18 October, 2022;
originally announced October 2022.
-
Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete
Authors:
Elisabeth Lobe,
Annette Lutz
Abstract:
The embedding is an essential step when calculating on the D-Wave machine. In this work we show the hardness of the embedding problem for both types of existing hardware, represented by the Chimera and the Pegasus graphs, containing unavailable qubits. We construct certain broken Chimera graphs, where it is hard to find a Hamiltonian cycle. As the Hamiltonian cycle problem is a special case of the…
▽ More
The embedding is an essential step when calculating on the D-Wave machine. In this work we show the hardness of the embedding problem for both types of existing hardware, represented by the Chimera and the Pegasus graphs, containing unavailable qubits. We construct certain broken Chimera graphs, where it is hard to find a Hamiltonian cycle. As the Hamiltonian cycle problem is a special case of the embedding problem, this proves the general complexity result for the Chimera graphs. By exploiting the subgraph relation between the Chimera and the Pegasus graphs, the proof is then further extended to the Pegasus graphs.
△ Less
Submitted 15 October, 2021;
originally announced October 2021.
-
Fractionally Subadditive Maximization under an Incremental Knapsack Constraint
Authors:
Yann Disser,
Max Klimm,
Annette Lutz,
David Weckbecker
Abstract:
We consider the problem of maximizing a fractionally subadditive function under a knapsack constraint that grows over time. An incremental solution to this problem is given by an order in which to include the elements of the ground set, and the competitive ratio of an incremental solution is defined by the worst ratio over all capacities relative to an optimum solution of the corresponding capacit…
▽ More
We consider the problem of maximizing a fractionally subadditive function under a knapsack constraint that grows over time. An incremental solution to this problem is given by an order in which to include the elements of the ground set, and the competitive ratio of an incremental solution is defined by the worst ratio over all capacities relative to an optimum solution of the corresponding capacity. We present an algorithm that finds an incremental solution of competitive ratio at most $\max\{3.293\sqrt{M},2M\}$, under the assumption that the values of singleton sets are in the range $[1,M]$, and we give a lower bound of $\max\{2.618,M\}$ on the attainable competitive ratio. In addition, we establish that our framework captures potential-based flows between two vertices, and we give a lower bound of $\max\{2,M\}$ and an upper bound of $2M$ for the incremental maximization of classical flows with capacities in $[1,M]$ which is tight for the unit capacity case.
△ Less
Submitted 24 May, 2023; v1 submitted 28 June, 2021;
originally announced June 2021.
-
Computational Enhancement of Molecularly Targeted Contrast-Enhanced Ultrasound: Application to Human Breast Tumor Imaging
Authors:
Andrew A. Berlin,
Mon Young,
Ahmed El Kaffas,
Sam Gambhir,
Amelie Lutz,
Maria Luigia Storto,
Juergen Willmann
Abstract:
Molecularly targeted contrast enhanced ultrasound (mCEUS) is a clinically promising approach for early cancer detection through targeted imaging of VEGFR2 (KDR) receptors. We have developed computational enhancement techniques for mCEUS tailored to address the unique challenges of imaging contrast accumulation in humans. These techniques utilize dynamic analysis to distinguish molecularly bound co…
▽ More
Molecularly targeted contrast enhanced ultrasound (mCEUS) is a clinically promising approach for early cancer detection through targeted imaging of VEGFR2 (KDR) receptors. We have developed computational enhancement techniques for mCEUS tailored to address the unique challenges of imaging contrast accumulation in humans. These techniques utilize dynamic analysis to distinguish molecularly bound contrast agent from other contrast-mode signal sources, enabling analysis of contrast agent accumulation to be performed during contrast bolus arrival when the signal due to molecular binding is strongest.
Applied to the 18 human patient examinations of the first-in-human molecular ultrasound breast lesion study, computational enhancement improved the ability to differentiate between pathology-proven lesion and pathology-proven normal tissue in real-world human examination conditions that involved both patient and probe motion, with improvements in contrast ratio between lesion and normal tissue that in most cases exceed an order of magnitude (10x). Notably, computational enhancement eliminated a false positive result in which tissue leakage signal was misinterpreted by radiologists to be contrast agent accumulation.
△ Less
Submitted 21 June, 2020;
originally announced June 2020.
-
High-dimensional and universally consistent k-sample tests
Authors:
Sambit Panda,
Cencheng Shen,
Ronan Perry,
Jelle Zorn,
Antoine Lutz,
Carey E. Priebe,
Joshua T. Vogelstein
Abstract:
The k-sample testing problem involves determining whether $k$ groups of data points are each drawn from the same distribution. The standard method for k-sample testing in biomedicine is Multivariate analysis of variance (MANOVA), despite that it depends on strong, and often unsuitable, parametric assumptions. Moreover, independence testing and k-sample testing are closely related, and several univ…
▽ More
The k-sample testing problem involves determining whether $k$ groups of data points are each drawn from the same distribution. The standard method for k-sample testing in biomedicine is Multivariate analysis of variance (MANOVA), despite that it depends on strong, and often unsuitable, parametric assumptions. Moreover, independence testing and k-sample testing are closely related, and several universally consistent high-dimensional independence tests such as distance correlation (Dcorr) and Hilbert-Schmidt-Independence-Criterion (Hsic) enjoy solid theoretical and empirical properties. In this paper, we prove that independence tests achieve universally consistent k-sample testing and that k-sample statistics such as Energy and Maximum Mean Discrepancy (MMD) are precisely equivalent to Dcorr. An empirical evaluation of nonparametric independence tests showed that they generally perform better than the popular MANOVA test, even in Gaussian distributed scenarios. The evaluation included several popular independence statistics and covered a comprehensive set of simulations. Additionally, the testing approach was extended to perform multiway and multilevel tests, which were demonstrated in a simulated study as well as a real-world fMRI brain scans with a set of attributes.
△ Less
Submitted 11 October, 2023; v1 submitted 19 October, 2019;
originally announced October 2019.
