In this paper, we study and analyze the mini-batch version of StochAstic Recursive grAdient algoritHm (SARAH), a method employing the stochastic recursive gradient, for solving empirical loss minimization for the case of nonconvex losses. We provide a sublinear convergence rate (to stationary points) for general noncon…
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 “nonconvex loss”
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 …
Proposes a generalized XGBoost method for nonconvex loss functions.
problem Limited to convex loss functions in XGBoost.
method Extends XGBoost to use nonconvex loss functions and multivariate loss functions.
result Generalized XGBoost method can model multiple parameters in various distributions.
Sign information is the key to overcoming the inevitable saturation error in compressive sensing systems, which causes information loss and results in bias. For sparse signal recovery from saturation, we propose to use a linear loss to improve the effectiveness from existing methods that utilize hard constraints/hinge …
MM for Penalized Estimationstat.CO
The MM algorithm improves robust penalized estimation for outlier-contaminated data.
problem Outliers in data affect the reliability of penalized estimation.
method Innovative MM algorithm for both convex and nonconvex loss functions.
result Established convergence theory for MM algorithm with various loss functions.
The success of deep learning has led to a rising interest in the generalization property of the stochastic gradient descent (SGD) method, and stability is one popular approach to study it. Existing works based on stability have studied nonconvex loss functions, but only considered the generalization error of the SGD in…
Develops a new framework for robust regression with EGM.
problem Addressing robust regression with heavy-tailed noise or outliers.
method Empirical gain maximization (EGM) to approximate noise density.
result Unified analysis of robust regression approaches.
Paper proposes robust tensor regression method for tensor data analysis.
problem Outliers in tensor data analysis can make existing methods sensitive.
method Nonconvex relaxation of tensor tubal rank in optimization framework.
result Global convergence of proposed estimation algorithm under mild assumptions.
This research analyzes the consistency of convex and nonconvex surrogate losses for adversarially robust classification.
problem Ensuring classifiers are robust to adversarial perturbations.
method Analysis of convex and nonconvex surrogate losses through the lens of calibration.
result No convex surrogate loss is calibrated with respect to the adversarial 0-1 loss for linear models, but nonconvex losses can be calibrated under certain conditions.
We demonstrate that the primal-dual witness proof method may be used to establish variable selection consistency and -bounds for sparse regression problems, even when the loss function and/or regularizer are nonconvex. Using this method, we derive two theorems concerning support recovery and -…
Unified SVM algorithm for various losses with fast training.
problem Training SVM models with different convex or nonconvex losses.
method Introducing LS-DC loss, proposing DCA-based UniSVM algorithm.
result Unified algorithm solves SVM models with any convex or nonconvex LS-DC loss efficiently.
Schedule-free SGD is optimal for nonconvex optimization problems.
problem Nonconvex optimization in neural networks.
method Developed a general framework for online-to-nonconvex conversion, which converts schedule-free SGD into an effective nonconvex optimization algorithm.
result Schedule-free SGD achieves optimal iteration complexity for nonsmooth, nonconvex optimization problems.
While many solutions for privacy-preserving convex empirical risk minimization (ERM) have been developed, privacy-preserving nonconvex ERM remains a challenge. We study nonconvex ERM, which takes the form of minimizing a finite-sum of nonconvex loss functions over a training set. We propose a new differentially private…
New research shows many batch selection methods for training work just as well as full batch training.
problem Finding optimal batch selection methods for training.
method Analysis of mini-batch Gradient Descent (GD) and Stochastic GD (SGD) with various batch selection rules.
result All mini-batch schedules, including deterministic ones, generalize optimally for smooth Lipschitz-convex/nonconvex/strongly-convex loss functions.
This paper studies noisy low-rank matrix completion: given partial and noisy entries of a large low-rank matrix, the goal is to estimate the underlying matrix faithfully and efficiently. Arguably one of the most popular paradigms to tackle this problem is convex relaxation, which achieves remarkable efficacy in practic…
We study the error landscape of deep linear and nonlinear neural networks with the squared error loss. Minimizing the loss of a deep linear neural network is a nonconvex problem, and despite recent progress, our understanding of this loss surface is still incomplete. For deep linear networks, we present necessary and s…
Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optimamath.ST
We provide novel theoretical results regarding local optima of regularized -estimators, allowing for nonconvexity in both loss and penalty functions. Under restricted strong convexity on the loss and suitable regularity conditions on the penalty, we prove that \emph{any stationary point} of the composite objective f…
In this paper, the estimation problem for sparse reduced rank regression (SRRR) model is considered. The SRRR model is widely used for dimension reduction and variable selection with applications in signal processing, econometrics, etc. The problem is formulated to minimize the least squares loss with a sparsity-induci…
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…
Apollo improves nonconvex stochastic optimization efficiency.
problem Nonconvex stochastic optimization challenges.
method Adaptive parameter-wise diagonal quasi-Newton method approximating Hessian.
result Significant improvements in convergence speed and generalization over SGD and Adam.
Full-batch GD achieves generalization close to any stationary point with fewer assumptions.
problem Generalization and excess risk bounds for smooth losses, including non-Lipschitz and nonconvex cases.
method Path-dependent analysis of GD's generalization error, focusing on optimization error and stability.
result Generalization error is tightly bound in terms of optimization error and iteration count, bypassing common assumptions.
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…
Covariates-Adjusted Mixed-Membership Estimation: A Novel Network Model with Optimal Guaranteesmath.ST
Novel network model estimates mixed-membership structure with covariate information.
problem Estimating latent mixed-membership structure in networks with covariate information.
method Proposes a novel network model that incorporates both community information and node covariate similarities.
result Achieves optimal estimation accuracy for similarity matrix and mixed-membership.
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.
SGD-trained deep nets have bounds on their generalization error.
problem Bounding generalization error for deep neural networks trained by SGD.
method Combining dynamical control of parameter norms and Rademacher complexity estimates.
result Explicit bounds depend on loss trajectory, work for various architectures.
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 .
New robust loss functions improve matrix completion accuracy.
problem Outliers in data corrupting matrix completion accuracy.
method Developed nonconvex M-estimator functions to down-weight outliers.
result Proposed methods outperform competitors in recovery accuracy and runtime.
Proposes a new loss function for robust learning.
problem Creating a robust loss function for machine learning.
method Extended pseudo Huber loss with log-exp transform and logistic function.
result Linear convergence algorithm for minimizer finding.
Paper improves robust PCA for noisy, outlier, and missing data.
problem Robust PCA with noise, outliers, and missing data.
method Bridging convex and nonconvex optimization.
result Near-optimal statistical accuracy for robust PCA.
Accelerated gradient method tackles nonconvex penalties in sparse learning.
problem Optimizing nonconvex penalties in sparse statistical learning.
method Generalized Nesterov's accelerated gradient method with hyperparameter optimization.
result Convergence can be made considerably faster with optimal hyperparameters.
The loss function of deep networks is known to be non-convex but the precise nature of this nonconvexity is still an active area of research. In this work, we study the loss landscape of deep networks through the eigendecompositions of their Hessian matrix. In particular, we examine how important the negative eigenvalu…
Establishes a condition for multiclass classification-calibration of Gamma-Phi losses.
problem Ensuring classification-calibration of multiclass Gamma-Phi losses.
method Develops a general sufficient condition for classification-calibration of Gamma-Phi losses.
result Proves the first family of nonconvex multiclass surrogate losses for which classification-calibration has been fully justified.
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.
A new method speeds up deep neural network training.
problem Nonconvex optimization in deep neural networks.
method Scaled conjugate gradient method for nonconvex optimization.
result The method converges faster and achieves lower scores in practical applications.
New bounds show faster convergence for learning algorithms.
problem Improving risk bounds for learning algorithms.
method Using algorithmic stability and common assumptions like Polyak-Lojasiewicz condition, smoothness, and Lipschitz continuity.
result Achieves convergence rate of with high probability.
Optimization geometry affects deep learning performance.
problem The impact of optimization geometry on deep learning performance.
method Analysis of pseudogradient methods for learning generalized linear models.
result Non-asymptotic bounds on generalization error characterize model performance.
Improved online learning for hidden-convex losses achieves optimal regret.
problem Adversarial online learning with nonconvex losses that become convex after reparameterization.
method Algorithmic equivalence between OGD and OMD on convex losses, with Hessian compatibility condition.
result OGD achieves regret for hidden-convex losses, matching optimal rate.
Local Linear Convergence of Gradient Methods for Subspace Optimization via Strict Complementaritymath.OC
New method solves subspace optimization problems efficiently.
problem Finding a k-dimensional subspace in high dimensions.
method Local linear convergence of gradient methods under strict complementarity.
result Gradient method converges linearly in high dimensions.
New analysis for black-box learning without gradients, improving generalization bounds.
problem Generalization error analysis for derivative-free optimization.
method Zeroth-order Stochastic Search (ZoSS) algorithm for Lipschitz and smooth losses.
result Generalization bounds independent of model dimension, batch size, and number of perturbed evaluations.
We analyze the performance of alternating minimization for loss functions optimized over two variables, where each variable may be restricted to lie in some potentially nonconvex constraint set. This type of setting arises naturally in high-dimensional statistics and signal processing, where the variables often reflect…
Improved complexity for smooth nonconvex optimization using quasi-Newton methods.
problem Finding ε-first-order stationary points of smooth functions with gradient information only.
method Two-level online learning approach involving quasi-Newton methods.
result Gradient complexity improved to O(d^(1/4)ε^(-13/8)) for d = O(ε^(-1/2)).
We solve ReLU regression with efficient approximations for various distributions.
problem Finding the best fitting ReLU function with square loss from unknown distributions.
method Introduced efficient constant-factor approximation algorithm and polynomial-time approximation scheme.
result First constant-factor approximation algorithm for ReLU regression with weak concentration conditions.
Optimizes nonconvex optimization by converting it to static regret minimization.
problem Nonconvex optimization challenges in machine learning.
method Black-box online-to-nonconvex conversion with static regret minimization oracles.
result Achieves optimal convergence rates for nonconvex optimization.
New method reduces over-parametrization in neural networks, ensuring sparsity and finite network size.
problem Over-parametrization leads to too many active neurons in neural networks, especially with large data.
method Investigates a nonconvex regularization method for shallow ReLU networks.
result Locally optimal networks are finite even with infinite data, maintaining approximation guarantees and network size bounds.
Nonconvex optimization problems such as the ones in training deep neural networks suffer from a phenomenon called saddle point proliferation. This means that there are a vast number of high error saddle points present in the loss function. Second order methods have been tremendously successful and widely adopted in the…
We study theoretical properties of regularized robust M-estimators, applicable when data are drawn from a sparse high-dimensional linear model and contaminated by heavy-tailed distributions and/or outliers in the additive errors and covariates. We first establish a form of local statistical consistency for the penalize…
New algorithm converges to equilibrium in nonconvex-nonconcave optimization problems without dimension dependence.
problem Min-max optimization in nonconvex-nonconcave landscapes.
method Convergent algorithm with greedy max-player updates and proposal distribution for min-player.
result Algorithm converges to equilibrium in non-dependent iterations, suitable for GAN training.
DESTRESS optimizes decentralized nonconvex optimization with optimal IFO complexity and efficient communication.
problem Decentralized nonconvex finite-sum optimization in multi-agent systems.
method DESTRESS uses stochastic recursive gradient updates, gradient tracking, and careful hyper-parameter choices to achieve optimal IFO complexity with efficient communication.
result DESTRESS matches the optimal IFO complexity of centralized algorithms while maintaining communication efficiency.