Federated Averaging (FedAvg) and its variants are the most popular optimization algorithms in federated learning (FL). Previous convergence analyses of FedAvg either assume full client participation or partial client participation where the clients can be uniformly sampled. However, in practical cross-device FL systems, only a subset of clients that satisfy local criteria such as battery status, network connectivity, and maximum participation frequency requirements (to ensure privacy) are available for training at a given time. As a result, client availability follows a natural cyclic pattern. We provide (to our knowledge) the first theoretical framework to analyze the convergence of FedAvg with cyclic client participation with several different client optimizers such as GD, SGD, and shuffled SGD. Our analysis discovers that cyclic client participation can achieve a faster asymptotic convergence rate than vanilla FedAvg with uniform client participation under suitable conditions, providing valuable insights into the design of client sampling protocols.
more »
« less
Efficient NUFFT backpropagation for stochastic sampling optimization
Optimization-based k-space sampling pattern design often involves the Jacobian matrix of non-uniform fast Fourier transform (NUFFT) operations. Previous works relying on auto-differentiation can be time-consuming and less accurate. This work proposes an approximation method using the relationship between exact non-uniform DFT (NDFT) and NUFFT, demonstrating improved results for the sampling pattern optimization problem.
more »
« less
- Award ID(s):
- 1838179
- NSF-PAR ID:
- 10309645
- Date Published:
- Journal Name:
- Proceeedings International Society of Magnetic Resonance in Medicine
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)With the widely deployment of powerful deep neural network (DNN) into smart, but resource limited IoT devices, many prior works have been proposed to compress DNN in a hardware-aware manner to reduce the computing complexity, while maintaining accuracy, such as weight quantization, pruning, convolution decomposition, etc. However, in typical DNN compression methods, a smaller, but fixed, network structure is generated from a relative large background model for resource limited hardware accelerator deployment. However, such optimization lacks the ability to tune its structure on-the-fly to best fit for a dynamic computing hardware resource allocation and workloads. In this paper, we mainly review two of our prior works [1], [2] to address this issue, discussing how to construct a dynamic DNN structure through either uniform or non-uniform channel selection based sub-network sampling. The constructed dynamic DNN could tune its computing path to involve different number of channels, thus providing the ability to trade-off between speed, power and accuracy on-the-fly after model deployment. Correspondingly, an emerging Spin-Orbit Torque Magnetic Random-Access-Memory (SOT-MRAM) based Processing-In-Memory (PIM) accelerator will also be discussed for such dynamic neural network structure.more » « less
-
null (Ed.)Matrix completion, the problem of completing missing entries in a data matrix with low-dimensional structure (such as rank), has seen many fruitful approaches and analyses. Tensor completion is the tensor analog that attempts to impute missing tensor entries from similar low-rank type assumptions. In this paper, we study the tensor completion problem when the sampling pattern is deterministic and possibly non-uniform. We first propose an efficient weighted Higher Order Singular Value Decomposition (HOSVD) algorithm for the recovery of the underlying low-rank tensor from noisy observations and then derive the error bounds under a properly weighted metric. Additionally, the efficiency and accuracy of our algorithm are both tested using synthetic and real datasets in numerical simulations.more » « less
-
In this work, we present a 3D single-particle tracking system that can apply tailored sampling patterns to selectively extract photons that yield the most information for particle localization. We demonstrate that off-center sampling at locations predicted by Fisher information utilizes photons most efficiently. When performing localization in a single dimension, optimized off-center sampling patterns gave doubled precision compared to uniform sampling. A ~20% increase in precision compared to uniform sampling can be achieved when a similar off-center pattern is used in 3D localization. Here, we systematically investigated the photon efficiency of different emission patterns in a diffraction-limited system and achieved higher precision than uniform sampling. The ability to maximize information from the limited number of photons demonstrated here is critical for particle tracking applications in biological samples, where photons may be limited.more » « less
-
more » « less
Abstract Linking morphology and function is critical to understanding the evolution of organismal shape. Performance landscapes, or performance surfaces, associate empirical functional performance data with a morphospace to assess how shape variation relates to functional variation. Performance surfaces for multiple functions also can be combined to understand the functional trade‐offs that affect the morphology of a particular structure across species. However, morphological performance surfaces usually require empirical determination of performance for a number of theoretical shapes that are evenly distributed throughout the morphospace. This process is time‐consuming, and is problematic for structures that are difficult to precisely manipulate.
We sought to (a) understand the degree and pattern of sampling required to produce a reliable and nuanced performance surface and (b) investigate the possibility of building a surface using only naturally occurring morphologies. To do this, we subsampled a pre‐existing set of turtle shell performance surfaces in four different ways: first, uniform subsampling of theoretical morphologies across the surface; second, random subsampling of theoretical morphologies across the surface; third, a combination uniform/random subsampling method called close‐pairs sampling and fourth, subsampling only points on the surface known to correspond to a naturally occurring turtle shell morphology. Each subset was interpolated with ordinary Kriging to produce a new performance surface for comparison to the original.
We found that using a fraction of the theoretical morphologies examined in the original study (half as many or fewer) was sufficient to produce a performance surface bearing close resemblance to the original (Pearson correlation ≥0.90); close‐pairs sampling dramatically increased the power of small sample sizes. We also discovered that only sampling points on the surface corresponding to naturally occurring morphologies produced an accurate surface, but results were better when individual specimens, rather than species averages, were used.
Our findings demonstrate the viability of using performance surfaces to understand the evolution of complex morphologies for which theoretical shape modelling is difficult or computationally burdensome. Both lower levels of carefully configured sampling throughout the theoretical morphospace, and development of performance surfaces using only data from naturally occurring morphologies, are acceptable alternatives to the dense theoretical shape sampling employed in previous studies.
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
