In this paper, we introduce a novel method to generate interpretable regression function estimators. The idea is based on called data-dependent coverings. The aim is to extract from the data a covering of the feature space instead of a partition. The estimator predicts the empirical conditional expectation over the cel…
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 “data-dependent partitioning”
A new learning rule consistently reduces error over data samples.
problem Finding a learning rule that consistently reduces error over all data distributions.
method A deterministic, data-dependent partitioning rule that only partitions cyclic intervals with sufficient empirical diversity of labels.
result The expected error is monotone non-increasing with the sample size under every data distribution.
New KD-tree based method for private synthetic data generation.
problem Creating private synthetic data that accurately represents real data.
method KD-trees combined with noise perturbation for differentially private synthetic data generation.
result Our data-dependent approach improves utility over prior work and scales well.
A new approach uses partial likelihood to improve tree-based density estimation and inference.
problem Inference on tree-based models suffers from overfitting and reduced efficiency due to data-independent partitioning.
method Proposes a partial likelihood approach to data-dependent partitioning of tree-based models.
result Significant gains in estimation accuracy and computational efficiency from adopting partial likelihood.
This research designs a data-driven partition to test independence between continuous variables.
problem Testing independence between continuous random variables.
method Empirical log-likelihood statistic and data-driven tree-structured partition.
result Strongly consistent test of independence over probability families.
In this paper, we investigate adaptive nonlinear regression and introduce tree based piecewise linear regression algorithms that are highly efficient and provide significantly improved performance with guaranteed upper bounds in an individual sequence manner. We use a tree notion in order to partition the space of regr…
New bounds ensure reliable deep learning performance without model changes.
problem Certifying deep neural networks' reliability without altering them.
method Data-dependent generalization bounds that apply directly to trained models.
result Achieves meaningful generalization guarantees for large, unaltered deep networks.
This paper tackles multilabel classification by exploiting label sparsity and hierarchy.
problem Sparse label vectors and unknown label hierarchy in large-scale multilabel classification problems.
method Data-dependent grouping and hierarchical partitioning to solve multilabel classification problems in a lower-dimensional space.
result Our methods achieve competitive accuracy with significantly lower computational costs compared to other methods.
In distributed machine learning, data is dispatched to multiple machines for processing. Motivated by the fact that similar data points often belong to the same or similar classes, and more generally, classification rules of high accuracy tend to be "locally simple but globally complex" (Vapnik & Bottou 1993), we propo…
In recent studies, the generalization properties for distributed learning and random features assumed the existence of the target concept over the hypothesis space. However, this strict condition is not applicable to the more common non-attainable case. In this paper, using refined proof techniques, we first extend the…
We reformulate data-dependent constraints to ensure they are always met with high probability.
problem Ensuring fairness and stability in machine learning models with data-dependent constraints.
method Calibrated reformulation of constraints to guarantee satisfaction with a specified probability.
result Our method guarantees that fairness constraints are met at test time with high probability.
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…
PAC-Bayesian theory applied to data-dependent hypothesis sets yields uniform generalization bounds.
problem Proving uniform generalization bounds for data-dependent hypothesis sets.
method Applying PAC-Bayesian framework on 'random sets' and considering data-dependent hypothesis sets.
result Data-dependent uniform generalization bounds are proven, providing tighter and unified results.
Optimal kernel in KR can be data-dependent, improving model performance.
problem Fixed kernel in KR limits model performance.
method Considered data-dependent kernels for KR, using posterior covariance.
result Data-dependent kernel choice leads to optimal performance.
The paper improves PAC-Bayes bounds for data-dependent predictors.
problem Guaranteeing the quality of predictions on unseen examples.
method Basic PAC-Bayes inequality for stochastic kernels, leading to various bounds.
result Validates PAC-Bayes bounds without fixed 'data-free' priors and bounded losses.
Paper introduces data-dependent SSP for private linear and logistic regression.
problem Private linear and logistic regression with better performance.
method Data-dependent sufficient statistic perturbation (SSP) for linear and logistic regression.
result Data-dependent SSP outperforms state-of-the-art methods for linear and logistic regression.
The paper shows robustness and generalization are closely connected via data-dependent bounds.
problem Connecting robustness and generalization in machine learning.
method Data-dependent generalization bounds that reduce dependence on covering number and hypothesis space.
result Proves robustness implies generalization, with near-exponential improvements in various situations.
Generalization Guarantees for Representation Learning via Data-Dependent Gaussian Mixture Priorsstat.ML
The study improves representation learning bounds using data-dependent Gaussian mixtures.
problem Improving generalization in representation learning.
method Established bounds using relative entropy and MDL of latent variables.
result The approach significantly improves generalization over existing methods.
We propose Rademacher complexity bounds for multiclass classifiers trained with a two-step semi-supervised model. In the first step, the algorithm partitions the partially labeled data and then identifies dense clusters containing predominant classes using the labeled training examples such that the proportion of t…
Meta-learning bounds derived using PAC-Bayes theory for improved generalization.
problem Uncertainty in generalization performance for meta-learning with new tasks.
method PAC-Bayes relative entropy bounds and empirical risk minimization (ERM) method.
result Competitive generalization performance and rapid convergence with data-dependent prior.
The Probably Approximately Correct (PAC) Bayes framework (McAllester, 1999) can incorporate knowledge about the learning algorithm and (data) distribution through the use of distribution-dependent priors, yielding tighter generalization bounds on data-dependent posteriors. Using this flexibility, however, is difficult,…
New algorithm achieves data-dependent regret bounds in MDPs with unknown transitions.
problem Achieving best-of-both-worlds guarantees with data-dependent regret bounds in MDPs with unknown transitions.
method Optimistic follow-the-regularized-leader algorithm with new optimistic Q-function estimators and transition bonus.
result First-order, second-order, and path-length bounds with polylog(T) regret in the stochastic regime.
ZNMF improves facial recognition performance using data-dependent penalties.
problem Facial recognition performance in the Cambridge ORL database.
method ZNMF uses data-dependent auxiliary constraints to modify NMF.
result ZNMF outperforms other constrained NMF algorithms in facial recognition.
Survey on new data-dependent bounds for neural networks.
problem Generalization of overparameterized neural networks.
method Extending PAC-Bayesian theory, refining complexity terms, and replacing information-theoretic terms with stability assumptions.
result Unified template inequality and comparison of bounds.
Fast robust subspace tracking in sparse data-dependent noise with near-optimal delay.
problem Robustly tracking time-varying subspaces in the presence of sparse outliers.
method Introduces a fast mini-batch robust ST solution under mild assumptions.
result Provably correct subspace tracking with near-optimal delay and same time complexity as simple PCA.
Reweighting improves risk bounds in certain data regions.
problem Improving risk bounds in classification and heteroscedastic regression.
method Weighted empirical risk minimization with a data-dependent weight function.
result A weighted ERM estimator can achieve superior performance in specific sub-regions.
We improve the robustness of Deep Neural Net (DNN) to adversarial attacks by using an interpolating function as the output activation. This data-dependent activation remarkably improves both the generalization and robustness of DNN. In the CIFAR10 benchmark, we raise the robust accuracy of the adversarially trained Res…
Enhances SDR via Hellinger correlation for better data dependency understanding.
problem Improving sufficient dimension reduction in single-index models.
method Developed a new method using Hellinger correlation for detecting the dimension reduction subspace.
result Significantly enhances and outperforms existing SDR methods through deeper data dependency understanding.
Paper establishes a generalization bound for gradient flow using a data-dependent kernel.
problem Understanding the generalization properties of gradient-based optimization methods.
method Establishes a generalization bound for gradient flow through a data-dependent kernel called the loss path kernel (LPK).
result The LPK captures the entire training trajectory and leads to tighter generalization guarantees.
In this paper, we consider the problem of prediction with expert advice in dynamic environments. We choose tracking regret as the performance metric and develop two adaptive and efficient algorithms with data-dependent tracking regret bounds. The first algorithm achieves a second-order tracking regret bound, which impr…
In this work, we improve upon the stepwise analysis of noisy iterative learning algorithms initiated by Pensia, Jog, and Loh (2018) and recently extended by Bu, Zou, and Veeravalli (2019). Our main contributions are significantly improved mutual information bounds for Stochastic Gradient Langevin Dynamics via data-depe…
This work obtains novel finite sample guarantees for Principal Component Analysis (PCA). These hold even when the corrupting noise is non-isotropic, and a part (or all of it) is data-dependent. Because of the latter, in general, the noise and the true data are correlated. The results in this work are a significant impr…
Framework evaluates privacy cost of non-private pre-processing in DP pipelines.
problem Privacy cost of non-private data-dependent pre-processing in DP machine learning pipelines.
method Establishes upper bounds on overall privacy guarantees using Smooth DP and bounded sensitivity.
result Explicit overall privacy guarantees for various pre-processing algorithms.
PriorGrad: Improving Conditional Denoising Diffusion Models with Data-Dependent Adaptive Priorstat.ML
PriorGrad improves speech synthesis models by using data-dependent adaptive priors.
problem Inefficiency in denoising diffusion models due to mismatch between prior and data distributions.
method Proposes PriorGrad, an adaptive prior derived from data statistics based on conditional information.
result PriorGrad achieves faster convergence and superior performance in speech synthesis models.
In this paper we bring to bear some new tools from statistical learning on the analysis of roll call data. We present a new data-driven model for roll call voting that is geometric in nature. We construct the model by adapting the "Partition Decoupling Method," an unsupervised learning technique originally developed fo…
The Adam algorithm has become extremely popular for large-scale machine learning. Under convexity condition, it has been proved to enjoy a data-dependant regret bound where is the time horizon. However, whether strong convexity can be utilized to further improve the performance remains an open problem…
Paper introduces new bounds linking data compressibility to generalization error.
problem Establishing data-dependent generalization bounds.
method Variable-size compressibility framework linking generalization error to compression rate of input data.
result New bounds depend on empirical data measure, subsuming existing PAC-Bayes and intrinsic dimension bounds.
In this paper, we consider the problem of recovering a graph that represents the statistical data dependency among nodes for a set of data samples generated by nodes, which provides the basic structure to perform an inference task, such as MAP (maximum a posteriori). This problem is referred to as structure learning. W…
New decentralized KRR algorithm adapts to node-specific data.
problem Consistent node-specific data in decentralized KRR.
method Data-dependent random features for adaptive RF generation.
result Average regression accuracy improved by 25.5% across six datasets.
Improved pruning method finds winning neural network subnetworks.
problem Finding a small subnetwork that performs as well as a full neural network.
method Data-dependent pruning criterion using gradient of training loss.
result Data-dependent pruning improves existing pruning algorithms.
We present algorithms for topic modeling based on the geometry of cross-document word-frequency patterns. This perspective gains significance under the so called separability condition. This is a condition on existence of novel-words that are unique to each topic. We present a suite of highly efficient algorithms based…
High-Dimensional Kernel Methods under Covariate Shift: Data-Dependent Implicit Regularizationstat.ML
The paper analyzes how re-weighting helps in reducing variance in high-dimensional kernel methods under covariate shifts.
problem The challenge of high-dimensional kernel methods under covariate shifts and the role of re-weighting.
method Derives asymptotic expansion of high-dimensional kernels under covariate shifts, analyzes bias-variance decomposition, and characterizes the regularized kernel.
result Re-weighting helps in decreasing variance and can be seen as a data-dependent regularization.
The randomized-feature approach has been successfully employed in large-scale kernel approximation and supervised learning. The distribution from which the random features are drawn impacts the number of features required to efficiently perform a learning task. Recently, it has been shown that employing data-dependent …
In this paper we analyze a budgeted learning setting, in which the learner can only choose and observe a small subset of the attributes of each training example. We develop efficient algorithms for ridge and lasso linear regression, which utilize the geometry of the data by a novel data-dependent sampling scheme. When …
In this dissertation we propose alternative analysis of distributed stochastic gradient descent (SGD) algorithms that rely on spectral properties of the data covariance. As a consequence we can relate questions pertaining to speedups and convergence rates for distributed SGD to the data distribution instead of the regu…
The study limits how many parts regular simplicial partitions can overlap.
problem Bounding the intersection number of regular simplicial partitions.
method Analyzing the properties of regular simplicial partitions.
result Established a maximum limit for the intersection number.
Algorithm provides online learning guarantees against general comparators in full and bandit feedback.
problem Adversarial online learning with data-dependent regret guarantees.
method Completely online algorithm with data-dependent regret guarantees for full and bandit feedback.
result Algorithm achieves expected performance against arbitrary comparator sequences in full and bandit feedback settings.
We establish a theoretical link between adversarial training and operator norm regularization for deep neural networks. Specifically, we prove that -norm constrained projected gradient ascent based adversarial training with an -norm loss on the logits of clean and perturbed inputs is equivalent to data-…