Author name cluster

Nova Fandina

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

2 author rows

ICML Conference 2023 Conference Paper

The Fast Johnson-Lindenstrauss Transform Is Even Faster

Nova Fandina
Mikael Møller Høgsgaard
Kasper Green Larsen

The Johnson-Lindenstaruss lemma (Johnson & Lindenstrauss, 1984) is a cornerstone result in dimensionality reduction, stating it is possible to embed a set of $n$ points in $d$-dimensional Euclidean space into optimal $k=O(\varepsilon^{-2} \ln n)$ dimensions, while preserving all pairwise distances to within a factor $(1 \pm \varepsilon)$. The seminal Fast Johnson-Lindenstrauss (Fast JL) transform by Ailon and Chazelle (SICOMP’09) supports computing the embedding of a data point in $O(d \ln d +k \ln^2 n)$ time, where the $d \ln d$ term comes from multiplication with a $d \times d$ Hadamard matrix and the $k \ln^2 n$ term comes from multiplication with a sparse $k \times d$ matrix. Despite the Fast JL transform being more than a decade old, it is one of the fastest dimensionality reduction techniques for many tradeoffs between $\varepsilon, d$ and $n$. In this work, we give a surprising new analysis of the Fast JL transform, showing that the $k \ln^2 n$ term in the embedding time can be improved to $(k \ln^2 n)/\alpha$ for an $\alpha = \Omega(\min\{\varepsilon^{-1}\ln(1/\varepsilon), \ln n\})$. The improvement follows by using an even sparser matrix. We complement our improved analysis with a lower bound showing that our new analysis is in fact tight.

Details

SODA Conference 2020 Conference Paper

Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds

Yair Bartal
Nova Fandina
Seeun William Umboh

Probabilistic metric embedding into trees is a powerful technique for designing online algorithms. The standard approach is to embed the entire underlying metric into a tree metric and then solve the problem on the latter. The overhead in the competitive ratio depends on the expected distortion of the embedding, which is logarithmic in n, the size of the underlying metric. For many online applications, such as online network design problems, it is natural to ask if it is possible to construct such embeddings in an online fashion such that the distortion would be a polylogarithmic function of k, the number of terminals. Our first main contribution is answering this question negatively, exhibiting a lower bound of (log k log ɸ), where ɸ is the aspect ratio of the set of terminals, showing that a simple modification of the probabilistic embedding into trees of Bartal (FOCS 1996), which has expected distortion of O (log k log ɸ), is nearly-tight. Unfortunately, this may result in a very bad (polynomial) dependence in terms of k. Our second main contribution is a general framework for bypassing this limitation. We show that for a large class of online problems this online probabilistic embedding can still be used to devise an algorithm with O (min{log k log( k λ), log 3 k }) overhead in the competitive ratio, where k is the current number of terminals, and λ is a measure of subadditivity of the cost function, which is at most r, the current number of requests. In particular, this implies the first algorithms with competitive ratio polylog( k ) for online subadditive network design ( buy-at-bulk network design being a special case), and polylog( k, r ) for online group Steiner forest.

Details

NeurIPS Conference 2019 Conference Paper

Dimensionality reduction: theoretical perspective on practical measures

Yair Bartal
Nova Fandina
Ofer Neiman

Dimensionality reduction plays a central role in real-world applications for Machine Learning, among many fields. In particular, metric dimensionality reduction where data from a general metric is mapped into low dimensional space, is often used as a first step before applying machine learning algorithms. In almost all these applications the quality of the embedding is measured by various average case criteria. Metric dimensionality reduction has also been studied in Math and TCS, within the extremely fruitful and influential field of metric embedding. Yet, the vast majority of theoretical research has been devoted to analyzing the worst case behavior of embeddings and therefore has little relevance to practical settings. The goal of this paper is to bridge the gap between theory and practice view-points of metric dimensionality reduction, laying the foundation for a theoretical study of more practically oriented analysis. This paper can be viewed as providing a comprehensive theoretical framework addressing a line of research initiated by VL [NeuroIPS' 18] who have set the goal of analyzing different distortion measurement criteria, with the lens of Machine Learning applicability, from both theoretical and practical perspectives. We complement their work by considering some important and vastly used average case criteria, some of which originated within the well-known Multi-Dimensional Scaling framework. While often studied in practice, no theoretical studies have thus far attempted at providing rigorous analysis of these criteria. In this paper we provide the first analysis of these, as well as the new distortion measure developed by [VL18] designed to possess Machine Learning desired properties. Moreover, we show that all measures considered can be adapted to possess similar qualities. The main consequences of our work are nearly tight bounds on the absolute values of all distortion criteria, as well as first approximation algorithms with provable guarantees.

PDF Details