Many real datasets contain values missing not at random (MNAR). In this scenario, investigators often perform list-wise deletion, or delete samples with any missing values, before applying causal discovery algorithms. List-wise deletion is a sound and general strategy when paired with algorithms such as FCI and RFCI, b…
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 “Randomized Deletion”
DaRE forests enable efficient data deletion from random forests.
problem Efficiently removing data from machine learning models.
method Random Forests with data deletion enabled (DaRE).
result Data deletion from DaRE models is orders of magnitude faster than retraining.
RS-Del provides robustness for sequence classifiers against edit distance attacks.
problem Certifying robustness of discrete sequence classifiers against edit distance attacks.
method Randomized deletion (RS-Del) for discrete sequence classifiers, focusing on edit distance-bounded adversaries.
result Achieved a certified accuracy of 91% at an edit distance radius of 128 bytes on malware detection.
A well-known problem in data science and machine learning is {\em linear regression}, which is recently extended to dynamic graphs. Existing exact algorithms for updating the solution of dynamic graph regression require at least a linear time (in terms of : the size of the graph). However, this time complexity might…
The paper compares two methods for handling missing data in causal discovery.
problem Handling missing data in causal discovery algorithms.
method Test-wise deletion and multiple imputation.
result Multiple imputation is more challenging for causal discovery than for estimation.
New approach protects privacy of deleted records in machine learning.
problem Privacy of deleted records in machine learning models.
method Sound deletion guarantee and noisy gradient descent algorithm.
result Privacy of existing records is necessary for deleted records' privacy.
New algorithm for maximizing submodular functions in real-time data changes.
problem Maximizing submodular functions under dynamic constraints.
method Randomized algorithm with amortized update time.
result 4-approximate solution to submodular maximization problem.
Paper tackles adaptive deletion of data points from trained models.
problem Adaptive deletion of data points from trained models.
method Reduction from adaptive to non-adaptive deletion guarantees using differential privacy and max information.
result Strong provable deletion guarantees for adaptive deletion sequences.
This research tackles data deletion in linear regression with noisy SGD, finding perfect deleted points.
problem Finding points to delete from a dataset without significantly affecting the training result.
method Signal-to-noise ratio and an algorithm based on it.
result The perfect deleted point is crucial for maintaining model performance and privacy budget.
We propose the Insertion-Deletion Transformer, a novel transformer-based neural architecture and training method for sequence generation. The model consists of two phases that are executed iteratively, 1) an insertion phase and 2) a deletion phase. The insertion phase parameterizes a distribution of insertions on the c…
Efficient algorithms for deleting data from machine learning models without significantly affecting performance.
problem Deleting data from machine learning models while maintaining performance.
method Leveraging convex optimization and reservoir sampling, the paper introduces algorithms for handling long sequences of adversarial updates.
result First data deletion algorithms that promise steady-state error not growing with the length of the update sequence.
Paper proposes a fast method for approximate data deletion in generative models.
problem Efficient data deletion in unsupervised learning models is an open problem.
method Density-ratio-based framework for generative models, fast method for approximate data deletion, statistical test.
result Theoretical guarantees and empirical demonstrations of the proposed methods across various generative models.
New method for efficiently deleting data from ML models.
problem Efficiently removing data from trained ML models without retraining.
method Approximate deletion method for linear and logistic models.
result Significantly faster than existing methods, with linear time dependence on feature dimension.
Study on deleting user data in linear regression models to maintain limited memory.
problem Deleting user data in a limited time frame for statistical models.
method Proposed FIFD-OLS and FIFD-Adaptive Ridge algorithms for low-dimensional and online settings.
result Demonstrated effectiveness of FIFD-Adaptive Ridge in maintaining statistical efficiency.
Study on tensor signal estimation from incomplete data.
problem Estimating a rank-one tensor signal from noisy, incomplete data.
method Reduction to random matrix model for spectral analysis.
result Loss of performance due to incomplete data.
The paper develops algorithms to find a robust summary of data under deletion, achieving good approximation guarantees.
problem Finding a summary of data that remains valuable even after some elements are deleted.
method Constant-factor approximation algorithms for deletion robust submodular maximization under matroid constraints.
result The algorithms provide good approximation guarantees for both centralized and streaming settings.
New formulas for feature importance tests in regression models.
problem Identifying important features in regression models.
method Established formulas for AUC criteria and proposed alternative metrics.
result Integrated Gradients (IG) performs nearly as well as Kernel SHAP (KS) but is faster.
With a sharp rise in fluency and users of "Hinglish" in linguistically diverse country, India, it has increasingly become important to analyze social content written in this language in platforms such as Twitter, Reddit, Facebook. This project focuses on using deep learning techniques to tackle a classification problem…
New examples show deletion type admissible pairs can be rigid under rational saturation.
problem Rigidity of admissible pairs of rational homogeneous spaces of Picard number one.
method Application of Mok's general criterion for non-subdiagram type admissible pairs.
result Examples of deletion type admissible pairs are rigid under rational saturation.
ID-ExpO fine-tunes neural networks for more faithful explanations.
problem Improving the faithfulness of explanations for complex machine learning models.
method Differentiable insertion/deletion metric-aware regularizers for optimization.
result Fine-tuned predictors produce more faithful explanations.
We observe the effects of the three different events that cause spread changes in the order book, namely trades, deletions and placement of limit orders. By looking at the frequencies of the relative amounts of price changing events, we discover that deletions of orders open the bid-ask spread of a stock more often tha…
Deleting an edge of a 3-cycle in an intrinsically knotted graph gives an intrinsically linked graphmath.CO
We show that deleting an edge of a 3-cycle in an intrinsically knotted graph gives an intrinsically linked graph.
Intense recent discussions have focused on how to provide individuals with control over when their data can and cannot be used --- the EU's Right To Be Forgotten regulation is an example of this effort. In this paper we initiate a framework studying what to do when it is no longer permissible to deploy models derivativ…
The paper tackles robust submodular maximization under matroid constraints, providing approximation algorithms for summary extraction.
problem Maximizing submodular functions while ensuring high value even after deletions.
method Constant-factor approximation algorithms for centralized and streaming settings, considering both non-monotone and monotone objectives.
result Approximation algorithms with space complexity depending on matroid rank and deleted elements, achieving improved factors in monotone cases.
Linear filtration helps delete training data from models.
problem Deleting training data from models when individuals request it.
method Linear filtration as a computationally efficient sanitization method.
result Demonstrates benefits in an adversarial setting over naive deletion schemes.
We use a variation on the commutator collection process to characterize those pure braids which become trivial when any one strand is deleted, or, more generally, those pure braids which become trivial when all the strands in any one of a list of sets of strands is deleted.
Graph pruning improves neural network performance by addressing squashing and smoothing issues.
problem Over-squashing and over-smoothing in Graph Neural Networks.
method Proposes edge deletions to simultaneously address over-squashing and over-smoothing, optimizing spectral gap.
result Edge deletions improve generalization and distinguishability of nodes of different classes.
Gordon and Litherland showed that all compact, unoriented, possibly non-orientable surfaces in bounded by a link are realted by attaching/deleting tubes and half twisted bands. In this note we give an elementary proof for this result.
The configuration space of ordered pairs of distinct points in a manifold , also known as the deleted square of , is not a homotopy invariant of : Longoni and Salvatore produced examples of homotopy equivalent lens spaces and of dimension three for which and are not homoto…
Proposes a new jackknife method for time series hyperparameter selection.
problem Hyperparameter selection for time series models.
method Artificial delete-d jackknife approach.
result Asymptotic and finite-sample advantages demonstrated.
We propose a framework for verifying data deletion in MLaaS systems.
problem Ensuring compliance with data deletion requests in MLaaS systems.
method Formal framework based on hypothesis testing, novel backdoor-based verification mechanism.
result Demonstrated high confidence in certifying data deletion with minimal impact on ML service accuracy.
New graph shows edge deletion/contraction doesn't always result in intrinsically linked graphs.
problem Edge operations in intrinsically knotted graphs don't always produce intrinsically linked graphs.
method Presented a new intrinsically knotted graph.
result Edge operations in intrinsically knotted graphs don't always result in intrinsically linked graphs.
Network representation learning in low dimensional vector space has attracted considerable attention in both academic and industrial domains. Most real-world networks are dynamic with addition/deletion of nodes and edges. The existing graph embedding methods are designed for static networks and they cannot capture evol…
New algorithms delete user data from machine learning models efficiently.
problem Deleting user data from machine learning models trained with empirical risk minimization.
method Developed an online unlearning algorithm using the infinitesimal jackknife, targeting non-smooth regularizers.
result Empirically improved runtime while maintaining memory requirements and test accuracy.
Second-order optimizers retain residual information after data deletion, affecting machine unlearning.
problem Residual information in second-order optimizers after data deletion.
method Comparison of first-order and second-order learners, eigendecomposition analysis.
result Second-order optimizers retain residual information, not detectable by first-order analysis.
We investigate the problem of reliable communication between two legitimate parties over deletion channels under an active eavesdropping (aka jamming) adversarial model. To this goal, we develop a theoretical framework based on probabilistic finite-state automata to define novel encoding and decoding schemes that ensur…
Efficiently clusters incomplete data without imputation or full EM, faster and more accurate.
problem Clustering partially recorded data efficiently.
method Model-based approach using multivariate t-distributions, considering only observed values.
result Approach is more accurate and computationally efficient than alternatives.
Efficiently adds or deletes data in GBDT models.
problem Traditional GBDT training requires all data to be accessed simultaneously, limiting add/delete operations.
method Proposes an online learning framework for GBDT supporting incremental and decremental learning.
result First work to unify incremental and decremental learning on GBDT in-place.
Applications in machine learning, optimization, and control require the sequential selection of a few system elements, such as sensors, data, or actuators, to optimize the system performance across multiple time steps. However, in failure-prone and adversarial environments, sensors get attacked, data get deleted, and a…
Graphs can be fooled by small edge changes, but this work protects them.
problem Adversaries can manipulate graph data to mislead graph classification models.
method We introduce a smoothed graph classification model with a robustness guarantee.
result The smoothed model maintains consistent predictions under small adversarial perturbations.
New algorithms reduce matching market regret to log(T) with improved stability.
problem Minimizing regret in two-sided matching markets with bandit feedback.
method Phase-based algorithm with local arm deletion to improve stability.
result Achieves Θ(log(T)) regret for markets with uniqueness consistency.
Neural sequence-to-sequence models, particularly the Transformer, are the state of the art in machine translation. Yet these neural networks are very sensitive to architecture and hyperparameter settings. Optimizing these settings by grid or random search is computationally expensive because it requires many training r…
New framework to test neural network representation similarity measures.
problem Disagreements among dissimilarity measures in neural networks.
method Statistical testing framework to evaluate measures based on functional behavior.
result Current metrics have different weaknesses; a classical baseline performs surprisingly well.
Jackknife variance estimation validated for generalized U-statistics.
problem Uncertainty quantification for subsampling-based estimators.
method Jackknife variance estimation for generalized U-statistics with row-wise weak law.
result Jackknife and delete- variance estimators are ratio-consistent for generalized U-statistics.
We introduce agents that use object-oriented reasoning to consider alternate states of the world in order to more quickly find solutions to problems. Specifically, a hierarchical controller directs a low-level agent to behave as if objects in the scene were added, deleted, or modified. The actions taken by the controll…
New framework for consistent submodular maximization with insertions and deletions.
problem Maintaining near-optimal solutions in a dynamic setting with insertions and deletions.
method Developed a general framework for fully dynamic submodular maximization, instantiated for cardinality and rank-k matroid constraints.
result First constant-factor approximations with sublinear consistency for both cardinality and rank-k matroid constraints.
Bayesian models can be tricked into believing false data.
problem Vulnerability of Bayesian inference to data poisoning attacks.
method Developed attacks to manipulate Bayesian posterior through deletion and replication of data.
result Demonstrated that Bayesian inference can be steered to target distributions.
We propose an approach for approximating the partition function which is based on two steps: (1) computing the partition function of a simplified model which is obtained by deleting model edges, and (2) rectifying the result by applying an edge-by-edge correction. The approach leads to an intuitive framework in which o…