We present a study of generalization for data-dependent hypothesis sets. We give a general learning guarantee for data-dependent hypothesis sets based on a notion of transductive Rademacher complexity. Our main result is a generalization bound for data-dependent hypothesis sets expressed in terms of a notion of hypothe…
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 “complex dependence”
Paper extends learning theory to dependent data with uniform risk bounds.
problem Learning with dependent data sequences.
method Derives uniform risk bounds for dependent data using VC-dimension and Rademacher complexity.
result Standard classification risk bounds hold for dependent data, same as for independent data.
New algorithms improve contextual bandit performance by adapting to problem difficulty.
problem Improving contextual bandit performance on problems with varying difficulty.
method Introducing complexity measures and oracle-efficient algorithms.
result Achieves optimal instance-dependent regret bounds for rich policy classes.
Optimizes quadratic bandits with tight Hessian-dependent sample complexity bounds.
problem Understanding optimal sample complexity for quadratic functions.
method Introduces energy allocation and optimal energy spectrum to prove tight lower bounds. Solves for Hessian-independent optimal algorithm.
result Proves optimal Hessian-dependent sample complexities and existence of a universally optimal algorithm.
Flexible Cox model for time-dependent covariates with complex sparsity patterns.
problem Lack of flexibility in enforcing specific sparsity patterns in time-dependent Cox models.
method Proposes a flexible framework for variable selection in time-dependent Cox models, accommodating complex selection rules.
result Achieves accurate estimation with low false alarm rates for complex covariate structures.
Survey on learning with graph-dependent data, deriving new generalization bounds.
problem Traditional i.i.d. data assumption fails in many real-life applications.
method Collect and analyze graph-dependent concentration bounds, derive generalization bounds.
result New generalization bounds for graph-dependent data.
New algorithm learns optimal policies with just 1 episode, settling horizon-dependence in RL.
problem Understanding the sample complexity of reinforcement learning with horizon length.
method Developed an algorithm using only episodes to achieve PAC guarantee, leveraging connections between value functions in discounted and finite-horizon MDPs and novel perturbation analysis.
result Achieved the same PAC guarantee with only episodes of environment interactions, completely settling horizon-dependence in RL.
A crucial assumption in most statistical learning theory is that samples are independently and identically distributed (i.i.d.). However, for many real applications, the i.i.d. assumption does not hold. We consider learning problems in which examples are dependent and their dependency relation is characterized by a gra…
Conventional sequential learning methods such as Recurrent Neural Networks (RNNs) focus on interactions between consecutive inputs, i.e. first-order Markovian dependency. However, most of sequential data, as seen with videos, have complex temporal dependencies that imply variable-length semantic flows and their composi…
On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluationcs.LG
Study on future-dependent value functions for off-policy evaluation in complex environments.
problem Exponential dependence on horizon in off-policy evaluation for complex observations.
method Developed novel coverage assumptions for POMDPs to achieve polynomial bounds.
result Achieved polynomial bounds on previously exponential quantities, improving off-policy evaluation.
The properties of q-dependent cross-correlation matrices of stock market have been analyzed by using the random matrix theory and complex network. The correlation structures of the fluctuations at different magnitudes have unique properties. The cross-correlations among small fluctuations are much stronger than those a…
New reinforcement learning algorithm achieves instance-optimal sample complexity.
problem Achieving low regret and identifying optimal policies in reinforcement learning.
method A novel planning-based algorithm that explicitly accounts for state visitation distributions.
result The proposed algorithm attains nearly minimax optimal sample complexity, improving over worst-case bounds.
Paper establishes first instance-dependent lower bound for PAC reinforcement learning.
problem Identifying near-optimal policies in tabular MDPs with minimal samples.
method Proposes instance-dependent lower bound for sample complexity.
result Lower bound closely matches PEDEL algorithm's sample complexity.
New RL method reduces sample complexity for large policy spaces.
problem Large-scale RL with unknown optimal policies and state/action spaces.
method Introduces eluder dimension for policy space, proving near-optimal sample complexity.
result Near-optimal sample complexity upper bound that depends linearly on eluder dimension.
Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcs.LG
Algorithm extsc{Pedel} learns near-optimal policies efficiently on specific problems.
problem Learning near-optimal policies in linear MDPs with minimal samples.
method Online experiment design to focus exploration on relevant directions.
result Achieves instance-dependent complexity, outperforming minimax-optimal algorithms.
In data science, it is often required to estimate dependencies between different data sources. These dependencies are typically calculated using Pearson's correlation, distance correlation, and/or mutual information. However, none of these measures satisfy all the Granger's axioms for an "ideal measure". One such ideal…
New complexes derived from any filtered cochain complex compute the same cohomology.
problem Constructing cohomologically equivalent subcomplexes from filtered cochain complexes.
method Presenting a general construction that produces subcomplexes from any filtered cochain complex of finite depth.
result The construction of subcomplexes depends only on the filtration up to isomorphism.
Proves minimax sample complexity for turn-based stochastic games.
problem Proving theoretical guarantees for reinforcement learning in turn-based stochastic games.
method Developing absorbing TBSG and reward perturbation techniques to handle statistical dependence.
result Empirical Nash equilibrium strategy approximates true Nash equilibrium in turn-based stochastic games.
Homotopy equivalent boundaries of cube complexes are studied.
problem The equivalence of different boundaries of cube complexes.
method Using a partial order on a quotient of the Roller boundary, we obtain the simplicial Roller boundary and show homotopy equivalence among the Tits, simplicial, and simplicial Roller boundaries.
result The Tits, simplicial, and simplicial Roller boundaries are homotopy equivalent.
The statistical complexity of quantum circuits is studied using Rademacher complexity.
problem Measuring the richness of quantum hypothesis spaces.
method Applying Rademacher complexity to quantum circuits, investigating dependencies on resources, depth, width, and input/output registers.
result Bounds on the capacity of quantum neural networks constrained by circuit depth, width, and resource measures.
We consider PAC-learning a good item from -subsetwise feedback information sampled from a Plackett-Luce probability model, with instance-dependent sample complexity performance. In the setting where subsets of a fixed size can be tested and top-ranked feedback is made available to the learner, we give an algorithm w…
HNP3: A Hierarchical Nonparametric Point Process for Modeling Content Diffusion over Social Mediastat.ML
This paper introduces a novel framework for modeling temporal events with complex longitudinal dependency that are generated by dependent sources. This framework takes advantage of multidimensional point processes for modeling time of events. The intensity function of the proposed process is a mixture of intensities, a…
Neural Bayes methods simplify fitting complex bivariate extremal models.
problem Inference on complex multivariate extremal dependence models with computationally expensive likelihood functions.
method Use neural networks to approximate Bayes estimators and classifiers for model selection.
result Proposed neural Bayes methods enable routine implementation of complex extreme-value dependence models.
We construct an explicit lower bound for the volume of a complex hyperbolic orbifold that depends only on dimension.
This study analyzes cryptocurrency market dynamics using a novel -dependent detrended cross-correlation method.
problem Capturing correlations at varying fluctuation amplitudes and time scales in complex systems.
method Extends traditional metrics with -dependent detrended cross-correlation coefficient ρ(q,s) and MSTs.
result Significant shifts in network structures during major disruptions, leading to decentralized correlations.
A deep learning model for traffic forecasting in telecommunication networks.
problem Complex spatial-temporal dependency in traffic forecasting.
method Spatio-Temporal Hybrid Graph Convolutional Network (STHGCN) combining GRUs and hybrid-GCN.
result The proposed model outperforms classical and state-of-the-art methods.
Existing Rademacher complexity bounds for neural networks rely only on norm control of the weight matrices and depend exponentially on depth via a product of the matrix norms. Lower bounds show that this exponential dependence on depth is unavoidable when no additional properties of the training data are considered. We…
On the Homotopy Type and the Fundamental Crossed Complex of the Skeletal Filtration of a CW-Complexmath.GT
We prove that if is a CW-complex, then the homotopy type of the skeletal filtration of does not depend on the cell decomposition of up to wedge products with -disks , when the later are given their natural CW-decomposition with unique cells of order 0, and ; a result resembling J.H.C. Whi…
A novel stepwise VI method using vine copulas for complex latent dependence.
problem Modeling complex latent dependence structures in probabilistic models.
method Stepwise estimation of vine copula parameters using Rényi divergence and a stopping criterion.
result Our method outperforms mean-field VI and is more parsimonious in complex applications.
Review of financial dependencies using econophysics and financial economics.
problem Analyzing financial dependencies between markets.
method Combining econophysics and financial economics approaches to model financial markets.
result Information filtering networks effectively describe financial dependencies.
Develops black-box methods to estimate parameters of complex models.
problem Lack of efficient methods to produce simulations for complex statistical models.
method Pre-training deep neural networks on extensive simulated databases for well-structured likelihoods. Iterative algorithm for other complex dependencies.
result Successfully estimates and quantifies uncertainty of parameters from non-Gaussian models.
Paper reduces sample complexity for bilinear systems identification to nearly constant.
problem Identifying discrete-time bilinear systems under bounded disturbances.
method Uses trajectory-dependent regressors and polynomial mean-square state growth analysis.
result Proves sample complexity of for estimation error .
Proposes SGM for modeling complex dependencies in high-dimensional systems.
problem Limited pairwise interactions in PGMs for high-dimensional systems.
method Simplicial Gaussian model (SGM) using discrete Hodge theory and independent random components.
result Maximum-likelihood inference algorithm for parameter recovery and conditional dependence structure.
Quantitative null-cobordismmath.GT
For a given null-cobordant Riemannian -manifold, how does the minimal geometric complexity of a null-cobordism depend on the geometric complexity of the manifold? In [Gro99], Gromov conjectured that this dependence should be linear. We show that it is at most a polynomial whose degree depends on . This constructi…
New empirical process bounds reveal trade-off between dependence and complexity in nonparametric learning.
problem Understanding generalization in nonparametric learning with temporal dependencies.
method Developed bounds on expected supremum of empirical processes under -mixing assumptions.
result Achieved rates similar to i.i.d. setting under long-range dependence with complex function classes.
Inference of time-ordered multibody interactionsphysics.soc-ph
We describe and extract time-ordered multibody interactions from complex systems.
problem Complex systems with temporal and multibody dependencies.
method Decompose multivariate Markov chains into time-ordered multibody interactions. Algorithm to extract interactions from data. Measure complexity of interaction ensembles.
result Robust and efficient algorithm to infer time-ordered multibody interactions from data.
We revisit the inductive matrix completion problem that aims to recover a rank- matrix with ambient dimension given features as the side prior information. The goal is to make use of the known features to reduce sample and computational complexities. We present and analyze a new gradient-based non-convex…
The paper introduces CoCoCat bonds for multi-region natural catastrophes, accounting for complex dependencies.
problem Valuation of multi-region contingent convertible bonds under complex dependencies.
method Developed a model accounting for inter-regional dependencies using change-of-measure techniques.
result Significant impact of inter-regional dependencies on CoCoCat bond pricing.
New bounds explain modern machine learning algorithms' generalization.
problem Explaining generalization behavior of modern machine learning algorithms.
method Proposes a new complexity measure based on empirical Rademacher complexity of an algorithm- and data-dependent hypothesis class.
result Obtains novel bounds with finite fractal dimension, simplifies proofs, and recovers known results.
We derive a priori estimates for the -plurisubharmonic solutions of general complex Hessian equations with right-hand side depending on gradients.
We show how to control the generalization error of time series models wherein past values of the outcome are used to predict future values. The results are based on a generalization of standard i.i.d. concentration inequalities to dependent data without the mixing assumptions common in the time series setting. Our proo…
Let be a close complex manifold and its holomorphic tangent bundle. We prove that if the global holomorphic sections of tangent bundle generate each fibre, then is a complex homogeneous manifold. Our proof depends on the complex version of Chow-Rashevskii theorem in Carnot-Caratheodory spaces.
Quantum algorithms improve perceptron learning efficiency.
problem Improving quantum algorithms for perceptron learning.
method Revisiting and correcting a flawed quantum version space perceptron algorithm, proposing quantum-enhanced cutting-plane algorithms.
result Improved complexity bounds for quantum perceptron learning.
Generative model captures complex dependence in financial data.
problem Complex dependence structure in business and financial data.
method Multivariate generative model with heterogeneous and asymmetric tail dependence.
result Novel moment learning algorithm for scalable parameter estimation.
Structured Nonparametric Variational Inference for Dependent Latent Modeling
problem Approximating posterior distributions with complex dependencies among latent variables
method Structured Nonparametric Variational Inference (SN-VI)
result Flexible and accurate posterior approximation with arbitrary shapes
New bounds for quantum circuits depend on how data is encoded.
problem Lack of explicit dependence on data encoding in generalization bounds for PQCs.
method Derived generalization bounds that depend on data encoding strategies using Rademacher complexity and metric entropy.
result Optimal data-encoding strategies can be selected via structural risk minimization.
Improved sample complexity for training diffusion models.
problem How many samples are needed to train an accurate diffusion model?
method Analyzing the sample complexity of training diffusion models using neural networks.
result Exponential improvement in the dependence on Wasserstein error and depth, along with improved dependencies on other parameters.
New algorithm reduces sample complexity for planning in MDPs.
problem Planning in MDPs with unknown transitions.
method MDP-GapE, a trajectory-based MCTS algorithm.
result Proves upper bound on sample complexity in terms of sub-optimality gaps.