Communication is a key bottleneck in distributed training. Recently, an \emph{error-compensated} compression technology was particularly designed for the \emph{centralized} learning and receives huge successes, by showing significant advantages over state-of-the-art compression based methods in saving the communication…
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,742 papers · 148 categories
Trend · papers per month
48 results for “compression-based algorithm”
One of the biggest issues in deep learning theory is the generalization ability of networks with huge model size. The classical learning theory suggests that overparameterized models cause overfitting. However, practically used large deep models avoid overfitting, which is not well explained by the classical approaches…
A fast compression-based similarity measure with applications to content-based image retrievalstat.ML
Compression-based similarity measures are effectively employed in applications on diverse data types with a basically parameter-free approach. Nevertheless, there are problems in applying these techniques to medium-to-large datasets which have been seldom addressed. This paper proposes a similarity measure based on com…
Introduces BWMD, a new distance measure for DNA and malware clustering.
problem Shortcomings of previous compression-based distance metrics.
method Embeds sequences into a fixed-length feature vector.
result Significantly improved clustering performance on larger malware corpora.
Tensor decompositions are powerful tools for large data analytics as they jointly model multiple aspects of data into one framework and enable the discovery of the latent structures and higher-order correlations within the data. One of the most widely studied and used decompositions, especially in data mining and machi…
New method learns robustly with less data, bridging theory and practice.
problem Adversarial robust learning with metric perturbation.
method Tolerant adversarial PAC-learning with perturb-and-smooth approach and compression-based algorithm.
result First PAC-type guarantees for popular adversarial learning techniques.
We consider lossless compression based on statistical data modeling followed by prediction-based encoding, where an accurate statistical model for the input data leads to substantial improvements in compression. We propose DZip, a general-purpose compressor for sequential data that exploits the well-known modeling capa…
Studies on generalization performance of machine learning algorithms under the scope of information theory suggest that compressed representations can guarantee good generalization, inspiring many compression-based regularization methods. In this paper, we introduce REVE, a new regularization scheme. Noting that compre…
Compressing neural nets is an active research problem, given the large size of state-of-the-art nets for tasks such as object recognition, and the computational limits imposed by mobile devices. We give a general formulation of model compression as constrained optimization. This includes many types of compression: quan…
This paper proposes to perform authorship analysis using the Fast Compression Distance (FCD), a similarity measure based on compression with dictionaries directly extracted from the written texts. The FCD computes a similarity between two documents through an effective binary search on the intersection set between the …
Determining Principal Component Cardinality through the Principle of Minimum Description Lengthcs.LG
PCA (Principal Component Analysis) and its variants areubiquitous techniques for matrix dimension reduction and reduced-dimensionlatent-factor extraction. One significant challenge in using PCA, is thechoice of the number of principal components. The information-theoreticMDL (Minimum Description Length) principle gives…
Flexible framework compresses models using LC algorithm.
problem Efficiently compressing neural networks for resource constraints.
method Decouples learning and compression steps with alternating L and C phases.
result Compressed models maintain performance and accuracy.
Universal consistency and rates of convergence of multiclass prototype algorithms in metric spacescs.LG
Prototype rules simplify multiclass classification in metric spaces, achieving consistency and reduced complexity.
problem Multiclass classification in metric spaces, focusing on universal consistency and convergence rates.
method Novel Proto-NN and hybrid rules for multiclass classification in metric spaces, analyzing convergence rates.
result Proto-NN is universally consistent and simpler to implement, with similar computational advantages.
This paper investigates, from information theoretic grounds, a learning problem based on the principle that any regularity in a given dataset can be exploited to extract compact features from data, i.e., using fewer bits than needed to fully describe the data itself, in order to build meaningful representations of a re…
OptiNet achieves near-minimax error rates with compression in Euclidean space.
problem Error and compression rates in non-parametric multiclass classification.
method Compression-based learning rule OptiNet and a novel general compression scheme.
result OptiNet achieves non-trivial compression rates with near-minimax error rates in Euclidean space.
We develop a secure aggregation protocol for federated learning that reduces communication and computation costs.
problem Expensive communication and privacy concerns in federated learning.
method Adapting compression-based federated techniques to additive secret sharing.
result Our protocol achieves high accuracy with low communication costs and is more efficient than prior work.
In this paper, we present NESTA, a specialized Neural engine that significantly accelerates the computation of convolution layers in a deep convolutional neural network, while reducing the computational energy. NESTA reformats Convolutions into batches and uses a hierarchy of Hamming Weight Compressors to …
Compression techniques for deep neural network models are becoming very important for the efficient execution of high-performance deep learning systems on edge-computing devices. The concept of model compression is also important for analyzing the generalization error of deep learning, known as the compression-based er…
New techniques improve distributed training with compressed gradients.
problem Gradient mismatch problem in local error feedback.
method Step-ahead error feedback and error averaging techniques.
result Our methods handle gradient mismatch and train faster than full-precision training.
Neural networks have been shown to be vulnerable against minor adversarial perturbations of their inputs, especially for high dimensional data under attacks. To combat this problem, techniques like adversarial training have been employed to obtain models which are robust on the training set. However, the …
New bounds for large language models using token properties.
problem Vacuous generalization bounds for large language models.
method Martingale properties and Monarch matrices.
result Non-vacuous generalization bounds for LLMs up to 70B parameters.
Advances understanding of neural network generalization via tensor analysis.
problem Understanding the generalizability of deep neural networks.
method Tensor analysis to measure compressibility and generalizability.
result Proposed generalization bound outperforms previous methods, especially for tensor-based networks.
BMRS offers a Bayesian approach to structured pruning of neural networks.
problem Overparameterized neural networks lead to high compute costs.
method Bayesian Model Reduction for Structured pruning (BMRS) based on two recent methods: Bayesian structured pruning with multiplicative noise and Bayesian model reduction.
result BMRS yields high compression rates and accuracy without tuning thresholds.
In this appraisal paper, we evaluate the efficacy of SHIELD, a compression-based defense framework for countering adversarial attacks on image classification models, which was published at KDD 2018. Here, we consider alternative threat models not studied in the original work, where we assume that an adaptive adversary …
HotNAS reduces AI search time from hundreds of GPU hours to less than 3 GPU hours.
problem High time required for AI solution generation from scratch.
method HotNAS starts from a 'hot' state using pre-trained models and integrates compression during co-search.
result Reduces search time from 200 GPU hours to less than 3 GPU hours.
Examines algorithmic modeling across three cultures.
problem Tackles algorithmic modeling in different cultural contexts.
method Uses parametric regressions, interpretable algorithms, and complex algorithms.
result Extension of Leo Breiman's thesis to include cultural differences.
Playing repeated matrix games (RMG) while maximizing the cumulative returns is a basic method to evaluate multi-agent learning (MAL) algorithms. Previous work has shown that , , or algorithms have good behaviours on average in RMG. Besides, hedging algorithms have been shown to be effective on predi…
Meta-algorithm selection aims to choose the best algorithm selector for a given problem instance.
problem Selecting the best algorithm selector for a specific problem instance.
method Apply algorithm selection to the selection of other algorithms (meta-algorithm selection).
result Meta-algorithm selection can be beneficial in some cases but faces challenges in solving the meta-level problem.
Proposes CLRS benchmark to evaluate algorithmic reasoning.
problem Difficulty in transferring results across publications due to targeted algorithmic data.
method Develops a comprehensive benchmark covering various algorithmic tasks.
result Demonstrates performance of algorithmic reasoning baselines on the CLRS benchmark.
Combines multiple bandit algorithms to create a nearly optimal single algorithm.
problem Designing a single bandit algorithm that performs nearly as well as the best individual algorithm in a stochastic environment.
method Develops two general corralling algorithms that achieve favorable regret guarantees.
result The regret of the corralling algorithms is no worse than the best individual algorithm's performance.
Accelerated Randomized Coordinate Descent Algorithms for Stochastic Optimization and Online Learningcs.LG
We propose accelerated randomized coordinate descent algorithms for stochastic optimization and online learning. Our algorithms have significantly less per-iteration complexity than the known accelerated gradient algorithms. The proposed algorithms for online learning have better regret performance than the known rando…
The exchange algorithm is studied for its convergence and asymptotic variance.
problem Theoretical limitations of the exchange algorithm in sampling from doubly-intractable distributions.
method Theoretical analysis of the exchange algorithm's convergence speed and asymptotic variance.
result The exchange algorithm converges at a geometric rate and satisfies a Central Limit Theorem.
Bayesian networks (BN) are used in a big range of applications but they have one issue concerning parameter learning. In real application, training data are always incomplete or some nodes are hidden. To deal with this problem many learning parameter algorithms are suggested foreground EM, Gibbs sampling and RBE algori…
No algorithm outperforms uniform sampling in A/B testing.
problem Identifying the best arm in A/B testing with fixed budget.
method Introducing consistent and stable algorithms, deriving lower bounds, and proving optimality of uniform sampling.
result No algorithm performs better than uniform sampling in A/B testing.
Improves algorithm selection for thousands of candidates using dyadic features.
problem Selecting the best algorithm from a large set of candidates for specific problems.
method Proposes extreme algorithm selection (XAS) with dyadic feature representation.
result Improves significantly over current state of the art in various metrics.
This review article surveys data augmentation MCMC algorithms.
problem Sampling from intractable probability distributions.
method Comprehensive study of DA MCMC algorithms, their convergence properties, and acceleration strategies.
result Synthesizes recent developments and provides insights for researchers.
The Bayesian Learning Rulestat.ML
Bayesian learning rule unifies and generalizes various machine learning algorithms.
problem Machine learning algorithms are diverse and not always understood.
method Bayesian principles and natural gradients are used to derive algorithms.
result Derives a wide range of algorithms including classical and modern ones.
Learning to Optimizecs.LG
Algorithm design is a laborious process and often requires many iterations of ideation and validation. In this paper, we explore automating algorithm design and present a method to learn an optimization algorithm, which we believe to be the first method that can automatically discover a better algorithm. We approach th…
This review summarizes five Lasso optimization algorithms.
problem Optimizing the Lasso objective function.
method Five representative algorithms: ISTA, FISTA, CGDA, SLA, PFA.
result Comparison of convergence rates and strengths/weaknesses.
Neural networks mimic algorithms to solve complex problems.
problem Current machine learning methods struggle with generalisation and efficiency.
method Representing algorithms in a continuous space and adapting them to real-world problems.
result Neural networks can execute classical algorithms more efficiently.
Paper proposes a reinforcement learning framework for efficient hyper-parameter tuning of stochastic optimization algorithms.
problem Efficient tuning of hyper-parameters for stochastic optimization algorithms.
method Modeling hyper-parameter tuning as a Markov decision process and using policy gradient algorithms.
result The proposed framework significantly reduces the time required for hyper-parameter tuning compared to Bayesian optimization.
In this paper, we propose a convergent parallel best-response algorithm with the exact line search for the nondifferentiable nonconvex sparsity-regularized rank minimization problem. On the one hand, it exhibits a faster convergence than subgradient algorithms and block coordinate descent algorithms. On the other hand,…
Approximate probabilistic inference algorithms are central to many fields. Examples include sequential Monte Carlo inference in robotics, variational inference in machine learning, and Markov chain Monte Carlo inference in statistics. A key problem faced by practitioners is measuring the accuracy of an approximate infe…
New algorithms reduce bilevel optimization complexity to ε^(-1.5).
problem Efficiently solving bilevel optimization problems in machine learning.
method Proposed two new algorithms: one using momentum-based recursive iterations, the other using recursive gradient estimations.
result Achieved computational complexity of ε^(-1.5), significantly faster than previous methods.
The inverse-free extreme learning machine (ELM) algorithm proposed in [4] was based on an inverse-free algorithm to compute the regularized pseudo-inverse, which was deduced from an inverse-free recursive algorithm to update the inverse of a Hermitian matrix. Before that recursive algorithm was applied in [4], its impr…
Researchers analyze how algorithmic and implementation choices affect RL performance.
problem Difficulty in separating algorithmic and implementation differences in RL performance.
method Unified derivations through a single control-as-inference objective, categorizing algorithms as EM or KL minimization.
result Implementation details are co-adapted with algorithmic choices, some transferable across algorithms.
Study on selecting between base algorithms in stochastic bandit problems.
problem Model selection in stochastic environments with contextual information.
method Developed a meta-algorithm-base algorithm abstraction with a smoothing transformation for optimal guarantees.
result Optimal model selection guarantees for stochastic contextual bandit problems.
New bounds derived for KG algorithm's performance in finite time.
problem Best arm identification problem in multi-armed bandit.
method Theoretical analysis of finite-time performance, deriving bounds for sample allocation, error probability, and regret.
result Upper and lower bounds for the probability of error and simple regret of the KG algorithm.