Coefficient complexity in low-access quantized linear computations

V Ramkumar, N Raviv, I Tamo - 2023 59th Annual Allerton …, 2023 - ieeexplore.ieee.org
2023 59th Annual Allerton Conference on Communication, Control …, 2023ieeexplore.ieee.org
Quantizing linear computations over the reals is a common practice in many distributed
systems, with applications in efficient, private, or robust machine learning algorithms. Recent
work studied the access parameter of such computations, ie, the maximum number of data
entries required to accommodate any given computation. It was shown that lower access
can be achieved with higher redundancy and vice versa, and a corresponding scheme
based on covering codes was given. Surprisingly, the resulting scheme is universal to all …
Quantizing linear computations over the reals is a common practice in many distributed systems, with applications in efficient, private, or robust machine learning algorithms. Recent work studied the access parameter of such computations, i.e., the maximum number of data entries required to accommodate any given computation. It was shown that lower access can be achieved with higher redundancy and vice versa, and a corresponding scheme based on covering codes was given. Surprisingly, the resulting scheme is universal to all possible two-valued quantizations, meaning that the same storage protocol can be used to retrieve any linear combination with two distinct coefficients—regardless of what those coefficients are—with the same access parameter. In this paper we extend this universal protocol to all possible quantizations with any number of values; while the storage parameter remains identical, the access parameter increases according to a new additive-combinatorics property we call coefficient complexity. We then turn to study the coefficient complexity—we characterize the complexity of small sets of coefficients, provide bounds, and identify coefficient sets having the highest and lowest complexity. Interestingly, arithmetic progressions have the lowest possible complexity, and some geometric progressions have the highest possible complexity, the former being particularly attractive for its common use in uniform quantization.
ieeexplore.ieee.org
以上显示的是最相近的搜索结果。 查看全部搜索结果