
Local SGD Optimizes Overparameterized Neural Networks in Polynomial Time
In this paper we prove that Local (S)GD (or FedAvg) can optimize twolay...
read it

Pareto Efficient Fairness in Supervised Learning: From Extraction to Tracing
As algorithmic decisionmaking systems are becoming more pervasive, it i...
read it

On the Importance of Sampling in Learning Graph Convolutional Networks
Graph Convolutional Networks (GCNs) have achieved impressive empirical a...
read it

Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency
Local SGD is a promising approach to overcome the communication overhead...
read it

Distributionally Robust Federated Averaging
In this paper, we study communication efficient distributed algorithms f...
read it

Communicationefficient kMeans for Edgebased Machine Learning
We consider the problem of computing the kmeans centers for a large hig...
read it

Online Structured Metalearning
Learning quickly is of great importance for machine intelligence deploye...
read it

Federated Learning with Compression: Unified Analysis and Sharp Guarantees
In federated learning, communication cost is often a critical bottleneck...
read it

Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks
Sampling methods (e.g., nodewise, layerwise, or subgraph) has become a...
read it

Adaptive Personalized Federated Learning
Investigation of the degree of personalization in federated learning alg...
read it

Efficient Fair Principal Component Analysis
The flourishing assessments of fairness measure in machine learning algo...
read it

On the Convergence of Local Descent Methods in Federated Learning
In federated distributed learning, the goal is to optimize a global trai...
read it

Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization
Communication overhead is one of the key challenges that hinders the sca...
read it

Learning Feature Nonlinearities with NonConvex Regularized Binned Regression
For various applications, the relations between the dependent and indepe...
read it

Sketching Meets Random Projection in the Dual: A Provable Recovery Algorithm for Big and Highdimensional Data
Sketching techniques have become popular for scaling up machine learning...
read it

Train and Test Tightness of LP Relaxations in Structured Prediction
Structured prediction is used in areas such as computer vision and natur...
read it

Binary Excess Risk for Smooth Convex Surrogates
In statistical learning theory, convex surrogates of the 01 loss are hi...
read it

Excess Risk Bounds for Exponentially Concave Losses
The overarching goal of this paper is to derive excess risk bounds for l...
read it

Beating the Minimax Rate of Active Learning with Prior Knowledge
Active learning refers to the learning protocol where the learner is all...
read it

Sparse Multiple Kernel Learning with Geometric Convergence Rate
In this paper, we study the problem of sparse multiple kernel learning (...
read it

An Improved Bound for the Nystrom Method for Large Eigengap
We develop an improved bound for the approximation error of the Nyström ...
read it
Mehrdad Mahdavi
is this you? claim profile