In this work, we will verify some comparison results on Kahler manifolds. They are complex Hessian comparison for the distance function from a closed complex submanifold of a Kahler manifold with holomorphic bisectional curvature bounded below by a constant, eigenvalue comparison and volume comparison in terms of scala…
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,657 papers · 148 categories
Trend · papers per month
48 results for “Complexity Comparison”
We study the problem of interactively learning a binary classifier using noisy labeling and pairwise comparison oracles, where the comparison oracle answers which one in the given two instances is more likely to be positive. Learning from such oracles has multiple applications where obtaining direct labels is harder bu…
The paper proves a comparison principle for complex Monge-Ampère flows and solves a uniqueness problem.
problem Proving uniqueness of weak solutions to the pluripotential Cauchy-Dirichlet problem.
method Proving a comparison principle for the pluripotential complex Monge-Ampère flows.
result Proves the uniqueness of the weak solution to the pluripotential Cauchy-Dirichlet problem.
This paper optimizes the number of comparisons needed to find the best k items from pairwise comparisons.
problem Finding the best k items from pairwise comparisons with limited comparisons.
method Developed algorithms for finding probably approximately correct and exact best k items under stochastic conditions.
result Upper and lower bounds on the number of comparisons for finding the best k items, with matching upper bounds for PAC best k items.
The paper extends Schwarz's lemma to RC-positivity and complex manifolds.
problem Comparing metrics with RC-positivity in complex manifolds.
method Establishing Schwarz lemmas for RC-positivity and applying them to complex manifolds.
result New diameter and volume comparison theorems.
Rank regression from pairwise comparisons requires many comparisons to accurately learn model parameters.
problem Learning model parameters for rank regression from noisy pairwise comparisons.
method Uniform random pairwise comparisons to estimate model parameters with a given accuracy.
result Learning model parameters requires a number of comparisons proportional to .
Paper compares topological and pro-étale fundamental groups.
problem No specific problem stated; comparing two fundamental groups.
method Constructs a comparison map between topological and pro-étale fundamental groups.
result Establishes a map between fundamental groups.
In this paper, by using the Bochner technique on almost Hermitian manifolds, we obtain a complex Hessian comparison for almost Hermitian manifolds generalizing the Laplacian comparison for almost Hermitian manifolds by Tossati, and reprove a diameter estimate for almost Hermitian manifolds by Gray. Moreover, we obtain …
Optimizes identifying top-k items from comparisons with minimal comparisons.
problem Finding the top-k items from pairwise comparisons with a fixed error rate.
method Developed an asymptotically optimal algorithm using primal-dual procedure and adaptive comparison allocation.
result Proves the algorithm is asymptotically optimal for top-k identification.
On Kahler manifolds with Ricci curvature lower bound, assuming the real analyticity of the metric, we establish a sharp relative volume comparison theorem for small balls. The model spaces being compared to are complex space forms, i.e, Kahler manifolds with constant holomorphic sectional curvature. Moreover, we give a…
Rank aggregation systems collect ordinal preferences from individuals to produce a global ranking that represents the social preference. Rank-breaking is a common practice to reduce the computational complexity of learning the global ranking. The individual preferences are broken into pairwise comparisons and applied t…
The paper designs tests for comparing ranked preference data and finds significant differences.
problem Comparing pairwise comparison and ranking data in various applications.
method Developed two-sample tests for pairwise comparison and ranking data, proving upper and lower bounds.
result Upper and lower bounds show tightness of the proposed tests, and significant differences in preferences were found.
SyncRank recovers global ranking from noisy comparisons with theoretical guarantees.
problem Recovering a global ranking from noisy pairwise comparisons.
method Complex-valued data model and SDP relaxation for exact ranking recovery.
result SyncRank achieves exact ranking recovery with high probability above a critical noise threshold of O(sqrt(n / log n)).
Sparse Dueling Banditsstat.ML
The dueling bandit problem is a variation of the classical multi-armed bandit in which the allowable actions are noisy comparisons between pairs of arms. This paper focuses on a new approach for finding the "best" arm according to the Borda criterion using noisy comparisons. We prove that in the absence of structural a…
We introduce a probabilistic framework for quantifying the semantic similarity between two groups of embeddings. We formulate the task of semantic similarity as a model comparison task in which we contrast a generative model which jointly models two sentences versus one that does not. We illustrate how this framework c…
New algorithm learns permutations mixtures with optimal sample complexity.
problem Learning mixtures of permutations in high-dimensional settings.
method Combining groups of pairwise comparisons and combinatorial method of moments.
result Optimal sample complexity proportional to log(n) for high-dimensional data.
Study of complex Hessian equations using subharmonic functions and geodesics.
problem Understanding geodesics within complex Hessian equations.
method Perron envelope construction, comparison principle, rooftop equality, Kiselman minimum principle.
result Established criterion for geodesic connectivity among -subharmonic functions.
This paper studies the problem of finding the exact ranking from noisy comparisons. A comparison over a set of items produces a noisy outcome about the most preferred item, and reveals some information about the ranking. By repeatedly and adaptively choosing items to compare, we want to fully rank the items with a …
New method improves ABC for Bayesian model comparison.
problem Comparing complex models with observed data.
method Approximate Bayesian Computation with posterior density estimation.
result Efficiently assigns high posterior probabilities to ground-truth models.
New method identifies Condorcet winner in dueling bandits with improved sample complexity.
problem Identifying Condorcet winner in noisy pairwise comparisons.
method Exploits full gap matrix Δ to improve sample complexity.
result Improves sample complexity guarantees by leveraging informative comparisons.
Evidence Networks simplify Bayesian model comparison for complex models.
problem Bayesian model comparison challenges with intractable likelihoods or priors.
method Loss functions and neural networks for fast, amortized estimation of Bayes factors.
result Evidence Networks provide accurate and scalable Bayes factor estimation.
Divergence estimators based on direct approximation of density-ratios without going through separate approximation of numerator and denominator densities have been successfully applied to machine learning tasks that involve distribution comparison such as outlier detection, transfer learning, and two-sample homogeneity…
Paper tackles noisy comparison oracle for robust clustering algorithms.
problem Finding robust clustering algorithms under noisy comparison oracle.
method Develops algorithms for k-center clustering and agglomerative hierarchical clustering using noisy comparison oracle.
result Proves robust algorithms achieve good approximation guarantees with high probability.
Many complex systems can be represented as networks, and the problem of network comparison is becoming increasingly relevant. There are many techniques for network comparison, from simply comparing network summary statistics to sophisticated but computationally costly alignment-based approaches. Yet it remains challeng…
We establish a uniform comparison between the spectrum of the rough Laplacian (acting on sections of a vector bundle of complex rank one or of harmonic curvature) with the spectrum of a discrete operator (a generalization of a discrete magnetic Laplacian added with a potential) acting on a finite dimensional space comi…
Paper tackles ranking items with a semi-random comparison graph and a monotone adversary.
problem Ranking items based on pairwise comparisons from a semi-random comparison graph with a monotone adversary.
method Developed a weighted maximum likelihood estimator (MLE) and an SDP-based approach to reweight the semi-random graph.
result Achieves near-optimal sample complexity, up to a log^2(n) factor, for identifying the top-K preferred items.
This work analyzes Fréchet regression using comparison geometry, providing theoretical and practical insights.
problem Analyzing data on complex structures like manifolds and graphs.
method Theoretical analysis through comparison geometry, focusing on existence, uniqueness, and stability of the Fréchet mean.
result Key results on the existence, uniqueness, and stability of the Fréchet mean, along with statistical guarantees for nonparametric regression.
This paper presents a detailed comparison of a recently proposed algorithm for optimizing decision trees, tree alternating optimization (TAO), with other popular, established algorithms. We compare their performance on a number of classification and regression datasets of various complexity, different size and dimensio…
This paper aims to present a general idea of method comparison of Credit Scoring techniques. Any scorecard can be made in various methods based on variable transformations in the logistic regression model. To make a comparison and come up with the proof that one technique is better than another is a big challenge due t…
We study the active learning problem of top- ranking from multi-wise comparisons under the popular multinomial logit model. Our goal is to identify the top- items with high probability by adaptively querying sets for comparisons and observing the noisy output of the most preferred item from each comparison. To ac…
The proof of the comparison principlein [EGZ11] is not complete. We provide here an alternative proof, valid in the ample locus of any big cohomology class, and discuss the resulting modifications.
Given a set of pairwise comparisons, the classical ranking problem computes a single ranking that best represents the preferences of all users. In this paper, we study the problem of inferring individual preferences, arising in the context of making personalized recommendations. In particular, we assume that there are …
Establishing criteria for top cell inertness in complexes.
problem Criteria for top cell inertness in Poincaré duality complexes.
method Algebraic intersection theory, homotopy fibrations, surgery, homogeneous spaces.
result Established various criteria for top cell inertness.
This is the content of the lectures given by the author at the winter school KAWA3 held at the University of Barcelona in 2012 from January 30 to February 3. The main goal was to give an account of viscosity techniques and to apply them to degenerate Complex Monge-Ampère equations following recent works of P. Eyssidieu…
Is Your Imitation Learning Policy Better than Mine? Policy Comparison with Near-Optimal Stoppingcs.RO
Paper proposes a sequential statistical test for comparing imitation learning policies with near-optimal stopping.
problem Challenges in rigorously comparing imitation learning policies due to small sample sizes and potential p-hacking.
method Sequential statistical test that adapts the number of trials based on intermediate results, achieving near-optimal stopping.
result Reduces the number of evaluation trials by up to 32% compared to state-of-the-art baselines, saving significant time and effort.
New construction reduces Vietoris-Rips complex construction time.
problem Efficiently constructing Vietoris-Rips complexes.
method Inductive construction avoiding unnecessary comparisons.
result Significant reduction in computational complexity.
Enhances AI models with human feedback for noisy data.
problem Improving AI model alignment with human feedback in noisy environments.
method Two-stage SL+LHF framework connecting machine learning with human feedback.
result The LNCA ratio identifies conditions for SL+LHF superiority over pure SL.
This paper provides lower bounds on the convergence rate of Derivative Free Optimization (DFO) with noisy function evaluations, exposing a fundamental and unavoidable gap between the performance of algorithms with access to gradients and those with access to only function evaluations. However, there are situations in w…
New oracle uses uncertainty for active classification with noisy feedback.
problem Improving query complexity in interactive binary classifier learning.
method Proposes a new pairwise comparison oracle that considers uncertainty and an adaptive labeling algorithm.
result Demonstrates improved performance and efficiency compared to existing methods.
New method speeds up knot computations in 3D.
problem Computational complexity in knot theory.
method 3D representation of knots for faster computation.
result Savings in computational complexity for knot invariants.
We consider the problem of finding a target object using pairwise comparisons, by asking an oracle questions of the form \emph{"Which object from the pair is more similar to ?"}. Objects live in a space of latent features, from which the oracle generates noisy answers. First, we consider the {\em non-bli…
We prove a version of Yau's Schwarz Lemma for general almost-complex manifolds equipped with Hermitian metrics. This requires an extension to this setting of the Laplacian comparison theorem. As an application we show that the product of two almost-complex manifolds does not admit any complete Hermitian metric with bis…
We consider the problem of estimating a ranking on a set of items from noisy pairwise comparisons given item features. We address the fact that pairwise comparison data often reflects irrational choice, e.g. intransitivity. Our key observation is that two items compared in isolation from other items may be compared bas…
In this note, we describe the Hermitian metrics that leave the total Monge-Ampere volume invariant. In particular, we give several characterizations of the Hermitian metrics which satisfy the comparison principle for the complex Monge-Ampere operator
Embeddings of knowledge graphs have received significant attention due to their excellent performance for tasks like link prediction and entity resolution. In this short paper, we are providing a comparison of two state-of-the-art knowledge graph embeddings for which their equivalence has recently been established, i.e…
New algorithm learns human preferences from few comparisons efficiently.
problem Learning human preferences from limited comparison feedback.
method Formulated as D-optimal design for Plackett-Luce model, solved using randomized Frank-Wolfe algorithm.
result Proposed algorithm efficiently solves D-optimal design problem for Plackett-Luce objective.
A new metric HCP distance for comparing distributions.
problem Comparing high-dimensional probability distributions efficiently.
method Hilbert curve projection to low-dimensional coupling, followed by transport distance calculation.
result HCP distance is a proper metric for probability measures with bounded supports.
Real-world problems typically require the simultaneous optimization of several, often conflicting objectives. Many of these multi-objective optimization problems are characterized by wide ranges of uncertainties in their decision variables or objective functions, which further increases the complexity of optimization. …