Sparse coding approximates the data sample as a sparse linear combination of some basic codewords and uses the sparse codes as new presentations. In this paper, we investigate learning discriminative sparse codes by sparse coding in a semi-supervised manner, where only a few training samples are labeled. By using the m…
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,695 papers · 148 categories
Trend · papers per month
48 results for “sparse sampling”
IDS improves sparse linear bandits by balancing information and regret.
problem Sparse linear bandits in high-dimensional decision-making.
method Information-directed sampling (IDS) with Bayesian regret bounds and empirical Bayesian sparse posterior sampling.
result IDS nearly matches existing lower bounds and significantly reduces regret.
Study shows inefficiency of sparse linear regression learning with fewer than Ω(k^2) samples.
problem Efficiency of sparse linear regression learning with minimal samples.
method Reduction to sparse PCA problems and lower bounds.
result Efficient algorithms for sparse linear regression require at least Ω(k^2) samples.
Topological data analysis (TDA) has emerged as one of the most promising techniques to reconstruct the unknown shapes of high-dimensional spaces from observed data samples. TDA, thus, yields key shape descriptors in the form of persistent topological features that can be used for any supervised or unsupervised learning…
Sparse support vector machine (SVM) is a popular classification technique that can simultaneously learn a small set of the most interpretable features and identify the support vectors. It has achieved great successes in many real-world applications. However, for large-scale problems involving a huge number of samples a…
Improved locally private sparse estimation with multiple samples per user.
problem Challenges in high-dimensional locally private sparse estimation.
method Proposes a framework for user-level locally private sparse linear regression with multiple samples per user.
result Eliminates the dependency of dimensionality on error bounds, achieving tighter error bounds.
This paper establishes conditions for sparse signal recovery with sparse measurements.
problem Recovering the support of a sparse signal using noisy projections with sparse measurement matrices.
method Establishes sufficient conditions for successful sparse recovery using sparse measurement matrices.
result A phase transition threshold for sparse recovery in the sparse setting is discovered, revealing a trade-off between sampling complexity and measurement sparsity.
New algorithm reduces sample complexity for sparse linear regression.
problem Sparse linear regression with correlated covariates and approximate dependencies.
method Polynomial-time algorithm that adapts the Lasso to tolerate approximate dependencies.
result Achieves near-optimal sample complexity for constant sparsity and ill-conditioned covariates.
New algorithm reduces runtime for robust sparse mean estimation.
problem Efficiently estimating mean from corrupted data with sparse constraints.
method Subquadratic time algorithm using poly(k, log d, 1/ε) samples.
result First subquadratic time algorithm for robust sparse mean estimation.
Self-attention prefers sparse functions of input sequences, reducing sample complexity.
problem Understanding the inductive biases of self-attention in modeling long-range dependencies.
method Theoretical analysis and synthetic experiments to probe sample complexity of learning sparse functions with Transformers.
result Bounded-norm Transformer networks can represent sparse functions of the input sequence with logarithmic sample complexity.
Improved Thompson Sampling for high-dimensional sparse bandits.
problem Stochastic linear contextual bandits with high-dimensional features.
method Thompson Sampling with spike-and-slab priors and variational inference.
result Nearly optimal upper bound on expected cumulative regret.
Paper introduces S-SSE for stable sparse subspace embedding.
problem Inefficient sparse random projection matrices with uneven non-zero distribution.
method Uses uniform sampling without replacement to create a stable sparse subspace embedded matrix (S-SSE).
result S-SSE maintains Euclidean distance better after dimension reduction.
We study sparse group Lasso for high-dimensional double sparse linear regression, where the parameter of interest is simultaneously element-wise and group-wise sparse. This problem is an important instance of the simultaneously structured model -- an actively studied topic in statistics and machine learning. In the noi…
Scalable algorithm for sampling Gaussian processes using sparse grids and preconditioners.
problem Generating high-dimensional Gaussian random vectors for GP sampling is computationally challenging.
method Proposes a scalable algorithm using inducing points approximation with sparse grids and additive Schwarz preconditioners.
result Demonstrates the efficacy and accuracy of the proposed method through experiments and comparisons.
Improves content allocation in educational platforms with sparse data.
problem Imbalanced content allocation and delayed convergence in adaptive strategies.
method Introduces WAPTS, an algorithm that refines Thompson Sampling for data-sparse environments.
result Demonstrates earlier and more reliable identification of promising treatments.
Paper optimizes privacy-preserving distribution estimation for sparse data.
problem Sparse distribution estimation under local differential privacy constraints.
method Compressive sensing approaches for privacy-preserving estimation.
result Significant reduction in sample complexity for approximately sparse distributions.
We analyze the computational complexity of Quantum Sparse Support Vector Machine, a linear classifier that minimizes the hinge loss and the norm of the feature weights vector and relies on a quantum linear programming solver instead of a classical solver. Sparse SVM leads to sparse models that use only a small fr…
Efficiently estimates sparse mean from heavy-tailed data.
problem Robustly estimating sparse mean from heavy-tailed distributions.
method Stability-based approach adapted for heavy-tailed data.
result Optimal sample complexity with logarithmic dependence on dimension.
Robust estimators for Gaussian sparse tasks with optimal error under contamination.
problem Robust mean estimation, PCA, and linear regression in the presence of Huber contamination.
method Novel multidimensional filtering method for sparse regime.
result Optimal error guarantees within constant factors for Gaussian robust -sparse mean estimation.
Proposes SVI for covariate-shift generalization with sparse variable independence.
problem Covariate-shift generalization with limited data and unstable variables.
method Introduces sparsity constraint and combines reweighting and selection in an iterative way.
result Improves covariate-shift generalization performance on synthetic and real-world datasets.
Online method learns sparse models efficiently in large scale settings.
problem Sparse model learning in large scale settings with high computational and memory costs.
method Online learning approach, mini-batch methods, hard thresholding based stochastic gradient algorithm.
result Sparsity promoted by batch methods is not preserved in online fashion.
PolytopeWalk library efficiently samples high-dimensional polytopes.
problem Sampling from high-dimensional polytopes efficiently.
method End-to-end solution including preprocessing and MCMC algorithms.
result Improved sampling efficiency and scalability to high dimensions.
Given two data matrices and , sparse canonical correlation analysis (SCCA) is to seek two sparse canonical vectors and to maximize the correlation between and . However, classical and sparse CCA models consider the contribution of all the samples of data matrices and thus cannot identify an unde…
Novel data acquisition schemes have been an emerging need for scanning microscopy based imaging techniques to reduce the time in data acquisition and to minimize probing radiation in sample exposure. Varies sparse sampling schemes have been studied and are ideally suited for such applications where the images can be re…
CoT improves transformer sample efficiency by reducing input token dependencies and attention sparsity.
problem Transformer sample inefficiency in simple tasks.
method Demonstrated through parity-learning setup, showing CoT reduces required samples from exponential to polynomial.
result Transformer learns function within polynomial samples with CoT, requiring exponential samples without CoT.
LSDAT reduces query efficiency for decision-based adversarial attacks.
problem Improving query efficiency for decision-based adversarial attacks.
method Low-rank and sparse decomposition (LSD) to craft perturbations.
result LSDAT achieves superior fooling rates with fewer queries.
CDSSD detects sparse changes in partially observable data streams.
problem Online change detection of sparse changes in partially observable high-dimensional data streams.
method Smooth-sparse decomposition, spike-slab variational Bayesian inference, adaptive sampling via Thompson sampling.
result CDSSD effectively detects sparse changes in partially observable data streams.
Improved sample complexity for Gaussian process approximations.
problem Efficiently approximating Gaussian processes with sparse spectrum.
method Improved sample complexity analysis and auto-encoding algorithm.
result Gaussian process predictions and model evidence can be well-approximated with low sample complexity.
Framework learns continuous dynamics from sparse trajectories.
problem Learning dynamics from sparsely sampled and high-dimensional trajectories.
method Interpolative Multi-Marginal Flow Matching (IMMFM) framework.
result IMMFM outperforms existing methods in forecasting and downstream tasks.
SAIL learns from sub-optimal demonstrations to improve sample efficiency in sparse reward tasks.
problem Reducing sample complexity in sparse-rewarded tasks.
method Self-Adaptive Imitation Learning (SAIL) that exploits sub-optimal demonstrations and efficient exploration.
result Significantly improved sample efficiency and better final performance across various tasks.
The paper efficiently estimates parameters from truncated Gaussian and linear models.
problem Estimating parameters from truncated Gaussian and linear models.
method Minimizes finite population negative log-likelihood function with an l1-regularization term.
result Efficient estimation of parameters from truncated samples.
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.
Solving Statistical Mechanics on Sparse Graphs with Feedback Set Variational Autoregressive Networkscond-mat.stat-mech
We propose a method for solving statistical mechanics problems defined on sparse graphs. It extracts a small Feedback Vertex Set (FVS) from the sparse graph, converting the sparse system to a much smaller system with many-body and dense interactions with an effective energy on every configuration of the FVS, then learn…
High-dimensional near-optimal experiment design for drug discovery via Bayesian sparse samplingcs.LG
Bayesian methods improve drug discovery experiment design.
problem Optimizing drug screening experiments in high-dimensional data.
method Bayesian inference and optimisation with upper confidence bound algorithms, Thompson sampling, and sparse tree search.
result Sparse tree search techniques outperform other methods in drug toxicity screening.
New method controls FDR for sparse GLMs, identifying positive and negative relationships.
problem Sparse GLMs with high-dimensional data and varying sample size.
method Debiased-Lasso estimator and CLIME method for precision matrix estimation.
result Asymptotically controls directional FDR and FDV for sparse GLMs.
New insights into statistical and computational limits for mixed sparse linear regression.
problem Recovering two sparse signals from noisy linear measurements.
method Analysis of low-degree polynomials and a simple thresholding algorithm.
result Identification of a smooth information-computation tradeoff and order-optimality of the thresholding algorithm.
New method learns sparse distributions by thresholding samples, improving performance and efficiency.
problem Sparse coding optimization in high-dimensional problems is computationally expensive and inefficient.
method Proposes a new variational sparse coding approach that learns sparse distributions by thresholding samples.
result Shows superior performance, statistical efficiency, and gradient estimation compared to other sparse distributions.
Sparse APCA identifies sparse factors in financial returns over time.
problem Analyzing co-movements of high-dimensional panel data over time.
method Sparse asymptotic PCA with truncated power method for sparse factors and sequential deflation for multi-factor cases.
result Identification of nine risk factors influencing the S&P 500 stock market.
Sparse GCA finds linear relationships in multiple datasets, using gradient descent.
problem Finding linear relationships across multiple datasets with sparse loading vectors.
method Formulated as generalized eigenvalue problems, used a thresholded gradient descent algorithm.
result Proposed algorithm yields tight estimation error bounds and demonstrates effectiveness on synthetic datasets.
Hadamard Wirtinger Flow recovers sparse signals from fewer measurements.
problem Reconstructing sparse signals from magnitude-only measurements.
method Gradient descent with Hadamard parametrization (HWF).
result A single step of HWF recovers support from samples.
Improved sample efficiency in learning sparse Ising models.
problem Learning the graph of a sparse Ising model with limited samples.
method Combining L0 and L2 norms to induce sparsity and model non-zero coefficients.
result Improved sample complexity, achieving new state-of-the-art recovery guarantees.
Study on sparse recovery with mixed-quality data, establishing sample-size conditions.
problem Sparse recovery with heterogeneous noise from high- and low-quality sources.
method Establishes linear trade-off for sufficient conditions, analyzes LASSO algorithm.
result Linear trade-off for sufficient conditions, robustness of LASSO to data heterogeneity.
Near-optimal sample complexity for phase retrieval with generative priors.
problem Phase retrieval with magnitude-only measurements and sparse signals.
method Near-optimal sample complexity with i.i.d. Gaussian measurements and generative models.
result O(k log L) samples suffice for phase retrieval with generative priors.
New method for estimating sparse means in noisy data.
problem Estimating the mean of a sparse distribution in the presence of outliers.
method Difference-of-Pairs Filtering technique for list-decodable sparse mean estimation.
result First sample and computationally efficient algorithm for list-decodable sparse mean estimation.
Learning to approximate a separable function is hard, requiring many samples even with sparse networks.
problem Learning the separable function with limited samples.
method Sparse neural networks vs. dense neural networks, explicit regularization.
result The sample complexity for dense networks is with explicit regularization, better than .
Sparse Linear Regression when Noises and Covariates are Heavy-Tailed and Contaminated by Outliersstat.ML
Efficiently estimates sparse linear regression with heavy-tailed and outlier-contaminated data.
problem Estimating sparse linear regression coefficients with heavy-tailed and outlier-contaminated data.
method Efficient computation of estimators with sharp error bounds.
result Sharp error bounds for efficient estimators.
We study the problem of inferring a sparse vector from random linear combinations of its components. We propose the Accelerated Orthogonal Least-Squares (AOLS) algorithm that improves performance of the well-known Orthogonal Least-Squares (OLS) algorithm while requiring significantly lower computational costs. While OL…
Sparse convex clustering is to cluster observations and conduct variable selection simultaneously in the framework of convex clustering. Although a weighted norm is usually employed for the regularization term in sparse convex clustering, its use increases the dependence on the data and reduces the estimation acc…