arXiv research

Gradient Descent Ascent converges to von-Neumann solution in hidden zero-sum games.

Derives exact formula for Minkowski sum of ellipsoids in N-space.

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 …

Characterizes compact complex surfaces with finite homotopy rank-sum.

It is well known that a random vector with given marginal distributions is comonotonic if and only if it has the largest sum with respect to the convex order [ Kaas, Dhaene, Vyncke, Goovaerts, Denuit (2002), A simple geometric proof that comonotonic risks have the convex-largest sum, ASTIN Bulletin 32, 71-80. Cheung (2…

Paper discusses natural quasiconvexity and its relation to decomposable sums in risk measures.

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

Derives curvature formulas for convex metric sums and conditions for positive average variation.

Many classical algorithms are found until several years later to outlive the confines in which they were conceived, and continue to be relevant in unforeseen settings. In this paper, we show that SVRG is one such method: being originally designed for strongly convex objectives, it is also very robust in non-strongly co…

Characterizes symmetric Bernoulli distributions with minimal convex sums.

Can the Minkowski sum of two compact convex bodies be made smoother by rotating one of them? We construct two infinitely differentiable strictly convex plane bodies such that after any generic rotation (in the Baire category sense) of one of the summands the Minkowski sum is not five times differentiable. On the other …

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

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

Paper introduces a new kernel model for PSD-valued functions with theoretical guarantees and applications.

We consider the problem of minimizing a sum of clipped convex functions; applications include clipped empirical risk minimization and clipped control. While the problem of minimizing the sum of clipped convex functions is NP-hard, we present some heuristics for approximately solving instances of these problems. These h…

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…

Paper solves anisotropic capillary Minkowski problem for p ≥ 1.

The paper develops sum-of-squares relaxations for computing $f$-divergences.

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…

The paper proves bounds on curvature and injectivity radius for convex sums of Riemannian metrics.

Log-concavity proven for multinomial likelihoods under specific constraints.

Proposes a differentiable LSE-ICNN for modeling multi-well potentials.

If $Γ$ is the range of a Jordan curve that bounds a convex set in $\mathbb{R}^2,$ then $\frac{1}{2}(Γ+Γ)=\mathsf{co}(Γ),$ where $+$ is the Minkowski sum and $\mathsf{co}$ is the convex hull. Answering a question of V.N. Ushakov, we construct a simple closed curve in $\mathbb{R}^3$ with range $Γ$ such that $\frac{1}{2}(…

We consider the problem of minimizing the sum of an average function of a large number of smooth convex components and a general, possibly non-differentiable, convex function. Although many methods have been proposed to solve this problem with the assumption that the sum is strongly convex, few methods support the non-…

New hyperbolic knots with convex Upsilon invariants constructed.

Unified analysis of multi-attribute graph learning with non-convex penalties.

Optimizes convergence rate of stochastic proximal algorithms for composite convex problems.

Unified framework for stability and generalization of Push-Sum in decentralized learning over directed graphs.

SignSVRG improves SignSGD by reducing variance, achieving similar convergence rates.

In this paper we construct Ricci-positive metrics on the connected sum of products of arbitrarily many spheres provided the dimensions of all but one sphere in each summand are at least 3. There are two new technical theorems required to extend previous results on sums of products of two spheres. The first theorem is a…

ZeroS improves Transformers by adding negative weights, matching or beating softmax attention.

We consider the fundamental problem in non-convex optimization of efficiently reaching a stationary point. In contrast to the convex case, in the long history of this basic problem, the only known theoretical results on first-order non-convex optimization remain to be full gradient descent that converges in $O(1/\varep…

New contact structures on folded sums of contact mapping tori are tight under certain conditions.

We show that the spectral norm of a random $n_1\times n_2\times \cdots \times n_K$ tensor (or higher-order array) scales as $O\left(\sqrt{(\sum_{k=1}^{K}n_k)\log(K)}\right)$ under some sub-Gaussian assumption on the entries. The proof is based on a covering number argument. Since the spectral norm is dual to the tensor…

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…

A new algorithm improves convergence rates for convex optimization problems.

Paper closes convergence gap for SGD without replacement.

The authors prove that the logarithmic Monge-Ampère flow with uniformly bound and convex initial data satisfies uniform decay estimates away from time $t=0$. Then applying the decay estimates, we conclude that every entire classical strictly convex solution of the equation {equation*} \det D^{2}u=\exp\{n(-u+1/2\sum_{i=…

Expanding FCCO to non-smooth weakly-convex problems, improving deep learning performance.

In this paper, we consider the convex and non-convex composition problem with the structure $\frac{1}{n}\sum\nolimits_{i = 1}^n {{F_i}( {G( x )} )}$, where $G( x )=\frac{1}{n}\sum\nolimits_{j = 1}^n {{G_j}( x )}$ is the inner function, and $F_i(\cdot)$ is the outer function. We explore the variance reduction based met…

Push-SAGA is a decentralized algorithm for directed graphs that converges linearly.

Convexity proven for sums of angles of unitary paths.

Improved variance reduction for Riemannian non-convex optimization with adaptive batch size.

Convex optimization is an essential tool for machine learning, as many of its problems can be formulated as minimization problems of specific objective functions. While there is a large variety of algorithms available to solve convex problems, we can argue that it becomes more and more important to focus on efficient, …

The total complexity (measured as the total number of gradient computations) of a stochastic first-order optimization algorithm that finds a first-order stationary point of a finite-sum smooth nonconvex objective function $F(w)=\frac{1}{n} \sum_{i=1}^n f_i(w)$ has been proven to be at least $Ω(\sqrt{n}/ε)$ for $n \leq …

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

New estimator avoids overfitting in convex regression.

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…