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.
Bayesian analysis shows unlabeled data improve graph-based semi-supervised learning.
problem Improving semi-supervised learning with limited labeled data.
method Bayesian nonparametric approach using unlabeled data for graph-based learning.
result Posterior contracts optimally around the truth with sufficient unlabeled data.
Survey of recent methods for testing high-dimensional multinomial hypotheses.
problem Statistical power issues in high-dimensional multinomial testing.
method Review of recent methods focusing on asymptotic normality and minimax perspectives.
result Refined tests can have high power even when null distributions are non-normal.
Paper explains adversarial training's robust overfitting through a minimax game perspective.
problem Adversarial training suffers from robust overfitting after learning rate decay.
method Viewing adversarial training as a dynamic minimax game, analyzing how LR decay breaks balance and leads to overfitting.
result ReBalanced Adversarial Training (ReBAT) alleviates robust overfitting without sacrificing robustness.
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.
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 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.
We investigate if kernel regularization methods can achieve minimax convergence rates over a source condition regularity assumption for the target function. These questions have been considered in past literature, but only under specific assumptions about the decay, typically polynomial, of the spectrum of the the kern…
The paper tackles individualized decision-making under unmeasured confounding, providing a novel minimax solution and a paradox.
problem Unmeasured confounding in causal inference leads to biased estimates and affects individualized decision-making.
method The authors establish a formal link between individualized decision-making under partial identification and classical decision theory, providing a minimax solution and a paradox.
result A novel minimax solution for individualized decision-making/policy assignment is provided, and an interesting paradox is drawn.
New statistical framework for coresets in density estimation.
problem Improving computational efficiency in density estimation.
method Developed a statistical framework for coresets in nonparametric density estimation.
result Practical coreset kernel density estimators are near-minimax optimal.
Paper addresses statistical inference for GANs and minimax problems.
problem Statistical properties of GANs and minimax problems.
method Consistent estimation and confidence sets for GAN parameters.
result Confidence sets for GAN parameters contain the population solutions with desired coverage probability.
This paper tackles convex-submodular minimax problems in mixed continuous-discrete domains.
problem Convex-submodular minimax problems in mixed continuous-discrete domains.
method Introduces new notions of optimality and proposes iterative algorithms combining discrete and continuous optimization.
result Characterizes convergence rates, computational complexity, and quality of solutions for convex and monotone-submodular minimax problems.
Study apple tasting feedback in online binary classification, providing new insights into minimax expected mistakes.
problem Online binary classification with partial feedback (apple tasting).
method Combinatorial analysis, Littlestone dimension, Effective width.
result Established a trichotomy of minimax expected mistakes in the realizable setting.
Generative adversarial networks (GANs) are successful deep generative models. GANs are based on a two-player minimax game. However, the objective function derived in the original motivation is changed to obtain stronger gradients when learning the generator. We propose a novel algorithm that repeats the density ratio e…
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.
New minimax optimal learner for robust predictors against adversarial examples.
problem Learning robust predictors against adversarial examples.
method Global perspective and new algorithmic ideas.
result Characterizes classes of predictors that are robustly learnable.
Canonical correlation analysis (CCA) is a fundamental statistical tool for exploring the correlation structure between two sets of random variables. In this paper, motivated by recent success of applying CCA to learn low dimensional representations of high dimensional objects, we propose to quantify the estimation loss…
Proposes a fairness criterion for multi-objective optimization in classification.
problem Ensuring fairness in classification models across different groups.
method Formulates a minimax Pareto fairness criterion and provides an optimization algorithm.
result Demonstrates improved fairness compared to existing methods on various real-world datasets.
Variable selection is a fundamental task in statistical data analysis. Sparsity-inducing regularization methods are a popular class of methods that simultaneously perform variable selection and model estimation. The central problem is a quadratic optimization problem with an l0-norm penalty. Exactly enforcing the l0-no…
New evidence shows computational barriers in graphon estimation using low-degree polynomials.
problem Estimating graphons efficiently and accurately.
method Low-degree polynomials to analyze computational limits.
result Low-degree polynomial estimators cannot significantly outperform USVT in graphon estimation.
Paper bridges theory and algorithm for domain adaptation.
problem Domain adaptation from theory to algorithm gap.
method Extended domain adaptation theories, introduced Margin Disparity Discrepancy, and transformed into adversarial learning algorithm.
result Empirical studies show state-of-the-art accuracies on domain adaptation tasks.
New methods improve tree ensemble models by compressing them while maintaining accuracy.
problem Theoretical understanding and practical compression of tree ensembles like random forests and gradient boosting machines.
method Spectral perspective on tree ensembles, deriving minimax rates and developing compression schemes.
result Leading eigenfunctions/singular vectors capture dominant predictive directions, leading to smaller, competitive models.
The paper introduces Shapley curves for measuring variable importance in nonparametric settings.
problem Limited statistical understanding of Shapley values as variable importance measures.
method Introduces Shapley curves based on conditional expectation and covariate distribution; derives convergence rates and normality; proposes a novel bootstrap procedure.
result Validates theoretical findings with numerical studies and analyzes vehicle prices determinants.
Score-based diffusion models achieve optimal error bounds under non-parametric assumptions.
problem Improving the minimax optimality of score-based diffusion models.
method Kernel-based score estimation and early stopping strategy.
result Achieves minimax optimal error bounds under sub-Gaussian and Sobolev space assumptions.
Transformers recall from long distributions with statistical guarantees.
problem Designing Transformers that can recall from arbitrarily long, distributional contexts.
method Recast associative memory as probability measures, decomposing the task into recall and prediction.
result A shallow measure-theoretic Transformer learns the recall-and-predict map under spectral assumptions.
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…
Study minimax rates for online learning with time-varying dynamics.
problem Online learning with time-varying state and cost dynamics.
method Non-constructive upper and lower bounds, complexity and stability terms.
result Characterization of minimax rates and necessary conditions for learnability.
When faced with high frequency streams of data, clustering raises theoretical and algorithmic pitfalls. We introduce a new and adaptive online clustering algorithm relying on a quasi-Bayesian approach, with a dynamic (i.e., time-dependent) estimation of the (unknown and changing) number of clusters. We prove that our a…
Theoretical analysis of DQN and its variants.
problem Understanding the theoretical foundations of deep Q-learning.
method Theoretical analysis of DQN and Minimax-DQN algorithms under mild assumptions.
result Established rates of convergence for action-value functions and provided justifications for DQN techniques.
Unified framework for analyzing stable learning algorithms across different dataset shifts.
problem Analyzing and comparing stability of learning algorithms across various dataset shifts.
method Causal graphical representation to express dataset shifts and a hierarchy of operators to disable shift-causing edges.
result Established conditions for optimal performance and derived new algorithms for finding stable distributions.
Risk-averse model uncertainty framework for safe reinforcement learning.
problem Safe decision making in uncertain environments.
method Risk-averse perspective towards model uncertainty using coherent distortion risk measures; equivalent to distributionally robust safe reinforcement learning problems; efficient, model-free implementation.
result Demonstrates robust performance and safety across perturbed test environments.
New method uses GANs and proper scoring rules for robust scatter estimation.
problem Robust scatter estimation in statistics.
method General learning via classification framework based on proper scoring rules.
result Proposed robust scatter estimators achieve minimax rate under Huber's contamination model.
New algorithm minimizes expert selection regret in partial bandit feedback.
problem Minimizing expert selection regret in partial bandit feedback.
method Develops a sequential minimax optimal algorithm for a generalized partial monitoring setting.
result Second order regret bounds against a general expert selection sequence.
This paper improves the convergence rates of bilevel optimization algorithms.
problem Improving the convergence rates of bilevel optimization algorithms.
method Provided lower complexity bounds and proposed an accelerated bilevel optimizer.
result AccBiO achieves optimal results under certain conditions.
The paper provides a statistical decision-theoretical derivation of the Two-Stage approach for parameter estimation.
problem Theoretical justification for the Two-Stage approach in situations where likelihood is difficult to evaluate.
method Statistical decision-theoretical derivation leading to Bayesian and Minimax estimators.
result The Two-Stage approach is justified theoretically and applied to independent and identically distributed samples.
Data augmentation can achieve the same statistical benefits as full augmentation up to an approximation error.
problem Data augmentation in learning problems
method Using Fourier analysis and representation theory of finite groups
result Partial data augmentation achieves the same minimax rates as full augmentation
New method identifies optimal subset of stable information to transfer for better model generalization.
problem Non-reliability of machine learning models to dataset shifts.
method Causal minimax learning approach to identify optimal subset of stable information.
result Proposed algorithm efficiently searches for optimal subset with minimal worst-case risk.
Paper analyzes GANs training difficulties and proposes a control framework.
problem Difficulties in training GANs, especially for financial time series.
method Stochastic control framework for hyper-parameters tuning.
result Explicit forms for optimal adaptive learning rate and batch size derived.
Overparametrized neural networks can generalize well with proper regularization.
problem Generalization guarantee for noisy data in overparametrized neural networks.
method Nonparametric analysis of ℓ 2 \ell_2 ℓ 2 -regularized GD trajectories. result Achieving minimax optimal rate of L 2 L_2 L 2 estimation error with ℓ 2 \ell_2 ℓ 2 regularization. A new GAN training method using primal-dual subgradient methods.
problem Training GANs to avoid mode collapse and generate diverse samples.
method Relating GANs to convex optimization via Lagrangian perspective and primal-dual subgradient methods.
result The proposed method resolves mode collapse and generates diverse samples.
Estimates isotonic functions under unknown permutations, achieving optimal statistical and computational efficiency.
problem Estimating isotonic functions with unknown permutations in multiway comparison data.
method Mirsky partition estimator for minimax optimal and adaptive estimation.
result Achieves optimal worst-case statistical performance and computational efficiency.
Study detects boundaries in unlabeled noisy images without labels.
problem Detecting boundaries in unlabeled noisy images without labels.
method Proposed a continuous hinge-type surrogate loss for boundary detection, combined with deep neural networks.
result Deep neural network achieves minimax-optimal boundary recovery rate under piecewise smooth boundary model.
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.
Two new algorithms solve nonconvex-strongly concave problems efficiently.
problem Solving nonconvex-strongly concave minimax problems.
method Proposed MINIMAX-TR and MINIMAX-TRACE algorithms.
result Find ( ε , ε ) (ε, \sqrtε) ( ε , ε ) -second order stationary points within O ( ε − 1.5 ) \mathcal{O}(ε^{-1.5}) O ( ε − 1.5 ) iterations. Framework uses Minimax distances for unsupervised feature extraction.
problem Extracting features from unlabeled data.
method Develops a framework for computing Minimax distances and embedding them into a vector space.
result Minimax distances effectively capture underlying patterns and structures in data.
The paper optimizes training samples for image denoising across different noise levels.
problem Training a denoiser for all noise levels with uniform sample distribution.
method Derives a dual ascent algorithm for optimal sampling distribution.
result The algorithm converges to an optimal sampling distribution for deep neural networks.
Optimistic Mirror Descent framework improves bidding strategies in non-stationary first-price auctions.
problem Optimizing bidding strategies in non-stationary first-price auctions.
method Introducing Optimistic Mirror Descent (OMD) framework with novel optimism configuration.
result Minimax-optimal dynamic regret rates achieved for non-stationary first-price auctions.
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.