arXiv research

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

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…

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…

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…

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…

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

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

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

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

New methods optimize machine learning models without sharing data.

New method reduces complexity for nonconvex optimization problems.

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

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

A new algorithm improves convergence rates for convex optimization problems.

In this work we establish the first linear convergence result for the stochastic heavy ball method. The method performs SGD steps with a fixed stepsize, amended by a heavy ball momentum term. In the analysis, we focus on minimizing the expected loss and not on finite-sum minimization, which is typically a much harder p…

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

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

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

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

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

Freya PAGE optimizes nonconvex optimization with heterogeneous, asynchronous workers.

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 …

We present novel minibatch stochastic optimization methods for empirical risk minimization problems, the methods efficiently leverage variance reduced first-order and sub-sampled higher-order information to accelerate the convergence speed. For quadratic objectives, we prove improved iteration complexity over state-of-…

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

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 …

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…

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 algorithms find near-stationary points in convex optimization.

Recent advances in optimization theory have shown that smooth strongly convex finite sums can be minimized faster than by treating them as a black box "batch" problem. In this work we introduce a new method in this class with a theoretical convergence rate four times faster than existing methods, for sums with sufficie…

Paper analyzes SARAH algorithm for smooth finite-sum optimization, achieving optimal complexity.

New method solves root-finding problems with faster convergence.

SAGA algorithm improved for arbitrary sampling and minibatching.

New algorithm finds local minima in non-convex problems efficiently.

We introduce and study co-dimension one area-minimizing locally rectifiable currents $T$ with $C^{1,α}$ tangentially immersed boundary: $\partial T$ is locally a finite sum of orientable co-dimension two submanifolds which only intersect tangentially with equal orientation. We show that any such $T$ is supported in a s…

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 …

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

An algorithm is proposed for solving stochastic and finite sum minimization problems. Based on a trust region methodology, the algorithm employs normalized steps, at least as long as the norms of the stochastic gradient estimates are within a specified interval. The complete algorithm---which dynamically chooses whethe…

Stochastic Gradient Descent underperforms on some problems, contrary to expectations.

New algorithm reduces distributed optimization time with stochastic delays.

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…

This paper proposes a framework of L-BFGS based on the (approximate) second-order information with stochastic batches, as a novel approach to the finite-sum minimization problems. Different from the classical L-BFGS where stochastic batches lead to instability, we use a smooth estimate for the evaluations of the gradie…

Paper develops efficient algorithms for robust optimization across multiple groups.

We consider the problem of finding the minimizer of a function $f: \mathbb{R}^d \rightarrow \mathbb{R}$ of the finite-sum form $\min f(w) = 1/n\sum_{i}^n f_i(w)$. This problem has been studied intensively in recent years in the field of machine learning (ML). One promising approach for large-scale data is to use a stoc…