Novel approach to universal online learning for bounded losses, closing open problems.
problem Characterizing processes for universal online learning under non-i.i.d. conditions.
method Characterization of processes admitting strong and weak universal learning, introduction of optimistically universal learning rule.
result Introduction of a novel 1NN algorithm that is optimistically universal for bounded losses.
New upper bound for Neumann Laplacian eigenvalues on convex domains.
problem Bounding Neumann eigenvalues on convex domains.
method Deriving a new upper bound for eigenvalues.
result Universal inequalities for Neumann eigenvalues derived from the upper bound.
Minimum width for ReLU networks to approximate L^p functions is max(d_x+1, d_y).
problem Characterizing the minimum width for ReLU networks to approximate L^p functions.
method Analyzing networks with ReLU activation functions and proving the minimum width required.
result The minimum width required for the universal approximation of L^p functions is exactly max(d_x+1, d_y).
Study of collapsed manifolds with bounded Ricci curvature and non-collapsed universal cover.
problem Understanding collapsed manifolds with specific Ricci curvature properties.
method Ricci flow techniques applied to non-collapsed universal cover.
result Partial extension of nilpotent structural results to global Ricci bounded covering geometry.
In analogy with the vector bundle theory we define universal and strongly universal Lefschetz fibrations over bounded surfaces. After giving a characterization of these fibrations we construct very special strongly universal Lefschetz fibrations when the fiber is the torus or an orientable surface with connected bounda…
Using deep analytic methods, Cheeger and Gromov showed that for any smooth (4k-1)-manifold there is a universal bound for the von Neumann L2 ρ-invariants associated to arbitrary regular covers. We present a proof of the existence of a universal bound for topological (4k-1)-manifolds, using L2-signatures of boun…
Reduces bounded loss learning to binary classification.
problem Universal consistency of non-i.i.d. processes with bounded loss.
method Constructive reduction to binary classification.
result Any bounded loss output setting can be reduced to binary classification.
Upper bound found for geodesic curvature on convex surfaces.
problem Bounding the total curvature of geodesics on convex surfaces.
method Provided a universal upper limit for minimizing geodesics.
result Established a universal upper bound for total curvature.
The paper tightens bounds on distances between Reeb graphs.
problem Certifying quasi-universality of distances between Reeb graphs.
method Establishes tight bi-Lipschitz bounds for various distances.
result Proves strict universality of the functional contortion distance for contour trees and coincides with interleaving distance for merge trees.
Universal algorithm for online convex optimization with optimal regret bounds.
problem Designing a universal algorithm for online convex optimization that works for multiple types of loss functions.
method Maler algorithm: runs multiple learning algorithms in parallel and selects the best one.
result Achieves optimal regret bounds for general convex, exponentially concave, and strongly convex functions.
Universal MLPs with a single hidden layer can learn any function.
problem Learning on various data structures like sequences, images, sets, and graphs.
method Using group theory, the paper proves the universality of a broad class of equivariant MLPs with a single hidden layer.
result Having a hidden layer on which the group acts regularly is sufficient for universal equivariance (invariance).
New method makes robust estimators work without knowing corruption levels.
problem Robust estimation algorithms struggle with unknown corruption levels.
method Abstracted geometric puzzle solution to universal meta technique.
result Converts any robust estimator to work without corruption bounds.
Universal functions and metrics with constant curvature on domains.
problem Finding universal functions and metrics with constant curvature.
method Proving Runge-type theorems and universality results for locally univalent functions, refining Heins' result.
result Existence of universal conformal metrics with constant curvature on hyperbolic domains.
In this paper, we investigate universal estimates for eigenvalues of a buckling problem. For a bounded domain in a Euclidean space, we give a positive contribution for obtaining a sharp universal inequality for eigenvalues of the buckling problem. For a domain in the unit sphere, we give an important improvement on the…
The universal Liouville action equals the renormalized volume of a hyperbolic 3-manifold.
problem Understanding the geometric significance of the universal Liouville action.
method Analyzing the Weil-Petersson universal Teichmüller space and its relation to hyperbolic 3-manifolds.
result The gradient flow of the universal Liouville action converges to the origin, providing a bound on Weil-Petersson distance.
It is shown that the diameter of a compact shrinking Ricci soliton has a universal lower bound. This is proved by extending universal estimates for the first non-zero eigenvalue of Laplacian on compact Riemannian manifolds with lower Ricci curvature bound to a twisted Laplacian on compact shrinking Ricci solitons.
Metric spaces with certain curvature properties are universally infinitesimally Hilbertian.
problem Analyzing the infinitesimal geometry of metric spaces with curvature bounds.
method Proving a metric space with a Gromov-Hausdorff tangent splitting property is universally infinitesimally Hilbertian.
result Metric spaces with curvature bounds are universally infinitesimally Hilbertian.
New method achieves both universality and adaptivity in online convex optimization.
problem Achieve optimal regret guarantees without prior knowledge of function curvature.
method Introduces UniGrad, a novel approach that achieves both universality and adaptivity.
result Achieves universal regret guarantees that adapt to gradient variation.
In this survey article we will consider universal lower bounds on the volume of a Riemannian manifold, given in terms of the volume of lower dimensional objects (primarily the lengths of geodesics). By `universal' we mean without curvature assumptions. The restriction to results with no (or only minimal) curvature assu…
Sharp lower bound on GHHs' representation power of CPWL functions.
problem Proving the minimum number of nestings for GHHs to represent arbitrary CPWL functions.
method Using a key lemma about finite sums of periodic functions, proving necessity of n nestings.
result Proving necessity of n nestings for GHHs to achieve universal representation power.
Constructs universal link invariants from intersections in configuration spaces.
problem Globalise topologically all coloured Jones polynomials and ADO polynomials.
method Defines new link invariants from graded intersections in configuration spaces.
result Recover all coloured Jones polynomials and ADO polynomials for links.
We prove trace identities for commutators of operators, which are used to derive sum rules and sharp universal bounds for the eigenvalues of periodic Schroedinger operators and Schroedinger operators on immersed manifolds. In particular, we prove bounds on the eigenvalue lambda_{N+1} in terms of the lower spectrum, bou…
We show that deep narrow Boltzmann machines are universal approximators of probability distributions on the activities of their visible units, provided they have sufficiently many hidden layers, each containing the same number of units as the visible layer. We show that, within certain parameter domains, deep Boltzmann…
In this paper we study the growth rates of Artin monoids and we show that 4 is a universal upper bound. We also show that the generating functions of the associated right-angled Artin monoids are given by families of Chebyshev polynomials. Applications to Artin groups and positive braids are given.
Paper establishes a universal growth rate for smooth surrogate losses in classification.
problem Analyzing growth rates of consistency bounds for various surrogate losses.
method Proves square-root growth rate for smooth margin-based losses; extends to multi-class classification.
result Demonstrates a universal square-root growth rate for smooth comp-sum and constrained losses.
Paper establishes universal lower bounds and optimal rates for clustering sub-exponential mixture models.
problem Achieving optimal error rates in clustering sub-exponential mixture models.
method Establishes universal lower bounds and demonstrates iterative algorithms' optimality in sub-exponential mixture models.
result Iterative algorithms achieve the universal lower bound in sub-exponential mixture models.
We prove that if Y is the Gromov-Hausdorff limit of a sequence of complete manifolds, Min, with a uniform lower bound on Ricci curvature then Y has a universal cover.
The paper proves macroscopic versions of conjectures about scalar curvature and volume bounds.
problem Bounding simplicial volume and L2-Betti numbers with scalar curvature constraints. method Using upper bounds on volumes of 1-balls in universal covers.
result Macroscopic versions of conjectures about scalar curvature and volume bounds are proven.
Complex-valued neural networks can approximate any continuous function with bounded widths and depths.
problem Approximating continuous functions with complex-valued neural networks of bounded widths and depths.
method Analyzing activation functions and proving universality for complex-valued networks.
result Deep narrow complex-valued networks are universal if and only if their activation function is neither holomorphic, nor antiholomorphic, nor R-affine. We construct a universal space for the class of proper metric spaces of bounded geometry and of given asymptotic dimension. As a consequence of this result, we establish coincidence of the asymptotic dimension with the asymptotic inductive dimensions.
Study on scalar curvature bounds and manifold topological complexity.
problem Understanding the topological complexity of manifolds with scalar curvature constraints.
method Introduced a small scale index theorem to establish bounds for Gromov's simplicial norm.
result Upper bound for Gromov's simplicial norm established in terms of scalar curvature, volume, and injectivity radius.
Quantum neural networks can approximate noisy functions accurately.
problem Approximating noisy functions with quantum neural networks.
method Universal approximation theorem with error bounds for noisy quantum neural networks.
result Quantum neural networks can approximate noisy functions with precise error bounds.
This paper gives a quantitative version of Thurston's hyperbolic Dehn surgery theorem. Applications include the first universal bounds on the number of non-hyperbolic Dehn fillings on a cusped hyperbolic 3-manifold, and estimates on the changes in volume and core geodesic length during hyperbolic Dehn filling. The proo…
A new stable edit distance for Reeb graphs is shown to be universal.
problem Stability and comparability of Reeb graphs under function similarity.
method Defined and proved stability and universality of Reeb graph edit distance.
result Reeb graph edit distance is the most stable and universal among distances.
The paper sets limits on neural network sizes based on dataset shapes.
problem Understanding the size of neural networks needed for accurate predictions.
method Examined how the shape of data influences neural network complexity.
result Established upper limits on neural network width based on dataset topology.
Study bounds Urysohn width of manifolds under surgeries.
problem Bounding Urysohn width of manifolds after surgeries.
method Analyzes connected sums and universal covers, applies to general surgeries.
result Optimal constants in estimates of width bounds are shown.
We study the size of the isometry group Isom(M, g) of Riemannian manifolds (M, g) as g varies. For M not admitting a circle action, we show that the order of Isom(M, g) can be universally bounded in terms of the bounds on Ricci curvature, diameter, and injectivity radius of M. This generalizes results known for negativ…
We will discuss fundamental domains for actions of discrete groups on the 3-dimensional Einstein Universe. These will be bounded by crooked surfaces, which are conformal compactifications of surfaces that arise in the construction of Margulis spacetimes. We will show that there exist pairwise disjoint crooked surfaces …
Study on solutions of conformal equations, proving bounds and profiles.
problem Analyzing solutions of conformally invariant equations on Euclidean domains.
method Established blow-up profiles and heights of solutions around blow-up points.
result Proved bounds on distances and heights of solutions around blow-up points.
Paper verifies volume space form rigidity for bounded Ricci curvature.
problem Quantitative volume space form rigidity conjecture for manifolds with Ricci curvature bounds.
method Analyzes closed n-manifolds with Ricci curvature bounds and verifies conjecture for non-collapsed spaces.
result Verifies conjecture for bounded Ricci curvature, without requiring non-collapsing condition.
We investigate the eigenvalues of the buckling problem of arbitrary order on compact domains in Euclidean spaces and spheres. We obtain universal bounds for the kth eigenvalue in terms of the lower eigenvalues independently of the particular geometry of the domain.
Study spherical cap packing with probabilistic methods for detecting low-rank structures.
problem Detecting low-rank structures in high-dimensional Gaussian data.
method Probabilistic spherical cap packing approach for asymptotic bounds and extreme value distributions.
result Developed fast detection method for low-rank structures without spectrum information.
Lazy Gradient Descent outperforms existing polytope algorithms in pseudo-regret.
problem Achieving optimal regret bounds on polytopes efficiently.
method Lazy Online Gradient Descent on polytopes.
result Proves O(1) pseudo-regret against i.i.d opponents. New lower bounds on embedding dimensions for neural network architectures.
problem Ensuring neural networks can handle symmetries like permutations in high dimensions.
method Novel technique to prove lower bounds on embedding dimensions.
result Proves new lower bounds on embedding dimensions for Deep Sets and Janossy pooling.
New analysis shows how deep networks are vulnerable to small, image-agnostic perturbations.
problem Vulnerability of deep networks to small, image-agnostic perturbations.
method Quantitative analysis linking robustness to geometry of decision boundaries.
result Deep networks are vulnerable to small perturbations along positively curved decision boundaries.
Proposes semi-random features for nonlinear function approximation.
problem Nonlinear function approximation in machine learning.
method Semi-random features as a middle ground between deep learning and kernel methods.
result Proves universal approximation and generalization for deep semi-random features.
Improved bounds linking entropy and volume in hyperbolic 3-manifolds.
problem Establishing bounds between entropy and volume in hyperbolic 3-manifolds.
method Heegaard Floer homology and hyperbolic geometry.
result Entropy is bounded by hyperbolic volume with logarithmic factor.
Study the topology of Ricci limit spaces using Gromov-Hausdorff limits.
problem Topology of Ricci limit spaces.
method Gromov-Hausdorff limits, slice theorem for isometric pseudo-group actions, uniform diameter bounds.
result Established semi-locally simply connected property and described universal cover.