Sharp bounds on uniform generalization errors in binary linear classification.
problem Understanding the uniform generalization errors in binary linear classification.
method Isoperimetric arguments, Poincaré and log-Sobolev inequalities for joint distributions.
result Sharp concentration bounds on uniform generalization errors, almost sure convergence in broad settings.
Sharp bounds established for Federated Averaging (FedAvg), improving convergence rates.
problem Undetermined convergence rate of Federated Averaging (FedAvg) in Federated Learning.
method Developed novel iterate bias concept and proved sharp bounds on it, leading to improved convergence results.
result Lower bounds for FedAvg match existing upper bounds, showing no improvable capacity.
Sharp bounds on weak convergence rate for rough volatility models.
problem Understanding the convergence rate in discretizing rough volatility models.
method Analyzing general and linear models to derive bounds.
result Sharper bound of \(H + 1/2\) for linear models.
New couplings improve understanding of molecular dynamics convergence.
problem Understanding convergence of Andersen dynamics in high dimensions.
method Presented couplings to obtain sharp convergence bounds in the Wasserstein sense.
result Sharp convergence bounds in the Wasserstein sense without global convexity.
Sharp estimates for Bergman metrics derived from Kähler quantization.
problem Estimating Bergman metrics in Kähler quantization.
method Upper and lower bounds on the Bergman metric expressed in terms of φ \varphi φ . result Optimal C 1 , 1 ˉ C^{1,\bar1} C 1 , 1 ˉ -convergence for quantization of Kähler currents. Sharp-MAML improves MAML by reducing saddle points in few-shot learning.
problem Challenges in optimizing MAML due to complex loss landscape.
method Sharpness-aware minimization applied to MAML.
result Sharp-MAML and its variant outperform plain MAML on few-shot learning tasks.
Sharp results link DLN gradient flow to basis pursuit optimization and GHA phase transitions.
problem Understanding implicit regularization in Diagonal Linear Networks.
method Sharp convergence bounds and characterization of ℓ 1 \ell_1 ℓ 1 minimizers. result Gradient flow of DLNs with tiny initialization approximates minimizers of basis pursuit optimization problem.
Improved KL convergence bounds for score diffusion models without restrictive assumptions.
problem Lack of comprehensive quantitative results for diffusion models, especially in non-regular scores and estimators.
method Score diffusion models with fixed step size from Ornstein-Uhlenbeck and kinetic semigroups, providing explicit and sharp KL convergence bounds.
result Explicit and sharp convergence bounds in KL applicable to any data distribution with finite Fisher information.
DGSAM improves domain generalization by minimizing individual sharpness.
problem Improving domain generalization models that perform well on unseen target domains.
method Shifts DG paradigm toward minimizing individual sharpness across source domains.
result DGSAM reduces performance variance across domains with less computational overhead.
We present some geometric applications, of global character, of the bubbling analysis developed by Buzano and Sharp for closed minimal surfaces, obtaining smooth multiplicity one convergence results under upper bounds on the Morse index and suitable lower bounds on either the genus or the area. For instance, we show th…
Paper introduces DMPMs for efficient discrete data generation with sharp convergence bounds.
problem Efficient generation of discrete data with theoretical guarantees.
method Discrete Markov Probabilistic Models (DMPMs) operating in bit space with time-reversal process.
result Sharp convergence bounds established under minimal assumptions, competitive performance in discrete data generation.
Study sharp convergence rates of empirical UOT for spatio-temporal point processes.
problem Statistical analysis of UOT for spatio-temporal point processes.
method Empirical plug-in estimators for Kantorovich-Rubinstein distance between intensity measures.
result Sharp convergence rates of empirical UOT in terms of intrinsic dimensions of measures.
New algorithm optimizes convex functions with noisy evaluations in one dimension.
problem Optimizing convex functions with noisy zero-order evaluations in one dimension.
method Proposed a computationally efficient algorithm achieving O ( 1 / T ) O(1/\sqrt{T}) O ( 1/ T ) convergence rate. result Achieved the optimal O ( 1 / T ) O(1/\sqrt{T}) O ( 1/ T ) convergence rate, closing the gap in one dimension. The article introduces a new convergence concept for Lorentzian spaces and applies it to generalized cones.
problem Stability of curvature bounds in generalized Lorentzian cones.
method Introduces ℓ \ell ℓ -convergence for Lorentzian pre-length spaces, applies it to generalized cones, and proves stability of curvature bounds. result Sharp timelike curvature and curvature-dimension bounds for generalized cones are established.
This paper closes the gap on matching pursuit's convergence rate.
problem Improving the understanding of matching pursuit's convergence rate.
method Constructing a worst case dictionary to analyze matching pursuit's performance.
result Sharp characterization of matching pursuit's convergence rate as n − α n^{-α} n − α , with α ≈ 0.182 α \approx 0.182 α ≈ 0.182 . Sharp convergence theorem for sphere submanifolds proved.
problem Sphere submanifolds in spheres.
method Proved a sharp convergence theorem.
result New differentiable sphere theorem for submanifolds in spheres.
Unified analysis improves SAM for non-convex optimization.
problem Improving generalization in machine learning models.
method Sharpness-aware minimization (SAM) and Unified SAM.
result Unified SAM provides convergence guarantees under relaxed assumptions.
We study the spherical cap packing problem with a probabilistic approach. Such probabilistic considerations result in an asymptotic sharp universal uniform bound on the maximal inner product between any set of unit vectors and a stochastically independent uniformly distributed unit vector. When the set of unit vectors …
The paper analyzes sampling efficiency of discrete diffusion models, providing sharp and adaptive guarantees.
problem Theoretical foundations of discrete diffusion models, especially sampling efficiency.
method Continuous-time Markov chain (CTMC) formulation, τ τ τ -leaping-based samplers, effective total correlation. result The τ τ τ -leaping algorithm achieves an iteration complexity of order i l d e O ( d / ε ) ilde O(d/\varepsilon) i l d e O ( d / ε ) for uniform discrete diffusion, improving existing bounds by a factor of d d d . Novel oracle-type inequality for logistic loss in DNNs achieves sharp convergence rates.
problem Generalization analysis for binary classification with DNNs and logistic loss.
method Established an oracle-type inequality to handle the boundedness of the target function.
result Optimal convergence rates for fully connected ReLU DNN classifiers trained with logistic loss.
Paper analyzes online tensorial ICA convergence with stochastic approximation.
problem Online tensorial ICA convergence analysis.
method Stochastic approximation for nonconvex optimization.
result Sharp finite-sample error bound of O ~ ( d / T ) \tilde{O}(\sqrt{d/T}) O ~ ( d / T ) . Sharp convergence analysis for nonconvex regression models.
problem Nonconvex optimization in regression models with normally distributed covariates.
method Gaussian comparison theorems for analyzing iterative algorithms.
result Sharp global convergence rates for various statistical models.
Forward regression is a statistical model selection and estimation procedure which inductively selects covariates that add predictive power into a working statistical regression model. Once a model is selected, unknown regression parameters are estimated by least squares. This paper analyzes forward regression in high-…
Develops a method to estimate policy values robustly in the presence of confounding variables.
problem Infinite-horizon reinforcement learning with unobserved confounding variables makes policy evaluation unidentifiable.
method Robust approach estimating sharp bounds on policy value using optimization over state-occupancy ratios and sensitivity model.
result Proves convergence to sharp bounds as more confounded data is collected.
The goal of decentralized optimization over a network is to optimize a global objective formed by a sum of local (possibly nonsmooth) convex functions using only local computation and communication. It arises in various application domains, including distributed tracking and localization, multi-agent co-ordination, est…
We study statistical risk minimization problems under a privacy model in which the data is kept confidential even from the learner. In this local privacy framework, we establish sharp upper and lower bounds on the convergence rates of statistical estimation procedures. As a consequence, we exhibit a precise tradeoff be…
SAM optimizes deep networks by oscillating between sides of the minimum.
problem Improving performance of deep networks.
method Gradient-based optimization method that oscillates between sides of the minimum.
result SAM effectively performs gradient descent on the spectral norm of the Hessian, encouraging drift towards wider minima.
Deep linear networks minimize sharpness, avoiding large eigenvalues.
problem Understanding optimization dynamics in deep linear networks for regression.
method Analyzing sharpness (largest eigenvalue of Hessian) of minimizers and gradient flow solutions.
result Gradient flow implicitly regularizes towards flat minima, with sharpness bounded by a constant.
When randomized ensembles such as bagging or random forests are used for binary classification, the prediction error of the ensemble tends to decrease and stabilize as the number of classifiers increases. However, the precise relationship between prediction error and ensemble size is unknown in practice. In the standar…
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…
Stochastic (sub)gradient methods require step size schedule tuning to perform well in practice. Classical tuning strategies decay the step size polynomially and lead to optimal sublinear rates on (strongly) convex problems. An alternative schedule, popular in nonconvex optimization, is called \emph{geometric step decay…
Sharp analysis of power iteration for tensor PCA, improving convergence and stopping criteria.
problem Analyzing the power iteration algorithm for tensor PCA to improve convergence and stopping criteria.
method Sharp bounds on the number of iterations, revealing a smaller algorithmic threshold, proposing a stopping criterion.
result Sharp bounds on the number of iterations required for power method to converge, revealing a smaller algorithmic threshold than previously conjectured.
Motivated by a classical comparison result of J. C. F. Sturm we introduce a curvature-dimension condition CD(k,N) for general metric measure spaces and variable lower curvature bound k. In the case of non-zero constant lower curvature our approach coincides with the celebrated condition that was proposed by K.-T. Sturm…
SAM optimizer struggles to converge to global minima or stationary points in practical settings.
problem Limited convergence of SAM optimizer to global minima or stationary points in practical scenarios.
method Deterministic and stochastic versions of SAM with constant perturbation size and gradient normalization were studied.
result SAM has limited capability to converge to global minima or stationary points in many scenarios.
This paper improves HNNs by learning optimal curvature for better generalization.
problem Inappropriate curvatures in HNNs lead to suboptimal performance.
method Sharpness-aware curvature learning method to smooth loss landscape.
result Proposed method improves HNNs' generalization across various settings.
A simple function shows how neural nets can converge despite high sharpness.
problem Understanding why neural nets converge with high sharpness.
method Constructed a minimal example function and analyzed its training dynamics rigorously.
result Final converging point has sharpness close to 2 / η 2/η 2/ η . Sharp bounds found for minimal surface solutions.
problem Finding bounds for minimal surface solutions.
method Analyzing minimal surface equation with specific boundary conditions.
result Sharp bounds established for solutions over certain domains.
Enhances deep learning by boosting generalization and convergence.
problem Improving generalization and convergence in deep learning models.
method Implicit Regularization Enhancement (IRE) framework that decouples flat and sharp directions.
result IRE consistently improves generalization performance across various deep learning tasks and models.
Sharp bounds on Alexandrov spaces' boundaries with rigidity analysis.
problem Volume bounds on Alexandrov spaces' boundaries.
method Sharp volume bounds and rigidity analysis of Alexandrov spaces.
result New sharp volume bounds and classification of rigidity cases.
This paper approximates SA iterates using Gaussian distributions for tail bounds.
problem Characterizing the distribution of stochastic approximation iterates in finite time.
method Approximating pre-limit distributions of SA iterates by Gaussian sequences with recursively defined covariances.
result Explicit bounds on the Wasserstein-1 distance between rescaled iterates and Gaussians.
Sharp Gaussian bounds derived for Schrödinger kernel on Ricci solitons.
problem Analyzing Schrödinger heat kernel on gradient shrinking Ricci solitons.
method Deriving sharp Gaussian upper bounds for the Schrödinger heat kernel.
result Sharp upper and lower bounds for eigenvalues of the Schrödinger operator.
Sharp convergence theorem for Yang-Mills flow on ALE manifolds proved.
problem Proving convergence of Yang-Mills flow on ALE gravitational instantons.
method Noncompact version of the 'parabolic gap theorem'.
result Sharp convergence theorem for Yang-Mills flow on ALE 4-manifolds.
WARPd method solves inverse problems with approximate sharpness conditions.
problem Reconstruction of signals from undersampled and noisy measurements.
method First-order method based on primal-dual iterations with restart-reweight scheme.
result WARPd achieves stable linear convergence under generic approximate sharpness condition.
Sharp bounds derived for the first two Steklov eigenvalues of exterior domains.
problem Finding bounds for the first two eigenvalues of Steklov eigenvalue problems on exterior domains.
method Sharp lower and upper bounds derived using the support function and distance function to the origin of the boundary.
result Sharp bounds for the first two eigenvalues of Steklov eigenvalue problems on exterior domains.
We consider the high-dimensional discriminant analysis problem. For this problem, different methods have been proposed and justified by establishing exact convergence rates for the classification risk, as well as the l2 convergence results to the discriminative rule. However, sharp theoretical analysis for the variable…
GD monotonically decreases GFS sharpness in neural networks and scalar models.
problem Oscillatory behavior of loss in GD training.
method Analysis of GFS sharpness and empirical validation.
result GFS sharpness decreases monotonically during GD training.
Sharp upper bound found for stable minimal surfaces.
problem Bounding the diameter of stable minimal surfaces.
method Analyzing three-dimensional Riemannian manifolds with specific curvature conditions.
result Sharp upper bound for the diameter of stable minimal surfaces.
The paper sharpens the analysis of sketch-and-project methods using randomized singular value decomposition.
problem Improving convergence rates of sketch-and-project methods for solving linear systems and non-linear optimization problems.
method Developing a theoretical framework and new spectral bounds for the expected sketched projection matrix.
result The convergence rate improves linearly with sketch size and even faster with certain spectral decays.