New framework converts offline to online estimation using black-box offline estimators.
problem Convert offline estimation algorithms to online estimation algorithms.
method Oracle-Efficient Online Estimation (OEOE) framework.
result Achieves near-optimal online estimation error via black-box offline estimators.
A genetic algorithm improves multivariate kernel density estimation.
problem Efficiently estimating multivariate kernel density functions.
method Genetic algorithm applied to subsamples of the original data.
result The genetic algorithm-based estimator performs better than traditional methods.
In this paper, a nonparametric maximum likelihood (ML) estimator for band-limited (BL) probability density functions (pdfs) is proposed. The BLML estimator is consistent and computationally efficient. To compute the BLML estimator, three approximate algorithms are presented: a binary quadratic programming (BQP) algorit…
New algorithm estimates treatment effects for more efficient contextual bandits.
problem Contextual bandits struggle with action-independent reward redundancies.
method Reduces contextual bandits to heterogeneous treatment effect estimation.
result Heterogeneous treatment effect estimation leads to more efficient model estimation.
Develops a novel stochastic algorithm for diagonal estimation of large matrices.
problem Efficient diagonal estimation for large or implicit matrices.
method Adaptive parameter selection in a stochastic algorithm.
result Lower bound on random query vectors needed for estimation.
Polynomial-time private algorithm for robust estimation of mean and covariance in the presence of outliers.
problem Estimating mean and covariance in the presence of adversarial outliers.
method Stabilizing convex relaxations using a new estimate-dependent noise injection mechanism.
result First efficient private robust estimation algorithm for covariance without condition-number assumptions.
The paper develops a new algorithm for constructing minimax estimators using online learning techniques.
problem Designing minimax estimators for probability distribution parameters.
method Viewing the problem as a zero-sum game and using online learning with non-convex losses to find a Nash equilibrium.
result The algorithm constructs both a minimax estimator and a least favorable prior.
Estimates funding impact from an algorithmic relief rule, finding little effect on hospital activities.
problem Evaluating the impact of algorithmic policy decisions.
method Developed a treatment-effect estimator using algorithmic decisions as instruments.
result Funding from an algorithmic relief rule had little effect on COVID-19-related hospital activities.
A significant hurdle for analyzing large sample data is the lack of effective statistical computing and inference methods. An emerging powerful approach for analyzing large sample data is subsampling, by which one takes a random subsample from the original full sample and uses it as a surrogate for subsequent computati…
Paper proposes robust gossip algorithms for mean and trimmed mean estimation.
problem Vulnerability of mean-based gossip algorithms to malicious nodes.
method Developed extsc{GoRank} for rank estimation and extsc{GoTrim} for trimmed mean estimation.
result Established convergence rates for rank and trimmed mean estimation.
Quantum algorithm estimates multivariate mean with near-optimal efficiency.
problem Estimating the mean of multivariate random variables efficiently in quantum computing.
method Combines amplitude amplification, quantum singular value transformation, and Bernstein-Vazirani algorithm.
result Quantum estimator outperforms classical estimators outside low-precision regime.
Two EM algorithms estimate prior distributions in mixture of linear regressions.
problem Estimating prior distributions in mixture of linear regressions.
method Two EM algorithms: one for continuous priors, one for discrete priors.
result Both algorithms accurately estimate prior distributions and the number of clusters.
OPAA estimates probability densities using functional analysis.
problem Estimating probability density functions efficiently and accurately.
method OPAA uses a parallelizable algorithm based on functional analysis to estimate probability distributions.
result OPAA provides an efficient method to estimate probability density functions and normalizing weights.
Paper proposes diagnostics for error and variance estimation in randomized matrix computations.
problem Safe use of randomized matrix algorithms in applications.
method Leave-one-out error estimator and jackknife resampling method.
result Provides rapid diagnostics to assess quality of randomized matrix computations.
New algorithm improves matrix estimation with one-sided covariates.
problem Estimating matrix means with unobserved row covariates.
method Proposes an algorithm for nonparametric matrix estimation with observed column covariates.
result Achieves minimax optimal nonparametric rate in moderately proportioned matrices.
Learning in the presence of outliers is a fundamental problem in statistics. Until recently, all known efficient unsupervised learning algorithms were very sensitive to outliers in high dimensions. In particular, even for the task of robust mean estimation under natural distributional assumptions, no efficient algorith…
Robust estimation methods find global minima efficiently via quasi-gradients.
problem Efficiently solving robust estimation problems with non-convex optimization.
method Identifying generalized quasi-gradients to guarantee low-regret algorithms.
result Generalized quasi-gradients ensure efficient approximation of global minima.
Quantum algorithm speeds up Gibbs partition function estimation.
problem Estimating partition functions in sublinear time.
method Sublinear-time quantum algorithm using quantum phase and amplitude estimation.
result First sublinear-time speed-up for partition function estimation.
OEUVRE estimates online loss with constant time and memory, outperforming other methods.
problem Accurately estimating expected loss in online learning.
method Recursive evaluation of each sample on current and previous models, using algorithmic stability for updates.
result Consistency, convergence rates, and concentration bounds proved for OEUVRE.
New algorithms estimate matrix leverage scores using rank revealing and randomization.
problem Estimating leverage scores for matrices of arbitrary rank.
method Combining rank revealing methods with randomized dimensionality reduction.
result Effective estimators for leverage scores, even in rank deficient cases.
Paper proposes a new method for estimating mixture proportions without irreducibility assumption.
problem Estimating mixture proportions when component distributions are not irreducible.
method Developed a resampling-based meta-algorithm that adapts existing MPE algorithms to non-irreducible settings.
result Empirical results show improved estimation performance compared to baseline methods and regrouping-based algorithms.
This is a technical report which explores the estimation methodologies on hyper-parameters in Markov Random Field and Gaussian Hidden Markov Random Field. In first section, we briefly investigate a theoretical framework on Metropolis-Hastings algorithm. Next, by using MH algorithm, we simulate the data from Ising model…
New algorithm reduces runtime for robust sparse mean estimation.
problem Efficiently estimating mean from corrupted data with sparse constraints.
method Subquadratic time algorithm using poly(k, log d, 1/ε) samples.
result First subquadratic time algorithm for robust sparse mean estimation.
A method for efficient statistical inference from online algorithms.
problem Computational constraints in online algorithms make traditional variance estimation difficult.
method HulC method that wraps around online algorithms to produce valid confidence regions.
result The HulC method produces asymptotically valid confidence regions for online algorithms.
Proposes a new method for kernel density estimation using stagewise minimization and a simple dictionary.
problem Kernel density estimation with data-adaptive weighting parameters and sparse representation.
method Stagewise minimization algorithm based on U-divergence and a simple dictionary. result Develops non-asymptotic error bound for the proposed estimator.
New collaborative algorithm improves personalized mean estimation in online settings.
problem Online estimation of means from multiple, possibly overlapping distributions.
method Novel collaborative strategy for active querying and mean estimation.
result Algorithm improves mean estimates through communication among agents.
Algorithm finds frequencies, amplitudes, and phases of sinusoids in noisy data.
problem Finding frequencies, amplitudes, and phases of sinusoids in noisy data.
method Maximum likelihood approach to estimate tone parameters from contaminated observations. Successively estimates frequencies and jointly optimizes amplitudes and phases.
result Near-linear computational complexity (O(N)) for estimating M number of sinusoidal sources. New spectral algorithm estimates random graph parameters robustly against corrupted nodes.
problem Estimating the parameter of an Erdős-Rényi random graph with adversarial corruption.
method Spectral algorithm designed for computational efficiency, with an inefficient but information-theoretic alternative.
result Achieves optimal error rate up to logarithmic factors, matching statistical lower bounds.
Examines WENDy-IRLS algorithm's noise robustness and efficiency in various differential equations.
problem Noise robustness and efficiency of WENDy-IRLS algorithm.
method Studied coverage and bias properties of WENDy-IRLS algorithm's estimators in various differential equations and noise distributions.
result WENDy-IRLS algorithm shows notable noise robustness and computational efficiency.
The paper extends NUP representations to factor graphs for better estimation.
problem Nontrivial model-based estimation problems.
method Augmenting factor graphs with convex-dual variables and NUP representations; proposing a new iterative algorithm.
result A new dual algorithm for state space problems.
New algorithms improve Gaussian mixture model estimation in DFL with heterogeneous data.
problem Bias in EM algorithm for Gaussian mixtures in DFL with heterogeneous data.
method MNEM and semi-MNEM algorithms integrating historical and partially labeled data.
result MNEM and semi-MNEM achieve asymptotic efficiency and improved convergence.
Paper introduces a new gradient estimator for SNNs.
problem High variance in score function gradient estimator impedes SNNs training.
method Developed a differentiable point process to derive path-wise gradient estimator.
result Demonstrated effectiveness of path-wise gradient estimator through simulations.
Algorithm performance in supervised learning is a combination of memorization, generalization, and luck. By estimating how much information an algorithm can memorize from a dataset, we can set a lower bound on the amount of performance due to other factors such as generalization and luck. With this goal in mind, we int…
Develops a computationally tractable high-dimensional differential privacy estimator.
problem Differential privacy in high dimensions is computationally intractable.
method Combines high-dimensional robust statistics with differential privacy techniques.
result A computationally tractable algorithm with dimension-independent privacy loss.
We present nonparametric algorithms for estimating optimal individualized treatment rules. The proposed algorithms are based on the XGBoost algorithm, which is known as one of the most powerful algorithms in the machine learning literature. Our main idea is to model the conditional mean of clinical outcome or the decis…
Private KL distribution estimation improved with instance-optimality.
problem Minimizing KL divergence between true and estimated distributions.
method Construct minimax optimal private estimators, then focus on instance-optimality.
result Achieved instance-optimality up to constant factors for KL estimation.
Software development effort estimation is considered a fundamental task for software development life cycle as well as for managing project cost, time and quality. Therefore, accurate estimation is a substantial factor in projects success and reducing the risks. In recent years, software effort estimation has received …
For massive data, the family of subsampling algorithms is popular to downsize the data volume and reduce computational burden. Existing studies focus on approximating the ordinary least squares estimate in linear regression, where statistical leverage scores are often used to define subsampling probabilities. In this p…
Polynomial-time algorithm estimates edge density of random graphs with privacy and robustness.
problem Estimating edge density of random graphs while maintaining privacy and robustness.
method Sum-of-squares algorithm for robust edge density estimation and reduction from privacy to robustness.
result Optimal error rate up to logarithmic factors, matching theoretical lower bounds.
A new method reduces complexity in estimating dynamic choice models.
problem Estimating structural parameters in dynamic discrete choice models using behavioral data.
method Two-stage approach: inverse reinforcement learning for Q-function estimation, state selection via clustering, and maximum likelihood estimation with nested fixed-point algorithm.
result The method mitigates the curse of dimensionality and provides finite-sample bounds on estimation error.
This work addresses the issue of large covariance matrix estimation in high-dimensional statistical analysis. Recently, improved iterative algorithms with positive-definite guarantee have been developed. However, these algorithms cannot be directly extended to use a nonconvex penalty for sparsity inducing. Generally, a…
New algorithms improve robust estimation in contaminated Gaussian models.
problem Simultaneous estimation of location and variance matrix in contaminated Gaussian models.
method Tractable adversarial algorithms with spline discriminators for robust estimation.
result Achieve minimax optimal rates or near-optimal rates under Huber's contamination model.
An algorithm estimates the mean of a process from noisy, online sensor data.
problem Estimating the mean of a process from noisy, online sensor data with some sensors behaving maliciously.
method An efficient online algorithm that produces estimates as data comes in, achieving nearly competitive error bounds.
result The algorithm can compute a good approximation to the true mean with error bounds of O(δlog(T)). Efficiently estimates Gaussian distributions privately and robustly.
problem Private and robust estimation of Gaussian distributions.
method Efficient algorithms for pure and approximate differential privacy models.
result Optimal sample complexity in both pure and approximate differential privacy settings.
New algorithms robustly estimate mean with near-optimal error rates.
problem Outlier robust mean estimation in high-dimensional data.
method Stability condition and iterative filtering algorithms.
result Optimal error rates with subgaussian rates for robust mean estimation.
The EM algorithm is a novel numerical method to obtain maximum likelihood estimates and is often used for practical calculations. However, many of maximum likelihood estimation problems are nonconvex, and it is known that the EM algorithm fails to give the optimal estimate by being trapped by local optima. In order to …
This paper considers the problem of robustly estimating a structured covariance matrix with an elliptical underlying distribution with known mean. In applications where the covariance matrix naturally possesses a certain structure, taking the prior structure information into account in the estimation procedure is benef…
New algorithms estimate matrix norms without matrix multiplication.
problem Estimating matrix norms efficiently in a matrix-free setting.
method Randomized algorithms based on Hutchinson's estimator modifications.
result Oracle complexity bounds for two-to-infinity and one-to-two norms.