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.

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

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…

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

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…

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…

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

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

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

Accelerates optimization in asynchronous systems with sparse updates.

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

Freya PAGE optimizes nonconvex optimization with heterogeneous, asynchronous workers.

SVRN accelerates Newton methods by reducing variance and improving performance.

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

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…

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 …

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

We study Nesterov's accelerated gradient method with constant step-size and momentum parameters in the stochastic approximation setting (unbiased gradients with bounded variance) and the finite-sum setting (where randomness is due to sampling mini-batches). To build better insight into the behavior of Nesterov's method…

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…

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

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.

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 …

PAGE is a simple gradient estimator for nonconvex optimization problems.

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…

A new algorithm improves convergence rates for convex optimization problems.

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

SMG combines shuffling and momentum for non-convex optimization.

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…

New algorithms find near-stationary points in convex optimization.

SLEDGE algorithm reduces gradient computation errors in optimization.

We develop two new stochastic Gauss-Newton algorithms for solving a class of non-convex stochastic compositional optimization problems frequently arising in practice. We consider both the expectation and finite-sum settings under standard assumptions, and use both classical stochastic and SARAH estimators for approxima…

Avare improves optimization and sampling with adaptive importance sampling.

In this paper, we consider a class of finite-sum convex optimization problems whose objective function is given by the summation of $m$ ($\ge 1$) smooth components together with some other relatively simple terms. We first introduce a deterministic primal-dual gradient (PDG) method that can achieve the optimal black-bo…

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.

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

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

Sampling without replacement speeds up optimization in minimax problems.

New algorithm finds approximate stationary points faster under differential privacy constraints.

Paper develops efficient algorithms for robust optimization across multiple groups.

New method solves root-finding problems with faster convergence.

We propose two algorithms that can find local minima faster than the state-of-the-art algorithms in both finite-sum and general stochastic nonconvex optimization. At the core of the proposed algorithms is $\text{One-epoch-SNVRG}^+$ using stochastic nested variance reduction (Zhou et al., 2018a), which outperforms the s…

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

Paper analyzes complexity of solving nonconvex-strongly-concave problems.

Doubly SGD improves convergence for intractable objective optimization.

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