research
∙
08/12/2023
Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More
Algorithms for node clustering typically focus on finding homophilous st...
share
research
∙
05/23/2023
Kernel Interpolation with Sparse Grids
Structured kernel interpolation (SKI) accelerates Gaussian process (GP) ...
research
∙
05/10/2023
Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra
Given 𝐀∈ℝ^n × n with entries bounded in magnitude by 1, it is well-known...
research
∙
05/04/2023
On the Unreasonable Effectiveness of Single Vector Krylov Methods for Low-Rank Approximation
Krylov subspace methods are a ubiquitous tool for computing near-optimal...
research
∙
04/05/2023
Optimal Sketching Bounds for Sparse Linear Regression
We study oblivious sketching for k-sparse linear regression under variou...
research
∙
03/11/2023
No-regret Algorithms for Fair Resource Allocation
We consider a fair resource allocation problem in the no-regret setting ...
research
∙
03/06/2023
Near-Optimality Guarantees for Approximating Rational Matrix Functions by the Lanczos Method
We study the Lanczos method for approximating the action of a symmetric ...
research
∙
01/14/2023
Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation
We present a new approach for computing compact sketches that can be use...
research
∙
11/21/2022
Toeplitz Low-Rank Approximation with Sublinear Query Complexity
We present a sublinear query algorithm for outputting a near-optimal low...
research
∙
11/13/2022
Near-Linear Sample Complexity for L_p Polynomial Regression
We study L_p polynomial regression. Given query access to a function f:[...
research
∙
10/12/2022
Sample Constrained Treatment Effect Estimation
Treatment effect estimation is a fundamental problem in causal inference...
research
∙
09/30/2022
Direct Embedding of Temporal Network Edges via Time-Decayed Line Graphs
Temporal networks model a variety of important phenomena involving timed...
research
∙
07/06/2022
Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set Queries
We study the problem of estimating the number of edges in an n-vertex gr...
research
∙
03/14/2022
Fast Regression for Structured Inputs
We study the ℓ_p regression problem, which requires finding 𝐱∈ℝ^d that m...
research
∙
02/23/2022
Low-memory Krylov subspace methods for optimal rational matrix function approximation
We describe a Lanczos-based algorithm for approximating the product of a...
research
∙
02/08/2022
Simplified Graph Convolution with Heterophily
Graph convolutional networks (GCNs) (Kipf Welling, 2017) attempt to ...
research
∙
12/17/2021
Sublinear Time Approximation of Text Similarity Matrices
We study algorithms for approximating pairwise similarity matrices that ...
research
∙
11/28/2021
Local Edge Dynamics and Opinion Polarization
The proliferation of social media platforms, recommender systems, and th...
research
∙
11/09/2021
Active Sampling for Linear Regression Beyond the ℓ_2 Norm
We study active sampling algorithms for linear regression, which aim to ...
research
∙
11/04/2021
An Interpretable Graph Generative Model with Heterophily
Many models for graphs fall under the framework of edge-independent dot ...
research
∙
10/29/2021
On the Power of Edge Independent Graph Models
Why do many modern neural-network-based graph generative models fail to ...
research
∙
09/16/2021
Sublinear Time Eigenvalue Approximation via Random Sampling
We study the problem of approximating the eigenspectrum of a symmetric m...
research
∙
06/17/2021
Error bounds for Lanczos-based matrix function approximation
We analyze the Lanczos method for matrix function approximation (Lanczos...
research
∙
06/08/2021
Coresets for Classification – Simplified and Strengthened
We give relative error coresets for training linear classifiers with a b...
research
∙
02/17/2021
DeepWalking Backwards: From Embeddings Back to Graphs
Low-dimensional node embeddings play a key role in analyzing graph datas...
research
∙
02/16/2021
Faster Kernel Matrix Algebra via Density Estimation
We study fast algorithms for computing fundamental properties of a posit...
research
∙
01/28/2021
Faster Kernel Interpolation for Gaussian Processes
A key challenge in scaling Gaussian Process (GP) regression to massive d...
research
∙
12/27/2020
Intervention Efficient Algorithms for Approximate Learning of Causal Graphs
We study the problem of learning the causal relationships between a set ...
research
∙
11/19/2020
Estimation of Shortest Path Covariance Matrices
We study the sample complexity of estimating the covariance matrix Σ∈ℝ^d...
research
∙
10/20/2020
Model-specific Data Subsampling with Influence Functions
Model selection requires repeatedly evaluating models on a given dataset...
research
∙
10/19/2020
Hutch++: Optimal Stochastic Trace Estimation
We study the problem of estimating the trace of a matrix A that can only...
research
∙
10/05/2020
Subspace Embeddings Under Nonlinear Transformations
We consider low-distortion embeddings for subspaces under entrywise nonl...
research
∙
10/03/2020
Spiking Neural Networks Through the Lens of Streaming Algorithms
We initiate the study of biological neural networks from the perspective...
research
∙
06/12/2020
Fourier Sparse Leverage Scores and Approximate Kernel Learning
We prove new explicit upper bounds on the leverage scores of Fourier spa...
research
∙
06/10/2020
Node Embeddings and Exact Low-Rank Representations of Complex Networks
Low-dimensional embeddings, from classical spectral embeddings to modern...
research
∙
05/29/2020
InfiniteWalk: Deep Network Embeddings as Laplacian Embeddings with a Nonlinearity
The skip-gram model for learning word embeddings (Mikolov et al. 2013) h...
research
∙
05/24/2020
Efficient Intervention Design for Causal Discovery with Latents
We consider recovering a causal graph in presence of latent variables, w...
research
∙
04/17/2020
Projection-Cost-Preserving Sketches: Proof Strategies and Constructions
In this note we illustrate how common matrix approximation methods, such...
research
∙
11/19/2019
Low-Rank Toeplitz Matrix Estimation via Random Ultra-Sparse Rulers
We study how to estimate a nearly low-rank Toeplitz covariance matrix T ...
research
∙
11/04/2019
Importance Sampling via Local Sensitivity
Given a loss function F:X→R^+ that can be written as the sum of losses o...
research
∙
06/06/2019
Toward a Characterization of Loss Functions for Distribution Learning
In this work we study loss functions for learning and evaluating probabi...
research
∙
05/14/2019
Sample Efficient Toeplitz Covariance Estimation
We study the query complexity of estimating the covariance matrix T of a...
research
∙
04/26/2019
Learning to Prune: Speeding up Repeated Computations
It is common to encounter situations where one must solve a sequence of ...
research
∙
04/25/2019
Winner-Take-All Computation in Spiking Neural Networks
In this work we study biological neural networks from an algorithmic per...
research
∙
04/22/2019
Low-Rank Approximation from Communication Complexity
In low-rank approximation with missing entries, given A∈R^n× n and binar...
research
∙
03/28/2019
Faster Spectral Sparsification in Dynamic Streams
Graph sketching has emerged as a powerful technique for processing massi...
research
∙
12/20/2018
A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms
Reconstructing continuous signals from a small number of discrete sample...
research
∙
08/12/2018
A Basic Compositional Model for Spiking Neural Networks
This paper is part of a project on developing an algorithmic theory of b...
research
∙
04/26/2018
Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
Random Fourier features is one of the most popular techniques for scalin...
research
∙
04/23/2018