Lower bounds on private estimation of Gaussian covariance matrices.
problem Private estimation of Gaussian covariance matrices under various parameter regimes.
method Stein-Haff identity and fingerprinting lemma extensions.
result Lower bounds match existing upper bounds in the widest known parameters.
Simple bounds for covariance and Gram matrices across various settings.
problem Capturing the behavior of smaller eigenvalues in covariance and Gram matrices.
method General-purpose theorem converting uniform bounds into relative bounds.
result Sharper control of eigenvalues across the spectrum.
New lower bounds for private covariance estimation of Gaussian distributions are proven.
problem Proving tight lower bounds for private estimation tasks under differential privacy.
method Generalized fingerprinting method for exponential families and private Assouad method.
result Tight lower bounds for private covariance estimation in Frobenius and spectral norms.
Study semi-supervised learning with noisy proxy covariates, deriving bounds and showing gains.
problem Learning from noisy proxy covariates with scarce labels.
method Two-stage estimator learning kernel eigenfeatures from all proxy covariates and fitting a ridge predictor on labeled data.
result Finite sample bounds show fast labeled sample rates and consistent gains over supervised and semi-supervised baselines.
Dynamic pricing algorithms can work with covariates without i.i.d. assumptions.
problem Dynamic pricing with covariates under a generalized linear demand model.
method UCB and Thompson sampling-based pricing algorithms.
result Achieves an O ( d T log T ) O(d\sqrt{T}\log T) O ( d T log T ) regret upper bound without i.i.d. covariates assumption. Robustly estimates linear regression coefficients with adversarial and noisy data.
problem Estimating robust linear regression coefficients with adversarial and noisy data.
method Adversarial robust weighted Huber regression with polynomial computational complexity.
result Derives an estimation error bound that depends on the stable rank and condition number of the covariance matrix.
Estimates for covariant derivatives and Riesz transforms on differential forms.
problem Bounding covariant derivatives and Riesz transforms on differential forms.
method Use Bismut derivative formula to prove heat kernel bounds and Riesz transform boundedness.
result Formulate and prove conjecture on boundedness of covariant local Riesz-transforms in L^p.
Study precise sample covariance error for Gaussian centered data.
problem Precise characterization of sample covariance error for Gaussian data.
method Developed a Random Duality Theory (RDT) framework to determine upper and lower bounds.
result Upper and lower bounds match in large-dimensional contexts, matching the spectral norm's limiting value.
The study bounds Riesz transforms on manifolds with controlled curvature.
problem Bounding Riesz transforms on manifolds with controlled curvature.
method Established L p L^p L p -boundedness of local covariant Riesz transforms for differential forms. result Calderón-Zygmund estimates for manifolds with bounded Riemannian curvature.
This paper establishes non-asymptotic learning bounds for the DR covariate shift adaptation.
problem Distribution shift between training and test domains in machine learning.
method Doubly-robust (DR) estimator combining density ratio estimation and pilot regression model.
result First non-asymptotic learning bounds for DR covariate shift adaptation.
Unified learning bound for covariate and concept shifts.
problem Generalization under distribution shift in machine learning.
method Support-agnostic definitions of covariate and concept shifts using entropic optimal transport, leading to a unified error bound applicable to various loss functions and label spaces.
result Development of estimators for shifts with concentration guarantees and the DataShifts algorithm for quantifying and estimating the error bound.
Study extends bounds on sample covariance matrices with general dependence.
problem Quantitative bounds on sample covariance matrices with i.i.d. columns.
method Extends previous work on deterministic equivalent to rectangular random matrices with general dependence structure.
result Proves quantitative bounds involving dimensions and spectral parameter, including closer proximity to real positive semi-line.
Optimizes SGLD noise structure for better generalization bounds.
problem Improving generalization bounds for large models trained with SGLD.
method Manipulates the noise structure in SGLD to optimize information-theoretical bounds.
result Optimal noise covariance is the square root of the expected gradient covariance under certain constraints.
The paper proposes a method to estimate treatment effects using CAR designs with additional covariates.
problem Estimating distributional treatment effects in CAR designs with additional covariates.
method Flexible distribution regression framework that incorporates additional covariates using machine learning methods.
result The proposed estimator attains the semiparametric efficiency bound for distributional treatment effects under CAR.
New SQ lower bounds show learning mixtures of bounded covariance Gaussians is hard.
problem Learning mixtures of Gaussians with bounded covariance matrices is hard.
method Statistical Query (SQ) lower bounds.
result Any SQ algorithm requires complexity at least d Ω ( 1 / ε ) d^{Ω(1/ε)} d Ω ( 1/ ε ) for learning mixtures of bounded covariance Gaussians. Identifying statistical dependence between the features and the label is a fundamental problem in supervised learning. This paper presents a framework for estimating dependence between numerical features and a categorical label using generalized Gini distance, an energy distance in reproducing kernel Hilbert spaces (RK…
SPARKLE handles high-dimensional covariates for online decision-making.
problem Complex reward-covariate relationships in high-dimensional settings.
method SPARKLE uses a sparse additive reward model with doubly penalized estimator and adaptive screening.
result SPARKLE achieves sublinear regret bound logarithmic in covariate dimensionality.
Study improves error bounds for sparse regression with heavy-tailed covariates.
problem Estimating sparse coefficients in linear regression with heavy-tailed covariates.
method Employed an ℓ 1 \ell_1 ℓ 1 -penalized Huber regression method. result Error bound identical to Gaussian case for L L L -subexponential covariates. Sparse covariance estimation in the vertical-split model achieves exponential improvement over dense estimates.
problem Minimax estimation error for distributed covariance matrix estimation in the vertical-split setting.
method Elementwise s s s -sparsity is shown to reduce communication and sample complexity. result Minimax lower bounds for 1 1 1 -sparse cross-covariance estimation are established. In this paper, we study the problem of estimating the covariance matrix under differential privacy, where the underlying covariance matrix is assumed to be sparse and of high dimensions. We propose a new method, called DP-Thresholding, to achieve a non-trivial ℓ 2 \ell_2 ℓ 2 -norm based error bound, which is significantly bet…
Study non-asymptotic estimation bounds for LTI models with Gaussian noise.
problem Estimating parameters of LTI models with non-asymptotic error bounds.
method Sharp non-asymptotic lower bounds using Cramér-Rao and van Trees inequalities, concentration results, and differential geometric constructions.
result Sharp and rate-optimal lower bounds for mean square estimation risk.
This paper addresses missing covariates in stochastic linear bandits, providing a high-probability regret bound.
problem Effect of missing covariates on regret in stochastic linear bandit algorithms.
method Proposes an algorithm that provides a high-probability upper bound on regret in terms of covariate sampling probabilities.
result Regret degrades due to missingness by at most ζ m i n 2 ζ_{min}^2 ζ min 2 , where ζ m i n ζ_{min} ζ min is the minimum probability of observing covariates. This study optimizes covariate density and propensity score for efficient ATE estimation.
problem Efficiently estimating average treatment effects (ATEs) with minimal variance.
method Adaptive experiment optimizing both covariate density and propensity score.
result Proposed method minimizes the semiparametric efficiency bound for ATE estimation.
Study improves treatment effect estimation using unlabeled covariates.
problem Estimating treatment effects with limited labeled data.
method Developed efficiency bounds and estimators for semi-supervised setting.
result Estimators using unlabeled covariates have lower asymptotic variance.
The paper provides PAC bounds for estimating causal effects using covariate adjustment with a valid set.
problem Estimating causal effects in high-dimensional settings without randomized experiments.
method PAC learning perspective, valid adjustment set, $\eps$ -Markov blanket, constraint-based algorithms.
result PAC-bounds the estimation error of covariate adjustment by a term exponential in the size of the adjustment set.
Structured credal learning separates covariate shift and label disagreement.
problem Uncertainty in real-world learning tasks due to covariate shift and noisy labels.
method Introduces a structured credal learning framework that explicitly separates these sources.
result Geometric bounds and decomposition reveal how covariate shifts affect label disagreement contributions.
This paper presents a new method for estimating high dimensional covariance matrices. The method, permuted rank-penalized least-squares (PRLS), is based on a Kronecker product series expansion of the true covariance matrix. Assuming an i.i.d. Gaussian random sample, we establish high dimensional rates of convergence to…
New bounds on self-normalized martingales improve online linear regression performance.
problem Improving regret bounds in online linear regression.
method Characterizing scale-invariant bounds on self-normalized martingales.
result For d = 1 d=1 d = 1 , O ( log T ) O(\log T) O ( log T ) doubly-uniform regret is possible; for d > 1 d>1 d > 1 , sublinear doubly-uniform regret is impossible. DARTS optimizes covariate selection in trials with limited data.
problem Limited budget for high-dimensional pretreatment data.
method Dynamic Adaptive Rerandomization via Thompson Sampling (DARTS).
result DARTS efficiently concentrates budget on informative features.
New methods estimate covariance for matrix data without assuming fixed size or specific distributions.
problem Estimating covariance for high-dimensional matrix data without distributional assumptions.
method Unified framework for bandable covariance estimation with rank one approximation, robust to heavy-tailed data.
result Proposed estimators are rate-optimal and perform well in simulations and real applications.
We consider random-design linear prediction and related questions on the lower tail of random matrices. It is known that, under boundedness constraints, the minimax risk is of order d / n d/n d / n in dimension d d d with n n n samples. Here, we study the minimax expected excess risk over the full linear class, depending on the dist…
The paper addresses the reliability of conformal prediction under covariate shift.
problem Ensuring reliable prediction sets under covariate shift.
method Derives upper bounds on training-conditional coverage.
result Offers PAC guarantees for conformal prediction methods.
Proofs Fisher-Rao distance on Gaussian covariance manifold.
problem Proving Fisher-Rao distance on Gaussian covariance manifold.
method Basic Riemannian geometry.
result Proof of Fisher-Rao distance on covariance cone.
New method estimates covariance in deep heteroscedastic regression without labels.
problem Estimating covariance in deep heteroscedastic models is challenging due to sample-dependent covariance and lack of ground truth.
method Proposes a self-supervised approach using KL Divergence and 2-Wasserstein distance for covariance estimation and a neighborhood-based heuristic for pseudo labels.
result Demonstrates effective pseudo labels and a computationally cheaper yet accurate deep heteroscedastic regression.
Efficiently estimates sparse linear regression with heavy-tailed and outlier-contaminated data.
problem Estimating sparse linear regression coefficients with heavy-tailed and outlier-contaminated data.
method Efficient computation of estimators with sharp error bounds.
result Sharp error bounds for efficient estimators.
New method reduces regret in nonparametric bandits with unknown covariate shifts.
problem Optimal actions depend on context, but context distributions can change over time.
method Derives new regret bounds for nonparametric bandits under covariate shifts.
result Regret bounds adaptively attainable without knowledge of shift time or magnitude.
The inverse covariance matrix provides considerable insight for understanding statistical models in the multivariate setting. In particular, when the distribution over variables is assumed to be multivariate normal, the sparsity pattern in the inverse covariance matrix, commonly referred to as the precision matrix, cor…
New approach for semi-supervised learning under covariate shifts.
problem Semi-supervised learning under covariate shifts where labeled and unlabeled data distributions differ.
method Information-theoretical approach, addressing covariate shifts.
result Improved performance compared to previous methods.
Paper tackles CATE estimation with missing treatment info.
problem Challenges in estimating CATE with missing treatment information.
method Developed MTRNet, a novel CATE estimation algorithm using domain adaptation.
result Improves CATE estimation over state-of-the-art methods.
New bounds for linear interpolators show how they generalize under covariate shifts.
problem Understanding how linear interpolators generalize under covariate shifts.
method Proved non-asymptotic excess risk bounds for benignly-overfit linear interpolators in transfer learning.
result Identified beneficial and malignant covariate shifts based on overparameterization degree.
Paper tackles moment estimation under covariate shift with a two-stage algorithm.
problem Estimating moments under covariate shift when source and target distributions differ.
method Proposes a two-stage algorithm: first, an optimal estimator for the source distribution; second, likelihood ratio reweighting for calibration.
result Achieves minimax optimal bound for moment estimation.
Robust covariance testing requires significantly more samples in contaminated data.
problem Testing the covariance matrix of a high-dimensional Gaussian in the presence of contamination.
method We study the problem in the Huber's contamination model, distinguishing between the identity matrix and matrices far from it in Frobenius norm.
result The sample complexity of covariance testing increases dramatically to Ω ( d 2 ) Ω(d^2) Ω ( d 2 ) in the contaminated setting. Study shows pretraining and finetuning can effectively tackle covariate shift in linear regression.
problem Linear regression under covariate shift where source and target distributions differ but conditional distribution remains similar.
method Pretraining on source data and finetuning on target data using online SGD.
result Transfer learning with O ( N 2 ) O(N^2) O ( N 2 ) source data is as effective as supervised learning with N N N target data. Unified error analysis for low-rank approximation improves data assimilation performance.
problem Analyzing the error in low-rank approximation methods for data assimilation.
method Unified stochastic analysis framework for Frobenius norm error bounds on centered and non-standard Gaussian matrices.
result Unified bounds provide clearer interpretations and enable better practical choices for covariance matrices.
Improved robust regression with clean covariates achieves better rates than Huber's model.
problem Robust regression under adaptive contamination of responses with clean covariates.
method Exploiting clean covariates to construct an estimator achieving better rates than Huber's model.
result Improved estimation rate even with constant contamination, achieving consistency.
Paper extends Bayesian Cramér-Rao bound with geometric considerations.
problem Estimation of covariance matrices with geometric structures.
method Intrinsic Bayesian Cramér-Rao bound with Riemannian geometry.
result Performance bounds for covariance matrix estimation.
Biological and social systems consist of myriad interacting units. The interactions can be represented in the form of a graph or network. Measurements of these graphs can reveal the underlying structure of these interactions, which provides insight into the systems that generated the graphs. Moreover, in applications s…
Optimally tackles covariate shift in RKHS-based nonparametric regression.
problem Covariate shift in nonparametric regression over RKHS.
method Two families of covariate shift problems defined using likelihood ratios. Minimax rate-optimal estimators for KRR and reweighted KRR.
result KRR is minimax rate-optimal and strictly sub-optimal compared to naive estimator under covariate shift.