arXiv research

New algorithm improves understanding of decentralized SBO transient iteration complexity.

Improved stochastic Halpern iteration for fixed-point approximation in normed spaces.

Formal normal form created for real-smooth hypersurfaces.

Chen's iterated integrals are treated within synthetic differential geometry. The main result is that iterated integrals produce a subcomplex of the de Rham complex on the free path space as well as based path spaces.

New sampler reduces MCMC complexity for Bayesian variable selection.

Basic elements of integral calculus over algebras of iterated differential forms, are presented. In particular, defining complexes for modules of integral forms are described and the corresponding berezinians and complexes of integral forms are computed. Various applications and the integral calculus over the algebra $…

FVI method calculates bicausal OT with neural networks, outperforming other methods.

Two new algorithms solve nonconvex-strongly concave problems efficiently.

Estimates complex Hessian integral for complex Monge-Ampère equations.

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

Principal component analysis (PCA) is one of the most powerful tools in machine learning. The simplest method for PCA, the power iteration, requires $\mathcal O(1/Δ)$ full-data passes to recover the principal component of a matrix with eigen-gap $Δ$. Lanczos, a significantly more complex method, achieves an accelerated…

SGD's performance improves with critical batch size, minimizing SFO complexity.

Many real world learning tasks involve complex or hard-to-specify objectives, and using an easier-to-specify proxy can lead to poor performance or misaligned behavior. One solution is to have humans provide a training signal by demonstrating or judging performance, but this approach fails if the task is too complicated…

Improved private learning of halfspaces with reduced sample complexity.

OptEx accelerates first-order optimization with parallelized iterations.

Adaptive SAA solves large-scale stochastic linear programs efficiently.

New algorithms solve complex minimax problems without needing derivatives.

Study of Ricci iterations on Kähler metrics, proving new theorems.

Paper develops a TR-SSQP method for noisy optimization with heavy-tailed noise.

Sublinear LSVI via LSH reduces runtime to sublinear in actions.

In this paper we consider $l_0$ regularized convex cone programming problems. In particular, we first propose an iterative hard thresholding (IHT) method and its variant for solving $l_0$ regularized box constrained convex programming. We show that the sequence generated by these methods converges to a local minimizer.…

Abstract: Deltoid map connects complex dynamics and algebra.

Cubic regularization (CR) is an optimization method with emerging popularity due to its capability to escape saddle points and converge to second-order stationary solutions for nonconvex optimization. However, CR encounters a high sample complexity issue for finite-sum problems with a large data size. %Various inexact …

New iterative regularization method tackles non-smooth, non-strongly convex functionals.

We propose an adaptive smoothing algorithm based on Nesterov's smoothing technique in \cite{Nesterov2005c} for solving "fully" nonsmooth composite convex optimization problems. Our method combines both Nesterov's accelerated proximal gradient scheme and a new homotopy strategy for smoothness parameter. By an appropriat…

New algorithms solve robust MDPs efficiently, significantly faster than existing methods.

In a recent paper Donaldson defines three operators on a space of Hermitian metrics on a complex projective manifold: $T, T_ν, T_K.$ Iterations of these operators converge to balanced metrics, and these themselves approximate constant scalar curvature metrics. In this paper we investigate the convergence properties of …

Scaled gradient descent improves matrix recovery for ill-conditioned matrices with optimal sampling complexity.

Study compares methods for computing hypergradients in machine learning problems.

Traditional learning methods for training Markov random fields require doing inference over all variables to compute the likelihood gradient. The iteration complexity for those methods therefore scales with the size of the graphical models. In this paper, we propose \emph{block belief propagation learning} (BBPL), whic…

This paper studies the problem of distributed stochastic optimization in an adversarial setting where, out of the $m$ machines which allegedly compute stochastic gradients every iteration, an $α$-fraction are Byzantine, and can behave arbitrarily and adversarially. Our main result is a variant of stochastic gradient de…

Polyak step size GD reaches final radius of convergence after log iterations.

New online method estimates OT distances from sample streams.

Paper achieves $ε^{-2}$ sample complexity for actor-critic methods with minimal assumptions.

In this paper, we propose a stochastic Primal-Dual Hybrid Gradient (PDHG) approach for solving a wide spectrum of regularized stochastic minimization problems, where the regularization term is composite with a linear function. It has been recognized that solving this kind of problem is challenging since the closed-form…

Improved algorithms for convex-concave min-max optimization and monotone variational inequalities.

We show that there can be no algorithm to decide whether infinite recursively described acyclic aspherical 2-complexes are contractible. We construct such a complex that is contractible if and only if the Collatz conjecture holds.

Method solves complex optimization problems with high probability bounds.

The cyclic block coordinate descent-type (CBCD-type) methods, which performs iterative updates for a few coordinates (a block) simultaneously throughout the procedure, have shown remarkable computational performance for solving strongly convex minimization problems. Typical applications include many popular statistical…

We study the Ricci iteration for homogeneous metrics on spheres and complex projective spaces. Such metrics can be described in terms of modifying the canonical metric on the fibers of a Hopf fibration. When the fibers of the Hopf fibration are circles or spheres of dimension 2 or 7, we observe that the Ricci iteration…

Paper tackles robust MDPs with sample complexity guarantees.

New method accelerates steepest descent for convex optimization.

We propose and analyze a new parallel coordinate descent method---`NSync---in which at each iteration a random subset of coordinates is updated, in parallel, allowing for the subsets to be chosen non-uniformly. We derive convergence rates under a strong convexity assumption, and comment on how to assign probabilities t…

We calculate the twisted Reidemeister torsion of the complement of an iterated torus knot associated with a representation of its fundamental group to the complex special linear group of degree two. We also show that the twisted Reidemeister torsions associated with various representations appear in the asymptotic expa…

Recently there has been a surge of interest in understanding implicit regularization properties of iterative gradient-based optimization algorithms. In this paper, we study the statistical guarantees on the excess risk achieved by early-stopped unconstrained mirror descent algorithms applied to the unregularized empiri…

Banach's fixed point theorem for contraction maps has been widely used to analyze the convergence of iterative methods in non-convex problems. It is a common experience, however, that iterative maps fail to be globally contracting under the natural metric in their domain, making the applicability of Banach's theorem li…

Given a linear regression setting, Iterative Least Trimmed Squares (ILTS) involves alternating between (a) selecting the subset of samples with lowest current loss, and (b) re-fitting the linear model only on that subset. Both steps are very fast and simple. In this paper we analyze ILTS in the setting of mixed linear …

In a recent paper, Darvas-Rubinstein proved a convergence result for the Kahler-Ricci iteration, which is a sequence of recursively defined complex Monge-Ampere equations. We introduce the Monge-Ampere iteration to be an analogous, but more general, sequence of recursively defined real Monge-Ampere second boundary valu…