arXiv research

Characterizes compact complex surfaces with finite homotopy rank-sum.

Characterizes Stein surfaces with finite homotopy rank-sum.

Genus 3 Heegaard groups of lens space connected sums are finitely generated.

We prove for any positive integer $n$ there exist boundary-sum irreducible ${\mathbb Z}_n$-corks with Stein structure. Here `boundary-sum irreducible' means the manifold is indecomposable with respect to boundary-sum. We also verify that some of the finite order corks admit hyperbolic boundary by HIKMOT.

New methods optimize sums of bivariate functions on finite domains.

Smooth finite-sum optimization has been widely studied in both convex and nonconvex settings. However, existing lower bounds for finite-sum optimization are mostly limited to the setting where each component function is (strongly) convex, while the lower bounds for nonconvex finite-sum optimization remain largely unsol…

New lower bounds for gradient methods in strongly convex finite-sum optimization.

Paper establishes lower bounds for finite-sum optimization problems using novel construction methods.

New method reduces complexity of minimizing convex finite sums without needing individual function indices.

We describe a novel optimization method for finite sums (such as empirical risk minimization problems) building on the recently introduced SAGA method. Our method achieves an accelerated convergence rate on strongly convex smooth problems. Our method has only one parameter (a step size), and is radically simpler than o…

We study the conditions under which one is able to efficiently apply variance-reduction and acceleration schemes on finite sum optimization problems. First, we show that, perhaps surprisingly, the finite sum structure by itself, is not sufficient for obtaining a complexity bound of $\tilde{\cO}((n+L/μ)\ln(1/ε))$ for $L…

Novel analysis of EFP for finite-sum problems in neural networks.

Lower bounds for higher-order methods in non-convex optimization.

Study on convergence of Langevin dynamics for zero-sum games in probability distributions.

Spatial graphs are decomposed into planar forests and braids.

Stochastic optimization algorithms with variance reduction have proven successful for minimizing large finite sums of functions. Unfortunately, these techniques are unable to deal with stochastic perturbations of input data, induced for example by data augmentation. In such cases, the objective is no longer a finite su…

We provide an explicit section for a mapping class group sequence.

Defines a universal state sum construction for various TQFTs.

Study on Nesterov's method in stochastic settings, revealing divergence under certain conditions.

DESTRESS optimizes decentralized nonconvex optimization with optimal IFO complexity and efficient communication.

Paper proposes a faster SPIDER-EM variant for large-scale nonconvex optimization.

A new method, Residual-Permuted Sums, improves confidence region construction for linear regression models.

The height function of various surfaces decomposes into finite sums of scaled and translated versions of itself.

Proves a formula for a special invariant of 4-manifolds.

This paper presents a lower bound for optimizing a finite sum of $n$ functions, where each function is $L$-smooth and the sum is $μ$-strongly convex. We show that no algorithm can reach an error $ε$ in minimizing all functions from this class in fewer than $Ω(n + \sqrt{n(κ-1)}\log(1/ε))$ iterations, where $κ=L/μ$ is a …

We give a short proof that if a non-trivial band sum of two knots results in a tight fibered knot, then the band sum is a connected sum. In particular, this means that any prime knot obtained by a non-trivial band sum is not tight fibered. Since a positive L-space knot is tight fibered, a non-trivial band sum never yie…

Summing over 3-manifolds using TQFT partition functions.

We prove that the expectation value of the index function i(x) over a probability space of injective function f on any finite simple graph G=(V,E) is equal to the curvature K(x) at the vertex x. This result complements and links Gauss-Bonnet sum K(x) = chi(G) and Poincare-Hopf sum i(x) = chi(G) which both hold for arbi…

SVRN accelerates Newton methods by reducing variance and improving performance.

New method solves root-finding problems with faster convergence.

Let H_g denote the closed 3-manifold obtained as the connected sum of g copies of S^2 times S^1, with free fundamental group of rank g. We prove that, for a finite group G acting on H_g which induces a faithful action on the fundamental group, there is an upper bound for the order of G which is quadratic in g, but that…

We analyze the obstruction to metrics of positive scalar curvature within a given bounded distortion class of metrics. This obstruction lives in a non-Hausdorff cohomology group Poincare dual to the uniformly finite homology studied by Block and Weinberger. One of the applications is a converse to their theorem on infi…

We study Farrell Nil-groups associated to a finite order automorphism of a ring $R$. We show that any such Farrell Nil-group is either trivial, or infinitely generated (as an abelian group). Building on this first result, we then show that any finite group that occurs in such a Farrell Nil-group occurs with infinite mu…

A perturbative approach is used to derive approximations of arbitrary order to estimate high percentiles of sums of positive independent random variables that exhibit heavy tails. Closed-form expressions for the successive approximations are obtained both when the number of terms in the sum is deterministic and when it…

Finite-sum optimization problems are ubiquitous in machine learning, and are commonly solved using first-order methods which rely on gradient computations. Recently, there has been growing interest in \emph{second-order} methods, which rely on both gradients and Hessians. In principle, second-order methods can require …

Study best-response learning dynamics in zero-sum polymatrix games under full and minimal information settings.

Colding and Gabai have given an effective version of Li's theorem that non-Haken hyperbolic 3-manifolds have finitely many irreducible Heegaard splittings. As a corollary of their work, we show that Haken hyperbolic 3-manifolds have a finite collection of strongly irreducible Heegaard surfaces $S_i$ and incompressible …

Optimal SGD rates achieved with shuffling, covering non-convex and convex cases.

We prove that the locally finite simplicial volume and the Lipschitz simplicial volume are additive with respect to certain gluings of manifolds. In particular, we prove that in dimension $\geq 3$ they are additive with respect to connected sums and gluings along $π_1$-injective, amenable aspherical boundary components…

Study on descent properties of complex affine surfaces under proper morphisms.

This paper develops a Hoeffding inequality for the partial sums $\sum_{k=1}^n f (X_k)$, where $\{X_k\}_{k \in \mathbb{Z}_{> 0}}$ is an irreducible Markov chain on a finite state space $S$, and $f : S \to [a, b]$ is a real-valued function. Our bound is simple, general, since it only assumes irreducibility and finiteness…

The problem of minimizing sum-of-nonconvex functions (i.e., convex functions that are average of non-convex ones) is becoming increasingly important in machine learning, and is the core machinery for PCA, SVD, regularized Newton's method, accelerated non-convex optimization, and more. We show how to provably obtain an …

For most positive integer pairs $(a,b)$, the topological space $#a{\mathbb C \mathbb P}^2#b{\bar{\mathbb C \mathbb P^2}}$ is shown to admit infinitely many inequivalent smooth structures which dissolve upon performing a single connected sum with $S^2\times S^2$. This is then used to construct infinitely many non-equiva…

The discrete sum of geometric Brownian motions plays an important role in modeling stochastic annuities in insurance. It also plays a pivotal role in the pricing of Asian options in mathematical finance. In this paper, we study the probability distributions of the infinite sum of geometric Brownian motions, the sum of …

We propose an optimization method for minimizing the finite sums of smooth convex functions. Our method incorporates an accelerated gradient descent (AGD) and a stochastic variance reduction gradient (SVRG) in a mini-batch setting. Unlike SVRG, our method can be directly applied to non-strongly and strongly convex prob…

Study shows non-cyclic groups of diffeomorphisms can't act on certain 3-manifolds.

The Black-Scholes model anticipates rather well the observed prices for options in the case of a strike price that is not too far from the current price of the underlying asset. Some useful extensions can be obtained by an adequate modification of the coefficients in the Black-Scholes equation. We investigate from a ma…

Two new Frank-Wolfe algorithms improve convergence for constrained optimization.