arXiv research

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…

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…

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…

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

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

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

This paper establishes lower bounds for smooth nonconvex finite-sum optimization.

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 …

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

Two new Frank-Wolfe algorithms improve convergence for constrained 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…

New framework guarantees convergence of multi-step MAML.

Improved SVRC algorithm reduces complexity for nonconvex optimization.

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

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.

SVRG reduces gradient evaluations for policy evaluation in reinforcement learning.

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…

New method solves root-finding problems with faster convergence.

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

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.

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…

Accelerates optimization in asynchronous systems with sparse updates.

Paper develops efficient algorithms for robust optimization across multiple groups.

New insights into tail behavior of heavy-tailed random vectors and processes.

Freya PAGE optimizes nonconvex optimization with heterogeneous, asynchronous workers.

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

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.

New methods optimize machine learning models without sharing data.

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…

New method reduces complexity for nonconvex optimization problems.

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

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…

RMDA trains structured neural networks with regularization and variance reduction.

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.