Paper reconciles minimax rates and optimal recovery rates for noisy observations.
problem Estimating a function from noisy observations.
method Develops NLA minimax rates for Besov classes in Lq-norms. result NLA minimax rates continuously depend on noise level and match optimal recovery rates as noise decreases.
Study confirms optimal minimax rate for nonlocal interaction kernel estimation.
problem Estimating nonlocal interaction kernels in interacting particle systems.
method Introduced tamed least squares estimator (tLSE) achieving optimal convergence rate.
result Optimal minimax rate of convergence confirmed for β≥1/4. This paper analyzes how machine learning models resist adversarial attacks in nonparametric regression.
problem Adversarial attacks on machine learning models in nonparametric regression.
method Theoretical analysis of minimax rates of convergence under adversarial sup-norm.
result The minimax rate under adversarial attacks is the sum of two terms: standard rate and deviation of true function.
Study on estimating invertible functions with minimax analysis.
problem Minimizing risk of estimating invertible functions on a plane.
method Introduce two types of L2-risks, derive lower and upper rates for minimax values, develop an asymptotically almost everywhere invertible estimator. result Invertibility does not reduce the complexity of the estimation problem in terms of the rate.
This paper studies continuum-armed bandits under Besov smoothness conditions and derives minimax rates.
problem Optimizing an unknown function with limited evaluations.
method Studies continuum-armed bandits under Besov smoothness conditions and derives minimax rates.
result Minimax rates over Besov spaces are identical to those over the smallest Hölder space into which Besov spaces embed.
Study exact minimax rates for density estimation over convex classes, extending previous work.
problem Deriving minimax rates for density estimation over convex density classes.
method Building on Le Cam's work, determine exact minimax rates using local metric entropy.
result Exact minimax rates derived for any convex density class, including nonparametric and parametric cases.
New adaptive learning rate for FTRL reduces regret to Θ(T^2/3).
problem Minimax regret of Θ(T^2/3) in online learning.
method Adaptive learning rate framework matching stability, penalty, and bias terms.
result Improves Best-of-Both-Worlds (BOBW) regret upper bounds.
New algorithm AG-OG optimizes separable convex-concave problems efficiently.
problem Efficiently solving separable convex-concave minimax optimization problems.
method Leverages Nesterov acceleration and optimistic gradient on component and coupling parts of the problem.
result Achieves optimal convergence rate for various settings including bilinearly coupled problems.
Study minimax rates for density estimation under Huber contamination and Besov IPM losses.
problem Minimax convergence rates of nonparametric density estimation under Huber contamination model with outliers.
method Re-scaled thresholding wavelet series estimator and GAN architectures.
result Achieves minimax optimal convergence rates under 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.
problem Vulnerability of machine learning models to adversarial attacks in nonparametric regression.
method Establishes minimax rate and proposes adaptive estimators for robust nonparametric regression under adversarial Lq-risks. result Achieves minimax optimality and provides adaptive estimators for robust nonparametric regression.
New research shows existing information-theoretic methods can't establish minimax rates for gradient descent in stochastic convex optimization.
problem Establishing minimax rates for gradient descent in stochastic convex optimization using information-theoretic methods.
method Examined several information-theoretic frameworks including input-output mutual information bounds, conditional mutual information bounds, PAC-Bayes bounds, and their variants.
result Proved that none of the examined information-theoretic frameworks can establish minimax rates for gradient descent in stochastic convex optimization.
Study on signal detection in sparse additive models with nonasymptotic minimax rates.
problem Signal detection in sparse additive models.
method Nonasymptotic minimax analysis of signal detection in sparse additive models.
result Established minimax separation rate for signal detection.
A novel decentralized algorithm improves minimax optimization in federated learning.
problem Minimax optimization in federated learning with data heterogeneity.
method Decentralized Gradient Tracking (K-GT-Minimax) for nonconvex-strongly-concave optimization.
result Demonstrates superior convergence rate for NC-SC minimax optimization.
Study minimax-optimal rates for offline decision-making with function approximation.
problem Statistical complexity of offline decision-making with function approximation.
method Near minimax-optimal rates for stochastic contextual bandits and Markov decision processes, using pseudo-dimension and behavior policy.
result Established performance limits and new characterization of behavior policy.
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 …
Unified framework for structure learning via conditional independence testing.
problem Optimal structure learning and conditional independence testing.
method Established a fundamental connection and reduction between structure learning and conditional independence testing.
result Optimal rates for structure learning are determined by conditional independence testing rates.
The paper optimizes k-NN for distributed learning with minimax optimal performance.
problem Minimizing error rates in classification, regression, and density estimation.
method Optimal aggregation of fixed-k nearest neighbors from multiple subsets of data.
result Achieves minimax optimal error rates up to a logarithmic factor.
The paper analyzes reinforcement learning methods for estimating weights and quality functions with fast convergence rates.
problem Estimating weights and quality functions in reinforcement learning with function approximation.
method The paper uses minimax methods for estimating marginal importance weights and q-functions.
result The minimax approach enables fast rates of convergence for weights and quality functions, achieving first-order efficiency.
Paper develops a method for estimating PFLM with minimized rates in high dimensions.
problem Estimating PFLM with minimized rates in high dimensions.
method Least square approach with mixed regularizations of function-norm and ℓ1-norm.
result Established optimal minimax rates of estimation for PFLM.
Classical scaling is shown to be optimal under various noisy conditions.
problem Consistency of classical scaling under general noise conditions.
method Established using finite fourth moments of noise, derived convergence rates, and matching minimax lower bounds.
result Classical scaling achieves minimax optimality in recovering true configuration from noisy dissimilarities.
Paper analyzes kNN estimator for KL divergence, proving its optimality.
problem Estimating KL divergence from identical samples.
method kNN estimator based on nearest neighbor distances.
result kNN method is asymptotically rate optimal for KL divergence estimation.
New algorithm ranks players from partial comparisons with optimal rate.
problem Ranking players from partial pairwise comparisons.
method Divide-and-conquer approach, local MLE within groups.
result Optimal ranking algorithm with minimax rate.
New SGDA method speeds up nonconvex minimax optimization.
problem Improving convergence of nonconvex minimax optimization.
method SGDA with random reshuffling for nonconvex-PŁ objectives.
result Convergence rates faster than with-replacement SGDA.
We study the minimax optimal rate for estimating the Wasserstein-1 metric between two unknown probability measures based on n i.i.d. empirical samples from them. We show that estimating the Wasserstein metric itself between probability measures, is not significantly easier than estimating the probability measures u…
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 L1-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.
problem Achieving statistical utility while maintaining privacy in two-sample testing.
method Private permutation tests for multinomial data and adaptive tests for continuous data.
result Minimax optimal tests for private two-sample testing under LDP.
Negative momentum accelerates convergence in minimax games but at a suboptimal rate.
problem The convergence rate of negative momentum in minimax games is suboptimal.
method Extending variational inequality formulation, connecting momentum method with Chebyshev polynomials.
result Negative momentum accelerates convergence locally but at a suboptimal rate.
Paper investigates optimal transport map estimation in infinite-dimensional spaces.
problem Estimating optimal transport maps in infinite-dimensional spaces is challenging.
method Characterizes γ-smoothness for optimal transport maps and develops a polynomial-rate estimator. result Shows polynomial-order minimax risk for optimal transport map estimation.
Study improves distributional regression evaluation with CRPS, finding optimal rates of convergence.
problem Improving probabilistic forecasts in meteorology using distributional regression.
method Extends theoretical properties of CRPS evaluation to include covariates and finite sample sizes, analyzing convergence rates for different methods.
result Optimal minimax rate of convergence for distributional regression methods is achieved by k-nearest neighbor and kernel methods.
k Nearest Neighbor (kNN) method is a simple and popular statistical method for classification and regression. For both classification and regression problems, existing works have shown that, if the distribution of the feature vector has bounded support and the probability density function is bounded away from zero in i…
Study robust estimation under varying corruption probabilities in data.
problem Robust estimation in scenarios with heterogeneous corruption rates.
method Developed estimators for mean and regression under various corruption patterns.
result Optimal estimators can discard corrupted samples beyond a specific threshold.
This paper surveys some recent developments in fundamental limits and optimal algorithms for network analysis. We focus on minimax optimal rates in three fundamental problems of network analysis: graphon estimation, community detection, and hypothesis testing. For each problem, we review state-of-the-art results in the…
Study reveals differences in label shift problem difficulty in supervised vs. unsupervised settings.
problem Label shift problem in non-parametric classification.
method Analysis of minimax rates in supervised and unsupervised settings, focusing on class conditional distributions estimation.
result A class proportion estimation approach is minimax rate-optimal in the unsupervised setting.
Alt-GDA outperforms Sim-GDA in minimax games with near-optimal local convergence.
problem Minimax optimization convergence rate comparison
method Alternating Gradient Descent-Ascent (Alt-GDA) vs. Simultaneous Gradient Descent-Ascent (Sim-GDA)
result Alt-GDA achieves near-optimal local convergence rate for strongly convex-strongly concave problems, while Sim-GDA converges slower.
Study shows attention-style models learn pairwise interactions efficiently.
problem Learning pairwise interactions in attention-style models.
method Proved minimax rate of convergence for learning pairwise interactions.
result Minimax rate is M−2β+12β independent of embedding dimension and token number. Many nonparametric regressors were recently shown to converge at rates that depend only on the intrinsic dimension of data. These regressors thus escape the curse of dimension when high-dimensional data has low intrinsic dimension (e.g. a manifold). We show that k-NN regression is also adaptive to intrinsic dimension. …
Study minimax rates for binary classifier estimation with margin conditions.
problem Estimating binary classifiers with geometric margin conditions.
method Derive lower bounds for worst-case learning rates over various function classes.
result Identify optimal rates close to O(n−1) for different function classes. New random forest variants achieve optimal performance in high dimensions.
problem Handling dependencies between features in high-dimensional data.
method Using oblique splits in random forests with general split directions.
result Achieved minimax optimal convergence rates in arbitrary dimension.
The study establishes minimax bounds for estimating operators from noisy samples.
problem Estimating unknown operators between Hilbert spaces from noisy data.
method Developed a minimax theory for uniformly bounded Lipschitz operators, proving lower and upper bounds.
result Sharp characterizations of minimax risk for generic Lipschitz operators, showing a curse of sample complexity.
We study the approximate nearest neighbour method for cost-sensitive classification on low-dimensional manifolds embedded within a high-dimensional feature space. We determine the minimax learning rates for distributions on a smooth manifold, in a cost-sensitive setting. This generalises a classic result of Audibert an…
Paper characterizes minimax regret rates for online ranking with top-k feedback.
problem Analyzing online ranking with partial feedback.
method Developed techniques from partial monitoring to characterize minimax regret rates.
result Full characterization of minimax regret rates for Precision@n.
This paper establishes minimax rates for online regression with arbitrary classes of functions and general losses. We show that below a certain threshold for the complexity of the function class, the minimax rates depend on both the curvature of the loss function and the sequential complexities of the class. Above this…
PAC-Bayesian bounds show fully connected DNNs with Gaussian priors match minimax rates.
problem Theoretical limits of fully connected deep neural networks with Gaussian priors.
method PAC-Bayesian bounds for fully connected Bayesian DNNs with Gaussian priors.
result PAC-Bayesian bounds match minimax-optimal rates in Besov space for nonparametric regression and binary classification.
MOSAIC detects change points in dynamic networks with low-rank and sparse changes.
problem Detecting change points in dynamic networks with specific structural properties.
method Eigen-decomposition-based test with screened signals and residual-based adjustment.
result MOSAIC achieves minimax-optimal detection and testing rates.
Study shows rates for Laplacian-eigenmap methods in nonparametric regression.
problem Minimizing error in nonparametric regression using Laplacian-eigenmap.
method Adaptive and non-adaptive minimax rates using Sobolev space constraints.
result Extends minimax rates to various weighted Laplacian matrices.
AGDA and variance-reduced methods solve nonconvex-nonconcave minimax problems globally and faster.
problem Solving nonconvex-nonconcave minimax problems in machine learning.
method Global convergence of AGDA and variance-reduced algorithms.
result AGDA and variance-reduced methods achieve global convergence and faster rates.
The paper analyzes kNN density estimation's convergence rates under different conditions.
problem Analyzing convergence rates of kNN density estimation under bounded and unbounded support conditions.
method Examined two cases: bounded support with known and unknown support sets, and unbounded support with smooth density function.
result kNN density estimation is minimax optimal under certain conditions and better than kernel density estimation in some cases.