arXiv research

New algorithm AG-OG optimizes separable convex-concave problems efficiently.

Study on signal detection in sparse additive models with nonasymptotic minimax rates.

We consider the closeness testing problem for discrete distributions. The goal is to distinguish whether two samples are drawn from the same unspecified distribution, or whether their respective distributions are separated in $L_1$-norm. In this paper, we focus on adapting the rate to the shape of the underlying distri…

Private two-sample tests under LDP achieve minimax rates for multinomial and continuous data.

Study on signal detection in heteroscedastic Gaussian sequences with sparse alternatives.

Study uniform rates for estimating Gaussian mixtures without separation assumption.

Study shows attention-style models learn pairwise interactions efficiently.

Characterizes distribution-free rates in unbalanced classification problems.

The paper improves prediction and testing for signals from a linear combination of translated features with Gaussian noise.

The study establishes minimax bounds for estimating operators from noisy samples.

Novel graph-spanning algorithm detects changes in high-dimensional data.

The study of networks leads to a wide range of high dimensional inference problems. In many practical applications, one needs to draw inference from one or few large sparse networks. The present paper studies hypothesis testing of graphs in this high-dimensional regime, where the goal is to test between two populations…

Unified framework for optimal kernel tests across MMD, HSIC, and KSD.

New method estimates discrete distributions while protecting privacy.

Despite remarkable empirical success, the training dynamics of generative adversarial networks (GAN), which involves solving a minimax game using stochastic gradients, is still poorly understood. In this work, we analyze last-iterate convergence of simultaneous gradient descent (simGD) and its variants under the assump…

New algorithm solves nonconvex-convex minimax problems efficiently.

We consider the goodness-of-fit testing problem of distinguishing whether the data are drawn from a specified distribution, versus a composite alternative separated from the null in the total variation metric. In the discrete case, we consider goodness-of-fit testing when the null distribution has a possibly growing or…

Paper develops a minimax optimal test for goodness-of-fit using kernel Stein discrepancy.

TiAda adapts adaptive gradient methods for nonconvex minimax optimization.

NeAda solves nonconvex minimax optimization by balancing primal and dual variables adaptively.

New algorithm improves matrix estimation with one-sided covariates.

The paper proposes a method for constructing confidence sets that adapt to the cardinality of the smallest component of a mean vector.

Paper reconciles minimax rates and optimal recovery rates for noisy observations.

Study confirms optimal minimax rate for nonlocal interaction kernel estimation.

This paper analyzes how machine learning models resist adversarial attacks in nonparametric regression.

Paper studies federated nonparametric testing with privacy constraints, achieving optimal rates and adaptive testing.

Finding anonymization mechanisms to protect personal data is at the heart of recent machine learning research. Here, we consider the consequences of local differential privacy constraints on goodness-of-fit testing, i.e. the statistical problem assessing whether sample points are generated from a fixed density $f_0$, o…

Study on estimating invertible functions with minimax analysis.

This paper studies continuum-armed bandits under Besov smoothness conditions and derives minimax rates.

A permutation-based SW test achieves minimax-optimal power for two-sample testing.

Study exact minimax rates for density estimation over convex classes, extending previous work.

We study the problem of independence testing given independent and identically distributed pairs taking values in a $σ$-finite, separable measure space. Defining a natural measure of dependence $D(f)$ as the squared $L^2$-distance between a joint density $f$ and the product of its marginals, we first show that there is…

New adaptive learning rate for FTRL reduces regret to Θ(T^2/3).

While several papers have investigated computationally and statistically efficient methods for learning Gaussian mixtures, precise minimax bounds for their statistical performance as well as fundamental limits in high-dimensional settings are not well-understood. In this paper, we provide precise information theoretic …

Study minimax rates for density estimation under Huber contamination and Besov IPM losses.

In this paper, we give a new sharp generalization bound of lp-MKL which is a generalized framework of multiple kernel learning (MKL) and imposes lp-mixed-norm regularization instead of l1-mixed-norm regularization. We utilize localization techniques to obtain the sharp learning rate. The bound is characterized by the d…

Paper tackles adversarial attacks on nonparametric regression models.

This work explores adaptive strategies for multi-armed bandits with causal structure, achieving optimal regret bounds.

New research shows existing information-theoretic methods can't establish minimax rates for gradient descent in stochastic convex optimization.

Efficiently tests two distributions using Nyström approximation of MMD.

We analyze the classical EM algorithm for parameter estimation in the symmetric two-component Gaussian mixtures in $d$ dimensions. We show that, even in the absence of any separation between components, provided that the sample size satisfies $n=Ω(d \log^3 d)$, the randomly initialized EM algorithm converges to an esti…

A novel decentralized algorithm improves minimax optimization in federated learning.

Study minimax-optimal rates for offline decision-making with function approximation.

Adaptive algorithm reduces regret in causal bandits.

Study detects boundaries in unlabeled noisy images without labels.

We find the minimax rate of convergence in Hausdorff distance for estimating a manifold M of dimension d embedded in R^D given a noisy sample from the manifold. We assume that the manifold satisfies a smoothness condition and that the noise distribution has compact support. We show that the optimal rate of convergence …

KSDAgg combines multiple KSD tests to improve goodness-of-fit testing without splitting data.

Unified framework for structure learning via conditional independence testing.