Iteratively reweighted algorithm is a popular algorithm for solving a large class of optimization problems whose objective is the sum of a Lipschitz differentiable loss function and a possibly nonconvex sparsity inducing regularizer. In this paper, motivated by the success of extrapolation techniques in accele…
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.
168,742 papers · 148 categories
Trend · papers per month
48 results for “Kurdyka-Łojasiewicz condition”
Proposes a new method for joint sample and feature selection in multi-view data.
problem Cannot detect latent subsets of samples and remove outliers.
method Weighted Sparse Partial Least Squares (-wsPLS) method for joint sample and feature selection.
result Developed globally convergent algorithm and iterative algorithms for multi-view data fusion.
In this paper, we consider a class of possibly nonconvex, nonsmooth and non-Lipschitz optimization problems arising in many contemporary applications such as machine learning, variable selection and image processing. To solve this class of problems, we propose a proximal gradient method with extrapolation and line sear…
New method tackles nonconvex-nonconcave problems with local KL condition.
problem Nonconvex-nonconcave minimax problems under varying KL conditions.
method Inexact proximal gradient method for KL-structured subproblems.
result Complexity guarantees for approximate stationary points.
New analysis reveals batch size effects on stochastic conditional gradient methods.
problem Understanding the role of batch size in stochastic conditional gradient methods.
method Deriving a new analysis focusing on momentum-based stochastic conditional gradient algorithms (e.g., Scion).
result Increasing batch size initially improves optimization accuracy but can degrade performance beyond a critical threshold.
This paper improves inverse problem solving with weakly convex regularisers and proves convergence.
problem Improving solution methods for inverse problems.
method Generalised formulation of convergent regularisation using weakly convex regularisers, and proof of convergence for primal-dual hybrid gradient method.
result Proves convergence of primal-dual hybrid gradient method for variational problems and shows improved performance with IWCNNs.
PPGD solves nonconvex nonsmooth optimization problems without KL property.
problem Nonconvex and nonsmooth optimization problems in statistics and machine learning.
method Projective Proximal Gradient Descent (PPGD) for solving a class of nonconvex and nonsmooth problems.
result PPGD achieves a fast convergence rate of O(1/k^2) for k ≥ k_0.
An inexact LPA for DC composite optimization and application to matrix completions with outliersmath.OC
Paper proposes iLPA for solving DC composite optimization problems, with applications to matrix completion with outliers.
problem Solving nonconvex and nonsmooth DC composite optimization problems.
method Inexact linearized proximal algorithm (iLPA) for DC composite optimization problems.
result The iLPA achieves local R-linear convergence rate under the Kurdyka-Łöjasiewicz property.
Kurdyka-Lojasiewicz (KL) exponent plays an important role in estimating the convergence rate of many contemporary first-order methods. In particular, a KL exponent of for a suitable potential function is related to local linear convergence. Nevertheless, KL exponent is in general extremely hard to estimate. I…
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.
Paper analyzes convergence rates of SGD for non-convex functions under various assumptions.
problem Analyzing convergence rates of SGD for non-convex functions.
method Studied convergence properties of Stochastic Gradient Descent (SGD) for invex functions under weaker and stronger hypotheses.
result Derives estimates on the rate of convergence of $J(oldsymbolθ_t)$ to its limit for functions satisfying the Polyak-Lojasiewicz (PL) condition.
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…
Study efficient iterative method for distribution matching using sliced optimal transport.
problem Efficiently match distributions using sliced optimal transport.
method Slice-matching scheme based on sliced optimal transport, with quantitative non-asymptotic rates derived.
result Derive quantitative non-asymptotic rates for convergence to target distribution.
In this paper, we study the efficiency of a {\bf R}estarted {\bf S}ub{\bf G}radient (RSG) method that periodically restarts the standard subgradient method (SG). We show that, when applied to a broad class of convex optimization problems, RSG method can find an -optimal solution with a lower complexity than the SG m…
New method solves complex constrained optimization problems.
problem Constrained nonconvex-nonconcave minimax optimization problems.
method Inexact proximal gradient method using sequential convex programming.
result Established complexity guarantees for approximate stationary points.
We derive bounds on the path length of gradient descent (GD) and gradient flow (GF) curves for various classes of smooth convex and nonconvex functions. Among other results, we prove that: (a) if the iterates are linearly convergent with factor , then is at most ; (b) under the Polyak-K…
Deep networks converge in direction, with implications for predictions and margins.
problem Understanding convergence and alignment in deep learning networks.
method Developed a theory of unbounded nonsmooth Kurdyka-Łojasiewicz inequalities for functions definable in an o-minimal structure.
result Network weights, predictions, training errors, and margin distribution converge in direction and align with gradient flow.
Cubic-regularized Newton's method (CR) is a popular algorithm that guarantees to produce a second-order stationary solution for solving nonconvex optimization problems. However, existing understandings of the convergence rate of CR are conditioned on special types of geometrical properties of the objective function. In…
Paper proposes a framework and algorithm for model compression in neural networks.
problem Training neural networks with model compression techniques suffers from accuracy loss and convergence issues.
method Holistic framework based on nonconvex optimization, using NN-BCD algorithm with closed-form iteration scheme.
result The proposed algorithm globally converges to a critical point at a rate of O(1/k).
In this paper, we further study the forward-backward envelope first introduced in [28] and [30] for problems whose objective is the sum of a proper closed convex function and a twice continuously differentiable possibly nonconvex function with Lipschitz continuous gradient. We derive sufficient conditions on the origin…
New algorithm solves -norm constrained multilinear logistic regression for tensor data.
problem Non-convex and nonsmooth -norm constraints in multilinear logistic regression.
method APALM method for globally convergent optimization.
result APALM ensures convergence to a first-order critical point.
Convergence of the Stochastic Heavy Ball Method With Approximate Gradients and/or Block Updatingmath.OC
Paper proves SHB convergence with biased gradients and approximate step sizes.
problem Establishing convergence of SHB with biased gradients and approximate step sizes.
method Generalizes SHB convergence conditions for biased gradients, approximate step sizes, and block updating.
result Proves convergence of SHB with new conditions for biased gradients and approximate step sizes.
In this paper, we study the Kurdyka-Łojasiewicz (KL) exponent, an important quantity for analyzing the convergence rate of first-order methods. Specifically, we develop various calculus rules to deduce the KL exponent of new (possibly nonconvex and nonsmooth) functions formed from functions with known KL exponents. In …
DS-GDA solves nonconvex-nonconcave problems without regularity conditions.
problem Nonconvex-nonconcave minimax optimization challenges.
method Doubly smoothed gradient descent ascent method (DS-GDA).
result Achieves convergence on various nonconvex-nonconcave problems.
In this paper, we consider high-dimensional nonconvex square-root-loss regression problems and introduce a proximal majorization-minimization (PMM) algorithm for these problems. Our key idea for making the proposed PMM to be efficient is to develop a sparse semismooth Newton method to solve the corresponding subproblem…
Efficient solver for nonconvex tensor regularization reduces computational cost.
problem Computational inefficiency in extending nonconvex regularization to tensor learning.
method Proximal average algorithm with adaptive momentum, maintaining sparse plus low-rank structure.
result Shows good statistical performance and accuracy on tensor completion problems.
Training deep neural networks (DNNs) efficiently is a challenge due to the associated highly nonconvex optimization. The backpropagation (backprop) algorithm has long been the most widely used algorithm for gradient computation of parameters of DNNs and is used along with gradient descent-type algorithms for this optim…
In this paper, we consider solving a class of nonconvex and nonsmooth problems frequently appearing in signal processing and machine learning research. The traditional alternating direction method of multipliers encounters troubles in both mathematics and computations in solving the nonconvex and nonsmooth subproblem. …
The paper proves a margin inequality for separating hyperplanes, useful for analyzing algorithmic bias.
problem Analyzing the implicit bias of algorithms in machine learning.
method Proves a nonsmooth Kurdyka-Lojasiewicz inequality for margin function.
result The bias of algorithm iterates converges at least as fast as the square-root of the margin convergence rate.
Convergence Analysis of a Momentum Algorithm with Adaptive Step Size for Non Convex Optimizationmath.OC
Although ADAM is a very popular algorithm for optimizing the weights of neural networks, it has been recently shown that it can diverge even in simple convex optimization examples. Several variants of ADAM have been proposed to circumvent this convergence issue. In this work, we study the ADAM algorithm for smooth nonc…
The paper proposes an efficient algorithm for solving Schatten- quasi-norm problems.
problem Finding low-rank solutions of linear inverse problems with Schatten- quasi-norm regularization.
method Dynamic proximal gradient algorithm using Cayley transformation and adaptive step size selection.
result The algorithm converges to a stationary point of the objective function under mild assumptions.
Develops a mean-field theory for multi-head self-attention under cross-entropy training.
problem Mean-field analysis of multi-head self-attention under cross-entropy training.
method Mean-field theory for a simplified single-layer causal multi-head self-attention model.
result Proves a static finite-head approximation bound for the optimal risk.
In this paper we study nonconvex penalization using Bernstein functions whose first-order derivatives are completely monotone. The Bernstein function can induce a class of nonconvex penalty functions for high-dimensional sparse estimation problems. We derive a thresholding function based on the Bernstein penalty and di…
New algorithm for private non-convex optimization with optimal rates.
problem Private optimization of non-convex functions under KL condition.
method Variance-reduced gradient descent and proximal point method.
result Achieves nearly optimal rates for excess empirical risk.
Paper confirms Thom's conjecture for nonlinear evolutions on manifolds.
problem Thom's gradient conjecture for nonlinear evolution equations.
method Extending and settling the conjecture in infinite dimensional problems using Łojasiewicz, L. Simon, and Kurdyka-Mostowski-Parusinski's foundational works.
result Uniqueness of the limiting direction and characterization of convergence rates for both classical and infinite dimensional settings.
Deep learning has aroused extensive attention due to its great empirical success. The efficiency of the block coordinate descent (BCD) methods has been recently demonstrated in deep neural network (DNN) training. However, theoretical studies on their convergence properties are limited due to the highly nonconvex nature…
Demixing Sparse Signals from Nonlinear Observations using Generalized Non-convex Regularizationstat.ML
New method recovers sparse signals from nonlinear observations with robust error bounds.
problem Recovering two sparse vectors from nonlinearly mixed observations with limited data.
method Regularization-based framework combining Huberized data fidelity and generalized folded-concave penalties with a proximal alternating algorithm.
result Estimation error bounds of order at every localized stationary point, with oracle rate under beta-min condition.
Book introduces deep learning methods with math, theory, and applications.
problem Understanding deep learning algorithms and their mathematical foundations.
method Reviews various ANN architectures and optimization methods, covers theoretical aspects.
result Provides a solid mathematical foundation for deep learning.
New method recovers matrices with nonlinear structures using optimization on Grassmann manifold.
problem Recovering high-rank matrices with nonlinear structures like subspaces or clusters.
method Formulated as rank minimization of a nonlinear feature map, approximated by constrained non-convex optimization on the Grassmann manifold, using Riemannian and alternating minimization schemes.
result Global convergence and worst-case complexity bounds for alternating minimization scheme, leading to unique limit point.
Boosted Difference of Convex Functions Algorithm solves VaR constrained portfolio optimization.
problem Designing VaR optimal portfolios under financial regulations.
method Boosted Difference of Convex Functions Algorithm (BDCA) with a novel line search framework.
result BDCA linearly converges to a Karush-Kuhn-Tucker point for VaR constrained portfolio problems.
Asynchronous Delay-Aware Accelerated Proximal Coordinate Descent for Nonconvex Nonsmooth Problemsmath.OC
Nonconvex and nonsmooth problems have recently attracted considerable attention in machine learning. However, developing efficient methods for the nonconvex and nonsmooth optimization problems with certain performance guarantee remains a challenge. Proximal coordinate descent (PCD) has been widely used for solving opti…
Defines smoothness of definable sets in o-minimal structures.
problem Characterizing smoothness of definable sets in o-minimal structures.
method Characterizes smoothness using tangent cones and metric properties.
result Equivalence of several conditions for smoothness of definable sets.
SONATA algorithm converges to solutions of nonconvex smooth functions with KL property.
problem Decentralized optimization over networks with nonconvex smooth functions and convex constraints.
method Decentralized gradient-tracking algorithm SONATA under the KL property.
result SONATA converges to stationary solutions at R-linear rate for , sublinear rate for , and R-linear rate for .
New method improves sampling for weakly log-concave posteriors.
problem Sampling from weakly log-concave posterior distributions.
method Stochastic Langevin Monte Carlo with over-damped diffusion.
result Simulation horizon is with Poisson subsampling.
We consider the problem of minimizing a difference-of-convex (DC) function, which can be written as the sum of a smooth convex function with Lipschitz gradient, a proper closed convex function and a continuous possibly nonsmooth concave function. We refine the convergence analysis in [38] for the proximal DC algorithm …
The great success of deep neural networks is built upon their over-parameterization, which smooths the optimization landscape without degrading the generalization ability. Despite the benefits of over-parameterization, a huge amount of parameters makes deep networks cumbersome in daily life applications. Though techniq…
Generates samples conditioned on labels using optimal transport.
problem Estimating conditional distributions for specific labels.
method Wasserstein geodesic generator based on optimal transport theory.
result Learned conditional distributions and optimal transport maps.
The paper classifies Finsler surfaces satisfying the T-condition or σT-condition.
problem Characterizing Finsler surfaces based on specific tensor conditions.
method Analyzing Finsler surfaces in dimensions n≥3, proving conditions equivalence, and solving PDEs.
result All Finsler surfaces satisfying the T-condition or σT-condition are classified.