Paper explores statistical and computational limits of estimating low-rank Gaussian mixtures.
problem Estimating low-rank matrix-variate observations with optimal statistical and computational limits.
method Low-rank Gaussian mixture model (LrMM) and minimax lower bounds.
result Minimax optimality of maximum likelihood estimator and spectral aggregation method.
Survey of network analysis limits and optimal methods.
problem Graphon estimation, community detection, and hypothesis testing.
method Review of minimax optimal rates and procedures.
result Optimal algorithms for network analysis.
Investigates the limits of cost-sensitive classification problems.
problem Cost-sensitive classification problem in mission-critical applications.
method Extending the minimax lower bound of balanced binary classification problem.
result Cost terms significantly impact the hardness of the problem.
Paper analyzes minimax regret in constrained online convex optimization with limited switching opportunities.
problem Minimizing regret in online convex optimization with limited switching opportunities.
method Introduced fugal game relaxation and mini-batching algorithm to establish minimax regret bounds.
result Minimax regret of switching-constrained OCO is Θ(T / √K).
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 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.
Paper improves risk bounds for nonconvex-strongly-concave minimax problems.
problem Achieving sharper risk bounds for nonconvex-strongly-concave minimax problems.
method Using uniform localized convergence to derive high probability generalization error bounds.
result Derives n times faster excess primal risk bounds for popular algorithms.
Paper sets limits on tensor data dictionary learning sample complexity.
problem Estimating atomic elements for tensor data with sparse representation.
method Proves minimax lower bound on sample complexity for Kronecker-structured dictionaries.
result Sample complexity for tensor data can be significantly lower than for unstructured data.
Proves non-asymptotic lower bounds for online learning with expert advice.
problem Finding optimal bounds for online learning performance.
method Proves lower bounds on the expectation of maxima of Gaussian and symmetric random variables.
result Establishes optimal leading constants for minimax regret in online learning.
The paper establishes limits of transfer learning with neural networks.
problem Understanding the fundamental limits of transfer learning.
method Statistical minimax framework for regression with linear and neural network models.
result Lower bounds for target generalization error.
Bayesian neural networks are shown to be minimax and admissible under certain conditions.
problem Optimality of Bayesian neural networks in deep learning models.
method Analysis of decision rules induced by BNNs in the normal location model under quadratic loss.
result A hyperprior on the effective output variance yields a minimax and admissible decision rule.
Option contracts are a type of financial derivative that allow investors to hedge risk and speculate on the variation of an asset's future market price. In short, an option has a particular payout that is based on the market price for an asset on a given date in the future. In 1973, Black and Scholes proposed a valuati…
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.
Paper defines local optimality for sequential nonconvex-nonconcave games.
problem Defining local optimality in sequential nonconvex-nonconcave minimax optimization.
method Proposes local minimax definition and connects to gradient descent ascent.
result Gradient descent ascent stable limit points are local minimax points.
We study high-dimensional asymptotic performance limits of binary supervised classification problems where the class conditional densities are Gaussian with unknown means and covariances and the number of signal dimensions scales faster than the number of labeled training samples. We show that the Bayes error, namely t…
New findings show many popular bandit algorithms are unstable, contradicting minimax optimality.
problem Challenges in statistical inference from bandit algorithms due to adaptive, non-i.i.d. nature.
method Analysis of stability properties of optimism-based bandit algorithms.
result Widely used minimax-optimal UCB-style algorithms are unstable.
New method detects communities in hypergraphs, achieving optimal statistical limit.
problem Community detection in hypergraphs under stochastic block model.
method Two-step algorithm: spectral clustering followed by local refinement.
result Achieves optimal statistical limit for community detection in hypergraphs.
New minimax rates for total variation denoising in higher dimensions, showing limitations of linear smoothers.
problem Estimating functions with bounded total variation over high-dimensional grids.
method Minimax analysis, focusing on linear and non-linear estimators.
result Linear estimators like Laplacian smoothing and eigenmaps are suboptimal for total variation denoising in higher dimensions.
GP-UCB performs suboptimally under certain conditions, as shown by a new regret lower bound.
problem The suboptimality of GP-UCB under polynomial effective optimism.
method Analysis of effective optimism level and new regret lower bound.
result GP-UCB is not minimax optimal under polynomial growth of effective optimism.
New framework formalizes estimating valid transport maps, revealing their statistical limits.
problem Estimating valid transport maps in generative modeling.
method Formalized a minimax framework for estimating valid transport maps.
result Estimating any valid transport map is as hard as estimating the optimal transport map under standard stability assumptions.
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 L q L_q L q -risks. result Achieves minimax optimality and provides adaptive estimators for robust nonparametric regression.
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.
Optimal first-order methods are shown to be fundamental limits in functional estimation.
problem Optimal functional estimation under weak conditions.
method Formalization of functional estimation with black-box nuisance function estimates and derivation of minimax lower bounds.
result First-order methods are optimal under weak conditions, but higher-order methods can outperform them when nuisance function structure is known.
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 L q L_q L q -norms. result NLA minimax rates continuously depend on noise level and match optimal recovery rates as noise decreases.
This work provides minimax bounds for structured prediction models.
problem Limited understanding of necessary sample complexity for structured prediction.
method Analysis of factor-graph inference models for structured prediction.
result Characterization of necessary sample complexity for any algorithm.
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.
Study on the limits of learning HMM parameters under various conditions.
problem Understanding the conditions under which hidden Markov model parameters can be learned.
method Nonasymptotic minimax upper and lower bounds, thresholds analysis.
result Nonasymptotic minimax bounds match up to constants, showing learnable thresholds.
Study tests uniformity of categorical data against missing-ball alternatives, finding chi-squared test outperforms.
problem Testing uniformity of categorical data against missing-ball alternatives.
method Characterizes minimax risk, uses collisions and chi-squared test, reduces to structured subset of alternatives.
result Minimax test outperforms chi-squared test under least favorable alternative.
New methods estimate transport-growth pairs in unbalanced optimal transport.
problem Statistical guarantees for Monge-type estimation in unbalanced optimal transport remain limited.
method Developed two estimators for transport-growth pairs under different setups.
result Achieved minimax optimal rate for estimation of transport-growth pairs.
Unified framework for structured principal subspace estimation with bounds and rates.
problem Structured principal subspace estimation problems.
method Unified framework, minimax lower and upper bounds, information-geometric complexity.
result Minimax rates of convergence for specific settings, including optimal rates for non-negative PCA/SVD.
New algorithm reduces regret for kernelized bandits by adapting to specific problem instances.
problem Efficiently learning the optimizer of an unknown function in RKHS with noisy oracle.
method Instance-dependent regret analysis and a new minimax near-optimal algorithm.
result New algorithm achieves better performance on specific problem instances.
Study optimizes shared singular subspace estimation from noisy matrices.
problem Estimating shared singular subspaces across multiple noisy matrices.
method Low-rank matrix denoising framework with Stack-SVD and novel estimators.
result Stack-SVD achieves minimax rate-optimality for identical shared subspaces, and novel estimators for partial sharing.
Personalizes pre-trained models for nonparametric regression with limited data.
problem Improving data efficiency in nonparametric regression with few samples.
method Develops a theoretical framework and algorithms for few-shot personalization of black-box models.
result Achieves minimax optimal rate for personalization in nonparametric regression.
New method avoids IV limitations for flexible estimation.
problem Nonparametric estimation of IV regressions with multiple solutions.
method Minimax penalized estimator avoiding identification and closedness conditions.
result Strong L 2 L_2 L 2 convergence rate without closedness condition. Paper explores limits of imitation learning in MDPs, setting new suboptimality bounds.
problem Understanding the statistical limits of imitation learning in MDPs.
method Analyzes minimax statistical limits in two settings: pre-interaction and interaction.
result Establishes suboptimality bounds for imitation learning in MDPs, showing improvements with knowledge of transition.
Study on regression with Markovian data, establishing limits and proposing an improved algorithm.
problem Least squares regression with dependent Markovian data.
method Sharp information theoretic lower bounds, analysis of SGD-DD and SGD, experience replay algorithm.
result Experience replay algorithm outperforms SGD-DD in Markovian data regression.
GANICE improves GAN-based causal inference by minimizing averaged Wasserstein risk.
problem Estimating interventional outcome distributions and quantiles in causal inference.
method GANICE uses extended Wasserstein distance and a cellwise critic to minimize averaged Wasserstein risk.
result GANICE achieves minimax optimality and consistently outperforms existing methods.
New methods identify limits of testing in high-dimensional models with non-sparse structures.
problem Understanding statistical inference in high-dimensional models with non-sparse regression coefficients.
method Developed new concepts of uniform and essentially uniform non-testability.
result Identified new tradeoffs between testability and feature correlation, showing that minimax lower bounds can be attained by tests with n \sqrt{n} n power. Diffusion models achieve nearly optimal distribution estimation in various spaces.
problem Theoretical limitations of diffusion modeling for distribution estimation.
method Analysis of approximation and generalization abilities of diffusion models in Besov spaces.
result Diffusion models achieve nearly minimax optimal estimation rates in total variation and Wasserstein distances.
The paper analyzes rates of approximation for eigenpairs of Laplace-Beltrami operators on manifolds.
problem Estimating eigenpairs of elliptic differential operators from manifold samples.
method Analyzes minimax rates for eigenvalue and eigenvector estimation using graph Laplacians.
result The minimax rate for H 1 ( M ) H^1(M) H 1 ( M ) -sense approximation is n − 2 / ( d + 4 ) n^{-2/(d+4)} n − 2/ ( d + 4 ) . Efficient estimator for two-sample functionals improves on oracle performance.
problem Estimating two-sample integral functionals efficiently.
method Weighted nearest neighbour estimator, central limit theorem.
result The estimator can outperform the oracle in certain cases.
A permutation-based SW test achieves minimax-optimal power for two-sample testing.
problem Nonparametric two-sample testing using the sliced Wasserstein distance.
method Proposes a permutation-based SW test and analyzes its performance.
result Achieves minimax separation rate n − 1 / 2 n^{-1/2} n − 1/2 over multinomial and bounded-support alternatives. The paper analyzes PPM for nonconvex-nonconcave problems, identifying three regions with varying convergence guarantees.
problem Challenges in nonconvex-nonconcave minimax optimization.
method Classic proximal point method with insights from the Moreau envelope.
result Identification of three regions with varying convergence guarantees for PPM.
Study on deep learning for speckle noise reduction in imaging modalities.
problem Multiplicative speckle noise challenges conventional deep learning methods for speckle denoising.
method Likelihood-based deep neural network (DNN) estimators for nonparametric regression under speckle noise.
result Established minimax rates for speckle denoising, matching those for additive Gaussian noise alone.
Paper shows MoM is optimal under adversarial contamination for certain distributions.
problem Optimality of MoM under adversarial contamination.
method Upper and lower bounds for MoM's error under adversarial contamination.
result MoM is (minimax) optimal for distributions with finite variance and infinite variance with finite absolute moments.
This paper analyzes neural networks for solving complex optimization problems.
problem Minimax optimization problems in infinite-dimensional function spaces.
method Mean-field analysis of stochastic gradient descent-ascent in neural networks.
result The algorithm converges to a stationary point at a sublinear rate.
New method for efficient matrix completion with nonignorable missing data.
problem Nonignorable missing data in matrix completion.
method Nuclear norm regularized U-statistic loss function and accelerated proximal gradient algorithm.
result Near minimax optimal statistical convergence rate for nonignorable missing data.
A central result in statistical theory is Pinsker's theorem, which characterizes the minimax rate in the normal means model of nonparametric estimation. In this paper, we present an extension to Pinsker's theorem where estimation is carried out under storage or communication constraints. In particular, we place limits …