arXiv research

One-Class Boundary Peeling detects outliers efficiently and robustly.

In this paper we study an experimentally-observed connection between two seemingly unrelated processes, one from computational geometry and the other from differential geometry. The first one (which we call "grid peeling") is the convex-layer decomposition of subsets $G\subset \mathbb Z^2$ of the integer grid, previous…

Proposes a privacy-preserving sign selection method for distributed systems.

Study peels tensor equations on Schwarzschild spacetime.

New model explains neural collapse and limits on minority classes in imbalanced datasets.

New method for causal discovery using peeling algorithms for various data types.

Study of Dirac fields on Kerr spacetimes using peeling method.

New supervised and unsupervised NFLTs for elliptical distributions.

Faster algorithm for generalized mean densest subgraph problem.

A new algorithm reduces graph complexity for better dense subgraph analysis.

In this paper, we show that the peeling property still holds for Bondi-Sachs metrics with nonzero cosmological constant under the boundary condition given by Sommerfeld's radiation condition together with three nontrivial $Λ$-independent functions $B$, $a$, $b$. This should indicate the new boundary condition is natura…

The paper uncovers symmetries in large language models through layer-peeled optimization.

This paper investigates graph clustering in the planted cluster model in the presence of {\em small clusters}. Traditional results dictate that for an algorithm to provably correctly recover the clusters, {\em all} clusters must be sufficiently large (in particular, $\tildeΩ(\sqrt{n})$ where $n$ is the number of nodes …

New method speeds up solving L0-regularized least-squares problems.

Study of Bondi-Sachs formalism for massless scalar field with zero cosmological constant.

Paper explains neural collapse in neural networks using a new model.

The paper develops a robust algorithm for contextual bandits with heavy-tailed rewards.

A new iterative low complexity algorithm has been presented for computing the Walsh-Hadamard transform (WHT) of an $N$ dimensional signal with a $K$-sparse WHT, where $N$ is a power of two and $K = O(N^α)$, scales sub-linearly in $N$ for some $0 < α< 1$. Assuming a random support model for the non-zero transform domain…

Significant improvements in regret analysis for adaptive online learning problems.

A lamination of a graph embedded on a surface is a collection of pairwise disjoint non-contractible simple closed curves drawn on the graph. In the case when the surface is a sphere with three punctures (a.k.a. a pair of pants), we first identify the lamination space of a graph embedded on that surface as a lattice pol…

The Sample Compression Conjecture of Littlestone & Warmuth has remained unsolved for over two decades. This paper presents a systematic geometric investigation of the compression of finite maximum concept classes. Simple arrangements of hyperplanes in Hyperbolic space, and Piecewise-Linear hyperplane arrangements, are …

Paper introduces efficient top-k selection with differential privacy.

Starting from an arbitrary sequence of polygons whose total perimeter is $2n$, we can build an (oriented) surface by pairing their sides in a uniform fashion. Chmutov and Pittel (arXiv:1503.01816) have shown that, regardless of the configuration of polygons we started with, the degree sequence of the graph obtained thi…

Paper proposes a privacy-preserving method to control false discoveries.

Mixtures of Mallows models are a popular generative model for ranking data coming from a heterogeneous population. They have a variety of applications including social choice, recommendation systems and natural language processing. Here we give the first polynomial time algorithm for provably learning the parameters of…

The paper analyzes generalization in deep contrastive learning.

New method reduces multi-armed bandit regret to near-optimal levels.

Study explains how noisyGD with DP improves feature learning despite high dimensionality.

We consider the estimation of treatment effects in settings when multiple treatments are assigned over time and treatments can have a causal effect on future outcomes or the state of the treated unit. We propose an extension of the double/debiased machine learning framework to estimate the dynamic effects of treatments…

Paper analyzes iterates in high-dimensional linear models and proposes estimators for their generalization error.

Paper analyzes iterative learning for concept classes and learns half-spaces.

WaveFit uses fixed-point iteration to create high-quality neural vocoders.

In this paper, we introduce the notions of an iterated planar Lefschetz fibration and an iterated planar open book decomposition and prove the Weinstein conjecture for contact manifolds supporting an open book that has iterated planar pages. For $n\geq 1$, we show that a $(2n+1)$-dimensional contact manifold $M$ suppor…

We prove that an iterated torus knot type fails the uniform thickness property (UTP) if and only if all of its iterations are positive cablings, which is precisely when an iterated torus knot type supports the standard contact structure. We also show that all iterated torus knots that fail the UTP support cabling knot …

Sharp analysis of power iteration for tensor PCA, improving convergence and stopping criteria.

We deduce from the work of Chen, that the restriction morphism from closed free iterated integrals to closed iterated integrals on loops is onto. We use this to show that the module of higher order invariants of smooth functions is generated by free closed iterated integrals.

In this paper we study the smooth convex-concave saddle point problem. Specifically, we analyze the last iterate convergence properties of the Extragradient (EG) algorithm. It is well known that the ergodic (averaged) iterates of EG converge at a rate of $O(1/T)$ (Nemirovski, 2004). In this paper, we show that the last…

Adaptive optimal control of nonlinear dynamic systems with deterministic and known dynamics under a known undiscounted infinite-horizon cost function is investigated. Policy iteration scheme initiated using a stabilizing initial control is analyzed in solving the problem. The convergence of the iterations and the optim…

An iterative SE(3)-Transformer model is developed for graph data.

Iterative method learns unknown constraints for MPC control.

Value iteration is a fixed point iteration technique utilized to obtain the optimal value function and policy in a discounted reward Markov Decision Process (MDP). Here, a contraction operator is constructed and applied repeatedly to arrive at the optimal solution. Value iteration is a first order method and therefore …

Iterates towards Kähler metrics with constant scalar curvature.

We give short proofs of the following two facts: Iterated principal circle bundles are precisely the nilmanifolds. Every iterated circle bundle is almost flat, and hence diffeomorphic to an infranilmanifold.

Algorithm recovers causal graphs from data with fewer tests.

Spherical T-duality for iterated sphere bundles

In this paper we investigate what kind of manifolds arise as the total spaces of iterated $S^1$-bundles. A real Bott tower studied in \cite{CMO}, \cite{KM} and \cite{KN} is an example of an iterated $S^1$-bundle. We show that the total space of an iterated $S^1$-bundle is homeomorphic to an infra-nilmanifold. A real Bo…

Improved generalization with iterate averaging and adaptive algorithms.

DSPI connects natural policy gradient to policy iteration, proving global convergence.