arXiv research

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.

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…

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

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

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…

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

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

New method solves root-finding problems with faster convergence.

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

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 …

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

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

Recent advances in randomized incremental methods for minimizing $L$-smooth $μ$-strongly convex finite sums have culminated in tight complexity of $\tilde{O}((n+\sqrt{n L/μ})\log(1/ε))$ and $O(n+\sqrt{nL/ε})$, where $μ>0$ and $μ=0$, respectively, and $n$ denotes the number of individual functions. Unlike incremental me…

SVRN accelerates Newton methods by reducing variance and improving performance.

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…

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

Accelerates optimization in asynchronous systems with sparse updates.

A thesis submitted for the degree of Doctor of Philosophy of The Australian National University. In this work we introduce several new optimisation methods for problems in machine learning. Our algorithms broadly fall into two categories: optimisation of finite sums and of graph structured objectives. The finite sum pr…

Freya PAGE optimizes nonconvex optimization with heterogeneous, asynchronous workers.

Novel Newton method for large-scale kernel methods using random features.

New framework guarantees convergence of multi-step MAML.

We consider the problem of minimizing the composition of a smooth (nonconvex) function and a smooth vector mapping, where the inner mapping is in the form of an expectation over some random variable or a finite sum. We propose a stochastic composite gradient method that employs an incremental variance-reduced estimator…

We propose an explicit recursive method to approximate a power-law with a finite sum of weighted exponentials. Applications to moving averages with long memory are discussed in relationship with stochastic volatility models.

We study Frank-Wolfe methods for nonconvex stochastic and finite-sum optimization problems. Frank-Wolfe methods (in the convex case) have gained tremendous recent interest in machine learning and optimization communities due to their projection-free property and their ability to exploit structured constraints. However,…

Paper develops probabilistic bounds for a stochastic gradient algorithm in non-convex problems.

In this paper, we consider a class of finite-sum convex optimization problems defined over a distributed multiagent network with $m$ agents connected to a central server. In particular, the objective function consists of the average of $m$ ($\ge 1$) smooth components associated with each network agent together with a s…

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

We propose a fast proximal Newton-type algorithm for minimizing regularized finite sums that returns an $ε$-suboptimal point in $\tilde{\mathcal{O}}(d(n + \sqrt{κd})\log(\frac{1}ε))$ FLOPS, where $n$ is number of samples, $d$ is feature dimension, and $κ$ is the condition number. As long as $n > d$, the proposed method…

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 …

A new algorithm improves convergence rates for convex optimization problems.

The paper analyzes the variance of different shuffling methods in stochastic gradient descent.

PAGE is a simple gradient estimator for nonconvex optimization problems.

Paper develops momentum schemes with variance reduction for non-convex composition optimization.

Techniques for reducing the variance of gradient estimates used in stochastic programming algorithms for convex finite-sum problems have received a great deal of attention in recent years. By leveraging dissipativity theory from control, we provide a new perspective on two important variance-reduction algorithms: SVRG …

Nesterov's momentum trick is famously known for accelerating gradient descent, and has been proven useful in building fast iterative algorithms. However, in the stochastic setting, counterexamples exist and prevent Nesterov's momentum from providing similar acceleration, even if the underlying problem is convex and fin…

Unified framework for decentralized optimization combining gradient tracking and variance reduction.

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

New algorithms solve non-convex optimization problems efficiently.

SMG combines shuffling and momentum for non-convex optimization.

Independent component analysis (ICA) is a widespread data exploration technique, where observed signals are modeled as linear mixtures of independent components. From a machine learning point of view, it amounts to a matrix factorization problem with a statistical independence criterion. Infomax is one of the most used…

A closed spin Kähler manifold of positive scalar curvature with smallest possible first eigenvalue of the Dirac operator is characterized by holomorphic spinors. It is shown that on any spin Kähler-Einstein manifold each holomorphic spinor is a finite sum of eigenspinors of the square of the Dirac operator. Vanishing t…

Many machine learning, statistical inference, and portfolio optimization problems require minimization of a composition of expected value functions (CEVF). Of particular interest is the finite-sum versions of such compositional optimization problems (FS-CEVF). Compositional stochastic variance reduced gradient (C-SVRG)…

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 …

A new decentralized method solves minimax problems with reduced communication and sample complexity.

New algorithms find near-stationary points in convex optimization.