Polynomial-time algorithm finds planted hypercube vectors in Gaussian mixtures.
problem Clustering d-dimensional Gaussian mixtures with unknown covariance.
method Lattice-based methods using Lenstra--Lenstra--Lovasz reduction.
result Achieves statistically-optimal sample complexity of d+1 samples.
Efficient method for tensor linear form inference with noisy incomplete data.
problem Statistical inference of tensor linear forms with incomplete and noisy observations.
method Initial estimate + debiasing + one-step power iteration.
result Optimal uncertainty quantification and statistical-to-computational gaps examined.
Study on detecting and recovering hidden dense cycles in random graphs.
problem Detecting and recovering hidden dense cycles in random graphs.
method Information-theoretic analysis of thresholds for detection and recovery.
result Characterization of information-theoretic thresholds for detection and recovery.
Characterizes optimal reconstruction error in high-dimensional Gaussian mixtures.
problem Optimizing reconstruction error in high-dimensional sparse Gaussian mixtures.
method Exact asymptotic characterization using state evolution of AMP algorithm.
result Identification of statistical-to-computational gap between AMP and information-theoretic threshold.
Noise Sensitivity Exponent controls statistical-computational gaps in learning.
problem Understanding when learning is statistically possible yet computationally hard in high-dimensional statistics.
method Investigating statistical-computational gaps in single- and multi-index models using Noise Sensitivity Exponent.
result Noise Sensitivity Exponent governs statistical-computational gaps in high-dimensional learning.
Study optimal algorithms for recovering signals through inhomogeneous low-rank channels.
problem Recovering signals through an inhomogeneous low-rank matrix channel.
method Derive and analyze an approximate message-passing algorithm (AMP) and a spectral method.
result The AMP iteration matches the conjectured optimal computational phase transition.
Statistical mechanics explains learning in large neural networks near interpolation.
problem Understanding the learning dynamics of large neural networks near interpolation.
method Statistical physics analysis of a two-layer network with generic weight distribution and activation function.
result Learning transitions and feature learning emerge as the number of data increases.
Develops a new tensor model for clustering with degree correction.
problem Clustering with unknown degree heterogeneity in multiway data.
method Degree-corrected tensor block model with estimation guarantees.
result Demonstrates an intrinsic statistical-to-computational gap for tensors of order three or greater.
An efficient algorithm identifies labels from sparse pooled data.
problem Identify unknown labels from condensed measurements of items.
method Design an efficient algorithm based on novel pooling scheme.
result Resolves statistical-to-computational gap in minimum pools needed.
Neural networks can learn from higher-order cumulants efficiently, requiring quadratic samples.
problem Learning from higher-order cumulants in high-dimensional data.
method Spiked cumulant model, polynomial time algorithms, neural networks, random features.
result Neural networks require quadratic samples to learn from higher-order cumulants efficiently, while random features require more samples.
Various alignment problems arising in cryo-electron microscopy, community detection, time synchronization, computer vision, and other fields fall into a common framework of synchronization problems over compact groups such as Z/L, U(1), or SO(3). The goal of such problems is to estimate an unknown vector of group eleme…
New insights into statistical and computational limits for mixed sparse linear regression.
problem Recovering two sparse signals from noisy linear measurements.
method Analysis of low-degree polynomials and a simple thresholding algorithm.
result Identification of a smooth information-computation tradeoff and order-optimality of the thresholding algorithm.
Wedge Sampling improves tensor completion with nearly-linear sample complexity.
problem Efficiently completing low-rank tensors from a subset of entries.
method Non-adaptive wedge sampling to promote structured connections in tensor completion.
result Polynomial-time algorithms achieve weak and exact recovery with nearly linear sample complexity.
Paper explores statistical and computational limits of estimating low-rank Gaussian mixtures.
problem Estimating low-rank matrix-variate observations with optimal statistical and computational limits.
method Low-rank Gaussian mixture model (LrMM) and minimax lower bounds.
result Minimax optimality of maximum likelihood estimator and spectral aggregation method.
New algorithms for hypothesis testing in high-dimensional data are shown to be effective under various noisy conditions.
problem Testing high-dimensional probability measures under noisy conditions.
method Low coordinate degree functions (LCDF) using Efron-Stein decomposition.
result LCDF can effectively test high-dimensional probability measures under noisy channels, with efficacy depending on scalar Fisher information.
Efficiently transforms Gaussian data to simulate various target distributions.
problem Generating observations from different target distributions given a single Gaussian observation.
method Designs computationally efficient procedures to approximate target distributions.
result Establishes reduction-based computational lower bounds for high-dimensional statistical models.
Enhances inference of spreading processes using neural-network priors.
problem Estimating initial states of graph processes from partial observations.
method Bayesian framework with single-layer perceptron neural network for initial states; hybrid BP-AMP algorithm.
result Model exhibits first-order phase transitions, creating a statistical-to-computational gap.
New algorithms detect categorical structures in high-dimensional data.
problem Detecting categorical structures in high-dimensional data.
method Low coordinate degree functions (LCDF) applied to categorical and stochastic block models.
result Unified analysis of LCDF performance for various SBMs and tight lower bounds.
Paper uses algebraic signatures to identify probabilistic structures in empirical data.
problem Identifying probabilistic structure from observed binomials in empirical probability tensors.
method Treating vanishing binomials as algebraic signatures, matching signatures to identify models without parameter estimation.
result The method successfully identified rank-one structures in real language data, revealing interpretable sets of words.
In this work we study the non-parametric reconstruction of spatio-temporal dynamical Gaussian processes (GPs) via GP regression from sparse and noisy data. GPs have been mainly applied to spatial regression where they represent one of the most powerful estimation approaches also thanks to their universal representing p…
The paper explores gaps in curvature-related metrics and rigidity.
problem Understanding gaps in curvature-related metrics and rigidity.
method Analyzes three types of gaps: spectral, metric-rigidity, and topological-rigidity.
result Proposes open problems in the field.
Study gap-dependent regret bounds for risk-sensitive RL.
problem Risk-sensitive reinforcement learning with entropic risk measure.
method Propose cascaded gaps to adapt to problem structures, derive regret bounds.
result Exponential improvement over existing bounds in appropriate settings.
Paper analyzes origami slope gaps and their distribution, finding a unique pattern.
problem Analyzing slope gaps in origami surfaces.
method Derived slope gap distribution of a specific origami by considering return times under the horocycle flow.
result Found a unique distribution of origami slope gaps, not a sum of scaled Hall distributions.
Random hyperbolic surfaces have nearly optimal spectral gaps.
problem Proving the nearly optimal spectral gap conjecture for random Belyi surfaces.
method Using the Brooks-Makover model, the authors show a spectral gap greater than 1/4 - c/log(n).
result A random hyperbolic surface in the Brooks-Makover model has a spectral gap greater than 1/4 - c/log(n).
Paper improves volume gap between minimal submanifolds and unit spheres.
problem Volume gap between minimal submanifolds and unit spheres.
method Modified Cheng-Li-Yau coefficients and applied Cheng-Yang eigenvalue estimate for Laplacian.
result Enhanced volume gap between minimal submanifolds and unit spheres.
The article proves a conjecture about the fundamental gap for horoconvex domains in hyperbolic space.
problem Proving a conjecture about the fundamental gap for horoconvex domains in hyperbolic space.
method Establishing conformal log-concavity estimates for the first eigenfunction.
result Proves a conjecture about the fundamental gap for horoconvex domains in hyperbolic space.
Local gaps in Ricci shrinkers depend only on dimension.
problem Understanding local properties of Ricci shrinkers.
method Proved local versions of Ricci curvature and entropy gap theorems.
result Local gaps depend only on dimension, not global entropy.
Study shows gaps in Bitcoin order book are linked to returns but only in the short term.
problem Understanding the relationship between gaps and returns in Bitcoin order books.
method Examined the dynamics of gaps and returns in a Bitcoin order book without considering long-term causation.
result The causal relationship between gaps and returns is limited to instantaneous causation.
Researchers compute gap distributions for saddle connection directions on specific translation surfaces.
problem Computing gap distributions for saddle connection directions on translation surfaces.
method Translation to dynamical question of return times to a transversal under the horocycle flow.
result Gap distributions have support at 0 and quadratic tail decay.
Proves gap rigidity theorem for Hermitian symmetric spaces.
problem Gap rigidity problems in compact Hermitian symmetric spaces.
method Dual analogy to Mok's noncompact case theorem, theorem on higher dimensional submanifolds.
result Proves gap rigidity theorem for diagonal curves in tube type spaces.
The paper introduces gapped scale-sensitive dimensions to improve learning rate bounds.
problem Improving lower bounds on rates of convergence in statistical and online learning.
method Introducing and analyzing gapped scale-sensitive dimensions for function classes.
result Gapped dimensions lead to stronger lower bounds on offset Rademacher averages.
The article explores the fundamental gap in Bakry-Emery geometry.
problem The fundamental gap in Bakry-Emery geometry.
method Recalled Bakry-Emery geometry and connected eigenvalues with boundary conditions. Showed a connection between fundamental gap and Bakry-Emery geometry.
result Presented key ideas in Andrews's and Clutterbuck's proof of the fundamental gap conjecture.
The paper calculates gap distributions for translation surfaces, focusing on the double heptagon.
problem Calculating gap distributions for translation surfaces.
method Describes a procedure to find winning holonomy vectors and applies it to the double heptagon.
result Explicitly computed gap distribution for the regular double heptagon translation surface.
Improved gap-dependent bounds for reinforcement learning with linear approximations.
problem Achieving nearly minimax-optimal performance with linear function approximation.
method Developed and analyzed the LSVI-UCB++ algorithm and its concurrent variant.
result First gap-dependent regret bound for nearly minimax-optimal algorithm LSVI-UCB++.
We present a data-driven framework called generative adversarial privacy (GAP). Inspired by recent advancements in generative adversarial networks (GANs), GAP allows the data holder to learn the privatization mechanism directly from the data. Under GAP, finding the optimal privacy mechanism is formulated as a constrain…
Computing unlinking number is usually very difficult and complex problem, therefore we define BJ-unlinking number and recall Bernhard-Jablan conjecture stating that the classical unknotting/unlinking number is equal to the BJ-unlinking number. We compute BJ-unlinking number for various families of knots and links for w…
New methods reduce bias in estimating optimality gaps for risk-averse stochastic programs.
problem Optimality gap estimation bias in risk-averse stochastic programs.
method Two independent samples, each estimating a different component of the optimality gap.
result Our method reduces bias in estimating optimality gaps for risk-averse problems.
New conditions prevent gaps in optimal control problems.
problem Preventing gaps in optimal control problems with state constraints.
method Developed new sufficient conditions not relying on convexity.
result Derived bounds for the size of the relaxation gap.
Federated learning studies separate client data and distribution gaps.
problem Understanding performance differences in federated learning across different datasets.
method Proposed a framework to disentangle out-of-sample and participation gaps.
result Dataset synthesis strategy is crucial for realistic simulations of federated learning generalization.
The paper proves gap theorems for Yang-Mills on manifolds with positive Yamabe.
problem Yang-Mills theory on manifolds with positive Yamabe constant.
method Extending Gursky-Kelleher-Streets results to complete manifolds.
result Equality in gap theorem described in terms of basic instanton.
Study simplicial volume for fixed fundamental groups, finding gaps.
problem Understanding simplicial volume for manifolds with fixed fundamental group.
method Relate gap problem to rationality questions in bounded (co)homology.
result Show existence of gaps in simplicial volume spectrum at zero.
Study shows fundamental gap of horoconvex domains in hyperbolic space has no positive lower bound.
problem Understanding the fundamental gap of horoconvex domains in hyperbolic space.
method Analysis of fundamental gap of geodesic balls as radius goes to infinity.
result Product of fundamental gap and square of diameter has no positive lower bound for horoconvex domains.
Study spectral gaps in hyperbolic rational homology spheres.
problem Finding spectral gaps in hyperbolic rational homology spheres.
method Construction of families of hyperbolic rational homology spheres with coexact 1-form spectral gaps.
result Provided intervals containing limit points of spectral gaps, with the rightmost interval being [0.8196, 0.8277].
New convex domains in hyperbolic space can have lower fundamental gap than constant potentials.
problem Finding convex domains with lower fundamental gap than constant potentials.
method Constructing specific convex domains and potentials with controlled eigenfunctions.
result Fundamental gap of −Δ+V can be strictly smaller than −Δ for convex domains. The study finds larger gaps in mean curvature for biharmonic submanifolds in spheres.
problem Understanding gaps in mean curvature for biharmonic submanifolds.
method Analyzing proper biharmonic submanifolds with parallel mean curvature vector field in Euclidean spheres.
result Determining larger gaps in mean curvature for specific biharmonic submanifolds.
Solves clustering contradictions by high-dimensional embedding with wide gaps.
problem Kleinberg's clustering axioms are contradictory.
method Embedding in high-dimensional space with wide gaps between clusters.
result Handles clustering contradictions by design.
The paper establishes pressure gaps for manifolds with flat subtori singularities.
problem Understanding phase transitions in nonpositively curved manifolds with flat subtori.
method Derives a pressure gap criterion for closed rank 1 manifolds with specific singular sets and proves Hölder continuity of geometric potentials.
result Geometric potentials have pressure gaps and no phase transitions under certain curvature constraints.
In their celebrated work, B. Andrews and J. Clutterbuck proved the fundamental gap (the difference between the first two eigenvalues) conjecture for convex domains in the Euclidean space and conjectured similar results holds for spaces with constant sectional curvature. We prove the conjecture for the sphere. Namely wh…