Paper tackles distinguishing discrete distributions with local minimax rates.
problem Distinguishing between two discrete distributions when they are close in L 1 L_1 L 1 -norm. method Local minimax approach to adapt rates to distribution shapes.
result First local minimax rate for separation distance up to logarithmic factors.
Study on hypothesis testing for densities and multinomials, showing local minimax rates and critical radii.
problem Testing goodness-of-fit for distributions with varying number of categories or unbounded support.
method Developed novel tests for both discrete and continuous cases, considering local minimax rates and critical radii.
result Characterized the dependence of critical radii on the null hypothesis and provided adaptive tests.
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.
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.
Paper analyzes minimax risks of personalized federated learning algorithms.
problem Statistical heterogeneity among clients in federated learning.
method Minimax analysis of FedAvg and local training approaches.
result Threshold for optimality between FedAvg and local training depends on data heterogeneity.
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. …
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.
Adversarial online nonparametric regression achieves optimal rates with locally adaptive learning.
problem Adversarial online nonparametric regression with general convex losses.
method Parameter-free learning algorithm leveraging chaining trees to compete against H{ö}lder functions, dynamically tracking and adapting to local smoothness variations.
result First computationally efficient algorithm with locally adaptive optimal rates for online regression in an adversarial setting.
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.
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…
Local minimax analysis for Poisson deconvolution of discrete signals.
problem Estimating a discrete uniform signal from Poisson convolutions.
method Local minimax risk analysis of a broad class of kernels.
result Sharp estimation rates as a function of signal clustering.
Study on efficient estimation of Gaussian mean with limited communication.
problem Estimating Gaussian mean under communication constraints.
method Decomposition into localization and refinement stages, development of communication-efficient and statistically optimal procedures.
result Established minimax rates of convergence and developed optimal procedures.
Privacy-preserving binary classification using locally differential private data.
problem Classifying data while protecting individual privacy.
method Locally differential private mechanism followed by a universally consistent classifier.
result Minimax rates of convergence are slower when using private data.
New method estimates discrete distributions while protecting privacy.
problem Estimating discrete distributions with local differential privacy.
method Combining robust learning and local differential privacy.
result Minimax estimation rate of ε d / α 2 k + d 2 / α 2 k n ε\sqrt{d/α^2 k}+\sqrt{d^2/α^2 kn} ε d / α 2 k + d 2 / α 2 k n under privacy constraint. 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 β \geq 1/4 β ≥ 1/4 . 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.
Paper optimizes federated PCA for covariance estimation under privacy constraints.
problem Privacy-preserving covariance estimation in federated learning.
method Federated PCA, matrix version of van Trees' inequality, three-layer spectral decomposition.
result Optimal rates of convergence for central server's estimation, robust to inconsistent local estimators.
New method solves complex constrained optimization problems.
problem Constrained nonconvex-nonconcave minimax optimization problems.
method Inexact proximal gradient method using sequential convex programming.
result Established complexity guarantees for approximate stationary points.
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.
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.
Shallow neural networks can represent polynomials efficiently.
problem Representing polynomials using shallow neural networks.
method Using shallow neural networks of width 2 ( R + d ) d 2(R+d)^d 2 ( R + d ) d to represent d d d -variate polynomials of degree R R R . result Derives minimax optimal convergence rate for shallow networks to unknown univariate regression functions.
ERM and RERM minimize error even with malicious label corruptions.
problem Malicious label corruptions in regression problems.
method Empirical Risk Minimizers (ERM) and Regularized Empirical Risk Minimizers (RERM) under a local Bernstein condition.
result The L 2 L_2 L 2 -error rate is bounded by $r_N + AL |\cO|/N$ under the local Bernstein condition. New method for private linear regression under privacy constraints, achieving optimal rates.
problem Statistical complexity of private linear regression under unknown, ill-conditioned covariates.
method Information-Weighted Regression method
result Optimal convergence rates for both central and local privacy models.
Optimizes smooth functions with noisy zeroth-order feedback.
problem Global optimization of unknown non-convex smooth functions with noisy evaluations.
method Local minimax framework to study zeroth-order optimization.
result Identifies near global minimizers with fewer queries for functions with fast level set growth.
New method for learning indirectly through control variables.
problem Learning relationships when direct manipulation of variables is impossible.
method Study of indirect active learning under nonparametric models with fixed budget.
result Minimax rates for estimating relationships between variables.
A new random forest algorithm improves tree construction for optimal performance.
problem Improving the performance of random forests, especially in complex and smooth scenarios.
method Adaptive split-balancing method using permutation-based splitting criterion.
result Achieves minimax optimality under various Lipschitz and Hölder classes.
Adapts to estimate functions from noisy ERT data.
problem Estimating functions from noisy Exponential Radon Transform data.
method Locally adaptive kernel type estimator for functions of varying smoothness.
result Achieves minimax optimal rate up to a log(n) factor for Sobolev functions.
The paper studies the benefits of curriculum learning in linear regression tasks.
problem Theoretical understanding of curriculum learning's benefits in machine learning.
method Theoretical analysis of curriculum learning in structured and unstructured multitask linear regression problems.
result Adaptive learning in the unstructured setting is fundamentally harder than oracle learning, but not in the structured setting.
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.
The paper proposes a method for constructing confidence sets that adapt to the cardinality of the smallest component of a mean vector.
problem Forming confidence sets for the smallest component of an unknown mean vector.
method Sample splitting and self-normalization approach to test each component for being the smallest, maintaining validity regardless of d d d and n n n . result The proposed tests achieve the local minimax separation rate and robust to heavy-tailed distributions.
New active learning algorithm adapts to data without strict assumptions.
problem Efficiently label data with expensive labeling costs.
method Nonparametric adaptive active learning under local smoothness condition.
result Achieves minimax rate of convergence, performs almost as well as best non-adaptive algorithms.
Paper proposes FR algorithm to solve minimax optimization locally.
problem Gradient descent fails to find local minimax in minimax optimization.
method Follow-the-Ridge (FR) algorithm, addressing rotational behavior of gradient dynamics.
result FR algorithm provably converges to local minimax.
New minimax results show how target labels benefit under covariate-shift.
problem Understanding the relative benefits of source and target labeled data under covariate-shift.
method Developed new minimax results and showed how a semi-supervised procedure can adapt to unknown transfer-exponent γ.
result Target labels can dramatically improve classification in certain regimes of covariate-shift.
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.
The paper develops a minimax optimal method for high-dimensional regression using auxiliary data.
problem High-dimensional additive regression with heavy-tailed errors and transfer learning.
method Smooth backfitting estimator with local linear smoothing, followed by a two-stage estimation method.
result The method achieves the minimax optimal rate under certain conditions.
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.
Optimal testing for densities under local differential privacy constraints.
problem Testing goodness-of-fit for densities under privacy constraints.
method Estimation of quadratic distance and minimax separation rates.
result First minimax optimal test under local differential privacy constraints.
This paper analyzes saddle points and minimax points in non-convex smooth games.
problem Understanding local optimal points in non-convex smooth games.
method Comprehensive analysis of local minimax points, including their optimality conditions and stability.
result Local saddle points are uniformly local minimax points under mild continuity assumptions.
Study on estimating invertible functions with minimax analysis.
problem Minimizing risk of estimating invertible functions on a plane.
method Introduce two types of L 2 L^2 L 2 -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.
Preconditioned non-convex gradient descent improves noisy matrix estimation.
problem Estimating low-rank matrices from noisy measurements.
method Preconditioned non-convex gradient descent for noisy measurements.
result Preconditioned method converges to minimax optimal estimate at a linear rate.
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.
Develops a new method for estimating models with conditional moment restrictions.
problem Estimating models with conditional moment restrictions, especially non-parametric instrumental variable regression.
method Introduces a min-max criterion function to solve a zero-sum game between modeler and adversary, analyzing estimation rates for various hypothesis spaces.
result Shows that with regularization and rich test function spaces, estimation rates scale with the critical radius of hypothesis and test function spaces.
KL nearest neighbor estimator achieves near-minimax rates for differential entropy.
problem Estimating differential entropy with Hölder smoothness.
method Uniform upper and lower bounds on KL estimator performance.
result KL estimator is near-minimax rate-optimal without knowing smoothness.
Paper analyzes convergence of GDA for nonconvex-nonconcave minimax problems.
problem Understanding convergence of GDA for nonconvex-nonconcave minimax problems.
method Local convergence analysis of GDA with stepsize ratio Θ(κ).
result Stepsize ratio of Θ(κ) is necessary and sufficient for local convergence of GDA to a Stackelberg Equilibrium.
Paper quantizes heavy-tailed data for near optimal estimation rates.
problem Estimating parameters from heavy-tailed data with quantization.
method Truncate and dither data, then uniformly quantize; achieves near minimax rates.
result Near optimal estimation rates achievable with quantized data.
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.
Proposes a new method to control FDR using frequentist-assisted horseshoe for high-dimensional testing.
problem Designing tests with frequentist false discovery rate control using horseshoe prior.
method Frequentist-assisted horseshoe procedure for high-dimensional normal means testing.
result Consistently achieves robust finite-sample FDR control in various sparse cases.