New proof for sphere recognition algorithm.
problem Sphere recognition algorithm proof.
method New proof of a lemma in Abigail Thompson's algorithm.
result New proof of a lemma in Abigail Thompson's proof of the Recognition Algorithm for 3-spheres.
Simplified proof for Tsallis-INF algorithm without conjugate functions.
problem Deriving a best-of-both-worlds guarantee for Tsallis-INF.
method Modern tools from online convex optimization, avoiding conjugate functions.
result A slimmer proof with simplified constants.
Polynomial-time algorithm estimates mean with bounded covariance using differential privacy.
problem Estimating mean of a d-variate distribution with differential privacy constraints.
method Sum of Squares (SoS) exponential mechanism for polynomial-time differentially private estimation.
result First polynomial-time algorithm with O(d) samples for mean estimation under pure differential privacy. We give an algorithmic proof of the theorem that a closed orientable irreducible and atoroidal 3-manifold has only finitely many Heegaard splittings in each genus, up to isotopy. The proof gives an algorithm to determine the Heegaard genus of an atoroidal 3-manifold.
Unified proof for various bandit algorithms with logarithmic regret.
problem Achieving logarithmic regret in stochastic bandit algorithms.
method Minimal high-probability concentration condition and two deterministic lemmas.
result Unified proofs for classical and contemporary bandit algorithms.
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.
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.
Sum-of-squares proofs help solve complex estimation problems.
problem Recovering hidden parameters from high-dimensional distributions.
method Sum-of-squares proofs for polynomial systems.
result Sum-of-squares proofs can be used to solve polynomial systems efficiently.
New proof eliminates definite fold in higher dimensions.
problem Eliminating definite fold in higher dimensions.
method Homotopy and algorithmic procedures for constructing examples.
result Non-existence of singular Legendre fibrations on 3-manifolds.
Simplified proof for approximations of set systems.
problem Approximations of set systems in various fields.
method Modular, self-contained proof using Chernoff's bound.
result Accessible proof for a wider audience.
We present a new proof of the classification of complex simple Lie algebras via the projective geometry of homogeneous varieties. Our proof proceeds by constructing homogeneous varieties using the ideals of the secant and tangential varieties of homogeneous varieties already constructed. Our algorithms make no referenc…
Improved the convergence proof of ADAM-Optimizer.
problem Incorrect convergence proof of ADAM-Optimizer.
method Provided an improved convergence proof.
result Corrected the convergence proof of ADAM-Optimizer.
We provide a proof of backpropagation algorithm in matrix notation.
problem The lack of a full induction proof of backpropagation algorithm in matrix notation.
method We provide a full induction proof of the BP algorithm in matrix notation, situating it in the framework of matrix differential calculus.
result We prove the validity of the backpropagation algorithm in inductive form.
Paper solves outlier robust mean estimation near breakdown point.
problem Estimating mean in presence of adversarial outliers.
method Sum-of-Squares approach to optimize error rate efficiently.
result Achieves optimal error rate for all ε ∈ [0, 1/2).
Paper analyzes CDRL algorithms for reinforcement learning.
problem Understanding theoretical properties of CDRL algorithms.
method Introduces a framework to analyze CDRL algorithms, establishes the importance of the projected distributional Bellman operator, draws connections to Cramér distance, and proves convergence.
result Proof of convergence for sample-based categorical distributional reinforcement learning algorithms.
This research simplifies verification of machine learning systems using reparameterization.
problem Reduce or eliminate serious bugs in machine learning systems.
method Use proof assistants to construct machine-checked proofs of correctness, leveraging reparameterization to handle probabilistic claims.
result Demonstrates broad applicability of reparameterization to verify different types of machine learning systems.
Algorithm learns Gaussian mixtures robust to outliers.
problem Efficiently learn high-dimensional Gaussian mixtures with outliers.
method Sum-of-Squares based proofs to algorithms approach.
result Polynomial time algorithm for k-mixture with pairwise separated components. 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.
This article contains detailed proofs and additional examples related to the UAI-2013 submission `Learning Sparse Causal Models is not NP-hard'. It describes the FCI+ algorithm: a method for sound and complete causal model discovery in the presence of latent confounders and/or selection bias, that has worst case polyno…
New convergence issues found in AMSGrad and a new version proposed.
problem AMSGrad convergence proof issues and neglected hyper-parameter treatment.
method Provided counter-example and proposed new convergence proof and version.
result AMSGrad convergence proof issues and new version AMSX.
Improved EM algorithm for faster convergence of mixture models.
problem Slow or invalid convergence of EM algorithm for mixture models.
method CM-EM algorithm with a step to optimize mixture ratios and maximize G.
result Global convergence proof for CM-EM algorithm using variational methods.
We provide the first differentially private algorithms for controlling the false discovery rate (FDR) in multiple hypothesis testing, with essentially no loss in power under certain conditions. Our general approach is to adapt a well-known variant of the Benjamini-Hochberg procedure (BHq), making each step differential…
We exhibit an algorithm to determine the bridge number of a hyperbolic knot in the 3-sphere. The proof uses adaptations of almost normal surface theory for compact surfaces with boundary in ideally triangulated knot exteriors.
The multiplicative update (MU) algorithm has been extensively used to estimate the basis and coefficient matrices in nonnegative matrix factorization (NMF) problems under a wide range of divergences and regularizers. However, theoretical convergence guarantees have only been derived for a few special divergences withou…
The earlier article tried to construct an algorithm to compute the Heegaard Floer homology \hat{HF}(Y) for a 3-manifold Y. However there is an error in a proof which the author, as of now, is unable to fix.
No standard compact Clifford-Klein forms found for exceptional Lie groups.
problem Proving the non-existence of standard compact Clifford-Klein forms for exceptional Lie groups.
method Computer-aided approach, algorithmic methods for classifying semisimple subalgebras, and invariant calculations.
result Proves the non-existence of standard compact Clifford-Klein forms for homogeneous spaces of exceptional Lie groups.
The split Bregman (SB) method [T. Goldstein and S. Osher, SIAM J. Imaging Sci., 2 (2009), pp. 323-43] is a fast splitting-based algorithm that solves image reconstruction problems with general l1, e.g., total-variation (TV) and compressed sensing (CS), regularizations by introducing a single variable split to decouple …
New IRL algorithm for continuous state spaces with formal guarantees.
problem Finding a reward function for expert behavior in continuous state spaces.
method Modeling the system using orthonormal functions and providing correctness proofs.
result Proof of correctness and formal guarantees on sample and time complexity.
There are three main thrusts to this article: a new proof of Levi's Enlargement Lemma for pseudoline arrangements in the real projective plane; a new characterization of pseudolinear drawings of the complete graph; and proofs that pseudolinear and convex drawings of Kn have n2+O(nlogn) and O(n2), respect…
AdaBoost's classifier and margins converge to a known value.
problem Convergence properties of AdaBoost algorithm.
method Formal proofs of convergence properties of AdaBoost's classifier and margins.
result AdaBoost's classifier and margins converge to a known value.
Proves and tests methods for learning time-series with breaks.
problem Learning time-series with structural breaks.
method Complete proofs and experimental validation of a regularized loss function.
result Experimental results support the validity of the techniques.
New framework reduces sum-of-squares proof degree, speeding up clustering and robust moment estimation.
problem Sum-of-squares proof optimization and faster algorithms for clustering and robust moment estimation.
method Introducing new variables to reduce the degree of sum-of-squares proofs.
result Significantly faster algorithms for clustering and robust moment estimation with the same statistical guarantees.
We present an iterative technique for finding zeroes of vector fields on Riemannian manifolds. As a special case we obtain a ``nonlinear averaging algorithm'' that computes the centroid of a mass distribution supported in a set of small enough diameter D in a Riemannian manifold M. We estimate the convergence rate of o…
We analyze relationships between quantum computation and a family of generalizations of the Jones polynomial. Extending recent work by Aharonov et al., we give efficient quantum circuits for implementing the unitary Jones-Wenzl representations of the braid group. We use these to provide new quantum algorithms for appro…
Improved Sinkhorn algorithm for UOT with near-linear complexity.
problem Solving the entropic regularized Unbalanced Optimal Transport problem efficiently.
method Geometric convergence analysis of Sinkhorn updates and primal solution properties.
result Near-linear time complexity for finding ε-approximate UOT solutions. We give a combinatorial proof of a theorem first proved by Souto which says the following. Let M_1 and M_2 be simple 3-manifolds with connected boundary of genus g>0. If M_1 and M_2 are glued via a complicated map, then every minimal Heegaard splitting of the resulting closed 3-manifold is an amalgamation. This proof a…
Formally verifies fairness and uniformity in financial market trades.
problem Ensuring fairness and uniformity in automated trading systems.
method Formal definition and verification in Coq proof assistant.
result Properties of double-sided auction mechanisms verified.
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 introduces proof-of-learning to verify ML model training.
problem No mechanism to prove ML model training parameters were obtained through optimization.
method Inspired by proof-of-work and verified computations, introduces proof-of-learning mechanism.
result Proves model training parameters were obtained through optimization with minimal adversary work.
We derive a new proof to show that the incremental resparsification algorithm proposed by Kelner and Levin (2013) produces a spectral sparsifier in high probability. We rigorously take into account the dependencies across subsequent resparsifications using martingale inequalities, fixing a flaw in the original analysis…
Paper develops PAC verification for hypothesis classes and statistical algorithms.
problem Verifying machine learning models interactively.
method Develops interactive proof for PAC verification, proves lower bounds, and introduces a generalization.
result Improved protocol for verifying unions of intervals and statistical query algorithms.
Polynomial-time algorithm for homotoping arcs or curves into efficient position.
problem Finding efficient position for arcs or curves on surfaces.
method Polynomial-time algorithm using local homotopies.
result Polynomial-time efficient position achieved for surfaces of positive complexity.
Proof of existence and uniqueness of weighted Voronoi-Delaunay on polyhedral surfaces.
problem Existence and uniqueness of weighted Voronoi-Delaunay on polyhedral surfaces.
method Construct an isotopic map instead of edge-flipping algorithm, generalizing Dyer et al's method.
result Strict proof of existence and uniqueness of weighted Voronoi-Delaunay on polyhedral surfaces.
Algorithm calculates polynomial coefficients of link invariants.
problem Computing first coefficients of link invariants.
method Dynamic programming algorithm for Homflypt and Kauffman polynomials.
result Polynomial time complexity for first coefficients.
We construct a Kirby diagram of the rational homology ball used in "generalized rational blow-down" developed by Jongil Park. The diagram consists of a dotted circle and a torus knot. The link is simpler, but the parameters are a little complicate. Euclidean Algorithm is used three times in the construction and the pro…
We propose the kl-UCB ++ algorithm for regret minimization in stochastic bandit models with exponential families of distributions. We prove that it is simultaneously asymptotically optimal (in the sense of Lai and Robbins' lower bound) and minimax optimal. This is the first algorithm proved to enjoy these two propertie…
Survey on minimal penalty algorithms and slope heuristics.
problem Choosing optimal multiplicative constants from data.
method Minimal penalty and slope heuristics approach.
result Slope heuristics performs almost as well as residual-based estimators.
Direct proof shows adaptive gradient descent converges near-linearly for convex functions.
problem Proving near-linear convergence of adaptive gradient descent for convex functions.
method Direct Lyapunov-based argument for convex functions with unique minimizer.
result Direct proof of near-linear convergence for convex functions.