Two-stage nonconvex algorithm and convex relaxation both achieve optimal accuracy in noisy blind deconvolution.
problem Solving bilinear systems of equations with random noise under different designs.
method Two-stage nonconvex algorithm and convex relaxation.
result Both methods achieve minimax-optimal accuracy in the presence of random noise.
The paper analyzes how clustering sensitive data can improve model generalization without revealing individual information.
problem Ensuring user data privacy in personalized recommendation systems.
method Look-alike clustering to replace sensitive features with cluster averages, analyzed using Convex Gaussian Minimax Theorem.
result Training models using anonymous cluster centers can improve generalization error, especially in high-dimensional settings.
New theorem guarantees approximate equilibrium in non-convex games.
problem No guarantee of equilibrium in non-convex games.
method Introduced a minimax theorem for non-convex games involving neural networks.
result Provided an approximate minimax theorem for non-convex games.
Paper proves Sion's theorem in geodesic spaces and develops a Riemannian extragradient method.
problem Understanding saddle points in nonconvex-nonconcave minimax problems.
method Geodesic metric space version of Sion's theorem and Riemannian extragradient method.
result Developed a Riemannian extragradient algorithm for smooth minimax problems.
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.
GAT-GMM improves GANs' performance in learning Gaussian mixture models.
problem GANs struggle with multi-modal distributions like Gaussian mixtures.
method Proposes a minimax GAN framework using random linear generator and softmax-based quadratic discriminator.
result Gradient Descent Ascent method converges to an approximate minimax point.
The paper develops a new algorithm for constructing minimax estimators using online learning techniques.
problem Designing minimax estimators for probability distribution parameters.
method Viewing the problem as a zero-sum game and using online learning with non-convex losses to find a Nash equilibrium.
result The algorithm constructs both a minimax estimator and a least favorable prior.
The paper tackles minimax optimality in continuum contextual bandits with Hölder continuity.
problem Minimizing regret in a continuum of contexts with Hölder continuity.
method Proves a static-to-contextual regret conversion theorem and analyzes various dependency cases.
result Achieves minimax optimal contextual regret for convex and strongly convex bandits.
The paper proves conditions for zero Gaussian curvature convex hypersurfaces to be hyperplanes.
problem Conditions for zero Gaussian curvature convex hypersurfaces to be hyperplanes.
method Proving Bernstein type theorems for entire convex graphical hypersurfaces with zero Gaussian curvature in Euclidean and Minkowski contexts.
result Zero Gaussian curvature convex hypersurfaces must be hyperplanes if the mean curvature goes to zero at infinity.
Study on predicting sequences with Gaussian constraints, linking to intrinsic volumes and metric complexity.
problem Predicting sequences almost as well as the best Gaussian distribution with mean in a given subset.
method Expressed minimax regret in terms of intrinsic volumes, established comparison inequality for Wills functional, characterized global covering numbers and local Gaussian widths.
result Sharp estimates on the log-Laplace transform of intrinsic volume sequence for a general nonconvex set.
Sharp risk bounds for early-stopping in Gaussian linear regression are derived.
problem Minimizing in-sample mean squared error in high-dimensional Gaussian linear regression.
method Early-stopped mirror descent (ESMD) with local Gaussian width bounds.
result Sharp risk bounds extend to early-stopped mirror descent for least squares estimator (LSE).
Least Squares Estimators are suboptimal for 5D convex functions.
problem Suboptimality of Least Squares Estimators in estimating multidimensional convex functions.
method Analysis of natural subclasses of convex functions in random and fixed design settings.
result Risk of LSE is n−2/d while minimax risk is n−4/(d+4) for d≥5. We study computational and statistical consequences of problem geometry in stochastic and online optimization. By focusing on constraint set and gradient geometry, we characterize the problem families for which stochastic- and adaptive-gradient methods are (minimax) optimal and, conversely, when nonlinear updates -- su…
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 …
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 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 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.
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.
New Gaussian min-max theorem extends classical results to non-i.i.d. Gaussian matrices.
problem Extending classical Gaussian min-max theorems to non-i.i.d. Gaussian matrices.
method Identifying a new pair of Gaussian processes that satisfy comparison inequalities.
result New Gaussian min-max and convex Gaussian min-max theorems with applications in multi-source Gaussian regression and binary classification.
The paper analyzes how optimization algorithms affect the generalization of minimax models.
problem The generalization performance of minimax models trained with different optimization algorithms.
method Analysis of gradient descent ascent (GDA) and proximal point method (PPM) algorithms under convex concave and non-convex non-concave settings.
result The PPM algorithm ensures a bounded excess risk in convex concave problems, while GDA's generalization depends on solving subproblems simultaneously.
The study uncovers the breakdown of Gaussian universality in high-dimensional empirical risk minimization.
problem Understanding the breakdown of Gaussian universality in high-dimensional empirical risk minimization.
method Extending the Convex Gaussian Min-Max Theorem to non-Gaussian settings, deriving asymptotic min-max characterizations, and proving asymptotic equivalence of regularizers.
result The projection of the ERM estimator onto a test covariate approximately follows a Gaussian convolution under certain conditions.
We analyze learning curves of RF models with convex regularization and derive precise asymptotic expressions.
problem Understanding the learning curves of RF models with general convex regularization.
method Novel multi-level application of the convex Gaussian min max theorem (CGMT) to compute precise asymptotic expressions.
result Precise asymptotic expressions for learning curves of RF models with separable strongly convex regularization or ℓ1 regularization. New algorithms ensure reproducibility and optimal convergence in convex optimization.
problem Trade-off between reproducibility and convergence rate in convex optimization.
method Regularization-based algorithms for smooth convex minimization and minimax optimization.
result Achieves optimal reproducibility and near-optimal gradient complexity for various oracle settings.
Deep learning has been applied to various tasks in the field of machine learning and has shown superiority to other common procedures such as kernel methods. To provide a better theoretical understanding of the reasons for its success, we discuss the performance of deep learning and other methods on a nonparametric reg…
Simple proof shows forecasts can be calibrated in a few periods.
problem Ensuring forecasts are calibrated over multiple periods.
method Uses minimax theorem to prove existence and guarantees calibration error.
result Calibration can be achieved in N3 periods with error at most 1/N. Paper improves algorithms for convex-concave minimax optimization problems.
problem Minimizing convex-concave functions with strong convexity and concavity properties.
method Proposes a new algorithm with improved gradient complexity.
result Improves gradient complexity upper bound for minimax optimization.
Paper finds periodic orbits for convex Lagrangian systems on noncompact manifolds.
problem Existence of periodic orbits in convex Lagrangian systems on complete Riemannian manifolds.
method Developed a modified minimax principle to prove the existence of periodic orbits.
result Proved the existence of contractible periodic orbits for almost every energy level.
New methods solve complex optimization problems without strong convexity assumptions.
problem Complex bilevel optimization problems with minimax lower-level structures.
method Penalty-based first-order methods for bilevel minimax optimization.
result Achieves ε-KKT point with improved oracle complexity. Paper solves minimax optimization gap with near-optimal algorithms.
problem Designing efficient algorithms for smooth and strongly-convex-strongly-concave minimax problems.
method Accelerated proximal point method and accelerated solver for minimax proximal steps.
result First algorithm with gradient complexity matching the lower bound up to logarithmic factors.
Study on signal detection in heteroscedastic Gaussian sequences with sparse alternatives.
problem Signal detection in heterogeneous Gaussian sequences with unknown means and known covariance.
method Characterization of minimax separation radius and derivation of matching upper and lower bounds.
result Matching minimax upper and lower bounds for signal detection in heteroscedastic Gaussian sequences.
MixMax improves model performance across different settings using convex optimization.
problem Worst-case performance in group distributionally robust optimization for non-convex and non-parametric models.
method Reparameterizing group DRO from parameter space to function space, resulting in a convex optimization problem.
result MixMax matches or outperforms standard group DRO baselines, improving XGBoost performance on specific datasets.
Paper solves DRO for continuous distributions with iterative algorithms.
problem Distributionally robust optimization with continuous worst-case distributions.
method Iterative algorithm for global convergence, leveraging Brenier's theorem and JKO scheme.
result Achieves global convergence under mild assumptions for minimax problems.
Rényi divergence is related to Rényi entropy much like Kullback-Leibler divergence is related to Shannon's entropy, and comes up in many settings. It was introduced by Rényi as a measure of information that satisfies almost the same axioms as Kullback-Leibler divergence, and depends on a parameter that is called its or…
SDP achieves optimal error in noisy phase synchronization.
problem Phase synchronization with noisy measurements.
method SDP relaxation of Maximum Likelihood Estimation (MLE).
result Achieves error bound of (1+o(1))2npσ2 under normalized squared ℓ2 loss, matching minimax lower bound. 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.
Gaussian processes struggle with compositional functions, but deep Gaussian processes can outperform.
problem Gaussian process regression struggles with compositional functions.
method We study information-theoretic lower bounds for posterior contraction rates in Gaussian process regression for a continuous regression model.
result Posterior based on any mean-zero Gaussian process can only recover the truth at a rate strictly slower than the minimax rate for generalized additive functions.
In this paper we give sufficient conditions guaranteeing the validity of the well-known minimax theorem for the lower Snell envelope with respect to a family of absolutely continuous probability measures. Such minimax results play an important role in the characterisation of arbitrage-free prices of American contingent…
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.
VRPG algorithm optimizes convex constraints with non-asymptotic guarantees.
problem Stochastic convex optimization under convex constraints.
method Natural variance reduced proximal gradient (VRPG) algorithm.
result VRPG achieves local minimax lower bound up to constants and log factor of N. Paper studies early-stopped mirror descent for noisy sparse phase retrieval.
problem Recovering a sparse signal from noisy quadratic measurements.
method Early-stopped mirror descent with hyperbolic entropy mirror map.
result Achieves nearly minimax-optimal rate of convergence for k-sparse signals. Paper proposes SMO for solving bilevel optimization problems efficiently.
problem Solving bilevel optimization problems with nonsmooth convex lower-level and nonconvex upper-level objectives.
method Sequential minimax optimization (SMO) method using modified augmented Lagrangian and penalty schemes.
result Improves operation complexity for finding ε-KKT solutions. New algorithm solves nonconvex-convex minimax problems efficiently.
problem Solving nonconvex-convex minimax problems with nonsmooth, nonconvex, and nonlinearity.
method Hybrid variance-reduced SGD algorithm combining smoothing and biased techniques.
result Achieves O(T^(-2/3)) convergence rate and best oracle complexity.
New research sets the minimax lower bound for KSD estimation at sqrt(n).
problem Estimating goodness-of-fit using Kernel Stein Discrepancy (KSD) on high-dimensional spaces.
method Two complementary results proving the minimax lower bound of KSD estimation.
result The minimax lower bound of KSD estimation is n^(-1/2), indicating exponential difficulty with dimensionality.
Deep random feature models are analyzed for their performance with exact asymptotic expressions.
problem Understanding the performance of deep random feature models.
method Established a novel universality result and used the convex Gaussian Min-Max theorem.
result Exact asymptotic expressions for the performance of deep random feature models are derived.
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.
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.
It is generally believed that ensemble approaches, which combine multiple algorithms or models, can outperform any single algorithm at machine learning tasks, such as prediction. In this paper, we propose Bayesian convex and linear aggregation approaches motivated by regression applications. We show that the proposed a…
We prove a new minimax theorem connecting the worst-case Bayesian regret and minimax regret under partial monitoring with no assumptions on the space of signals or decisions of the adversary. We then generalise the information-theoretic tools of Russo and Van Roy (2016) for proving Bayesian regret bounds and combine th…