Memory constraints slow linear regression convergence.
problem Linear regression with limited memory.
method Analyzing memory and sample requirements for regression.
result Subquadratic memory algorithms converge slower than unrestricted methods.
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.
169,051 papers · 148 categories
Trend · papers per month
48 results for “memory/sample tradeoffs”
We perform the first study of the tradeoff space of access methods and replication to support statistical analytics using first-order methods executed in the main memory of a Non-Uniform Memory Access (NUMA) machine. Statistical analytics systems differ from conventional SQL-analytics in the amount and types of memory …
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.
A new method reduces memory usage for large models by three orders of magnitude.
problem Memory limitations in training large models.
method Extreme tensoring for adaptive preconditioning.
result Significant reduction in memory usage without performance degradation.
Study identifies three quantization regimes for ReLU networks.
problem Approximation of Lipschitz functions by ReLU networks with finite-precision weights.
method Established through nonasymptotic tight lower and upper bounds on minimax approximation error.
result Memory-optimality achieved in proper quantization regime for deep networks.
We show that a simple modification of the 1-nearest neighbor classifier yields a strongly Bayes consistent learner. Prior to this work, the only strongly Bayes consistent proximity-based method was the k-nearest neighbor classifier, for k growing appropriately with sample size. We will argue that a margin-regularized 1…
Sublinear memory sketch finds nearest neighbors in streaming data.
problem Finding nearest neighbors in large datasets with limited memory.
method Combines LSH, online kernel density estimation, and compressed sensing to achieve sublinear memory.
result Achieves sublinear memory performance on stable queries, reporting nearest neighbors efficiently.
The paper explores how word embeddings affect the stability of downstream NLP models.
problem Small changes in training data can cause significant changes in model predictions.
method Empirical and theoretical analysis of embedding instability, including the introduction of eigenspace instability measure.
result Increasing embedding memory can reduce the disagreement in predictions by 5% to 37%.
Gradient descent is efficient for solving feasibility problems with minimal memory and queries.
problem Finding a point in a given set using a memory-constrained algorithm with a separation oracle.
method Oracle complexity lower bounds for gradient descent and other algorithms.
result Gradient descent is Pareto-optimal in the oracle complexity/memory tradeoff for feasibility problems.
Despite their attractiveness, popular perception is that techniques for nonparametric function approximation do not scale to streaming data due to an intractable growth in the amount of storage they require. To solve this problem in a memory-affordable way, we propose an online technique based on functional stochastic …
Analyzes self-attention in recurrent networks, proving it mitigates vanishing gradients.
problem Vanishing gradients in recurrent networks when capturing long-term dependencies.
method Formal analysis of self-attention's effect on gradient propagation, proposing a relevancy screening mechanism.
result Self-attention mitigates vanishing gradients in recurrent networks, providing guarantees.
Researchers study fairness-accuracy tradeoffs in predictive models for multiple groups.
problem Understanding the tradeoff between fairness and accuracy in models serving multiple demographic groups.
method Characterizing the fairness-accuracy (FA) Pareto frontier, approximating it from limited data, and bounding the worst-case gap.
result Derivation of worst-case-optimal estimators and uniform finite-sample bounds for the entire FA frontier.
Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noisecs.LG
Study shows a tradeoff between sample complexity and computational efficiency for learning halfspaces with random noise.
problem PAC learning γ-margin halfspaces with Random Classification Noise.
method Established an information-computation tradeoff and provided a simple efficient algorithm with sample complexity O(1/(γ^2 ε^2)). Also, proved lower bounds for SQ algorithms and low-degree polynomial tests.
result Inherent gap between sample complexity and computational efficiency for learning halfspaces with random noise.
Structured linear substitutions improve both efficiency and accuracy in neural networks.
problem Improving neural network efficiency and accuracy tradeoff.
method Replacing linear components in pointwise convolutions with structured linear decompositions.
result Structured layers provide Pareto-optimal benefits in efficiency/accuracy.
In this paper, we exhibit the tradeoffs between the (training) sample, computation and storage complexity for the problem of supervised classification using signal subspace estimation. Our main tool is the use of tensor subspaces, i.e. subspaces with a Kronecker structure, for embedding the data into lower dimensions. …
This work analyzes and optimizes memory and compute costs of learned optimizers.
problem High memory and compute costs of learned optimizers.
method Identified and quantified design features of learned and hand-designed optimizers, constructed a more efficient learned optimizer.
result A learned optimizer that is faster and more memory efficient than previous work.
Optimizes sample and round complexity in adaptive sampling from multiple distributions.
problem Adaptive sampling from multiple distributions with limited rounds and samples.
method Introduces OODS framework and analyzes tradeoffs between sample and round complexity.
result Achieves near-optimal sample complexity and sub-polynomial round complexity.
Study shows how to balance memory and learning efficiency in continual learning.
problem Balancing memory and learning efficiency in continual learning.
method Structural regularization with Hessian-based regularization.
result Structural regularization improves statistical performance at the cost of increased memory complexity.
The study reduces neural network training memory by up to 60.7x on CIFAR-10.
problem Reducing memory requirements for neural network training.
method Profiled memory usage, evaluated four techniques: sparsity, low precision, microbatching, gradient checkpointing.
result Appropriate combinations of techniques can reduce memory usage up to 60.7x on CIFAR-10.
This work explores feature learning tradeoffs in neural networks.
problem Resource tradeoffs in neural feature learning.
method Theoretical and experimental investigation of offline sparse parity learning.
result Width improves sample efficiency in sparse feature learning.
CDC-FM improves generative model quality-generalization tradeoff by regularizing with geometry-aware noise.
problem Tradeoff between high sample quality and memorization in deep generative models.
method Introduces Carré du champ flow matching (CDC-FM) that replaces homogeneous noise with anisotropic Gaussian noise capturing latent data manifold geometry.
result CDC-FM consistently offers better quality-generalization tradeoff across diverse datasets and architectures.
GPG improves RL from feedback with less memory and compute.
problem Improving reinforcement learning from human feedback.
method Group-based Monte Carlo advantage estimator replacing learned value function.
result GPG matches or outperforms PPO on standard benchmarks.
Belief Propagation outperforms other algorithms in reconstructing binary symmetric channel trees.
problem Reconstructing binary symmetric channel trees with bounded memory.
method Combining recursive reconstruction, information theory, and optimal transport.
result Any recursive algorithm with bounded memory for the reconstruction problem on binary symmetric channel trees has a phase transition strictly below the Belief Propagation threshold.
KSD Thinning uses KSD to thin MCMC samples efficiently.
problem Efficiently representing posterior distributions in Bayesian inference.
method KSD Thinning: retains only samples exceeding a KSD threshold.
result Established convergence and complexity tradeoffs for KSD Thinning.
More data can actually hurt linear regression performance in certain conditions.
problem The test risk of linear regression estimators increases with additional samples in overparameterized settings.
method An analysis of linear regression with isotropic Gaussian covariates using gradient descent.
result The bias decreases with more samples, but variance increases, leading to a surprising increase in test risk.
Efficient sampling reduces memory usage for Minimax distance analysis.
problem Quadratic memory requirement for existing Minimax distance methods.
method Proposes a novel sampling technique with linear space complexity.
result Demonstrates significant reduction in memory usage for Minimax distances.
New model captures long-range patterns in sequences efficiently.
problem Efficiently capturing long-range patterns in sequential data.
method Inspired by wavelet multiresolution analysis, introduces MultiresLayer with multiresolution convolution.
result State-of-the-art performance on sequence classification and autoregressive density estimation tasks.
This paper balances bias and variance in adaptive importance sampling using mirror descent.
problem Large variance in adaptive importance sampling weights.
method Regularization strategy with power raised importance weights connected to mirror descent.
result The regularization parameter balances bias and variance.
Paper solves NGCA for discrete distributions using LLL method.
problem Learning hidden non-Gaussian components in discrete distributions.
method Utilizes LLL lattice basis reduction method.
result Sample and computationally efficient algorithm for NGCA in discrete distributions.
Efficiently preserves old class knowledge in memory-limited settings.
problem Catastrophic forgetting in class-incremental learning.
method Memory-efficient exemplar preserving scheme and domain-compatible feature extractors.
result Low-fidelity exemplar samples can replace high-fidelity ones with less memory cost.
This paper presents a bias-variance tradeoff of graph Laplacian regularizer, which is widely used in graph signal processing and semi-supervised learning tasks. The scaling law of the optimal regularization parameter is specified in terms of the spectral graph properties and a novel signal-to-noise ratio parameter, whi…
Paper speeds up boosting algorithms with less memory.
problem Boosting algorithms require large memory for training, limiting scalability.
method Combines early stopping, effective sample size, and stratified sampling.
result Achieves 10-100 speedup over XGBoost with limited memory.
Algorithm balances online and offline data for linear bandits.
problem Online learning with an offline dataset in linear bandits.
method Proposes a linear bandit algorithm that uses offline data early and increasingly favors exploration as the horizon grows.
result Establishes regret bounds showing competitive performance with both purely online and offline solutions.
Efficiently tests discrete distributions with limited memory and communication.
problem Testing discrete distributions with constraints on memory and communication.
method Developed efficient algorithms for uniformity/identity and closeness testing in streaming and distributed models.
result Nearly-tight lower bounds on sample complexity and communication cost for uniformity testing.
New algorithms improve privacy in statistical estimation by making them robust.
problem Improving privacy in statistical estimation methods.
method Black-box reduction from privacy to robustness, using Sum-of-Squares method.
result Design of polynomial-time private estimators with optimal tradeoffs among sample complexity, accuracy, and privacy.
The paper studies how to improve language model inference using particle filtering.
problem Understanding the accuracy-cost tradeoffs of inference-time methods for large language models.
method Introduces particle filtering algorithms like Sequential Monte Carlo (SMC) to study language model inference.
result Identifies criteria enabling non-asymptotic guarantees for SMC and fundamental limits faced by all particle filtering methods.
New data structure identifies close match from multiple distributions.
problem Identify the closest distribution to a given sample.
method Developed a sublinear-time data structure for identifying the closest distribution.
result First data structure that identifies the closest distribution in sublinear time.
We consider streaming, one-pass principal component analysis (PCA), in the high-dimensional regime, with limited memory. Here, -dimensional samples are presented sequentially, and the goal is to produce the -dimensional subspace that best approximates these points. Standard algorithms require memory; mea…
Modern ML methods show unexpected behaviors that contradict classical statistics.
problem Modern machine learning methods exhibit behaviors at odds with classical statistical intuitions.
method Comparison between fixed and random design settings in ML and statistics.
result Moving from fixed to random designs reveals new insights into bias-variance tradeoffs and overfitting.
TensorOpt finds optimal parallelization strategies for DNN training.
problem Finding efficient parallelization strategies for DNN training.
method TensorOpt uses an algorithm (FT) to search for an optimal set of parallelization strategies considering multiple objectives.
result TensorOpt provides accurate runtime cost estimation and adapts to resource availability.
This paper merges deterministic policy gradient estimations to improve deep reinforcement learning performance.
problem The bias-variance tradeoff in estimating and using policy gradients for deep reinforcement learning.
method Introduces elite policy gradients and a two-step merging method to balance bias-variance tradeoffs.
result Two-step merging outperforms interpolation merging and state-of-the-art algorithms on benchmark control tasks.
We propose an efficient end-to-end convolutional neural network architecture, AclNet, for audio classification. When trained with our data augmentation and regularization, we achieved state-of-the-art performance on the ESC-50 corpus with 85:65% accuracy. Our network allows configurations such that memory and compute r…
Paper proposes a federated XGBoost for anomaly detection balancing privacy and accuracy.
problem Balancing privacy and accuracy in anomaly detection for unbalanced datasets.
method Proposes a horizontal federated XGBoost algorithm with data aggregation and sparse update processes.
result Demonstrates effectiveness of the proposed scheme compared to state-of-the-arts.
The bias-variance tradeoff doesn't always apply in neural networks, contradicting textbook claims.
problem The bias-variance tradeoff is not universally applicable in neural networks, contradicting textbook teachings.
method Extensive experiments and analysis on neural networks, revisiting Geman et al. (1992) experiments.
result Neural networks do not exhibit a bias-variance tradeoff when increasing network width, contradicting textbook claims.
The bias-variance tradeoff tells us that as model complexity increases, bias falls and variances increases, leading to a U-shaped test error curve. However, recent empirical results with over-parameterized neural networks are marked by a striking absence of the classic U-shaped test error curve: test error keeps decrea…
This work tackles online memory selection in continual learning using information theory.
problem Online selection of a representative replay memory from data streams.
method Information-theoretic criteria (surprise, learnability) and Bayesian model for efficient computation.
result InfoRS improves robustness against data imbalance compared to reservoir sampling.
Neural networks can achieve optimal sample complexity for learning single-index models.
problem Achieving optimal computational-statistical tradeoff in learning Gaussian single-index models.
method Unified gradient-based algorithm for training a two-layer neural network, adaptable to various loss and activation functions.
result Sample complexity of matches the SQ lower bound up to a polylogarithmic factor.
We propose a new random pruning method (called "submodular sparsification (SS)") to reduce the cost of submodular maximization. The pruning is applied via a "submodularity graph" over the ground elements, where each directed edge is associated with a pairwise dependency defined by the submodular function. In each s…