arXiv research

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-…

The Adam algorithm has become extremely popular for large-scale machine learning. Under convexity condition, it has been proved to enjoy a data-dependant $O(\sqrt{T})$ regret bound where $T$ is the time horizon. However, whether strong convexity can be utilized to further improve the performance remains an open problem…

New study shows acceleration in hyperbolic spaces is impossible for strongly geodesically convex functions.

Almost all local minima in neural networks are strongly convex.

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…

The paper proves a Schwarz lemma for weakly Kähler-Finsler manifolds.

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

New methods accelerate gradient descent for convex and strongly convex functions.

Let $U\subseteq\mathbb{R}^{n}$ be open and convex. We show that every (not necessarily Lipschitz or strongly) convex function $f:U\to\mathbb{R}$ can be approximated by real analytic convex functions, uniformly on all of $U$. In doing so we provide a technique which transfers results on uniform approximation on bounded …

Improved dynamic regret analysis for strongly convex and smooth functions.

We study dual-based algorithms for distributed convex optimization problems over networks, where the objective is to minimize a sum $\sum_{i=1}^{m}f_i(z)$ of functions over in a network. We provide complexity bounds for four different cases, namely: each function $f_i$ is strongly convex and smooth, each function is ei…

Strongly convex bodies can be approximated by smooth ones.

New algorithm solves complex non-convex problems efficiently.

Study large deviations rates for SGD with strongly convex functions.

The paper explores inequalities for strongly-convex sets in weighted Riemannian manifolds.

Random permutations can offer faster convergence than with-replacement sampling for some functions.

Paper closes convergence gap for SGD without replacement.

A new method solves convex optimization problems on manifolds efficiently.

Improved privacy-preserving methods for convex optimization with heavy-tailed data.

New algorithm tackles heterogeneous curvature in online convex optimization.

In large-scale distributed learning, security issues have become increasingly important. Particularly in a decentralized environment, some computing units may behave abnormally, or even exhibit Byzantine failures -- arbitrary and potentially adversarial behavior. In this paper, we develop distributed learning algorithm…

It has recently been shown that the problem of testing global convexity of polynomials of degree four is {strongly} NP-hard, answering an open question of N.Z. Shor. This result is minimal in the degree of the polynomial when global convexity is of concern. In a number of applications however, one is interested in test…

SA algorithms control dynamic regret in non-stationary settings with strong convexity or exp-concavity.

The study finds conditions for certain surfaces to have a specific type of metric.

In this paper we establish a gap theorem for the complex geometry of smoothly bounded convex domains which informally says that if the complex geometry near the boundary is close to the complex geometry of the unit ball, then the domain must be strongly pseudoconvex. One consequence of our general result is the followi…

Uniform diffusion approximation for SGD in non-convex settings.

We propose a family of optimization methods that achieve linear convergence using first-order gradient information and constant step sizes on a class of convex functions much larger than the smooth and strongly convex ones. This larger class includes functions whose second derivatives may be singular or unbounded at th…

Convex optimization with sparsity-promoting convex regularization is a standard approach for estimating sparse signals in noise. In order to promote sparsity more strongly than convex regularization, it is also standard practice to employ non-convex optimization. In this paper, we take a third approach. We utilize a no…

SGD converges to global minimum for structured non-convex functions.

Adaptive gradient methods have become recently very popular, in particular as they have been shown to be useful in the training of deep neural networks. In this paper we have analyzed RMSProp, originally proposed for the training of deep neural networks, in the context of online convex optimization and show $\sqrt{T}$-…

Study optimizes zero-order strongly convex function minimization with higher order smoothness.

In this paper, we prove that a strongly convex complex Finsler metric $F$ on a domain $D\subset\mathbb{C}^n$ is projectively flat (resp. dually flat) if and only if $F$ comes from a strongly convex complex Minkowski metric.

Sharp estimates for Finsler metrics in convex domains.

A generalized optimistic method for saddle point problems with improved complexity.

Stochastic gradient descent in continuous time (SGDCT) provides a computationally efficient method for the statistical learning of continuous-time models, which are widely used in science, engineering, and finance. The SGDCT algorithm follows a (noisy) descent direction along a continuous stream of data. The parameter …

In this paper, we study the optimal convergence rate for distributed convex optimization problems in networks. We model the communication restrictions imposed by the network as a set of affine constraints and provide optimal complexity bounds for four different setups, namely: the function $F(\xb) \triangleq \sum_{i=1}…

New methods optimize functions on hyperbolic and spherical spaces, matching Euclidean rates up to logarithmic factors.

A multiobjective optimization problem is $C^r$ simplicial if the Pareto set and the Pareto front are $C^r$ diffeomorphic to a simplex and, under the $C^r$ diffeomorphisms, each face of the simplex corresponds to the Pareto set and the Pareto front of a subproblem, where $0\leq r\leq \infty$. In the paper titled "Topolo…

The incremental aggregated gradient algorithm is popular in network optimization and machine learning research. However, the current convergence results require the objective function to be strongly convex. And the existing convergence rates are also limited to linear convergence. Due to the mathematical techniques, th…

We develop and analyze an asynchronous algorithm for distributed convex optimization when the objective writes a sum of smooth functions, local to each worker, and a non-smooth function. Unlike many existing methods, our distributed algorithm is adjustable to various levels of communication cost, delays, machines compu…

The paper tackles minimax optimality in continuum contextual bandits with Hölder continuity.

This paper analyzes SGD with increasingly weighted averaging for optimization and generalization.

We develop a family of accelerated stochastic algorithms that minimize sums of convex functions. Our algorithms improve upon the fastest running time for empirical risk minimization (ERM), and in particular linear least-squares regression, across a wide range of problem settings. To achieve this, we establish a framewo…

The main goal of this work is equipping convex and nonconvex problems with Barzilai-Borwein (BB) step size. With the adaptivity of BB step sizes granted, they can fail when the objective function is not strongly convex. To overcome this challenge, the key idea here is to bridge (non)convex problems and strongly convex …

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…

Study smooths Finsler structures on Lie groups, proving extremal convergence.

This paper resolves a longstanding open question pertaining to the design of near-optimal first-order algorithms for smooth and strongly-convex-strongly-concave minimax problems. Current state-of-the-art first-order algorithms find an approximate Nash equilibrium using $\tilde{O}(κ_{\mathbf x}+κ_{\mathbf y})$ or $\tild…

The paper proves properties of complex Finsler metrics on specific domains.