Implementing large-scale deep neural networks with high computational complexity on low-cost IoT devices may inevitably be constrained by limited computation resource, making the devices hard to respond in real-time. This disjunction makes the state-of-art deep learning algorithms, i.e. CNN (Convolutional Neural Networ…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,657 papers · 148 categories
Trend · papers per month
48 results for “bit complexity”
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.
WrapNet optimizes inference for low-resolution neural networks by using 8-bit additions.
problem Reducing multiplication complexity in low-resolution neural networks.
method Adapting neural networks to use low-resolution (8-bit) additions in accumulators, with a cyclic activation layer and overflow penalty regularizer.
result Achieves comparable classification accuracy to 32-bit counterparts using low-resolution additions.
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.
The goal of standard 1-bit compressive sensing is to accurately recover an unknown sparse vector from binary-valued measurements, each indicating the sign of a linear function of the vector. Motivated by recent advances in compressive sensing with generative models, where a generative modeling assumption replaces the u…
Paper proposes a 1-bit mean estimation method with near-optimal sample complexity.
problem Distributed mean estimation with 1-bit communication constraints.
method Randomized and sequentially-chosen interval queries to estimate mean.
result Sample complexity bound matches minimax lower bound with logarithmic factors.
We study an extreme scenario in multi-label learning where each training instance is endowed with a single one-bit label out of multiple labels. We formulate this problem as a non-trivial special case of one-bit rank-one matrix sensing and develop an efficient non-convex algorithm based on alternating power iteration. …
The FloatSD technology has been shown to have excellent performance on low-complexity convolutional neural networks (CNNs) training and inference. In this paper, we applied FloatSD to recurrent neural networks (RNNs), specifically long short-term memory (LSTM). In addition to FloatSD weight representation, we quantized…
This paper develops novel deep learning-based architectures and design methodologies for an orthogonal frequency division multiplexing (OFDM) receiver under the constraint of one-bit complex quantization. Single bit quantization greatly reduces complexity and power consumption, but makes accurate channel estimation and…
Parameterized mathematical models play a central role in understanding and design of complex information systems. However, they often cannot take into account the intricate interactions innate to such systems. On the contrary, purely data-driven approaches do not need explicit mathematical models for data generation an…
Optimal ReLU networks can memorize any separable set of points with a small number of parameters.
problem The optimal number of parameters required to memorize a set of points using ReLU networks.
method Construction of ReLU networks with specific bit complexity to memorize points satisfying a mild separability assumption.
result Optimal ReLU networks can memorize any separable set of points with a number of parameters that is .
Occam's Ghoststat.ML
The article applies Occam's Razor to non-parametric model building, minimizing the number of bits for data encoding.
problem Overlooking the role of model parameters in data encoding leads to inefficient probability density estimators.
method Extends bit counting to model parameters, providing a true measure of complexity for parametric models.
result Minimizing total bit requirement leads to smoother, more efficient probability density estimates and fewer relevant parameters.
Parameterized mathematical models play a central role in understanding and design of complex information systems. However, they often cannot take into account the intricate interactions innate to such systems. On the contrary, purely data-driven approaches do not need explicit mathematical models for data generation an…
New techniques improve 16-bit training accuracy without 32-bit units.
problem Training deep learning models with only 16-bit floating-point units.
method Studied BFloat16 units and applied stochastic rounding and Kahan summation techniques.
result Up to 7% absolute validation accuracy gain in 16-bit-FPU training.
Bayesian Bits unifies quantization and pruning through gradient optimization.
problem Joint mixed precision quantization and pruning for efficient neural networks.
method Gradient-based optimization with a novel bit width decomposition and learnable stochastic gates.
result Bayesian Bits achieves better accuracy vs. efficiency trade-off compared to static bit width networks.
New constraints on space and adaptivity in bandits force more batches and memory use.
problem Simultaneous space and adaptivity constraints in stochastic bandits.
method Proved lower bounds and constructed an algorithm with near-minimax regret.
result Near-minimax regret requires more batches and memory than previously thought.
New algorithm learns halfspaces with noise using Forster decomposition.
problem Learning halfspaces in noisy data.
method Forster decomposition and efficient mixture of distributions.
result First polynomial-time algorithm with strongly polynomial sample complexity.
Low-bit training framework reduces energy consumption in CNNs.
problem Reducing energy consumption in convolutional neural networks.
method Low-bit training framework using MLS tensor format with dynamic quantization.
result Achieves superior trade-off between accuracy and bit-width.
DQA efficiently quantizes deep neural network activations for resource-constrained devices.
problem Efficiently quantizing deep neural network activations for resource-constrained devices.
method DQA uses simple shifting-based operations and Huffman coding for sub-6-bit quantization.
result DQA achieves significantly better accuracy than direct quantization and state-of-the-art methods.
BITS for GAPS: Bayesian Information-Theoretic Sampling for hierarchical GAussian Process Surrogatesstat.ML
BITS for GAPS uses Bayesian methods to improve surrogate model accuracy in complex systems.
problem Improving surrogate model accuracy in complex physical systems with uncertainty.
method Bayesian Information-Theoretic Sampling for hierarchical Gaussian Process Surrogates.
result Increased expected information gain and predictive accuracy by targeting high-uncertainty regions.
Paper improves DNN accelerator robustness against bit errors with energy savings.
problem Bit errors in quantized DNN weights reduce energy efficiency.
method Combines robust fixed-point quantization, weight clipping, and random bit error training.
result Significantly improves robustness against random bit errors with high energy savings.
Bit-Swap: Recursive Bits-Back Coding for Lossless Compression with Hierarchical Latent Variablescs.LG
The bits-back argument suggests that latent variable models can be turned into lossless compression schemes. Translating the bits-back argument into efficient and practical lossless compression schemes for general latent variable models, however, is still an open problem. Bits-Back with Asymmetric Numeral Systems (BB-A…
The high computational complexity associated with training deep neural networks limits online and real-time training on edge devices. This paper proposed an end-to-end training and inference scheme that eliminates multiplications by approximate operations in the log-domain which has the potential to significantly reduc…
Paper tackles 1-bit compressed sensing, presenting efficient algorithm for sparse signal estimation.
problem Estimating sparse signals from binary measurements.
method Non-convex sparsity-constrained program with one-shot hard thresholding.
result Simple algorithm produces accurate signal approximation with high probability.
NeuroAttack: Undermining Spiking Neural Networks Security through Externally Triggered Bit-Flipscs.CR
Paper proposes NeuroAttack to undermine SNNs security through bit-flips.
problem Security and reliability issues in SNNs.
method Cross-layer attack exploiting low-level reliability issues via adversarial input noise.
result Serious integrity threat to SNNs and DNNs.
New memory-query tradeoffs for convex optimization algorithms.
problem Optimizing memory usage for convex optimization algorithms.
method Analyzing randomized first-order algorithms for minimizing convex functions.
result Cutting plane methods are optimal in terms of memory and query complexity.
The state-of-the-art hardware platforms for training Deep Neural Networks (DNNs) are moving from traditional single precision (32-bit) computations towards 16 bits of precision -- in large part due to the high energy efficiency and smaller bit storage associated with using reduced-precision representations. However, un…
Paper proposes a learning-based sparse Bayesian method for accurate off-grid DOA estimation.
problem One-bit off-grid direction of arrival (DOA) estimation in a single snapshot scenario.
method Formulated off-grid DOA estimation model, used Sparse Bayesian framework, proposed Learning-based Sparse Bayesian approach.
result Improved computational efficiency and accuracy in off-grid DOA estimation.
Majority bit estimation in noisy random recursive DAGs.
problem Estimating the majority bit in a noisy random recursive DAG.
method Majority rule among nodes, with bit flipping and noisy channel.
result Identification of the threshold for at which majority rule yields errors.
Paper proposes a CNN-based method for estimating intra frame bits and quality.
problem Efficient video delivery and bit allocation in video coding.
method Deep learning approach using CNNs trained on original frames and encoded distortions.
result Accurate estimation of intra frame bits and quality for better bit allocation.
Emerging resistive random-access memory (ReRAM) has recently been intensively investigated to accelerate the processing of deep neural networks (DNNs). Due to the in-situ computation capability, analog ReRAM crossbars yield significant throughput improvement and energy reduction compared to traditional digital methods.…
Improves matrix multiplication throughput for asymmetric bit-width operands.
problem Matrix multiplications between asymmetric bit-width operands, especially 8- and 4-bit, are not efficiently handled by existing SIMD instructions.
method Proposes a new SIMD matrix multiplication instruction that uses mixed precision on inputs (8- and 4-bit) and accumulates into 16-bit output, improving throughput.
result Offers 2x improvement in throughput compared to existing symmetric-operand-size instructions, with negligible overflow.
It is becoming increasingly important to understand the vulnerability of machine learning models to adversarial attacks. In this paper we study the feasibility of robust learning from the perspective of computational learning theory, considering both sample and computational complexity. In particular, our definition of…
New protocols show 1-bit mean estimation can be order-optimal without interaction.
problem Can 1-bit mean estimation be optimal without interaction?
method Adaptive and non-adaptive threshold and interval queries, with one adaptive transition.
result Arbitrary non-adaptive quantizers can match the adaptive rate, suggesting interaction is not necessary.
Quantized Neural Networks (QNNs) are often used to improve network efficiency during the inference phase, i.e. after the network has been trained. Extensive research in the field suggests many different quantization schemes. Still, the number of bits required, as well as the best quantization scheme, are yet unknown. O…
Topological data analysis classifies encrypted bits with success.
problem Classifying encrypted data with traditional machine learning methods.
method Persistent homology for generating topological features, machine learning pipeline.
result Successfully classifies encrypted data, outperforming classical models.
We consider the problem of estimating the mean of a symmetric log-concave distribution under the constraint that only a single bit per sample from this distribution is available to the estimator. We study the mean squared error as a function of the sample size (and hence the number of bits). We consider three settings:…
Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priorscs.LG
Paper offers robust recovery for 1-bit sensing with partial Gaussian circulant matrices.
problem Accurately recovering vectors from 1-bit measurements using structured matrices.
method Correlation-based optimization with randomly signed partial Gaussian circulant matrices and generative models.
result Recovery guarantees match those for i.i.d. Gaussian matrices but with faster computation.
Study on recovering sparse linear classifiers from mixed binary responses.
problem Learning a mixture of sparse linear classifiers from binary responses.
method Query-based approach to identify all sparse vectors from a set.
result Upper bounds on the number of queries required for recovery.
One-bit feedback suffices for a bandit problem's optimal strategy.
problem Optimal strategy for multi-armed bandit problem with limited feedback.
method Coding and decoding schemes for one-bit feedback to mimic full-reward feedback.
result Regret ratio approaches 1 with one-bit feedback.
New algorithm tackles batched stochastic linear bandits with 1-bit communication constraints.
problem Stochastic linear bandits with 1-bit communication constraints.
method Phased-elimination algorithms based on G-optimal designs and 1-bit mean estimation.
result Achieves near-optimal regret bounds for broad scaling regimes.
ADD embeds a 48-bit message into images, achieving high accuracy and speed.
problem Embedding high-fidelity messages into images to detect authenticity and source.
method Two-stage process: linear combination and addition of watermark to image, followed by decoding.
result ADD achieves 100% decoding accuracy for 48-bit watermarking, with minimal performance drop under various distortions.
How many bits of information are required to PAC learn a class of hypotheses of VC dimension ? The mathematical setting we follow is that of Bassily et al. (2018), where the value of interest is the mutual information between the input sample and the hypothesis outputted by the learning algo…
This letter proposes a dictionary learning algorithm for blind one bit compressed sensing. In the blind one bit compressed sensing framework, the original signal to be reconstructed from one bit linear random measurements is sparse in an unknown domain. In this context, the multiplication of measurement matrix $\Ab$ an…
Directional oil well drilling requires high precision of the wellbore positioning inside the productive area. However, due to specifics of engineering design, sensors that explicitly determine the type of the drilled rock are located farther than 15m from the drilling bit. As a result, the target area runaways can be d…
Generalizes bits back coding for time-series models with latent Markov structures.
problem Efficiently compressing time-series data with latent Markov structures.
method Extends bits back coding to time-series models with latent Markov structures, including HMMs and LGSSMs.
result Effective for small scale models, promising for larger scale settings like video compression.
FleXOR trains fractional quantization for neural networks, improving accuracy and size.
problem Quantization limits to integer bits restricts compression and accuracy.
method Encryption algorithm with XOR gates for fractional bits during inference.
result FleXOR achieves high accuracy with fractional sub-1-bit weights.
Reduced precision computation for deep neural networks is one of the key areas addressing the widening compute gap driven by an exponential growth in model size. In recent years, deep learning training has largely migrated to 16-bit precision, with significant gains in performance and energy efficiency. However, attemp…