Efficiently Learning Fourier Sparse Set Functions
Authors: Andisheh Amrollahi, Amir Zandieh, Michael Kapralov, Andreas Krause
NeurIPS 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We test our EXACTSHT algorithm for graph sketching on a real world data set. and This allows us to learn sparse graphs which have in the range of 800 vertices in 2 seconds whereas the previous methods [12] were constrained to the range of 100 for similar runtimes. |
| Researcher Affiliation | Academia | Andisheh Amrollahi ETH Zurich Zurich, Switzerland amrollaa@ethz.ch, Amir Zandieh EPFL Lausanne, Switzerland amir.zandieh@epfl.ch, Michael Kapralov EPFL Lausanne, Switzerland michael.kapralov@epfl.ch, Andreas Krause ETH Zurich Zurich, Switzerland krausea@ethz.ch |
| Pseudocode | Yes | Algorithm 1 RECOVERFREQUENCY, Algorithm 2 HASH2BINS, Algorithm 3 SHTINNER, Algorithm 4 EXACTSHT |
| Open Source Code | No | No statement or link providing access to open-source code for the described methodology was found. |
| Open Datasets | Yes | We utilize the autonomous systems dataset from the SNAP data collection.3 snap.stanford.edu/data/ |
| Dataset Splits | No | The paper describes using a dataset and varying parameters like number of vertices (n) and edges (e) for experiments. However, it does not explicitly provide details about training, validation, or test dataset splits (e.g., percentages, sample counts, or references to predefined splits). |
| Hardware Specification | No | The paper mentions performance metrics like '800 vertices in 2 seconds' but does not specify any particular CPU, GPU, or other hardware components used for running the experiments. |
| Software Dependencies | No | No specific software dependencies with version numbers (e.g., programming languages, libraries, frameworks with their versions) are mentioned. |
| Experiment Setup | No | The paper describes how graphs were generated ('order the vertices of the graph by their degree', 'pick e = 50 edges uniformly at random') and that parameters were tuned ('The parameters tuned in our algorithm to reach this error probability are the initial number of buckets the frequencies are hashed to and the ratio at which they reduce in each iteration.'). However, it does not provide explicit values for these or other typical experimental setup details such as learning rates, batch sizes, or optimizer settings often found in machine learning papers. |