Stochastic proximal point algorithm with momentum converges faster and is more stable than standard methods.
problem Improving convergence and stability of stochastic optimization methods.
method Developed and analyzed the convergence and stability of the stochastic proximal point algorithm with momentum (SPPAM).
result SPPAM converges faster and is more stable than standard stochastic proximal point algorithm (SPPA) and stochastic gradient descent with momentum (SGDM).
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.
Unified analysis of EG and OGDA for saddle point problems using proximal point method.
problem Solving saddle point problems in bilinear and strongly convex-strongly concave settings.
method Unified analysis as approximations of the proximal point method.
result Unified analysis of EG and OGDA for saddle point problems.
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.
Improves RL algorithms with two techniques.
problem Enhance off-policy RL performance.
method Formulates RL as proximal point iteration; uses value functions for improved action value estimate.
result Significant performance improvement on RL benchmarks.
New algorithm speeds up solving saddle-point problems with large condition numbers.
problem Solving saddle-point problems with large condition numbers.
method Proposes a stochastic proximal point algorithm that accelerates variance reduction methods.
result Reduces logarithmic term of condition number for iteration complexity.
Proximal boosting improves gradient boosting for non-differentiable losses.
problem Minimizing non-differentiable losses in prediction models.
method Proximal point algorithm applied to gradient boosting.
result Proximal boosting outperforms gradient boosting in convergence rate and accuracy.
In this paper we develop proximal methods for statistical learning. Proximal point algorithms are useful in statistics and machine learning for obtaining optimization solutions for composite functions. Our approach exploits closed-form solutions of proximal operators and envelope representations based on the Moreau, Fo…
A new optimization method, BPM, converges linearly in non-convex, non-smooth problems.
problem Non-smooth and non-convex optimization challenges.
method Ball-Proximal Point Method (BPM), inspired by Proximal Point Method (PPM).
result BPM converges linearly and in a finite number of steps in non-convex, non-smooth problems.
New findings show Bregman proximal algorithms can get stuck near non-stationary points.
problem Bregman proximal algorithms can get stuck near non-stationary points, misleadingly suggesting convergence.
method Analysis of Bregman proximal algorithms and their behavior near non-stationary points.
result Bregman proximal algorithms can get stuck near spurious stationary points, even in convex 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.
New algorithms improve empirical risk minimization across various settings.
problem Minimizing sums of convex functions efficiently.
method Developed a family of accelerated stochastic algorithms based on proximal point algorithm.
result Improved running time for empirical risk minimization across a wide range of problem settings.
Develops a new algorithm for computing exact Wasserstein distance efficiently.
problem High computational complexity of exact Wasserstein distance computation.
method Inexact Proximal Point Method (IPOT) with approximate projections to the probability simplex.
result Algorithm converges to exact Wasserstein distance with theoretical guarantees and robust regularization parameter selection.
Two new algorithms improve federated optimization under second-order similarity.
problem Federated learning under communication constraints and second-order similarity.
method SVRP and Catalyzed SVRP algorithms combining proximal point evaluations, client sampling, and variance reduction.
result Achieves superior performance and uniformly improves upon existing algorithms for federated optimization under second-order similarity and strong convexity.
Improved sampling guarantees for weakly log-concave distributions.
problem Sampling from distributions that are not strongly log-concave.
method Proximal sampler with convergence guarantees under weaker assumptions.
result New state-of-the-art sampling guarantees for various target distributions.
New algorithm improves convergence rates for convex optimization problems.
problem Convex optimization problems with noisy stochastic data.
method Stochastic proximal point algorithm with weak linear regularity condition.
result Achieves $\mathcal{O}\left(\frac{1}{k}
ight)$ convergence rate for SPP.
The paper analyzes convergence properties of NGA and PAMe for L1-norm PCA.
problem Finite-step convergence of L1-norm PCA algorithms. method Conditional subgradient and alternating maximization interpretations of NGA, and PAMe with extrapolation.
result Iterative points of modified NGA and PAMe remain constant after finitely many steps under certain conditions.
A method for estimating the median of gradients in stochastic optimization.
problem Robust gradient estimation in stochastic optimization for various applications.
method Stochastic Proximal Point Method for median gradient estimation.
result The proposed method can converge even under heavy-tailed, state-dependent noise.
New algorithm solves GDS with faster convergence and FDR control.
problem Generalized Dantzig Selector estimation problem.
method Primal-dual proximal extragradient algorithm with saddle-point reformulation.
result Achieves optimal O(1/k) convergence rate. New algorithms tackle machine learning problems using manifold proximal point methods.
problem Maximizing the ℓ1 norm of a linear map over the sphere in machine learning.
method Manifold Proximal Point Algorithms (ManPPA) and Stochastic ManPPA (StManPPA).
result ManPPA and StManPPA achieve faster convergence rates than existing methods.
A new method solves optimization problems over Stiefel manifold.
problem Optimization problems over the Stiefel manifold with smooth and nonsmooth components.
method Proximal gradient method based on retraction.
result The method globally converges to a stationary point and has iteration complexity.
New model approximates sparse mean-CVaR portfolio optimization efficiently.
problem NP-hard ℓ0-constrained mean-CVaR optimization. method Proximal alternating linearized minimization algorithm with nested fixed-point proximity.
result The model offers a guaranteed approximation of the ℓ0-constrained mean-CVaR model. Heavy-ball algorithms can always avoid saddle points with random initialization.
problem Optimizing nonconvex functions with saddle points.
method Developed a new mapping to interpret heavy-ball algorithms as iterations, proving they can escape saddle points.
result Heavy-ball algorithms can escape saddle points with random initialization.
Paper establishes lower bounds for optimization of convex functions.
problem Lower bounds for optimization of convex functions with gradient and proximal oracle access.
method Developed a novel construction to prove lower bounds for strongly-convex case.
result Lower bound matches upper bound of existing algorithm Point-SAGA.
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…
The paper shows linear convergence of a proximal gradient algorithm with extrapolation for nonconvex problems.
problem Minimizing the sum of a differentiable and a convex function under error bound condition.
method Proximal gradient algorithm with extrapolation, under error bound condition.
result The sequence generated converges R-linearly to a stationary point of the problem.
Paper introduces a new reinforcement learning method with improved performance.
problem Designing and analyzing efficient reinforcement learning algorithms.
method Proximal gradient temporal difference learning (GTD) with accelerated algorithm GTD2-MP.
result GTD algorithms have linear complexity and improved convergence rate.
Paper develops accelerated APCD for nonconvex nonsmooth problems with performance guarantees.
problem Efficient methods for nonconvex nonsmooth optimization problems with performance guarantees.
method Asynchronous Accelerated Proximal Coordinate Descent (AAPCD) for nonsmooth and nonconvex problems.
result AAPCD ensures that every limit point is a critical point and achieves linear and sublinear convergence rates.
New algorithms solve nonconvex, nonsmooth optimization problems.
problem Optimizing nonconvex, nonsmooth finite-sum problems with limited existing knowledge.
method Developed fast stochastic algorithms for constant minibatches.
result Proved global linear convergence rate for a specific class of functions.
New algorithm solves non-convex optimization problems with DC functions.
problem Non-convex optimization problems with DC functions.
method DC Proximal Newton algorithm for non-convex optimization.
result The algorithm finds stationary points of DC objective function.
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 scientific and engineering applications feature nonsmooth convex minimization problems over convex sets. In this paper, we address an important instance of this broad class where we assume that the nonsmooth objective is equipped with a tractable proximity operator and that the convex constraint set affords a self…
New algorithms accelerate model-based optimization for stochastic problems.
problem Optimizing model-based stochastic optimization problems efficiently.
method Proposed new model-based algorithms with acceleration and minibatch techniques.
result Non-asymptotic convergence guarantees with linear speedup in minibatch size.
New analysis shows convergence rate of 1/k for gradient and extra-gradient methods.
problem Finding saddle points in convex-concave problems.
method Interpreted as proximal point method approximations, showing iterates remain bounded.
result Primal dual gap converges at rate O(1/k).
Improves time series classification with forest proximities.
problem Time series classification accuracy and efficiency.
method PF-GAP, an extension of RF-GAP proximities to proximity forests, combined with Multi-Dimensional Scaling and Local Outlier Factors.
result Forest proximities show stronger connection between misclassified points and outliers.
Improved random forest proximities capture data geometry.
problem Inaccurate random forest proximities do not reflect learned data geometry.
method Introduce RF-GAP: Geometry- and Accuracy-Preserving proximities.
result RF-GAP improves geometric representation in tasks like data imputation.
POP3D is a new reinforcement learning algorithm that improves upon PPO.
problem The shortcomings of existing reinforcement learning algorithms.
method Policy Optimization with Penalized Point Probability Distance (POP3D) as a lower bound to the square of total variance divergence.
result POP3D is highly competitive compared to PPO in various benchmarks.
Improved DNN training with BCD converging faster than SGD.
problem Training deep neural networks efficiently and accurately.
method Developed a smooth multi-convex formulation and BCD algorithm for training Tikhonov regularized DNNs.
result BCD algorithm converges globally to a stationary point with R-linear rate.
A new method for RLHF using proximal point Nash learning.
problem Capturing real human preferences in RLHF.
method Proximal point Nash learning, embedding self-play updates into a proximal point framework.
result High-probability last-iterate convergence for the combined method.
New method solves saddle-point problems faster than existing methods.
problem Large-scale saddle-point problems in optimization.
method Sequential subspace optimization with proximal regularization.
result Significantly better convergence compared to first-order methods.
New algorithm solves non-convex, non-differentiable min-max games.
problem Limited theoretical understanding of non-smooth min-max games.
method Proximal gradient descent-ascent algorithm for convex-strongly convex games.
result Algorithm converges to ε-Nash equilibrium with polynomial gradient evaluations.
Proposes a semi-implicit back propagation method for neural networks.
problem Challenges in training neural networks, especially gradient vanishing and small step sizes.
method Proposes a semi-implicit back propagation method using error back propagation and proximal methods.
result The proposed method leads to better performance in terms of loss decreasing and training/validation accuracy compared to SGD and ProxBP.
PPOS improves PPO by smoothing the surrogate objective function.
problem Performance instability and optimization inefficiency in PPO.
method Use of a functional clipping method instead of a flat clipping method.
result PPOS conducts more accurate updates and outperforms other PPO variants.
Two algorithms find optimal points in decentralized optimization.
problem Decentralized non-convex stochastic optimization with composite objective functions.
method Prox-DASA and Prox-DASA-GT algorithms for finding ε-stationary points.
result Achieves comparable complexity without large batch sizes or complex per-iteration operations.
Two new methods solve nonsmooth optimization on Riemannian Stiefel manifold.
problem Optimization over nonsmooth, non-differentiable functions on Riemannian manifolds.
method R-ProxSGD and R-ProxSPB, generalizing proximal SGD and SpiderBoost.
result R-ProxSPB finds ε-stationary points with IFO complexity of Ø(ε^(-3)) in online and Ø(n + √nε^(-2)) in finite-sum cases.
Decentralized method solves saddle point problems with theoretical guarantees.
problem Solving saddle point problems in a decentralized network.
method Proximal point method adapted for decentralized networks.
result Converges to approximate stationarity with rate of O(1/√T).
Paper develops a constant step stochastic Douglas-Rachford algorithm for convex minimization.
problem Finding solutions to convex minimization problems with random functions.
method Stochastic Douglas-Rachford algorithm with constant step size.
result Iterates stay close to the solution set with high probability.
New method reduces variance in stochastic optimization with high confidence.
problem Achieving high-probability guarantees in stochastic optimization with weaker noise assumptions.
method Stochastic proximal point method combining proximal subproblem solver and probability booster.
result Demonstrates convergence with low sample complexity under bounded variance assumptions.