We generalize Newton-type methods for minimizing smooth functions to handle a sum of two convex functions: a smooth function and a nonsmooth function with a simple proximal mapping. We show that the resulting proximal Newton-type methods inherit the desirable convergence behavior of Newton-type methods for minimizing s…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
169,291 papers · 148 categories
Trend · papers per month
48 results for “proximal Newton”
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.
problem Weakly convex, composite optimization problems.
method Inexact semismooth Newton framework with variance reduction for stochastic proximal point updates.
result Establishes convergence results for the proposed algorithm.
Proposes a new algorithm for nonconvex sparse learning problems that converges quickly.
problem Nonconvex sparse learning problems in high dimensions.
method Combines proximal Newton algorithm with DC programming for multi-stage convex relaxation.
result Achieves quadratic convergence and finds sparse approximate local optima.
Introduces PPMM algorithm for nonconvex robust regression problems.
problem Nonconvex tuning-free robust regression problems.
method PPMM algorithm with inner subproblems solved by SSN-PPA.
result Converges to d-stationary point with KL property.
Efficient algorithm solves sparse nonconvex regression problems.
problem Sparse nonconvex square-root-loss regression problems.
method Proximal majorization-minimization (PMM) algorithm with sparse semismooth Newton method.
result Converges to a d-stationary point with Kurdyka-Łojasiewicz property.
Many machine learning techniques sacrifice convenient computational structures to gain estimation robustness and modeling flexibility. However, by exploring the modeling structures, we find these "sacrifices" do not always require more computational efforts. To shed light on such a "free-lunch" phenomenon, we study the…
Physics insights into optimization algorithms using differential equations.
problem Understanding dynamics of optimization algorithms in machine learning.
method Unified framework based on physical systems analysis of popular optimization algorithms.
result Unified analysis applicable to non-convex and non-strongly convex problems.
A new method solves nonsmooth nonconvex optimization problems with noisy gradients.
problem Solving nonsmooth nonconvex optimization problems with noisy gradient information.
method Globalized stochastic semismooth Newton method combining semismooth Newton steps and proximal gradient steps.
result The method converges globally to stationary points in expectation and locally r-superlinearly.
Estimates MoE models with feature selection for high-dimensional data.
problem Estimation and feature selection in Mixtures-of-Experts models with high-dimensional predictors.
method Regularized maximum likelihood estimation with proximal-Newton EM algorithm.
result Good performance in recovering sparse solutions, parameter estimation, and clustering of heterogeneous data.
We consider the class of optimization problems arising from computationally intensive L1-regularized M-estimators, where the function or gradient values are very expensive to compute. A particular instance of interest is the L1-regularized MLE for learning Conditional Random Fields (CRFs), which are a popular class of …
In this paper we consider the composite self-concordant (CSC) minimization problem, which minimizes the sum of a self-concordant function and a (possibly nonsmooth) proper closed convex function . The CSC minimization is the cornerstone of the path-following interior point methods for solving a broad class of co…
We propose an algorithmic framework for convex minimization problems of a composite function with two terms: a self-concordant function and a possibly nonsmooth regularization term. Our method is a new proximal Newton algorithm that features a local quadratic convergence rate. As a specific instance of our framework, w…
A new algorithm speeds up machine learning by solving large-scale problems more efficiently.
problem Efficiently solving large-scale machine learning problems with regularization.
method Subsampled proximal Newton-type method that leverages finite sum structure and recent stochastic first-order methods.
result The method achieves faster convergence than state-of-the-art methods for non-smooth regularizers.
New method solves convex optimization faster than NAG.
problem Unconstrained smooth convex optimization problems.
method Accelerated quasi-Newton proximal extragradient (A-QPNE) method.
result Achieves a faster convergence rate of .
Develops a new method for solving nonsmooth nonconvex optimization problems.
problem Solving nonsmooth nonconvex composite optimization problems with noisy gradient information.
method Combines stochastic higher order steps and additional stochastic proximal gradient steps.
result Global convergence to stationary points in expectation with favorable performance on large-scale problems.
Proposes an accelerated optimization algorithm for composite objectives.
problem Gradient-based optimization with sparse solutions and high dimensions.
method Inexact variable-metric proximal point algorithm (QNing) with limited-memory BFGS.
result Significant improvements over competing methods in training machine learning models.
Paper improves a method for fast global and local convergence in optimization.
problem Slow global convergence in optimization methods with noisy Hessian estimates.
method Stochastic Newton Proximal Extragradient method using HPE framework.
result Faster global linear rate and superlinear convergence in fewer iterations.
Novel algorithm accelerates PnP methods for image deblurring and super-resolution.
problem Efficiently solving inverse problems and imaging with provable convergence guarantees.
method Incorporates quasi-Newton steps into provable PnP framework based on proximal denoisers.
result 2--8x faster convergence compared to other provable PnP methods with similar quality.
In many learning tasks, structural models usually lead to better interpretability and higher generalization performance. In recent years, however, the simple structural models such as lasso are frequently proved to be insufficient. Accordingly, there has been a lot of work on "superposition-structured" models where mul…
Efficient Gauss-Newton optimisation for neural networks.
problem Optimizing deep learning models efficiently and effectively.
method Block-diagonal approximation of Gauss-Newton matrix for neural networks.
result The resulting algorithm outperforms state-of-the-art first-order optimisation methods.
In this paper, we discuss the problem of minimizing the sum of two convex functions: a smooth function plus a non-smooth function. Further, the smooth part can be expressed by the average of a large number of smooth component functions, and the non-smooth part is equipped with a simple proximal mapping. We propose a pr…
A distributed semismooth Newton based augmented Lagrangian method for distributed optimizationmath.OC
A new method solves distributed optimization problems over networks.
problem Solving optimization problems over networks with local cost functions and limited communication.
method Distributed semismooth Newton based augmented Lagrangian method.
result The method efficiently solves distributed optimization problems over networks.
We introduce a novel algorithm for solving learning problems where both the loss function and the regularizer are non-convex but belong to the class of difference of convex (DC) functions. Our contribution is a new general purpose proximal Newton algorithm that is able to deal with such a situation. The algorithm consi…
New quasi-Newton method guarantees global superlinear convergence.
problem Global convergence and superlinear convergence of quasi-Newton methods.
method Hybrid proximal extragradient method with online learning for Hessian approximation.
result First globally convergent quasi-Newton method with explicit superlinear convergence rate.
New algorithm solves complex medical radiation therapy problems.
problem Optimizing radiation therapy treatment plans.
method Majorization-minimization principle applied to non-linear split feasibility problems.
result Euclidean norm in proximity function replaced by Bregman divergences.
Unified Newton-type methods for convex optimization using generalized self-concordant functions.
problem Designing efficient Newton-type methods for convex optimization.
method Introducing generalized self-concordant functions and developing Newton-type methods.
result Unified framework for global and local convergence of Newton-type methods.
OPDA optimizes L1-regularized models with faster convergence and sparsity.
problem Optimizing -regularized models for sparse regression or classification.
method Orthant-wise passive descent algorithm (OPDA) using SVRG initialization and alignment operator.
result OPDA achieves linear convergence on smooth and strongly-convex loss functions.
We propose a new proximal, path-following framework for a class of constrained convex problems. We consider settings where the nonlinear---and possibly non-smooth---objective part is endowed with a proximity operator, and the constraint set is equipped with a self-concordant barrier. Our approach relies on the followin…
New method approximates CV for model assessment and selection.
problem Efficient model assessment and selection with large number of folds.
method Approximates expensive refitting with a single Newton step warm-started from full training set optimizer.
result Uniform non-asymptotic, deterministic model assessment guarantees for approximate CV.
Paper proposes a quasi-Newton method for nonlinear equations with global convergence guarantees.
problem Solving smooth and monotone nonlinear equations efficiently and globally.
method Hybrid proximal extragradient framework combined with online learning for Jacobian approximation.
result First global convergence results showing quasi-Newton method's advantage over extragradient method.
Paper proposes a new method to find approximate SOSP for nonconvex constrained optimization problems.
problem Finding a second-order stationary point of nonconvex equality constrained optimization.
method Newton-CG based augmented Lagrangian method with a new Newton-CG subproblem solver.
result Achieves better complexity guarantees for finding approximate SOSP with high probability.
Paper tackles multivariate shape-constrained convex regression problems.
problem Fitting a convex function to data with component-wise monotonicity and uniform Lipschitz continuity.
method Least squares estimator via solving a constrained convex quadratic programming problem. Efficient algorithms designed: sGS-ADMM and pALM.
result Both proposed algorithms outperform state-of-the-art methods in numerical experiments.
The paper analyzes momentum variants of various stochastic optimization methods.
problem Improving the convergence rates of stochastic optimization methods.
method Stochastic gradient descent, Newton, proximal point, and subspace ascent methods with momentum.
result Global linear convergence rates for various measures of success.
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…
Unified view of accelerated and stochastic optimization methods.
problem Optimization challenges in machine learning and physics.
method Unified gradient flow approach to proximal algorithms and their accelerated variants.
result Unified framework for accelerated and stochastic optimization methods.
A new algorithm solves the metric nearness problem efficiently.
problem Finding the nearest distance matrix that satisfies triangle inequalities.
method Delayed constraint generation with semismooth Newton based proximal augmented Lagrangian method (PALM).
result Solves problems with up to 10^8 variables and 10^13 constraints efficiently.
Improves robustness of high-dimensional regression with rank objective and group lasso regularization.
problem Heavy-tailed noise and outliers in high-dimensional regression.
method Non-smooth Wilcoxon score based rank objective, group lasso regularization, data-driven tuning rule, proximal augmented Lagrangian method.
result Robust estimator with finite-sample error bound and efficient computational method.
Chandrasekaran, Parrilo and Willsky (2010) proposed a convex optimization problem to characterize graphical model selection in the presence of unobserved variables. This convex optimization problem aims to estimate an inverse covariance matrix that can be decomposed into a sparse matrix minus a low-rank matrix from sam…
New algorithm solves clustered lasso problem efficiently.
problem Learning group structure in regression parameters.
method Inexact semismooth Newton augmented Lagrangian algorithm with efficient Jacobian computation.
result The {\sc Ssnal} algorithm outperforms existing methods.
We consider the class of convex minimization problems, composed of a self-concordant function, such as the metric, a convex data fidelity term and, a regularizing -- possibly non-smooth -- function . This type of problems have recently attracted a great deal of interest, mainly due to th…
Stochastic Newton and quasi-Newton methods solve large linear least-squares problems efficiently.
problem Efficiently solve large linear least-squares problems with limited computational resources.
method Introduce stochasticity in Newton and quasi-Newton approaches to handle large datasets.
result Stochastic Newton iterates may not converge to the least-squares solution.
Proposes a robust and sparse portfolio selection model to reduce estimation errors and transaction costs.
problem Reduces impact of estimation errors and fixed transaction costs in portfolio selection.
method Develops an efficient algorithm to solve a mixed integer problem with an ellipsoidal uncertainty set.
result Proves the convergence of the algorithm to at least a local minimizer with a locally linear convergence rate.
A new method for optimization in probability space using Newton's flows.
problem Optimization in probability space with information metrics.
method Information Newton's flows, including Fisher-Rao and Wasserstein-2 metrics, with Newton's Langevin dynamics and variational methods.
result Effective numerical implementation and convergence results for the proposed method.
Newton's method solves variational problems on manifolds.
problem Solving variational equations on manifolds.
method Newton's method with affine covariant damping strategy.
result Numerical results for variational problems demonstrated.
This research compares gradient and Newton boosting methods in classification and regression.
problem The distinction between gradient descent and Newton updates in boosting algorithms is not well understood.
method Presented a unified framework for gradient and Newton boosting, and compared them with tree base learners.
result Newton boosting outperforms gradient and hybrid boosting in predictive accuracy on most datasets.
Muon with Newton-Schulz converges to the same stationary point as SVD-polar, up to a constant factor.
problem Improving the convergence rate of Muon optimizer.
method Using Newton-Schulz steps for momentum orthogonalization, proving convergence rate and constant factor.
result 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.
problem Optimizing CNNs for deep learning applications.
method Detailed investigation and implementation of Newton methods for CNNs.
result Newton methods for CNNs achieve competitive test accuracy.