惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

Apple Machine Learning Research
Apple Machine Learning Research
aimingoo的专栏
aimingoo的专栏
酷 壳 – CoolShell
酷 壳 – CoolShell
博客园 - 聂微东
Engineering at Meta
Engineering at Meta
N
Netflix TechBlog - Medium
Blog — PlanetScale
Blog — PlanetScale
大猫的无限游戏
大猫的无限游戏
Vercel News
Vercel News
D
DataBreaches.Net
让小产品的独立变现更简单 - ezindie.com
让小产品的独立变现更简单 - ezindie.com
WordPress大学
WordPress大学
L
LangChain Blog
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
F
Fortinet All Blogs
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
J
Java Code Geeks
Recent Announcements
Recent Announcements
Jina AI
Jina AI
G
Google Developers Blog
腾讯CDC
博客园_首页
博客园 - 【当耐特】

math.ST updates on arXiv.org

What is Learnable in Valiant's Theory of the Learnable? Learning Perturbations to Extrapolate Your LLM Byzantine-Robust Distributed Sparse Learning Revisited The Sample Complexity of Multiple Change Point Identification under Bandit Feedback A proximal gradient algorithm for composite log-concave sampling Model-based Bootstrap of Controlled Markov Chains Approximation of Maximally Monotone Operators : A Graph Convergence Perspective Posterior Contraction Rates for Sparse Kolmogorov-Arnold Networks in Anisotropic Besov Spaces MIST: Reliable Streaming Decision Trees for Online Class-Incremental Learning via McDiarmid Bound A Spectral Framework for Closed-Form Relative Density Estimation Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability Higher-Order Equilibrium Tracking for EM-Compressible Online Estimation Scaling Limits of Long-Context Transformers A Note on Non-Negative $L_1$-Approximating Polynomials Susceptibilities and Patterning: A Primer on Linear Response in Bayesian Learning Linear Response Estimators for Singular Statistical Models Statistical inference with belief functions: A survey Robust stochastic first order methods in heavy-tailed noise via medoid mini-batch gradient sampling Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexity Adaptive auditing of AI systems with anytime-valid guarantees Locally Near Optimal Piecewise Linear Regression in High Dimensions via Difference of Max-Affine Functions Risk-Controlled Post-Processing of Decision Policies Covariate Balancing and Riesz Regression Should Be Guided by the Neyman Orthogonal Score in Debiased Machine Learning A Unified Pair-GRPO Family: From Implicit to Explicit Preference Constraints for Stable and General RL Alignment Time-Inhomogeneous Preconditioned Langevin Dynamics A Fine-Grained Understanding of Uniform Convergence for Halfspaces CITE: Anytime-Valid Statistical Inference in LLM Self-Consistency Ratio-based Loss Functions Optimal Confidence Band for Kernel Gradient Flow Estimator A renormalization-group inspired lattice-based framework for piecewise generalized linear models
Online Robust Mean Estimation
Daniel M. Kane, Ilias Diakonikolas, Hanshen Xiao, Sihan Liu · 2023-10-24 · via math.ST updates on arXiv.org

We study the problem of high-dimensional robust mean estimation in an online setting. Specifically, we consider a scenario where $n$ sensors are measuring some common, ongoing phenomenon. At each time step $t=1,2,\ldots,T$, the $i^{th}$ sensor reports its readings $x^{(i)}_t$ for that time step. The algorithm must then commit to its estimate $μ_t$ for the true mean value of the process at time $t$. We assume that most of the sensors observe independent samples from some common distribution $X$, but an $ε$-fraction of them may instead behave maliciously. The algorithm wishes to compute a good approximation $μ$ to the true mean $μ^\ast := \mathbf{E}[X]$. We note that if the algorithm is allowed to wait until time $T$ to report its estimate, this reduces to the well-studied problem of robust mean estimation. However, the requirement that our algorithm produces partial estimates as the data is coming in substantially complicates the situation. We prove two main results about online robust mean estimation in this model. First, if the uncorrupted samples satisfy the standard condition of $(ε,δ)$-stability, we give an efficient online algorithm that outputs estimates $μ_t$, $t \in [T],$ such that with high probability it holds that $\|μ-μ^\ast\|_2 = O(δ\log(T))$, where $μ= (μ_t)_{t \in [T]}$. We note that this error bound is nearly competitive with the best offline algorithms, which would achieve $\ell_2$-error of $O(δ)$. Our second main result shows that with additional assumptions on the input (most notably that $X$ is a product distribution) there are inefficient algorithms whose error does not depend on $T$ at all.