A version of Dehn's algorithm for simple diagrams on a once punctured surface representing simple diagrams on a closed surface is presented
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.
169,042 papers · 148 categories
Trend · papers per month
48 results for “Simple Algorithms”
Bayes optimal algorithm under certain conditions doesn't achieve exponential simple regret.
problem Best arm identification with normal rewards over time.
method Fixed-budget best arm identification problem with rewards from normal distributions. Evaluates performance via simple regret.
result Bayes optimal algorithm does not yield exponential decrease in simple regret.
The paper offers simple, near-optimal algorithms for multi-group learning.
problem Learning predictors within subgroups of a population, addressing fairness and hidden stratification.
method Studies the structure of solutions and provides simple, near-optimal algorithms.
result Simple and near-optimal algorithms for multi-group learning.
Simple algorithms for Dueling Bandits with improved regret bounds.
problem Optimizing decisions in a comparison-based environment with unknown preference gaps.
method Presented simple algorithms with specific regret bounds.
result Regret bounds of order O(T^rho ) with 1/2 <= rho <= 3/4, independent of preference gaps.
New meta-learning framework for minimizing simple regret in bandits.
problem Minimizing simple regret in a sequence of bandit tasks with unknown distributions.
method Developed Bayesian and frequentist meta-learning algorithms for bandits, analyzing their meta simple regret.
result Bayesian algorithm achieves meta simple regret, frequentist algorithm .
Simple algorithm for computing link polynomials using skein relations.
problem Computing link polynomials efficiently and accurately.
method New total order on braid representatives to define and compute link polynomials.
result New complete link invariant as a by-product of the algorithm.
A simple linear algebraic explanation of the algorithm in "A Spectral Algorithm for Learning Hidden Markov Models" (COLT 2009). Most of the content is in Figure 2; the text just makes everything precise in four nearly-trivial claims.
New algorithms minimize simple and cumulative regret in contextual bandits.
problem Minimizing simple and cumulative regret in contextual bandit settings.
method Proposed new algorithms using conformal arm sets (CASs).
result Near-optimal minimax guarantees for simple regret and state-of-the-art guarantees for cumulative regret.
A simple algorithm for Gaussian mean testing with optimal sample complexity.
problem Distinguishing between standard Gaussian and other Gaussian distributions with unknown mean and covariance.
method An extremely simple algorithm with a one-page analysis.
result Optimal sample complexity of Θ(√d/ε^2) with sample linear time.
Fibered simple knotsmath.GT
Simple knots in lens spaces fiber if their order doesn't divide certain Euclidean remainders.
problem Characterizing fibered simple knots in lens spaces.
method Direct, combinatorial, and geometric methods.
result Conditions for fibered simple knots in lens spaces are determined.
Differential privacy for simple linear regression protects small datasets from individual data leaks.
problem Protecting sensitive personal information in small datasets from individual data leaks.
method Differential privacy algorithms for simple linear regression tailored for small datasets (tens to hundreds of datapoints).
result Robust estimators like Theil-Sen perform well on small datasets, but standard algorithms improve as dataset size increases.
We provide an elementary proof of a simple, efficient algorithm for computing the Euclidean projection of a point onto the probability simplex. We also show an application in Laplacian K-modes clustering.
In this work, we develop a simple algorithm for semi-supervised regression. The key idea is to use the top eigenfunctions of integral operator derived from both labeled and unlabeled examples as the basis functions and learn the prediction function by a simple linear regression. We show that under appropriate assumptio…
RSHT algorithm simplifies complex shapes to points.
problem Simplifying complex shapes to points in higher dimensions.
method Combines simplicial collapses and expansions.
result Reduces triangulated d-manifolds to points using RSHT.
New algorithm optimizes best arm identification with minimal regret.
problem Best arm identification in multi-armed bandit problems.
method Characterized Bayesian simple regret with continuity conditions of prior, proposed a simple algorithm.
result Proposed algorithm achieves rate-optimal Bayesian simple regret.
In this paper, we propose a simple, versatile model for learning the structure and parameters of multivariate distributions from a data set. Learning a Markov network from a given data set is not a simple problem, because Markov networks rigorously represent Markov properties, and this rigor imposes complex constraints…
The paper proposes a new algorithm to select subsets of training data for better accuracy and explainability.
problem Tackles the challenge of balancing accuracy and explainability in pattern recognition.
method Identifies multiple subsets with simple local patterns by clustering similar instances.
result The sub-setting algorithm outperformed traditional decision trees by 15% on the international stroke dataset.
This papers introduces an algorithm for the solution of multiple kernel learning (MKL) problems with elastic-net constraints on the kernel weights. The algorithm compares very favourably in terms of time and space complexity to existing approaches and can be implemented with simple code that does not rely on external l…
The action of the mapping class group of the thrice-punctured projective plane on its character variety produces an algorithm for generating the simple length spectra of quasi-Fuchsian thrice-punctured projective planes. We apply this algorithm to quasi-Fuchsian representations of the corres…
New algorithm improves on static methods in Active Simple Hypothesis Testing.
problem Optimizing Active Simple Hypothesis Testing with active sampling.
method Game-theoretic formulation, differential games, PDEs, Blackwell Approachability.
result Proposes an efficient algorithm that outperforms static methods in ASHT.
Simple algorithm approximates rare event frequencies.
problem Approximating the frequency of rare events.
method Iterative update of categorical click-distribution, resulting in a random walk on an n-dimensional simplex.
result The random walk corresponds to a biased Bernoulli convolution under certain conditions.
New algorithm solves complex optimization problems efficiently.
problem Minimizing convex upper-level functions over optimal lower-level solutions.
method Reformulates bilevel problems into functionally constrained problems, achieving near-optimal rates.
result Achieves near-optimal rates for both smooth and nonsmooth problems.
Sparse coding is a basic task in many fields including signal processing, neuroscience and machine learning where the goal is to learn a basis that enables a sparse representation of a given set of data, if one exists. Its standard formulation is as a non-convex optimization problem which is solved in practice by heuri…
A regularized optimization problem over a large unstructured graph is studied, where the regularization term is tied to the graph geometry. Typical regularization examples include the total variation and the Laplacian regularizations over the graph. When applying the proximal gradient algorithm to solve this problem, t…
Paper finds linking numbers for Montesinos links using a simple algorithm.
problem Calculating linking numbers for Montesinos links.
method Simple proof and numerical algorithm for rational links, extending to Montesinos links.
result Linking numbers found for any two components in Montesinos links.
Simple DP algorithms find approximate solutions for nonconvex ERM.
problem Finding approximate solutions to nonconvex ERM problems with privacy.
method Differential privacy, descent directions, line search, mini-batching, two-phase strategy.
result Effective algorithms for nonconvex ERM with privacy guarantees.
AWR simplifies RL with simple supervised learning.
problem Developing scalable RL algorithms for off-policy data.
method Two supervised learning steps: value function and policy.
result AWR achieves competitive performance and effective policies.
We provide an algorithm to determine the Heegaard genus of simple 3-manifolds with non-empty boundary. More generally, we supply an algorithm to determine (up to ambient isotopy) all the Heegaard splittings of any given genus for the manifold. As a consequence, the tunnel number of a hyperbolic link is algorithmically …
New algorithm trains neural nets on simple skills to learn complex tasks faster.
problem Learning complex tasks through simple imitation.
method Train neural networks on simple, easy-to-learn skills to accelerate learning of complex, hard-to-learn tasks.
result Consistently outperforms state-of-the-art baseline in training speed and performance.
Data that is gathered adaptively --- via bandit algorithms, for example --- exhibits bias. This is true both when gathering simple numeric valued data --- the empirical means kept track of by stochastic bandit algorithms are biased downwards --- and when gathering more complicated data --- running hypothesis tests on c…
The expected improvement (EI) algorithm is a popular strategy for information collection in optimization under uncertainty. The algorithm is widely known to be too greedy, but nevertheless enjoys wide use due to its simplicity and ability to handle uncertainty and noise in a coherent decision theoretic framework. To pr…
Proposes a new method for kernel density estimation using stagewise minimization and a simple dictionary.
problem Kernel density estimation with data-adaptive weighting parameters and sparse representation.
method Stagewise minimization algorithm based on -divergence and a simple dictionary.
result Develops non-asymptotic error bound for the proposed estimator.
SURF simplifies distribution estimation with simple, robust, and fast algorithms.
problem Efficient and accurate distribution estimation in statistics and machine learning.
method Piecewise polynomial approximation using empirical probability interpolation and divide-and-conquer merging.
result Surpassing state-of-the-art algorithms in efficiency and accuracy, SURF estimates distributions robustly and quickly.
SSRGD finds local minima in nonconvex problems with simple gradient updates.
problem Finding local minima in nonconvex optimization problems.
method Simple perturbed stochastic recursive gradient descent (SSRGD).
result SSRGD finds -second-order stationary points efficiently.
A streamlined DRL algorithm improves sample efficiency without entropy maximization.
problem Improving sample efficiency in off-policy DRL algorithms.
method Output normalization and non-uniform sampling.
result Proposed algorithm matches SAC's performance without entropy maximization and improves sample efficiency.
Algorithm for recognizing and performing Reidemeister moves in Gauss diagrams.
problem Recognizing and performing Reidemeister moves in Gauss diagrams.
method Simple algorithm for recognizing and performing Reidemeister moves in Gauss diagrams.
result Simple algorithm for recognizing and performing Reidemeister moves in Gauss diagrams.
Simple proof of knot genus theorem using Alexander polynomial.
problem Proving the genus of an alternating knot equals half the breadth of its Alexander polynomial.
method Elementary, self-contained proof using Seifert's algorithm.
result Minimal genus surface obtained from any alternating knot diagram.
New simulation shows trading algorithms' performance varies with parallelism.
problem Validation of trading algorithms' performance in parallel markets.
method Used TBSE, a threaded market simulator, to compare algorithms' performance.
result Trading algorithms' performance differs in parallel vs. sequential markets.
Simple method for black-box adversarial attacks with low query efficiency.
problem Efficient construction of adversarial images in the black-box setting.
method Randomly sampling from an orthonormal basis and adjusting images.
result Demonstrated unprecedented query efficiency in both untargeted and targeted attacks.
A faster algorithm for ranking from pairwise comparisons.
problem Efficiently ranking individuals or objects from pairwise comparisons.
method An alternative and simpler iterative algorithm for ranking that converges faster.
result The new algorithm is over 100 times faster in some cases.
Optimal simple regret bound for Gaussian Process bandits.
problem Sequential optimization of expensive-to-evaluate functions.
method Proved a bound on simple regret for pure exploration algorithms.
result Order optimal bound on simple regret for Gaussian Process bandits.
New algorithms learn simple staged trees from data, improving model fit.
problem Complex conditional independences in categorical data vectors.
method Structural learning algorithms for simple staged trees, coalescing the underlying tree.
result Data-learned simple staged trees often outperform Bayesian networks in model fit.
The Thermodynamic Costs of Simple Linear Regressioncond-mat.stat-mech
Study on thermodynamic costs of simple linear regression.
problem Understanding thermodynamic costs in machine learning models.
method Approximated thermodynamic lower bounds for exact and stochastic linear regression.
result Derived scaling laws for optimal dataset size based on generalization error.
A computationally simple genome-wide association study (GWAS) algorithm for estimating the main and epistatic effects of markers or single nucleotide polymorphisms (SNPs) is proposed. It is based on the intuitive assumption that changes of alleles corresponding to important SNPs in a pair of individuals lead to large d…
The paper characterizes simple closed curves on surfaces using profinite rigidity.
problem Characterizing simple closed curves on surfaces using profinite rigidity.
method Proving that elements with the same images under all finite groups are simple closed curves.
result The set of simple closed curves is closed in the profinite topology of the surface group.
A celebrated and deep theorem in the theory of Riemann surfaces states the existence and uniqueness of the Jenkins-Strebel differentials on a Riemann surface under some conditions, but the proof is non-constructive and examples are difficult to find. This paper deals with an example of a simple case, namely Jenkins-Str…
Graph classification has recently received a lot of attention from various fields of machine learning e.g. kernel methods, sequential modeling or graph embedding. All these approaches offer promising results with different respective strengths and weaknesses. However, most of them rely on complex mathematics and requir…
Algorithms are increasingly used to aid, or in some cases supplant, human decision-making, particularly for decisions that hinge on predictions. As a result, two additional features in addition to prediction quality have generated interest: (i) to facilitate human interaction and understanding with these algorithms, we…