In this work we consider the stochastic minimization of nonsmooth convex loss functions, a central problem in machine learning. We propose a novel algorithm called Accelerated Nonsmooth Stochastic Gradient Descent (ANSGD), which exploits the structure of common nonsmooth loss functions to achieve optimal convergence ra…
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,657 papers · 148 categories
Trend · papers per month
48 results for “nonsmooth loss function”
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…
New stability bounds for SGD on nonsmooth convex losses.
problem Understanding stability of SGD on nonsmooth convex losses.
method Sharp upper and lower bounds for SGD and full-batch GD on nonsmooth convex losses.
result SGD can be less stable but still useful for generalization bounds.
Develops a fast algorithm for high-dimensional LASSO penalized quantile regression.
problem Computational challenges in high-dimensional penalized quantile regression.
method Pathwise coordinate descent algorithm to solve exact coordinatewise minimum of the nonsmooth loss function.
result Algorithm runs faster than existing alternatives and maintains estimation accuracy.
Efficient Distributed Learning over Decentralized Networks with Convoluted Support Vector Machinestat.ML
Paper tackles efficient SVM classification over decentralized networks.
problem Efficiently classifying high-dimensional data over decentralized networks.
method Convolution-based smoothing technique for nonsmooth hinge loss function, combined with an efficient ADMM algorithm.
result Provable linear convergence of the ADMM algorithm and near-optimal statistical convergence of the sparse estimator.
New solver for MKL-SVM with 0/1 loss function.
problem Optimizing MKL-SVM with -loss function.
method Developed an ADMM solver for nonconvex, nonsmooth optimization.
result Shows promise in simple numerical experiment.
The flare Package for High Dimensional Linear Regression and Precision Matrix Estimation in Rstat.ML
A new R package for high-dimensional regression and precision matrix estimation.
problem High-dimensional linear regression and precision matrix estimation challenges.
method flare package implements various regression methods and extensions for sparse precision matrix estimation.
result The flare package is efficient and scalable for large problems.
Paper introduces privacy-preserving inventory policy learning for feature-based newsvendor with unknown demand.
problem Privacy-preserving inventory policy learning for feature-based newsvendor with unknown demand distribution and nonsmooth loss function.
method Developed a clipped noisy gradient descent algorithm based on convolution smoothing for optimal inventory estimation within f-differential privacy framework.
result Achieved privacy-preserving optimal inventory policy with provable privacy guarantees and desirable statistical precision.
Nonsmooth High-Order Averaging Theory with Application to Extremum Seeking Optimization and Controlmath.OC
New theory for nonsmooth systems helps optimize and control complex functions.
problem Optimizing and controlling systems with nonsmooth functions.
method Higher-order averaging theory with nonsmooth near-identity transformation and lexicographic differentiation.
result Closed formula for nonsmooth first and second-order averaging.
We study the performance of a family of randomized parallel coordinate descent methods for minimizing the sum of a nonsmooth and separable convex functions. The problem class includes as a special case L1-regularized L1 regression and the minimization of the exponential loss ("AdaBoost problem"). We assume the input da…
The Strength of Nesterov's Extrapolation in the Individual Convergence of Nonsmooth Optimizationcs.LG
Nesterov's extrapolation improves convergence in nonsmooth optimization.
problem Improving convergence rate in nonsmooth convex optimization.
method Nesterov's extrapolation applied to projected subgradient methods.
result Nesterov's extrapolation optimizes individual convergence for nonsmooth problems.
In regularized risk minimization, the associated optimization problem becomes particularly difficult when both the loss and regularizer are nonsmooth. Existing approaches either have slow or unclear convergence properties, are restricted to limited problem subclasses, or require careful setting of a smoothing parameter…
We introduce a class of quadratic support (QS) functions, many of which play a crucial role in a variety of applications, including machine learning, robust statistical inference, sparsity promotion, and Kalman smoothing. Well known examples include the l2, Huber, l1 and Vapnik losses. We build on a dual representation…
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.
MKL--SVMstat.ML
Paper introduces MKL--SVM for SVM with loss.
problem Optimization of SVM with loss function.
method MKL framework combined with ADMM algorithm for solving the optimization problem.
result Performance of MKL--SVM comparable to SimpleMKL.
Study compares nonsmooth spaces with integrable Ricci bounds.
problem Comparing geometric and functional inequalities on nonsmooth spaces.
method Localization method and one-dimensional comparison estimates.
result Extension of comparison principles to nonsmooth settings.
We analyze stochastic algorithms for optimizing nonconvex, nonsmooth finite-sum problems, where the nonconvex part is smooth and the nonsmooth part is convex. Surprisingly, unlike the smooth case, our knowledge of this fundamental problem is very limited. For example, it is not known whether the proximal stochastic gra…
Regularity results for geodesic X-ray transform on nonsmooth manifolds
problem Geodesic X-ray transform on nonsmooth simple manifolds
method Symbol smoothing arguments and pseudodifferential operators with low regularity symbols
result Improved injectivity results for functions
Analysis of Generalized Bregman Surrogate Algorithms for Nonsmooth Nonconvex Statistical Learningmath.OC
Paper develops algorithms for nonsmooth, nonconvex statistical learning problems.
problem Nonsmooth and nonconvex objectives in statistical learning.
method Bregman-surrogate algorithm framework, including local linear approximation, mirror descent, iterative thresholding, DC programming.
result Global convergence rates for nonconvex and nonsmooth objectives in high dimensions.
New Langevin Monte Carlo algorithms for sampling from nonsmooth distributions.
problem Sampling from distributions with nonsmooth convex composite potentials.
method Leveraging Bregman--Moreau envelopes and proximal operators in mirror descent.
result Efficiency in sampling from nonsmooth distributions, extending existing methods.
We consider a class of nonconvex nonsmooth optimization problems whose objective is the sum of a smooth function and a finite number of nonnegative proper closed possibly nonsmooth functions (whose proximal mappings are easy to compute), some of which are further composed with linear maps. This kind of problems arises …
New methods help escape strict saddle points in nonsmooth optimization.
problem Escaping strict saddle points in nonsmooth optimization.
method An inexact stochastically perturbed gradient method applied to the Moreau envelope.
result A variety of algorithms for nonsmooth optimization can efficiently escape strict saddle points of the Moreau envelope.
We present a stochastic setting for optimization problems with nonsmooth convex separable objective functions over linear equality constraints. To solve such problems, we propose a stochastic Alternating Direction Method of Multipliers (ADMM) algorithm. Our algorithm applies to a more general class of nonsmooth convex …
KL property of exponent of -norm and DC regularized factorizations for low-rank matrix recoverymath.OC
This paper is concerned with the factorization form of the rank regularized loss minimization problem. To cater for the scenario in which only a coarse estimation is available for the rank of the true matrix, an -norm regularized term is added to the factored loss function to reduce the rank adaptively; and…
Stochastic Subgradient Methods with Guaranteed Global Stability in Nonsmooth Nonconvex Optimizationmath.OC
The paper guarantees global stability for stochastic subgradient methods in nonsmooth nonconvex optimization.
problem Minimizing nonsmooth nonconvex functions with convergence guarantees.
method Developed a framework for stochastic subgradient methods with global stability guarantees.
result Iterates are uniformly bounded and asymptotically stabilize around the stable set of the differential inclusion.
We extend the well-known BFGS quasi-Newton method and its memory-limited variant LBFGS to the optimization of nonsmooth convex objectives. This is done in a rigorous fashion by generalizing three components of BFGS to subdifferentials: the local quadratic model, the identification of a descent direction, and the Wolfe …
Paper develops privacy-preserving federated learning for nonsmooth objectives.
problem Solving nonsmooth objective functions in a privacy-preserving manner.
method Zero-concentrated differential privacy (zCDP) with Gaussian noise, distributed ADMM, and approximation of augmented Lagrangian.
result The algorithm achieves a competitive privacy-accuracy trade-off and converges to the exact solution.
Sign-RIP improves robust low-rank matrix recovery by preserving norms even with corrupted measurements.
problem Robust low-rank matrix recovery in the presence of corrupted measurements.
method Proposed Sign-RIP, a robust restricted isometry property.
result Sign-RIP guarantees uniform convergence of subdifferentials in robust low-rank matrix recovery.
Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimizationmath.OC
Improved shuffling gradient methods converge faster for nonsmooth convex optimization.
problem Improving convergence rates for nonsmooth convex optimization problems.
method Analysis of shuffling gradient methods, focusing on Random Reshuffle and Single Shuffle strategies.
result Shuffling gradient methods, particularly Random Reshuffle and Single Shuffle, converge faster than Proximal Gradient Descent for nonsmooth convex optimization.
We study the phase retrieval problem, which solves quadratic system of equations, i.e., recovers a vector from its magnitude measurements . We develop a gradient-like algorithm (referred to as RWF representing reshaped W…
Develops a mathematical model for automatic differentiation in machine learning.
problem Current automatic differentiation lacks a simple mathematical model for machine learning.
method Articulates relationships between program differentiation and nonsmooth functions, provides a class of functions and nonsmooth calculus.
result Shows how nonsmooth calculus applies to stochastic approximation methods and evidence of artificial critical points.
With the large rising of complex data, the nonconvex models such as nonconvex loss function and nonconvex regularizer are widely used in machine learning and pattern recognition. In this paper, we propose a class of mini-batch stochastic ADMMs (alternating direction method of multipliers) for solving large-scale noncon…
Riemannian Stochastic Proximal Gradient Methods for Nonsmooth Optimization over the Stiefel Manifoldmath.OC
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.
We consider in this paper a class of composite optimization problems whose objective function is given by the summation of a general smooth and nonsmooth component, together with a relatively simple nonsmooth term. We present a new class of first-order methods, namely the gradient sliding algorithms, which can skip the…
In this paper, we consider the problem of minimizing the average of a large number of nonsmooth and convex functions. Such problems often arise in typical machine learning problems as empirical risk minimization, but are computationally very challenging. We develop and analyze a new algorithm that achieves robust linea…
New method solves nonsmooth low-rank matrix optimization problems efficiently.
problem Nonsmooth and low-rank matrix optimization problems in statistics and machine learning.
method Low-rank Extragradient Method with warm-start initialization.
result The extragradient method converges to an optimal solution with rate and requires only two low-rank SVDs per iteration.
New algorithm for fast nonsmooth optimization with applications in image processing and machine learning.
problem Minimizing the sum of three convex functions with specific properties.
method PDDY algorithm, based on Davis-Yin splitting in a primal-dual product space.
result Sublinear and linear convergence rates in various scenarios, including strong convexity.
Frank-Wolfe methods (FW) have gained significant interest in the machine learning community due to its ability to efficiently solve large problems that admit a sparse structure (e.g. sparse vectors and low-rank matrices). However the performance of the existing FW method hinges on the quality of the linear approximatio…
Study on numerical reliability of AD for MaxPool in neural nets.
problem Reliability of automatic differentiation for nonsmooth operations like MaxPool.
method Investigation across precision levels and architectures on various datasets.
result Lower norms of nonsmooth Jacobians help maintain stable learning.
We introduce a proximal subdifferential and develop a calculus for nonsmooth functions defined on any Riemannian manifold . We give several applications of this theory, concerning: 1) differentiability and geometrical properties of the distance function to a closed subset of ; 2) solvability and implicit func…
Improved DP optimization for nonconvex, nonsmooth objectives with reduced sample complexity.
problem Differentially private optimization of nonconvex, nonsmooth objectives.
method Proposes single-pass and multi-pass DP algorithms with improved sample complexity.
result Sample complexity bounds improved by factors of and .
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 use of convex regularizers allows for easy optimization, though they often produce biased estimation and inferior prediction performance. Recently, nonconvex regularizers have attracted a lot of attention and outperformed convex ones. However, the resultant optimization problem is much harder. In this paper, for a …
This paper concerns dictionary learning, i.e., sparse coding, a fundamental representation learning problem. We show that a subgradient descent algorithm, with random initialization, can provably recover orthogonal dictionaries on a natural nonsmooth, nonconvex minimization formulation of the problem, under mi…
We study the dual formulation of the utility maximization problem in incomplete markets when the utility function is finitely valued on the whole real line. We extend the existing results in this literature in two directions. First, we allow for nonsmooth utility functions, so as to include the shortfall minimization p…
Unified Lagrangian-based methods for nonsmooth nonconvex optimization.
problem Minimizing nonsmooth nonconvex functions with constraints.
method Developed a unified framework for Lagrangian-based methods using subgradient updates.
result Global convergence guarantees for the proposed framework under mild conditions.
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…
Study on Adam-family methods for nonsmooth optimization with convergence guarantees.
problem Training nonsmooth neural networks with convergence guarantees.
method Two-timescale updating scheme and stochastic subgradient methods with gradient clipping.
result Convergence guarantees for various Adam-family methods in training nonsmooth neural networks.