Discovering a correlation from one variable to another variable is of fundamental scientific and practical interest. While existing correlation measures are suitable for discovering average correlation, they fail to discover hidden or potential correlations. To bridge this gap, (i) we postulate a set of natural axioms …
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
25 results for “hypercontractive”
Logarithmic-Sobolev inequalities on non-compact Euclidean submanifolds: sharpness and rigiditymath.DG
Sharp -logarithmic-Sobolev inequalities on submanifolds with applications to hypercontractivity.
problem Developing inequalities on submanifolds of Euclidean space.
method Optimal mass transport theory on submanifolds, sharpness analysis.
result Sharp inequalities and equality conditions for submanifolds.
Universal tester-learner for halfspaces over structured distributions.
problem Learning halfspaces over a wide class of structured distributions.
method Uses a fully polynomial tester-learner based on hypercontractivity and sum-of-squares (SOS) programs.
result Achieves error on any labeled distribution that the tester accepts.
Study fast learning rates for square loss in dependent data with hypercontractivity condition.
problem Learning from dependent data with fast rates matching independent data.
method Martingale difference noise, trajectory hypercontractivity condition, least-squares estimator.
result Excess risk bound matches iid rate after burn-in time, independent of mixing-time.
Robustly clusters mixtures of Gaussians even with outliers.
problem Clustering mixtures of statistically separated Gaussians robustly to outliers.
method Uses certifiable hypercontractivity, bounded variance, and anti-concentration of linear projections.
result First efficient algorithm for robust clustering of statistically separated Gaussians mixtures.
Sharp comparison theorems are derived for all eigenvalues of the (weighted) Laplacian, for various classes of weighted-manifolds (i.e. Riemannian manifolds endowed with a smooth positive density). Examples include Euclidean space endowed with strongly log-concave and log-convex densities, extensions to -exponential …
Random features and KRR generalize similarly when N is large enough.
problem Understanding the generalization error of random features and KRR methods.
method Analyzing spectral conditions and hypercontractivity on kernel eigenfunctions.
result The test error of random features is larger than KRR when N is small, but they achieve the same error when N is large.
New method for robust linear regression in nearly linear time.
problem High-dimensional robust linear regression with adversarial corruption.
method Proposes estimators for two settings with near linear time complexity.
result Achieves optimal sample complexities and recovery guarantees.
Efficiently estimates linear models robust to corrupted data.
problem Learning linear models under adversarial corruption and minimal distributional assumptions.
method Develops a polynomial relaxation of independence to achieve optimal convergence rate.
result Achieves optimal convergence rate of for -hypercontractive distributions.
Let be the diffusion semigroup generated by on a complete connected Riemannian manifold with for some constants and the Riemannian distance to a fixed point. It is shown that is hypercontractive, or the log-Sobolev inequality holds for the…
Polynomial-time algorithm for estimating covariance in corrupted Gaussian data.
problem Estimating covariance in data with up to 1-α fraction of adversarial corruptions.
method Uses low-degree sum-of-squares certificates for anti-concentration and hypercontractivity.
result Outputs a list of candidate parameters with high probability containing a nearly correct covariance.
Improved subspace recovery algorithm with dimension-independent error and polynomial time.
problem Efficiently recover a covariance matrix from a mix of inliers and adversarial outliers.
method List-decodable subspace recovery algorithm with faster fixed-polynomial time and less restrictive distributional assumptions.
result Achieved dimension-independent error guarantee of O(1/α) with poly(1/α d^O(1)) time complexity.
Sharp Gaussian isoperimetry proven along Ricci flow.
problem Proving sharp Gaussian isoperimetric inequality for Ricci flow.
method Using monotonicity formula to prove inequality.
result Exact Gaussian enlargement theorem and concentration estimates.
The paper extends kernel ridge regression to product kernels and reveals new convergence behaviors.
problem Understanding kernel ridge regression in large dimensions with various kernels.
method Established a broad family of large dimensional kernels and derived convergence rates.
result Revealed new phenomena including minimax optimality, saturation effect, and multiple descent behavior.
Sharp log-Sobolev inequalities proved for spaces.
problem Proving log-Sobolev inequalities in noncompact metric measure spaces.
method Sharp isoperimetric inequality, symmetrisation, scaling argument, Hamilton-Jacobi inequality, Sobolev regularity.
result Sharp log-Sobolev inequalities established in spaces.
Robust statistics traditionally focuses on outliers, or perturbations in total variation distance. However, a dataset could be corrupted in many other ways, such as systematic measurement errors and missing covariates. We generalize the robust statistics approach to consider perturbations under any Wasserstein distance…
We give the first polynomial-time algorithm for performing linear or polynomial regression resilient to adversarial corruptions in both examples and labels. Given a sufficiently large (polynomial-size) training set drawn i.i.d. from distribution D and subsequently corrupted on some fraction of points, our algorithm out…
In the dictionary learning (or sparse coding) problem, we are given a collection of signals (vectors in ), and the goal is to find a "basis" in which the signals have a sparse (approximate) representation. The problem has received a lot of attention in signal processing, learning, and theoretical computer…
New algorithm reduces contamination in supervised learning.
problem Learning with contamination in supervised learning.
method Iterative polynomial filtering.
result Efficient learning of functions with contamination.
Robust estimation methods find global minima efficiently via quasi-gradients.
problem Efficiently solving robust estimation problems with non-convex optimization.
method Identifying generalized quasi-gradients to guarantee low-regret algorithms.
result Generalized quasi-gradients ensure efficient approximation of global minima.
Polynomial-time private algorithm for robust estimation of mean and covariance in the presence of outliers.
problem Estimating mean and covariance in the presence of adversarial outliers.
method Stabilizing convex relaxations using a new estimate-dependent noise injection mechanism.
result First efficient private robust estimation algorithm for covariance without condition-number assumptions.
New algorithms improve approximation of matrix norms, with applications in statistics and machine learning.
problem Improving approximation of matrix norms for in polynomial time.
method Polynomial-time multiplicative approximation algorithms for norm, leveraging sum-of-squares certificates.
result Achieved polynomially improved approximation factors, notably for .
New study shows exponential lower bound for RL even with constant suboptimality gap.
problem Can RL be sample-efficient with a constant suboptimality gap?
method Analyzes reinforcement learning in the online setting with a linearly realizable optimal Q-function.
result An exponential sample complexity lower bound still holds even with a constant suboptimality gap.
New findings show that common optimization algorithms struggle with random problems.
problem Finding near-optimal solutions to random optimization problems.
method Low-degree polynomials, Boolean circuits, and Langevin dynamics.
result These algorithms fail to produce nearly optimal solutions with high probability.
A new method estimates parameters in heavy-tailed corrupted regression with unknown covariance and heterogeneous noise.
problem Estimating parameters in regression with heavy-tailed errors and unknown covariance.
method Near-optimal computationally tractable estimator based on power method and Multiplicative Weight Update algorithm.
result The estimator achieves the optimal statistical rate and breakdown-point under near-optimal sample size.