Improved k-NN active learning with local smoothness assumption.
problem Active learning convergence rates under smoothness assumptions.
method Designing an active learning algorithm with better convergence rate using local smoothness assumption for k-NN.
result Better convergence rate than in passive learning.
A boosting method improves nonparametric density estimation without smoothing assumptions.
problem Overfitting in nonparametric data fitting.
method Introduces a boosting algorithm for univariate nonparametric maximum likelihood estimation.
result Demonstrates the effectiveness of the boosting approach through simulations and real data experiments.
Novel active learning algorithm with improved convergence rate under local smoothness condition.
problem Improving convergence rates in active learning under specific smoothness assumptions.
method Developed a novel active learning algorithm with a rate of convergence better than in passive learning, using a local smoothness assumption for k-nearest neighbors.
result The algorithm achieves a better convergence rate than passive learning algorithms, avoiding strong density assumptions.
This paper analyzes the convergence of Federated Average under relaxed assumptions.
problem Lack of theoretical analysis for Federated Average under assumptions beyond smoothness.
method Relaxing assumptions of strong smoothness to semi-smoothness and semi-Lipschitz properties, and introducing a bound on the gradient.
result Provides a theoretical convergence study on Federated Learning under new assumptions.
We show that every smooth manifold admits a smooth triangulation transverse to a given smooth map. This removes the properness assumption on the smooth map used in an essential way in Scharlemann's construction [5].
Extends Kollár's result to fibered Calabi-Yau varieties with cohomological assumption.
problem Deformations of fibered Calabi-Yau varieties under cohomological constraints.
method Hodge theoretic techniques and T1-lifting criterion of Kawamata-Ran. result Small deformations of fibered Calabi-Yau varieties remain fibered.
The paper tackles contextual bandits with continuous actions using smoothing and zooming techniques.
problem Learning with continuous action spaces in the context of contextual bandits.
method The approach involves smoothing and zooming techniques to handle the continuous action space and unknown smoothness parameters.
result Improved regret bounds and adaptive algorithms for contextual bandits with continuous actions.
Improved model for non-smooth signals with complex spectra.
problem Current models struggle with non-smooth signals and complex spectral structures.
method CGPCM and RGPCM models with causality and Bayesian nonparametric interpretations, improved variational inference.
result Proposed models show better performance on synthetic and real-world data.
Paper addresses bias in kernel density estimation under minimal assumptions.
problem Kernel density estimation bias under minimal assumptions.
method Demonstrates the need for a balance between kernel decay and bandwidth eigenvalues, and rigorously derives bias bounds.
result Explicit constants and rigorous derivation of bias bounds under minimal assumptions.
New algorithms SVCA and SSPA improve robustness to noise in nonnegative matrix factorization.
problem Estimating vertices from noisy data points in convex hull.
method Smoothed VCA (SVCA) and Smoothed SPA (SSPA) algorithms.
result Improved robustness to noise compared to existing methods.
New findings show learning deeper neural networks is hard even with Gaussian inputs and non-degenerate weights.
problem The computational complexity of learning neural networks, especially deeper ones.
method Smoothed analysis framework and local pseudorandom generators.
result Learning depth-3 ReLU networks under Gaussian input distribution is hard even if weight matrices are non-degenerate.
Generalizes Thurston's jiggling lemma for piecewise smooth solutions.
problem Creating piecewise smooth solutions of differential relations without homotopical assumptions.
method Jiggling arbitrary sections of E to construct solutions of R. result Generalization of Thurston's lemma for piecewise smooth solutions of differential relations.
New method improves RL in continuous spaces with kernel smoothing.
problem Sample efficiency and structural assumptions in classical RL.
method Kernel smoothing model-based approach with Bernstein-style exploration bonus.
result Achieves improved regret bound in finite-horizon settings.
Smooth submetries between curved spaces are smooth.
problem Smoothness of submetries between curved spaces.
method Proving smoothness of submetries in a general setting, including Riemannian submersions and isometric actions.
result Smoothness of the base manifold is implied by the smoothness of the total manifold without curvature assumptions.
New active learning algorithm adapts to data without strict assumptions.
problem Efficiently label data with expensive labeling costs.
method Nonparametric adaptive active learning under local smoothness condition.
result Achieves minimax rate of convergence, performs almost as well as best non-adaptive algorithms.
Confirming operator characterization on smooth manifolds.
problem Characterizing an operator on smooth sections of tangent bundles.
method Using algebraic axioms and H^1(M, R) = {0} assumption.
result Operator can be characterized universally for any smooth manifold.
The estimation of probabilities of network edges from the observed adjacency matrix has important applications to predicting missing links and network denoising. It has usually been addressed by estimating the graphon, a function that determines the matrix of edge probabilities, but this is ill-defined without strong a…
We show that one can lift locally real analytic curves from the orbit space of a compact Lie group representation, and that one can lift smooth curves even globally, but under an assumption.
Lower bounds for higher-order methods in non-convex optimization.
problem Proving lower bounds for higher-order methods in smooth non-convex finite-sum optimization.
method Analyzing deterministic and randomized algorithms, proposing a new smoothness assumption.
result Proves optimal lower bounds for simulating pth-order regularized methods on the whole function.
New algorithm finds local minima in non-convex, non-smooth problems.
problem Finding local minimizers in non-convex and non-smooth optimization.
method Perturbed Proximal Descent, tailored for non-smooth cases.
result First known results for non-smooth optimization.
New method removes scalar curvature assumption in Ricci flow smoothing.
problem Uniform bounds on scalar curvature and other factors for Ricci flow.
method Quantitative short-time existence of Ricci flow without scalar curvature assumption.
result Ricci flow smoothing for measure space limits, Gromov-Hausdorff compactness, and topological rigidity results.
New shuffling methods improve convergence without Lipschitz smoothness.
problem Lack of convergence guarantees for shuffling methods under non-Lipschitz conditions.
method Revisit shuffling methods, prove convergence under general bounded variance condition.
result Matched current best-known convergence rates without Lipschitz smoothness.
Study of elliptic boundary value problems on non-compact manifolds.
problem Analyzing elliptic differential operators on manifolds with non-compact boundaries.
method Regularity theory and trace theorems for sections in the maximal domain under various assumptions.
result Systematic study of local and nonlocal boundary conditions, including the Atiyah-Patodi-Singer condition.
New moving plane method for varifolds promotes smoothness from boundary to interior.
problem Promoting smoothness from boundary to interior for singular hypersurfaces.
method Introduced a moving plane method for varifolds, showing smoothness as a conclusion.
result Smoothness and symmetry in the interior can be promoted from smoothness and symmetry at infinity.
Morse theory extended to non-degenerate functions.
problem Smooth functions on compact Riemannian manifolds without nondegeneracy.
method Extension of Morse theory without nondegeneracy assumptions.
result Morse theory applies to functions with finitely many connected critical points.
Study of Laplacians on smooth distributions in compact manifolds.
problem Understanding spectral properties of Laplacians on smooth distributions.
method Proving Laplacian as an unbounded regular self-adjoint operator in a Hilbert module over the foliation C*-algebra.
result Laplacians on smooth distributions define unbounded regular self-adjoint operators.
First order discretizations of Langevin diffusion can achieve better generalization error with additional smoothness assumptions.
problem Analyzing generalization error for first order discretizations of Langevin diffusion.
method Providing a sufficient smoothness condition to show that first order methods can achieve arbitrarily runtime complexity for a given expected generalization error.
result First order methods can achieve arbitrarily runtime complexity with additional smoothness assumptions.
Existing approaches to analyzing the asymptotics of graph Laplacians typically assume a well-behaved kernel function with smoothness assumptions. We remove the smoothness assumption and generalize the analysis of graph Laplacians to include previously unstudied graphs including kNN graphs. We also introduce a kernel-fr…
Kernel smoothing on unknown manifolds with bounds and asymptotic normality.
problem Data on unknown manifolds without boundaries.
method Finite sample bounds and asymptotic normality for kernel smoothing and its derivatives.
result Established finite sample bounds and asymptotic normality for kernel smoothing.
For binary classification we establish learning rates up to the order of n−1 for support vector machines (SVMs) with hinge loss and Gaussian RBF kernels. These rates are in terms of two assumptions on the considered distributions: Tsybakov's noise assumption to establish a small estimation error, and a new geometr…
In this paper, we develop a novel {\bf ho}moto{\bf p}y {\bf s}moothing (HOPS) algorithm for solving a family of non-smooth problems that is composed of a non-smooth term with an explicit max-structure and a smooth term or a simple non-smooth term whose proximal mapping is easy to compute. The best known iteration compl…
New algorithm learns halfspaces over hypercube with random bit flips.
problem Agnostic learning of Boolean halfspaces over discrete domains is computationally hard.
method Smoothed analysis with random bit flips for discrete inputs.
result First efficient algorithm for smoothed agnostic learning of halfspaces over Boolean hypercube.
New Langevin algorithm works well even for rough distributions.
problem Sampling from non-smooth distributions.
method Simple Langevin algorithm without smoothness assumptions.
result Algorithm performs well even with discontinuous gradients.
The paper proves smoothness of Sobolev maps and applies it to conformal maps.
problem Smoothness of Sobolev maps and conformal maps in specific dimensions.
method Using minors and Sobolev spaces, the paper derives a proof of Liouville's theorem.
result Smoothness of Sobolev maps and conformal maps under specific conditions.
Develops PRPCA for smooth image recovery combining low-rank and smoothness.
problem Image matrix recovery under low-rank and smoothness assumptions.
method Projected Robust PCA (PRPCA) framework combining low-rank and smoothness.
result Explicit statistical guarantees for PRPCA, reducing matrix dimensionality.
It is observed that on many 4-manifolds there is a unique smooth structure underlying a globally hyperbolic Lorentz metric. For instance, every contractible smooth 4-manifold admitting a globally hyperbolic Lorentz metric is diffeomorphic to the standard R4. Similarly, a smooth 4-manifold homeomorphic to the produc…
In this paper, we study the partial convexity of smooth solutions to the heat equation on a compact or complete non-compact Riemannian manifold M or Kahler-Ricci flow. We show that under a natural assumption, a new partial convexity property for smooth solutions to the heat equation is preserved.
Paper studies Adam's convergence under relaxed assumptions, proving a rate of O(poly(log T)/sqrt(T)).
problem Understanding Adam's convergence in non-convex, stochastic optimization with unbounded gradients and noise.
method Introduced a comprehensive noise model and used it to prove Adam's convergence rate.
result Adam finds a stationary point with a rate of O(poly(log T)/sqrt(T)) in high probability.
We consider Fano manifolds M that admit a collection of finite automorphism groups G_1, ..., G_k, such that the quotients M/G_i are smooth Fano manifolds possessing a Kaehler-Einstein metric. Under some numerical and smoothness assumptions on the ramification divisors, we prove that M admits a Kaehler-Einstein metric t…
New SPS variant improves non-smooth optimization without small gradients.
problem Improving non-smooth optimization without small gradients.
method Safeguarded Stochastic Polyak Step Size (SPSsafe) for non-smooth optimization. result Rigorous convergence guarantees for non-smooth convex optimization without strong assumptions.
Stochastic Gradient Descent (SGD) is one of the simplest and most popular stochastic optimization methods. While it has already been theoretically studied for decades, the classical analysis usually required non-trivial smoothness assumptions, which do not apply to many modern applications of SGD with non-smooth object…
Semisupervised methods inevitably invoke some assumption that links the marginal distribution of the features to the regression function of the label. Most commonly, the cluster or manifold assumptions are used which imply that the regression function is smooth over high-density clusters or manifolds supporting the dat…
New model improves GP approximations by relaxing independence across resolutions.
problem Overfitting and non-smooth predictions in multiresolution GPs.
method Conditional independence among GPs across resolutions.
result Improved robustness against overfitting and smoother predictions.
Let f:M→N be a smooth area decreasing map between two Riemannian manifolds $(M,\gm)$ and $(N,\gn)$. Under weak and natural assumptions on the curvatures of $(M,\gm)$ and $(N,\gn)$, we prove that the mean curvature flow provides a smooth homotopy of f to a constant map.
New polynomial convergence guarantees for SGM on general data distributions.
problem Efficient guarantees for multimodal and non-smooth distributions in SGM.
method Polynomial convergence guarantees for denoising diffusion models on general data distributions, with no assumptions on functional inequalities or smoothness.
result Wasserstein distance guarantees for distributions of bounded support or decaying tails, and TV guarantees for further smoothness assumptions.
Adam converges to stationary points under relaxed conditions.
problem Understanding and proving convergence of Adam under realistic assumptions.
method New proof of boundedness of gradients and variance-reduced Adam.
result Adam converges to ε-stationary points with O(ε⁻⁴) gradient complexity under realistic conditions.
Paper optimizes multi-fidelity function with fast learning rates.
problem Optimizing a locally smooth function with limited budget and varying fidelity approximations.
method Kometo algorithm that achieves simple regret rates without knowing function smoothness or fidelity assumptions.
result Kometo algorithm outperforms previous methods empirically.
Full-batch GD achieves generalization close to any stationary point with fewer assumptions.
problem Generalization and excess risk bounds for smooth losses, including non-Lipschitz and nonconvex cases.
method Path-dependent analysis of GD's generalization error, focusing on optimization error and stability.
result Generalization error is tightly bound in terms of optimization error and iteration count, bypassing common assumptions.