A Unified Theory of Decentralized SGD with Changing Topology and Local Updates

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In this work, we study online submodular maximization and how the requirement of maintaining a stable solution impacts the approximation. In particular, we seek bounds on the best-possible approximation ratio that is attainable when the algorithm is allowe ...

We describe a randomized algorithm for producing a near-optimal hierarchical off-diagonal low-rank (HODLR) approximation to an n × n matrix A, accessible only though matrix-vector products with A and AT. We prove that, for the rank-k HODLR approximation pr ...

Many challenges of modern graph processing stem from the fact that graphs have become massive and change frequently. Numerous techniques have been developed to address those issues, with graph cut sparsification offering to replace original graphs with th ...

This limitation is circumvented by using scalable and non–memory–intensive harmonic expansions. In this paper, the projection of parametric surfaces onto disk and spherical harmonics bases is investigated, and three novel computationally efficient algorith ...

SKIPTRAIN is a novel Decentralized Learning (DL) algorithm, which minimizes energy consumption in decentralized learning by strategically skipping some training rounds and substituting them with synchronization rounds. These trainingsilent periods, besides ...

The aim of this work is to develop a fast algorithm for approximating the matrix function f(A) of a square matrix A that is symmetric and has hierarchically semiseparable (HSS) structure. Appearing in a wide variety of applications, often in the context of ...

This work presents a graph neural network (GNN) framework for solving the maximum independent set (MIS) problem, inspired by dynamic programming (DP). Specifically, given a graph, we propose a DP-like recursive algorithm based on GNNs that firstly construc ...

This paper presents a distributed shadow dynamic consensus (DSDC) framework to address the generation company (GENCO) strategic bidding problem in the independent system operator (ISO) operation. First, each sub-group is defined according to the communicat ...

We propose Grab-UCB, a graph-kernelmulti-arms bandit algorithm to learn online the optimal source placement in large scale networks, such that the reward obtained from a priori unknown network processes is maximized. The uncertainty calls for online learni ...

The goal of this thesis is the development and the analysis of numerical methods for problems where the unknown is a curve on a smooth manifold. In particular, the thesis is structured around the three following problems: homotopy continuation, curve inter ...

In this article, we consider decentralized optimization problems where agents have individual cost functions to minimize subject to subspace constraints that require the minimizers across the network to lie in low-dimensional subspaces. This constrained fo ...

In this work, we develop timing-driven CAD support for FPGA architectures with direct connections between LUTs. We do so by proposing an efficient ILP-based detailed placer, which moves a carefully selected subset of LUTs from their original positions, so ...

The Learning Parity with Noise (LPN) problem is a famous cryptographic problem consisting in recovering a secret from noised samples. This problem is usually solved via reduction techniques, that is, one reduces the original instance to a smaller one befor ...

The success of deep learning may be attributed in large part to remarkable growth in the size and complexity of deep neural networks. However, present learning systems raise significant efficiency concerns and privacy: (1) currently, training systems are l ...

Semi-Lagrangian (SL) schemes are of utmost relevance to simulate two-phase flows where advection dominates. The combination of SL schemes with the finite element (FE) method and arbitrary Lagrangian-Eulerian (ALE) dynamic meshes yields a strong ingredient ...

We present a general framework to find ε-equilibrium solutions of oligopolistic markets in which demand is modeled at the disaggregate level using discrete choice models. Consumer choices are modeled according to random utility theory, and the choice proba ...

While the basic greedy algorithm gives a semi-streaming algorithm with an approximation guarantee of 2 for the unweighted matching problem, it was only recently that Paz and Schwartzman obtained an analogous result for weighted instances. Their approach is ...

A CUR approximation of a matrix A is a particular type of low-rank approximation A approximate to CUR, where C and R consist of columns and rows of A, respectively. One way to obtain such an approximation is to apply column subset selection to A and A(T). ...

The target assignment methods applied to robotic fiber positioners are only applicable to homogeneous sets of targets to be observed. However, different batches of robotic fiber positioners available at the focal plane of a telescope can be simultaneously ...

Basis adaptation in Homogeneous Chaos spaces rely on a suitable rotation of the underlying Gaussian germ. Several rotations have been proposed in the literature resulting in adaptations with different convergence properties. In this paper we present a new ...

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates

Chat with Graph Search

The Cost of Consistency: Submodular Maximization with Constant Recourse

Near-optimal hierarchical matrix approximation from matrix-vector products

Graph sparsification, sketching and adaptivity

On the conjugate symmetry and sparsity of the harmonic decomposition of parametric surfaces with the randomised Kaczmarz method

Energy-Aware Decentralized Learning with Intermittent Model Training

COMPUTING FUNCTIONS OF SYMMETRIC HIERARCHICALLY SEMISEPARABLE MATRICES

Maximum Independent Set: Self-Training through Dynamic Programming

Distributed Shadow Dynamic Consensus Optimization Framework for Power Market with Parameterization Bidding Strategy of GENCOs

Online Network Source Optimization with Graph-Kernel MAB

Retraction-based numerical methods for continuation, interpolation and time integration on manifolds

Quantization for Decentralized Learning Under Subspace Constraints

Detailed Placement for Dedicated LUT-Level FPGA Interconnect

Solving the Learning Parity with Noise Problem Using Quantum Algorithms

Algorithms for Efficient and Robust Distributed Deep Learning

One- and two-step semi-Lagrangian integrators for arbitrary Lagrangian-Eulerian-finite element two-phase flow simulations

A disaggregate choice-based approach to find ε-equilibria of oligopolistic markets

Semi-streaming Algorithms for Submodular Matroid Intersection

Low-Rank Approximation In The Frobenius Norm By Column And Row Subset Selection

Heterogeneous Target Assignment to Robotic Fiber Positioner Systems

Compressive sensing adaptation for polynomial chaos expansions