arXiv research

The paper studies the solution of stochastic optimization problems in which approximations to the gradient and Hessian are obtained through subsampling. We first consider Newton-like methods that employ these approximations and discuss how to coordinate the accuracy in the gradient and Hessian to yield a superlinear ra…

In [19], a general, inexact, efficient proximal quasi-Newton algorithm for composite optimization problems has been proposed and a sublinear global convergence rate has been established. In this paper, we analyze the convergence properties of this method, both in the exact and inexact setting, in the case when the obje…

Develops a new SPP algorithm with variance reduction for weakly convex optimization.

Proposes STRON method for large-scale machine learning problems.

ERNN improves RNN accuracy and stability with time-delayed self-feedback.

The paper analyzes inexact variants of iterative methods for solving optimization problems.

We consider distributed convex optimization problems originated from sample average approximation of stochastic optimization, or empirical risk minimization in machine learning. We assume that each machine in the distributed computing system has access to a local empirical loss function, constructed with i.i.d. data sa…

New method solves constrained optimization problems efficiently.

In this work, we present a globalized stochastic semismooth Newton method for solving stochastic optimization problems involving smooth nonconvex and nonsmooth convex terms in the objective function. We assume that only noisy gradient and Hessian information of the smooth part of the objective function is available via…

First-order optimization methods, such as stochastic gradient descent (SGD) and its variants, are widely used in machine learning applications due to their simplicity and low per-iteration costs. However, they often require larger numbers of iterations, with associated communication costs in distributed environments. I…

New algorithm improves convergence of gradient boosting trees.

We propose an inexact variable-metric proximal point algorithm to accelerate gradient-based optimization algorithms. The proposed scheme, called QNing can be notably applied to incremental first-order methods such as the stochastic variance-reduced gradient descent algorithm (SVRG) and other randomized incremental opti…

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…

We consider variants of trust-region and cubic regularization methods for non-convex optimization, in which the Hessian matrix is approximated. Under mild conditions on the inexact Hessian, and using approximate solution of the corresponding sub-problems, we provide iteration complexity to achieve $ε$-approximate seco…

New methods optimize functions faster with less gradient accuracy needed.

The paper applies momentum to CR Newton's method for nonconvex optimization, improving convergence.

Recently several methods were proposed for sparse optimization which make careful use of second-order information [10, 28, 16, 3] to improve local convergence rates. These methods construct a composite quadratic approximation using Hessian information, optimize this approximation using a first-order method, such as coo…

We consider the class of convex minimization problems, composed of a self-concordant function, such as the $\log\det$ metric, a convex data fidelity term $h(\cdot)$ and, a regularizing -- possibly non-smooth -- function $g(\cdot)$. This type of problems have recently attracted a great deal of interest, mainly due to th…

Proposes a method for anomaly detection with inexact labels.

We consider the problem of finding the minimizer of a convex function $F: \mathbb R^d \rightarrow \mathbb R$ of the form $F(w) := \sum_{i=1}^n f_i(w) + R(w)$ where a low-rank factorization of $\nabla^2 f_i(w)$ is readily available. We consider the regime where $n \gg d$. As second-order methods prove to be effective in…

The class of non-rigid registration methods proposed in the framework of PDE-constrained Large Deformation Diffeomorphic Metric Mapping is a particularly interesting family of physically meaningful diffeomorphic registration methods. PDE-constrained LDDMM methods are formulated as constrained variational problems, wher…

MuonEq improves training of matrix-valued parameters by rebalancing momentum before orthogonalization.

In machine learning research, the proximal gradient methods are popular for solving various optimization problems with non-smooth regularization. Inexact proximal gradient methods are extremely important when exactly solving the proximal operator is time-consuming, or the proximal operator does not have an analytic sol…

Paper shows how gradient concentration helps in learning from inexact data.

New characterization limits sampling with inexact scores.

Inexact Riemannian optimization converges to stationary points efficiently.

We focus on solving the clustered lasso problem, which is a least squares problem with the $\ell_1$-type penalties imposed on both the coefficients and their pairwise differences to learn the group structure of the regression parameters. Here we first reformulate the clustered lasso regularizer as a weighted ordered-la…

Inexact acquisition solutions in BO lead to sublinear cumulative regret.

This paper analyzes the bias of inexact MCMC methods in high dimensions.

Evolutionary forms, as well as exterior forms, are skew-symmetric differential forms. But in contrast to the exterior forms, the basis of evolutionary forms is deforming manifolds (with unclosed metric forms). Such forms possess a peculiarity, namely, the closed inexact exterior forms are obtained from that. The closur…

New methods solve complex optimization problems in machine learning.

New algorithm solves phase retrieval with adaptive stopping criteria.

New algorithm tackles complex optimization problems with inexact and stochastic methods.

Optimizes solving complex min-max problems with stochastic and nonconvex elements.

Large scale optimization problems are ubiquitous in machine learning and data analysis and there is a plethora of algorithms for solving such problems. Many of these algorithms employ sub-sampling, as a way to either speed up the computations and/or to implicitly implement a form of statistical regularization. In this …

Stochastic methods tackle inexact Hessian and gradient computations in large-scale non-convex optimization.

We propose novel first-order stochastic approximation algorithms for canonical correlation analysis (CCA). Algorithms presented are instances of inexact matrix stochastic gradient (MSG) and inexact matrix exponentiated gradient (MEG), and achieve $ε$-suboptimality in the population objective in $\operatorname{poly}(\fr…

Second order Sobolev metrics are a useful tool in the shape analysis of curves. In this paper we combine these metrics with varifold-based inexact matching to explore a new strategy of computing geodesics between unparametrized curves. We describe the numerical method used for solving the inexact matching problem, appl…

A new method for optimization in probability space using Newton's flows.

We describe stochastic Newton and stochastic quasi-Newton approaches to efficiently solve large linear least-squares problems where the very large data sets present a significant computational burden (e.g., the size may exceed computer memory or data are collected in real-time). In our proposed framework, stochasticity…

Newton's method solves variational problems on manifolds.

In this paper, we consider the convergence of an abstract inexact nonconvex and nonsmooth algorithm. We promise a pseudo sufficient descent condition and a pseudo relative error condition, which are both related to an auxiliary sequence, for the algorithm; and a continuity condition is assumed to hold. In fact, a lot o…

In kernel methods, the kernels are often required to be positive definite, which restricts the use of many indefinite kernels. To consider those non-positive definite kernels, in this paper, we aim to build an indefinite kernel learning framework for kernel logistic regression. The proposed indefinite kernel logistic r…

Muon with Newton-Schulz converges to the same stationary point as SVD-polar, up to a constant factor.

Newton methods improve CNN optimization, showing competitive accuracy.

Study optimizes decisions in real-time using inexact simulation solutions.

Simple stochastic Newton and cubic Newton methods with fast convergence.

Generalizes Newton's Second Law for field theory.