Study on distributed estimation under communication constraints.
problem Distributed estimation in constrained communication environments.
method Derive minimax lower bounds and exhibit adaptive methods.
result Adaptive estimation possible in distributed nonparametric regression.
The paper sets communication limits for distributed optimization with feature-based data partitions.
problem Understanding communication limits in distributed convex optimization with feature-based data partitions.
method Developed tight lower bounds on communication rounds for non-incremental and incremental algorithms.
result Established communication limits for a broad class of algorithms under feature-based data partitioning.
Paper studies signal detection in noisy environments with limited communication.
problem Signal detection in Gaussian noise with 1-bit communication constraints.
method Derives lower bounds and exhibits optimal testing strategies.
result Optimal distributed testing strategies attain the derived lower bound.
The paper improves regret lower bounds for communicating MDPs.
problem Regret lower bounds for communicating MDPs.
method Lower bound proof and optimization problem formulation.
result Regret lower bound becomes significantly more complex in communicating MDPs.
Proves exponential sample complexity separations in local differential privacy.
problem Sample complexity in locally private protocols.
method Connection between communication complexity and sample complexity, using specific lower bounds for two problems.
result Exponential separations between differentially private protocols.
New estimator for overlapping community detection in graphs.
problem Reconstructing community relations in graphs with overlapping memberships.
method Proposes a new estimator for Mixed-Membership Stochastic Block Model (MMSB) under diverging spiked eigenvalues condition.
result New estimator matches theoretical minimax lower bound on estimation error.
Study on efficient estimation of Gaussian mean with limited communication.
problem Estimating Gaussian mean under communication constraints.
method Decomposition into localization and refinement stages, development of communication-efficient and statistically optimal procedures.
result Established minimax rates of convergence and developed optimal procedures.
Study on statistical estimation over Gaussian MAC, comparing analog and digital schemes.
problem Distributed minimax statistical estimation over a Gaussian MAC.
method Developed analog joint estimation-communication schemes and derived information-theoretic lower bounds.
result Achieved risk within a logarithmic factor of information-theoretic lower bounds.
We study distributed optimization algorithms for minimizing the average of convex functions. The applications include empirical risk minimization problems in statistical machine learning where the datasets are large and have to be stored on different machines. We design a distributed stochastic variance reduced gradien…
Efficient algorithm for CLSBM reduces misclassification rate.
problem Reducing misclassification in community detection for CLSBM.
method Spectral-based algorithm for CLSBM, with theoretical misclassification bounds.
result Upper bound on misclassification rate of efficient algorithm.
Efficiently tests discrete distributions with limited memory and communication.
problem Testing discrete distributions with constraints on memory and communication.
method Developed efficient algorithms for uniformity/identity and closeness testing in streaming and distributed models.
result Nearly-tight lower bounds on sample complexity and communication cost for uniformity testing.
In this paper, we study the information-theoretic limits of community detection in the symmetric two-community stochastic block model, with intra-community and inter-community edge probabilities a n \frac{a}{n} n a and b n \frac{b}{n} n b respectively. We consider the sparse setting, in which a a a and b b b do not scale with n n n , and…
The paper tackles nonparametric regression with distributed data under communication constraints.
problem Nonparametric estimation of a smooth function with data distributed across multiple machines and limited communication.
method The approach involves constructing an estimator of the true function at a central machine with limited bits for transmission, considering various settings of machine number, data size, and communication budget.
result The paper identifies three regimes based on the relationship among machines, data size, and communication budget, providing both lower and upper bounds on statistical risk.
In this paper, we consider the distributed stochastic multi-armed bandit problem, where a global arm set can be accessed by multiple players independently. The players are allowed to exchange their history of observations with each other at specific points in time. We study the relationship between regret and communica…
We study the following generalized matrix rank estimation problem: given an n × n n \times n n × n matrix and a constant c ≥ 0 c \geq 0 c ≥ 0 , estimate the number of eigenvalues that are greater than c c c . In the distributed setting, the matrix of interest is the sum of m m m matrices held by separate machines. We show that any deterministic…
Paper studies statistical-computational trade-offs in tensor PCA and related problems.
problem Statistical-computational gap in tensor PCA estimation.
method Derives computational lower bounds using communication complexity.
result Lower bounds specify trade-off among passes, sample size, and memory.
Paper sets fundamental limits for distributed covariance estimation with constrained communication.
problem Estimating high-dimensional covariance matrices in a feature-split setting with limited communication.
method Developed a Conditional Strong Data Processing Inequality (C-SDPI) to establish minimax lower bounds and an optimal estimation protocol.
result Achieved nearly optimal estimation protocol with sample and communication requirements matching lower bounds up to logarithmic factors.
New algorithm reduces regret in collaborative multi-agent bandit problems.
problem Optimizing decisions in a network of agents with communication delays.
method Follow-the-Regularized-Leader (FTRL) algorithm with suitable regularizers and communication protocols.
result Upper bound on individual regret matches lower bound up to a constant factor.
Paper proposes GPM for simultaneous community detection and group synchronization.
problem Simultaneous community detection and group synchronization in networks.
method Generalized Power Method (GPM) for non-convex optimization.
result GPM achieves exact recovery in O ( n log 2 n ) O(n\log^2n) O ( n log 2 n ) time, outperforming SDP. A new test optimizes detecting small communities in large networks.
problem Detecting small communities in large networks.
method Using Sinkhorn's theorem and a degree-corrected block model (DCBM), the study optimizes the SgnQ test for this challenging setting.
result The SgnQ test is optimal for detecting communities larger than √n, achieving the computational lower bound (CLB).
We study the tradeoff between the statistical error and communication cost of distributed statistical estimation problems in high dimensions. In the distributed sparse Gaussian mean estimation problem, each of the m m m machines receives n n n data points from a d d d -dimensional Gaussian distribution with unknown mean θ θ θ w…
Federated learning limits and optimal algorithm with low communication cost.
problem Achieving optimal performance in one-shot federated learning with limited communication.
method Investigates the impact of communication constraints on expected error, proposes Multi-Resolution Estimator (MRE).
result MRE achieves error close to theoretical limit with B ≥ log m n B \ge \log mn B ≥ log mn and is order optimal. In this paper, we present two new communication-efficient methods for distributed minimization of an average of functions. The first algorithm is an inexact variant of the DANE algorithm that allows any local algorithm to return an approximate solution to a local subproblem. We show that such a strategy does not affect…
The study sets up a framework to analyze parallel optimization problems with graph dependencies.
problem Analyzing the complexity of parallel stochastic optimization problems with graph dependencies.
method Developed a graph oracle-based framework to derive lower bounds and highlight gaps.
result Identified gaps between lower and upper bounds for specific parallel optimization settings.
New study shows non-interactive privacy model requires exponentially more data.
problem Privacy constraints limit data analysis efficiency.
method Developed new technique to prove lower bounds on data samples needed.
result Exponential lower bound on samples needed for learning tasks.
Efficient algorithm for Bayesian estimation from few samples, focusing on community detection.
problem Bayesian estimation problems, especially community detection in graphs.
method Meta-algorithm based on low-degree polynomials, semidefinite programming, and tensor decomposition.
result Best recovery guarantees for community detection in sparse stochastic block models and mixed-membership stochastic block models.
Optimal distributed testing under communication constraints with shared randomness.
problem Signal detection in a distributed system with limited communication.
method Derivation of minimax testing errors, distributed testing algorithms, and theoretical lower bounds.
result Consistent nonparametric distributed testing is possible even with minimal communication.
Study how communication and feedback graphs affect learning outcomes.
problem Understanding the impact of feedback graphs on cooperative online learning.
method Analyzed network regret in terms of the independence number of the strong product of communication and feedback graphs.
result Proved bounds for network regret and demonstrated the non-improvable nature of positive results in pathological cases.
Sparse covariance estimation in the vertical-split model achieves exponential improvement over dense estimates.
problem Minimax estimation error for distributed covariance matrix estimation in the vertical-split setting.
method Elementwise s s s -sparsity is shown to reduce communication and sample complexity. result Minimax lower bounds for 1 1 1 -sparse cross-covariance estimation are established. A distributed algorithm reduces communication cost in linear bandits to near-optimal levels.
problem Cooperative linear bandit optimization with stochastic contexts.
method DisBE-LUCB algorithm, DecBE-LUCB algorithm, sharing information through a central server or immediate neighbors.
result Communication cost of DisBE-LUCB matches information-theoretic lower bound up to logarithmic factors.
In this paper, we study the sensitivity of the spectral clustering based community detection algorithm subject to a Erdos-Renyi type random noise model. We prove phase transitions in community detectability as a function of the external edge connection probability and the noisy edge presence probability under a general…
Study quantile reward identification with 1-bit feedback constraints.
problem Best arm identification with quantile reward and 1-bit communication.
method Proposes an algorithm using noisy binary search for quantile reward estimation.
result Derives upper and lower bounds on sample complexity for 1-bit feedback.
Study on individual regret in cooperative MAB with agents communicating over a graph.
problem Individual regret in cooperative stochastic multi-armed bandits with communication constraints.
method Analyzed COOP-SE algorithm, derived individual regret bounds under various communication constraints.
result First to show an individual regret bound in cooperative stochastic MAB independent of graph diameter.
A bandit algorithm reduces regret in noisy, communication-constrained feedback.
problem Distributed stochastic multi-armed bandit with noisy, communication-constrained feedback.
method Proposes a multi-phase bandit algorithm, UE-UCB++, that matches an information-theoretic lower bound.
result Matches an information-theoretic lower bound of Ω(√(KT/σ²)) on the minimax regret.
This paper sets communication complexity bounds for distributed RL.
problem Establishing minimum communication requirements for distributed RL.
method Information-theoretic lower bounds and algorithm development.
result Developed algorithms achieving optimal risk up to logarithmic factors.
Paper develops an efficient mean estimator for 1-bit communication constraints.
problem Mean estimation under 1-bit communication constraints.
method Adaptive mean estimator based on randomized threshold queries.
result Order-optimal sample complexity in various tail regimes.
New framework for distributed nonparametric estimation under slow communication.
problem Efficiently estimate nonparametric models across multiple nodes with limited communication.
method Developed a general framework for nonparametric estimation under communication constraints.
result Derived minimax lower and upper bounds for various models.
Paper studies collaboration in multi-armed bandits with limited interaction.
problem Identifying the best arm collaboratively with limited communication.
method Developed techniques to quantify and prove round-speedup tradeoffs.
result Almost tight round-speedup tradeoffs for distributed exploration.
Optimizes learning policies in MDPs with weakly communicating structure.
problem Learning optimal policies in weakly communicating MDPs with generative model.
method Span-based approach, reducing to discounted MDPs for analysis.
result First minimax optimal sample complexity bound for weakly communicating MDPs.
Two non-communicating players minimize regret in a multi-armed bandit game.
problem Optimal regret in non-communicating multi-armed bandit players.
method Proposed a strategy with no collisions, achieving near-optimal regret.
result Near-optimal regret of O ( T log ( T ) ) O(\sqrt{T \log(T)}) O ( T log ( T ) ) with very high probability. A study on the communication complexity of estimating correlations between variables.
problem Estimating the correlation between two sets of correlated random variables with limited communication.
method One-way interactive protocol exchanging k bits, optimizing over interaction protocol and estimator.
result Achieves optimal performance with communication complexity of 1/k, improving over naive schemes.
New algorithms for community detection in graphs with privacy constraints.
problem Community recovery in stochastic block models with node-wise privacy.
method Spectral clustering with privacy mechanisms, including privatized PCA, convex optimization, and matrix estimation.
result Developed algorithms that are computable in polynomial-time and achieve consistent community estimation under node differential privacy.
Safe-EF improves federated learning for non-smooth, constrained optimization.
problem Federated learning's communication bottlenecks with high-dimensional model updates.
method Error feedback (EF) for non-smooth convex optimization with safety constraints.
result Safe-EF matches lower complexity bounds and ensures safety constraints.
We formalize the problem of detecting a community in a network into testing whether in a given (random) graph there is a subgraph that is unusually dense. We observe an undirected and unweighted graph on N nodes. Under the null hypothesis, the graph is a realization of an Erdös-Rényi graph with probability p0. Under th…
Improved algorithm reduces communication rounds for distributed online learning.
problem Complicated constraints in distributed online learning with locally light computations.
method Proposed D-BOCG algorithm with delayed update mechanism and redefined surrogate loss function.
result Achieved O ( T 3 / 4 ) O(T^{3/4}) O ( T 3/4 ) regret bound with O ( T ) O(\sqrt{T}) O ( T ) communication rounds for convex losses. New method estimates node community memberships in networks.
problem Estimating community memberships of nodes in networks with overlapping communities.
method Sharp eigenvector deviation bounds for Mixed Membership Stochastic Blockmodel (MMSB).
result Uniform rates of convergence for node community membership vectors.
New tests detect communities in dense bipartite graphs with high accuracy.
problem Detecting communities in dense bipartite graphs with high accuracy.
method Non-asymptotic upper and lower bounds, novel minimax-optimal tests, hard-thresholded nonlinear statistics.
result Non-asymptotic upper and lower bounds match for any configuration of graph sizes.
This paper studies the problem of detecting the presence of a small dense community planted in a large Erdős-Rényi random graph G ( N , q ) \mathcal{G}(N,q) G ( N , q ) , where the edge probability within the community exceeds q q q by a constant factor. Assuming the hardness of the planted clique detection problem, we show that the computatio…