Spectral ranking methods are improved against semi-random graph sampling.
problem Improving spectral ranking methods in semi-random graph sampling.
method Investigating entry-wise error of spectral algorithms against a semi-random adversary.
result Asymptotic performance can be recovered by reweighting observed edges.
Paper tackles ranking items with a semi-random comparison graph and a monotone adversary.
problem Ranking items based on pairwise comparisons from a semi-random comparison graph with a monotone adversary.
method Developed a weighted maximum likelihood estimator (MLE) and an SDP-based approach to reweight the semi-random graph.
result Achieves near-optimal sample complexity, up to a log^2(n) factor, for identifying the top-K preferred items.
We propose semi-random features for nonlinear function approximation. The flexibility of semi-random feature lies between the fully adjustable units in deep learning and the random features used in kernel methods. For one hidden layer models with semi-random features, we prove with no unrealistic assumptions that the m…
Matrix completion is a well-studied problem with many machine learning applications. In practice, the problem is often solved by non-convex optimization algorithms. However, the current theoretical analysis for non-convex algorithms relies heavily on the assumption that every entry is observed with exactly the same pro…
KSS method converges and recovers correct clustering under certain conditions.
problem Subspace clustering for semi-randomly sampled data.
method Local convergence analysis and recovery guarantee for KSS method.
result KSS method converges superlinearly and finds correct clustering within loglog N iterations.
New method robust to semi-random sparse recovery, nearly-linear time.
problem Brittleness of fast sparse recovery algorithms under generative model changes.
method Designing a new iterative method robust to semi-random model.
result Proves robustness of new method to semi-random generative models.
We consider the problem of estimating the discrete clustering structures under the Sub-Gaussian Mixture Model. Our main results establish a hidden integrality property of a semidefinite programming (SDP) relaxation for this problem: while the optimal solution to the SDP is not integer-valued in general, its estimation …
Several recent works have shown that state-of-the-art classifiers are vulnerable to worst-case (i.e., adversarial) perturbations of the datapoints. On the other hand, it has been empirically observed that these same classifiers are relatively robust to random noise. In this paper, we propose to study a \textit{semi-ran…
This work proposes a non-iterative strategy for missing value imputations which is guided by similarity between observations, but instead of explicitly determining distances or nearest neighbors, it assigns observations to overlapping buckets through recursive semi-random hyperplane cuts, in which weighted averages are…
Efficient exploration is an unsolved problem in Reinforcement Learning which is usually addressed by reactively rewarding the agent for fortuitously encountering novel situations. This paper introduces an efficient active exploration algorithm, Model-Based Active eXploration (MAX), which uses an ensemble of forward mod…
Improved SGD for robust linear and ReLU regression with adversarial corruptions.
problem Robust regression with adversarial corruptions in streaming data.
method Stochastic gradient descent (SGD-exp) with exponentially decaying step size.
result Nearly linear convergence to true parameter with up to 50% Massart corruption rate.
Efficient algorithm detects communities in noisy graphs with robustness.
problem Community detection in stochastic block models with adversarial corruptions.
method Efficient algorithm using semidefinite programming for robust clustering.
result Achieves error O(ε)+e−2C(1±o(1)) for ε-fraction of corruptions. Study on ReLU regression with Massart noise, achieving exact parameter recovery.
problem Efficiently fitting ReLUs to data in the presence of Massart noise.
method Developed an efficient algorithm for exact parameter recovery under mild assumptions.
result Achieved exact parameter recovery in ReLU regression with Massart noise.
Graph clustering involves the task of dividing nodes into clusters, so that the edge density is higher within clusters as opposed to across clusters. A natural, classic and popular statistical setting for evaluating solutions to this problem is the stochastic block model, also referred to as the planted partition model…
Metric learning is a key problem for many data mining and machine learning applications, and has long been dominated by Mahalanobis methods. Recent advances in nonlinear metric learning have demonstrated the potential power of non-Mahalanobis distance functions, particularly tree-based functions. We propose a novel non…
Paper improves ℓ0-SSC for noisy data by proving SDP and proposing Noisy-DR-ℓ0-SSC.
problem Noisy data and less restrictive subspace affinity in sparse subspace clustering.
method Proposes Noisy-DR-ℓ0-SSC, which projects data onto a lower dimensional space and then applies noisy ℓ0-SSC. result Theoretical guarantee on the correctness of noisy ℓ0-SSC in terms of SDP on noisy data. This paper improves linear system solving by optimizing matrix diagonal scaling.
problem Improving the condition number of a matrix for faster iterative methods.
method Left or right diagonal rescaling of the matrix A, with new bounds and algorithms.
result Jacobi preconditioning reduces A's condition number to within a quadratic factor of the best possible scaling.
New formula refutes random CSPs with fewer constraints.
problem Refuting random constraint satisfaction problems efficiently.
method Introduced a non-backtracking matrix and proved an Ihara-Bass formula.
result Efficiently refutes random CSPs with fewer constraints.
Enhanced Sampling Scheme improves masked generative modeling.
problem Limitations of existing sampling schemes in masked non-autoregressive generative modeling.
method ESS consists of three stages: Naive Iterative Decoding, Critical Reverse Sampling, and Critical Resampling.
result ESS achieves significant performance gains in unconditional and class-conditional sampling.
PRS improves rejection sampling by learning better proposals.
problem High rejection rate in traditional rejection sampling.
method PRS uses a kernel estimator to learn better sampling proposals.
result PRS guarantees a low number of accepted samples.
This paper reviews various sampling methods from statistics and machine learning.
problem Addressing sampling methods in statistics and machine learning.
method Explains and reviews simple random sampling, bootstrapping, stratified sampling, cluster sampling, multistage sampling, network sampling, snowball sampling, and sampling from cumulative distribution function.
result Summarizes characteristics, pros, and cons of different sampling methods.
RISA improves VFL by using imputed samples with low uncertainty.
problem Limited overlapping samples constrain VFL performance.
method Imputing non-overlapping samples and using evidence theory to select reliable imputed samples.
result Significant performance gains achieved, especially with limited overlapping samples.
Improved privacy-preserving methods for estimating multiple samples from distributions.
problem Estimating multiple samples from distributions while maintaining privacy.
method Developed new multi-sampling techniques for differentially private data estimation.
result Achieved significant reduction in sample complexity for multi-sampling from finite domains and Gaussian distributions.
Paper introduces a new sampling method combining Consistency Models with importance sampling.
problem Inherent errors in samples and high NFEs for high-quality samples in Boltzmann distributions.
method Combines Consistency Models with importance sampling to produce unbiased samples with minimal NFEs.
result Produces unbiased samples using only 6-25 NFEs, comparable to 100 NFEs for DDPMs.
Neural network accuracy improves with denser training samples.
problem Improving neural network accuracy on unseen test samples.
method Bounding empirical training error smoothed across activation regions and using it to discard high-risk test samples.
result Discarding high-risk test samples based on error bounds improves prediction accuracy by up to 20%.
Wedge Sampling improves tensor completion with nearly-linear sample complexity.
problem Efficiently completing low-rank tensors from a subset of entries.
method Non-adaptive wedge sampling to promote structured connections in tensor completion.
result Polynomial-time algorithms achieve weak and exact recovery with nearly linear sample complexity.
Algorithm samples constrained stochastic differential equations.
problem Sampling stochastic differential equations with complex constraints.
method Pathspace Metropolis-adjusted manifold sampling.
result Demonstrated effectiveness in various constrained conditions.
In modern data analysis, random sampling is an efficient and widely-used strategy to overcome the computational difficulties brought by large sample size. In previous studies, researchers conducted random sampling which is according to the input data but independent on the response variable, however the response variab…
Generative models map simple samples to complex target samples.
problem Improving Monte-Carlo sampling techniques.
method Variational learning of dynamical maps between base and target measures.
result Improved sampling efficiency through feedback loops.
Sampling is a fundamental problem in computer science and statistics. However, for a given task and stream, it is often not possible to choose good sampling probabilities in advance. We derive a general framework for adaptively changing the sampling probabilities via a collection of thresholds.In general, adaptive samp…
New sampling algorithm for non-smooth potentials.
problem Sampling from non-smooth potentials.
method Proximal algorithm based on rejection sampling.
result Achieves better complexity than existing methods.
Efficiently samples sequences without replacement for machine learning models.
problem Generating diverse outputs from sequential models without duplicates.
method Incremental sampling procedure for randomized programs, including neural models.
result Efficacy and flexibility of incremental sampling for large output spaces.
Ensemble sampling approximates Thompson sampling for complex models.
problem Computational intractability of exact posterior distributions.
method Thompson sampling approximation with information-theoretic concepts.
result Established a first rigorous regret bound for ensemble sampling.
Optimizes biomolecular simulations by ranking adaptive sampling policies.
problem Efficiently sampling biomolecular systems to capture complex dynamical behaviors.
method Metric-driven ranking of adaptive sampling policies to identify the optimal policy for each round.
result Different adaptive sampling policies lead to faster convergence and improved sampling performance.
Optimizes sample and round complexity in adaptive sampling from multiple distributions.
problem Adaptive sampling from multiple distributions with limited rounds and samples.
method Introduces OODS framework and analyzes tradeoffs between sample and round complexity.
result Achieves near-optimal sample complexity and sub-polynomial round complexity.
Meta-learners improve causal effect estimation in small samples.
problem Estimating causal effects using machine learning methods.
method Sample-splitting and cross-fitting to reduce overfitting bias.
result Meta-learners' performance depends on sample size and estimation procedure.
REP-GAN improves GANs by reparameterizing proposals for better sample quality and efficiency.
problem Poor sample efficiency in GANs due to independent proposal sampling.
method REParameterizing Markov chains into the latent space of the generator to create dependent proposals.
result Empirically shows significant improvement in sample efficiency and quality.
Unified framework for model-based RL with sample complexity guarantees.
problem Designing efficient posterior sampling methods for model-based RL.
method Optimistic posterior sampling, Hellinger distance reduction, data likelihood measurement.
result Unified algorithms with state-of-the-art sample complexity guarantees.
Proposes a neural network method to combine nonprobability and probability survey samples.
problem Combining nonprobability and probability survey samples for accurate population mean estimation.
method Uses a deep neural network to estimate sampling scores from nonprobability samples and combines them with probability sample information.
result Proposed estimators improve robustness to parametric propensity-score misspecification, especially for nonlinear selection mechanisms.
Dynamic Influence Tracker measures changing sample importance during model training.
problem Static influence measurements during training overlook how sample importance varies over time.
method Dynamic Influence Tracker (DIT) captures time-varying sample influence across arbitrary time windows.
result DIT reveals distinct learning phases with shifting priorities and detects corrupted samples more efficiently.
New sampling methods improve classifier performance estimation.
problem Efficiently selecting data points to estimate classifier performance.
method Introduced and compared Importance Sampling and Poisson Sampling.
result Poisson Sampling outperforms Importance Sampling.
Optimized sampling scheme for compressed sensing combining randomness and determinism.
problem Improving compressed sensing performance with deterministic sampling.
method Optimized sampling scheme combining random and deterministic selection of rows.
result Measurable improvements in image compressed sensing for generative and sparse priors.
Predictive sampling improves on Thompson sampling for non-stationary bandit environments.
problem Thompson sampling fails in non-stationary bandit environments.
method Proposes predictive sampling, which deprioritizes actions based on information loss rate.
result Predictive sampling outperforms Thompson sampling in all tested non-stationary environments.
Algorithm samples from Bingham distribution efficiently.
problem Sampling from the Bingham distribution on a sphere.
method Rejection sampling with polynomial approximation.
result Exact samples from Bingham distribution in polynomial time.
Self-taught learning is a technique that uses a large number of unlabeled data as source samples to improve the task performance on target samples. Compared with other transfer learning techniques, self-taught learning can be applied to a broader set of scenarios due to the loose restrictions on the source data. Howeve…
A new algorithm for sampling from complex distributions.
problem Sampling from high-dimensional multivariate probability densities.
method Combines kernel herding and Gibbs sampling for deterministic sampling.
result Significantly lower computation time compared to kernel herding.
Efficiently tests two distributions with few label queries.
problem Two-sample test with limited label information.
method Three-stage framework: classifier training, bimodal query, FR test.
result Significantly reduces Type II error compared to uniform querying.
A new graph-based sampling method improves classification of imbalanced COVID-19 datasets.
problem Classification of imbalanced COVID-19 datasets.
method Modified Random Walk Under-sampling based on graphs.
result The method increases the boundary of the minority class without raising outliers.