The interaction between transitivity and sparsity, two common features in empirical networks, implies that there are local regions of large sparse networks that are dense. We call this the blessing of transitivity and it has consequences for both modeling and inference. Extant research suggests that statistical inferen…
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 “Sparse Transition”
CtrlNS learns latent factors and distribution shifts from sparse transitions without prior knowledge.
problem Lack of prior knowledge of domain variables limits causal temporal representation learning.
method Sparse transition assumption and identifiability results from theoretical perspective.
result Effective in identifying distribution shifts and latent factors without prior knowledge.
New approach selects sparse features without validation.
problem Overfitting and high storage/compute costs in AI models.
method Phase transition in probability of feature retrieval.
result Flexible approach for various models and loss functions.
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.
We study sparse principal component analysis for high dimensional vector autoregressive time series under a doubly asymptotic framework, which allows the dimension to scale with the series length . We treat the transition matrix of time series as a nuisance parameter and directly apply sparse principal component…
The paper tackles reward-relevance in offline RL with sparse decision dynamics.
problem Offline reinforcement learning with sparse decision dynamics and estimation sparsity.
method Reward-filtered least-squares policy evaluation using thresholded lasso.
result The method provides theoretical guarantees with sample complexity dependent on sparse component size.
Study on estimating sparse transition matrix of partially-observed VAR with noisy and sparse data.
problem Estimating sparse transition matrix of partially-observed VAR with noisy and sparse data.
method Yule-Walker equation, Dantzig selector, minimax lower bound.
result Near-optimality of the proposed estimator with convergence rate analysis.
Sparse neural encoding can store more memories as targets become sparser.
problem Storing sparse input-target associations in neural networks.
method Mathematical proofs using properties of random polytopes and sub-gaussian random vector variables.
result The capacity of neural maps increases with sparsity in target layers.
Algorithm learns graph operator from sparse space-time samples.
problem Learning time-varying graph signals from partial observations.
method Non-convex IRLS algorithm for low-rank matrix completion.
result No more than O(rn log(nT)) space-time samples needed for accurate recovery.
Missing Data in Sparse Transition Matrix Estimation for Sub-Gaussian Vector Autoregressive Processesstat.ML
High-dimensional time series data exist in numerous areas such as finance, genomics, healthcare, and neuroscience. An unavoidable aspect of all such datasets is missing data, and dealing with this issue has been an important focus in statistics, control, and machine learning. In this work, we consider a high-dimensiona…
We propose Deep Q-Networks (DQN) with model-based exploration, an algorithm combining both model-free and model-based approaches that explores better and learns environments with sparse rewards more efficiently. DQN is a general-purpose, model-free algorithm and has been proven to perform well in a variety of tasks inc…
Characterizing the phase transitions of convex optimizations in recovering structured signals or data is of central importance in compressed sensing, machine learning and statistics. The phase transitions of many convex optimization signal recovery methods such as minimization and nuclear norm minimization are…
In banking practice, rating transition matrices have become the standard approach of deriving multi-year probabilities of default (PDs) from one-year PDs, the latter normally being available from Basel ratings. Rating transition matrices have gained in importance with the newly adopted IFRS 9 accounting standard. Here,…
Study on signal recovery from low-rank matrix with sparse noise.
problem Inference of a rank-one signal in the presence of sparse noise.
method Replica method from statistical physics, recursive distributional equations, population dynamics algorithm.
result Critical signal strength for recovery via top eigenvector identified.
New method reduces regret for sparse adversarial SSP problems.
problem Sparse adversarial Stochastic Shortest Path problem.
method Proposed -norm regularizers for adaptive sparsity.
result Regret scales with instead of .
Minimax Optimal Rates of Estimation in High Dimensional Additive Models: Universal Phase Transitionmath.ST
We establish minimax optimal rates of convergence for estimation in a high dimensional additive model assuming that it is approximately sparse. Our results reveal an interesting phase transition behavior universal to this class of high dimensional problems. In the {\it sparse regime} when the components are sufficientl…
We present a novel binary convex reformulation of the sparse regression problem that constitutes a new duality perspective. We devise a new cutting plane method and provide evidence that it can solve to provable optimality the sparse regression problem for sample sizes n and number of regressors p in the 100,000s, that…
Study on signal detection in heteroscedastic Gaussian sequences with sparse alternatives.
problem Signal detection in heterogeneous Gaussian sequences with unknown means and known covariance.
method Characterization of minimax separation radius and derivation of matching upper and lower bounds.
result Matching minimax upper and lower bounds for signal detection in heteroscedastic Gaussian sequences.
New model for pairwise comparisons without stochastic transitivity.
problem Suboptimal performance of models assuming stochastic transitivity in real-world scenarios.
method Proposes a general family of statistical models using a skew-symmetric matrix.
result Achieves minimax-rate optimality and adapts to data sparsity.
A phase transition for finding needles in nonlinear haystacks with LASSO artificial neural networksstat.ML
ANN learner finds sparse needles in nonlinear haystacks with high probability.
problem Finding sparse features in nonlinear data.
method Generalized LASSO penalty with stochastic gradient descent, warm-start algorithm.
result Phase transition in ANN learner's ability to find needles, better than other learners.
SGD learns sparse parities near computational limits with discontinuous phase transitions.
problem Learning sparse parities in deep learning.
method Empirical and theoretical analysis of SGD on sparse parities.
result SGD makes progress on sparse parities via Fourier gap, not Langevin-like mechanism.
New algorithms detect communities in sparse graphs with labeled data.
problem Detecting communities in sparse graphs with limited labeled data.
method Introduces two algorithms: combinatorial and optimization-based, to integrate labeled data with graph structures.
result Detection of communities is feasible throughout the parameter domain with arbitrary labeled data.
We present a representation for describing transition models in complex uncertain domains using relational rules. For any action, a rule selects a set of relevant objects and computes a distribution over properties of just those objects in the resulting state given their properties in the previous state. An iterative g…
We present a novel method for exact hierarchical sparse polynomial regression. Our regressor is that degree polynomial which depends on at most inputs, counting at most monomial terms, which minimizes the sum of the squares of its prediction errors. The previous hierarchical sparse specification aligns w…
UCB-TQL learns from multiple tasks with shared dynamics and adapts to task-specific variations.
problem Transfer reinforcement learning with composite MDPs where tasks share core dynamics but have sparse differences.
method UCB-TQL, a novel transfer RL algorithm for composite MDPs.
result Achieved a regret bound of that scales independently of the ambient dimension.
Autoencoders fail to capture sparse structure in 1-bit data compression.
problem Proving the performance of shallow autoencoders on sparse data compression.
method Gradient descent analysis and approximate message passing.
result Gradient descent minimizer for sparse data is the identity (up to permutation) above critical sparsity.
We study optimal estimation for sparse principal component analysis when the number of non-zero elements is small but on the same order as the dimension of the data. We employ approximate message passing (AMP) algorithm and its state evolution to analyze what is the information theoretically minimal mean-squared error …
Sparse Tucker Decomposition and Graph Regularization for High-Dimensional Time Series Forecastingmath.ST
Sparse Tucker decomposition with graph regularization improves time series forecasting accuracy.
problem High-dimensional time series forecasting with over-parameterization issue.
method Sparse Tucker decomposition and graph regularization for tensor-based model.
result Non-asymptotic error bound and superior performance in numerical experiments.
Paper tackles matrix estimation under arbitrary noise, achieving minimax optimality.
problem Noisy low-rank-plus-sparse matrix recovery under arbitrary dependence.
method Incoherent-constrained least-square estimator, novel energy spreading result.
result Achieves minimax optimality in estimating structured Markov transition kernels.
Predicting labels of nodes in a network, such as community memberships or demographic variables, is an important problem with applications in social and biological networks. A recently-discovered phase transition puts fundamental limits on the accuracy of these predictions if we have access only to the network topology…
There have been several spectral bounds for the percolation transition in networks, using spectrum of matrices associated with the network such as the adjacency matrix and the non-backtracking matrix. However they are far from being tight when the network is sparse and displays clustering or transitivity, which is repr…
Quasi-potential and drift decomposition in stochastic systems by sparse identificationcond-mat.stat-mech
Paper uses sparse learning to estimate quasi-potential and drift components in stochastic systems.
problem Estimating quasi-potential and drift components in stochastic systems.
method Sparse identification of non-linear dynamics (SINDy) combined with action minimization methods.
result Evaluation of quasi-potential landscape from a single trajectory.
Proposes a differentiable LSE-ICNN for modeling multi-well potentials.
problem Modeling multi-well potentials in various scientific domains.
method Log-sum-exponential (LSE) mixture of input convex neural network (ICNN) modes.
result Smooth surrogate that retains convexity within basins and allows gradient-based learning.
Linear Dynamical System (LDS) is an elegant mathematical framework for modeling and learning multivariate time series. However, in general, it is difficult to set the dimension of its hidden state space. A small number of hidden states may not be able to model the complexities of a time series, while a large number of …
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.
Overparameterized ReLU Neural Networks Learn the Simplest Models: Neural Isometry and Exact Recoverycs.LG
ReLU networks learn simple models even with many parameters, overcoming traditional wisdom.
problem Generalization of overparameterized neural networks.
method Convex optimization and sparse recovery perspective applied to two-layer ReLU networks with standard weight decay.
result ReLU networks learn simple models that explain the data, analogous to sparse recovery in compressed sensing.
Optimal feature transfer identified through bias-variance analysis.
problem Optimizing feature transfer in transfer learning.
method Simple linear model with fine-grained bias-variance decomposition.
result Optimal pretrained feature transform is naturally sparse.
State-space models are successfully used in many areas of science, engineering and economics to model time series and dynamical systems. We present a fully Bayesian approach to inference \emph{and learning} (i.e. state estimation and system identification) in nonlinear nonparametric state-space models. We place a Gauss…
Study shows how much information can be learned from sparse signals with limited data.
problem Understanding information limits in learning sparse signals with sublinear data.
method Proved variational formula for mutual information, derived MMSE expressions, analyzed phase transitions.
result Nonincreasing piecewise constant MMSE with all-or-nothing phase transitions for certain conditions.
Reinforcement learning usually uses the feedback rewards of environmental to train agents. But the rewards in the actual environment are sparse, and even some environments will not rewards. Most of the current methods are difficult to get good performance in sparse reward or non-reward environments. Although using shap…
Phase Transitions in Operational Riskphysics.soc-ph
In this paper we explore the functional correlation approach to operational risk. We consider networks with heterogeneous a-priori conditional and unconditional failure probability. In the limit of sparse connectivity, self-consistent expressions for the dynamical evolution of order parameters are obtained. Under equil…
A nonparametric Bayesian sparse graph linear dynamical system (SGLDS) is proposed to model sequentially observed multivariate data. SGLDS uses the Bernoulli-Poisson link together with a gamma process to generate an infinite dimensional sparse random graph to model state transitions. Depending on the sparsity pattern of…
ETGL-DDPG improves DDPG for sparse reward control with new exploration and replay techniques.
problem Sparse reward continuous control in reinforcement learning.
method Introduces -greedy search and GDRB framework for efficient exploration and reward use.
result ETGL-DDPG outperforms DDPG and other methods on sparse-reward continuous benchmarks.
Sparse reward problems are one of the biggest challenges in Reinforcement Learning. Goal-directed tasks are one such sparse reward problems where a reward signal is received only when the goal is reached. One promising way to train an agent to perform goal-directed tasks is to use Hindsight Learning approaches. In thes…
Characterizes optimal reconstruction error in high-dimensional Gaussian mixtures.
problem Optimizing reconstruction error in high-dimensional sparse Gaussian mixtures.
method Exact asymptotic characterization using state evolution of AMP algorithm.
result Identification of statistical-to-computational gap between AMP and information-theoretic threshold.
Sparse RSP routing improves graph exploration and classification.
problem Optimal randomized routing and distance measures on weighted graphs.
method Tsallis divergence regularization for sparse RSP.
result Sparse random walk converges to least-cost graph as temperature decreases.
Minimum-Excess-Work Guidancestat.ML
Proposes a thermodynamic work minimization framework for guiding generative models.
problem Guiding generative models in sparse-data regimes with limited target samples or constraints.
method Regularization framework inspired by thermodynamic work, introducing Path Guidance and Observable Guidance.
result Improves sample efficiency and reduces bias in molecular simulations.
We consider a random sparse graph with bounded average degree, in which a subset of vertices has higher connectivity than the background. In particular, the average degree inside this subset of vertices is larger than outside (but still bounded). Given a realization of such graph, we aim at identifying the hidden subse…