Gradient descent converges to global minima for ResNets with linearly scaled width.
problem Understanding the convergence of deep residual networks with varying network width and dataset size.
method Analyzing the Jacobian of ResNets and applying gradient descent for quadratic loss.
result Gradient descent converges to global minima for ResNets with linearly scaled width and independent of depth.
Gradient descent converges to perfect classification in neural nets for non-separable data.
problem Classifying linearly non-separable data using neural networks.
method Analysis of gradient descent dynamics in neural networks with sufficient but not large number of neurons.
result Gradient descent converges to global minima with perfect classification in the landscape of minimization problems.
Newton's method converges linearly for stable Hessians, even with approximations.
problem Finding global linear convergence for functions without strong convexity or Lipschitz gradients.
method Global linear convergence of Newton's method for stable Hessians, using approximate Hessians and subproblems.
result Global linear convergence rate for a broad class of functions, superior to first-order methods.
SGD converges to global minimum for certain non-convex functions.
problem Theoretical challenges in optimizing non-convex functions in machine learning.
method Perturbed SGD on a broad class of non-convex functions.
result SGD converges to global minimum for certain non-convex functions.
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.
We propose a simple, scalable, and fast gradient descent algorithm to optimize a nonconvex objective for the rank minimization problem and a closely related family of semidefinite programs. With O ( r 3 κ 2 n log n ) O(r^3 κ^2 n \log n) O ( r 3 κ 2 n log n ) random measurements of a positive semidefinite n × n n \times n n × n matrix of rank r r r and condition number κ κ κ …
New algorithm efficiently computes Wasserstein barycenters for large datasets.
problem Computing Wasserstein barycenters for large sets of discrete distributions.
method Adapted sGS-ADMM to solve dual problem with global convergence and linear rate.
result Global linear convergence rate and efficient solution of subproblems.
Paper proves IRLS converges to subspace from any start, with practical benefits.
problem Robust subspace estimation in machine learning.
method Iteratively Reweighted Least Squares (IRLS) with dynamic smoothing regularization.
result IRLS converges linearly to the underlying subspace from any initialization under deterministic conditions.
Wide neural networks converge linearly to zero loss with feature learning.
problem Optimizing wide neural networks with feature learning guarantees.
method Gradient flow analysis for wide shallow and multi-layer NNs.
result Training loss converges linearly to zero for wide NNs under GF, demonstrating feature learning and better generalization.
Entropy-regularized NPG methods converge linearly in discounted MDPs.
problem Theoretical limitations of NPG methods in reinforcement learning.
method Entropy regularization in conjunction with NPG methods for discounted MDPs.
result Entropy-regularized NPG methods converge linearly in discounted MDPs.
Gradient descent and SGD can converge to max-margin directions in ReLU models.
problem Understanding the implicit bias of gradient methods in ReLU models.
method Characterization of loss function landscape, analysis of GD and SGD convergence, exploration of multi-neuron network learning.
result Gradient descent and SGD can converge to max-margin directions in ReLU models.
We address the rectangular matrix completion problem by lifting the unknown matrix to a positive semidefinite matrix in higher dimension, and optimizing a nonconvex objective over the semidefinite factor using a simple gradient descent scheme. With O ( μ r 2 κ 2 n max ( μ , log n ) ) O( μr^2 κ^2 n \max(μ, \log n)) O ( μ r 2 κ 2 n max ( μ , log n )) random observations of a $n_1 \times n…
Sharp convergence analysis for nonconvex regression models.
problem Nonconvex optimization in regression models with normally distributed covariates.
method Gaussian comparison theorems for analyzing iterative algorithms.
result Sharp global convergence rates for various statistical models.
Stochastic second-order methods converge fast under interpolation conditions.
problem Minimizing smooth and strongly-convex functions efficiently.
method Regularized subsampled Newton method (R-SSN) and stochastic BFGS algorithms.
result R-SSN achieves global linear convergence and quadratic rate in a local neighbourhood.
This paper shows how deep neural networks can learn rich, independent features that significantly deviate from initialization.
problem Understanding how deep neural networks achieve meaningful feature learning and global convergence.
method Investigation of infinitely wide, L L L -layer neural networks using the tensor program framework under Maximal Update parametrization. result SGD enables these networks to learn linearly independent features that substantially deviate from their initial values, capturing relevant data information.
Gradient descent converges linearly for neural networks with specific conditions.
problem Optimizing neural networks with fixed width and depth.
method Local Polyak-Lojasiewicz criterion for gradient flow and descent.
result Gradient descent converges to zero-loss solutions under certain conditions.
Gradient descent converges linearly for deep linear networks under specific conditions.
problem Speed of convergence in gradient descent for deep linear neural networks.
method Analysis of gradient descent training for deep linear neural networks minimizing ℓ 2 \ell_2 ℓ 2 loss. result Gradient descent converges linearly under specific conditions on layer dimensions, initialization, and initial loss.
Accelerated SGD method converges linearly to local minima of nonconvex problems.
problem Nonconvex nonsmooth optimization problems.
method Combining variance reduction and Nesterov's extrapolation for accelerated SGD.
result Linear convergence to a stationary point of the nonconvex optimization problem.
Gradient descent in logistic regression converges to the maximum margin predictor.
problem Convergence and risk of logistic regression parameters.
method Gradient descent applied to logistic regression.
result Gradient descent iterates converge to the maximum margin predictor at a rate of O ( ln ln t / ln t ) \mathcal{O}(\ln\ln t / \ln t) O ( ln ln t / ln t ) . FedAvg converges linearly to global minimum in federated learning with partial participation.
problem Challenges in federated learning with partial client participation.
method Federated averaging (FedAvg) method for over-parameterized neural networks.
result FedAvg converges to global minimum at a linear rate after t iterations.
We study time-like hypersurfaces with vanishing mean curvature in the (3+1) dimensional Minkowski space, which are the hyperbolic counterparts to minimal embeddings of Riemannian manifolds. The catenoid is a stationary solution of the associated Cauchy problem. This solution is linearly unstable, and we show that this …
Paper tackles learning ReLU networks for binary classification with linearly separable data.
problem Learning two-layer ReLU networks for binary classification with linearly separable data.
method Stochastic gradient descent (SGD) algorithm with random noise perturbation.
result Proves global optimality of SGD for training any single-hidden-layer ReLU network.
GD converges faster to flatter minima than gradient flow in shallow networks.
problem Understanding the dynamics of gradient descent in shallow linear networks.
method Analyzing the convergence rate and solution of gradient descent in depth-2 linear neural networks.
result GD converges linearly to flatter minima than gradient flow, even with large step sizes.
Paper proposes a new algorithm combining gradient descent and Langevin dynamics.
problem Gradient descent can get stuck in local minima, while Langevin dynamics can explore but is slow.
method Replica exchange mechanism swaps positions if Langevin yields a lower objective function.
result New algorithm converges to global minimum linearly with high probability.
WSFN overcomes saddle points for non-convex functionals in Wasserstein space.
problem Minimizing non-convex functionals over the Wasserstein space with saddle point avoidance.
method WSFN is a second-order method that preconditions the Wasserstein gradient to avoid saddle points.
result WSFN escapes saddle regions and reaches a global minimizer in polynomial time.
Paper develops methods for non-quadratic loss low-rank matrix recovery.
problem Recovery of low-rank matrices with non-quadratic losses.
method Projected gradient method with a regularity projection oracle.
result Projected gradient method converges globally and linearly.
Gradient descent converges linearly for overparameterized linear networks.
problem Convergence of gradient descent for overparameterized neural networks.
method Local Polyak-Lojasiewicz and Descent Lemma for overparameterized linear models.
result Gradient descent achieves linear convergence for two-layer linear networks under relaxed assumptions.
We analyze the convergence behaviour of a recently proposed algorithm for regularized estimation called Dual Augmented Lagrangian (DAL). Our analysis is based on a new interpretation of DAL as a proximal minimization algorithm. We theoretically show under some conditions that DAL converges super-linearly in a non-asymp…
This paper studies how label noise affects Federated Learning.
problem The impact of label noise on Federated Learning.
method The paper derives an upper bound for the generalization error and conducts experiments on MNIST and CIFAR-10 datasets.
result The global model accuracy decreases linearly with increasing label noise, consistent with theoretical analysis.
Transformers converge linearly to optimal models for Gaussian mixtures classification.
problem Theoretical understanding of transformers' in-context classification.
method Gradient descent training of a single-layer transformer for Gaussian mixtures classification.
result Transformers converge linearly to globally optimal models for Gaussian mixtures classification.
New algorithms improve sampling from complex distributions.
problem Sampling from high-dimensional target distributions with super-linearly growing potentials.
method Proposed aHOLA and aHOLLA algorithms with non-asymptotic convergence bounds.
result Achieved state-of-the-art rates of convergence in non-convex settings.
CD converges linearly for MCP/SCAD penalized least squares.
problem Recovering sparse signals from data.
method Coordinate descent for MCP/SCAD penalized least squares.
result CD converges linearly to solutions of MCP/SCAD penalized least squares.
New method improves convergence for smooth games.
problem Improving convergence for smooth games.
method Stochastic Hamiltonian Gradient Methods (SHGD).
result SHGD converges linearly to the neighbourhood of a stationary point.
Large stepsizes can accelerate gradient descent for logistic regression.
problem Optimizing logistic regression with large stepsizes.
method Gradient descent with large stepsize for ℓ 2 \ell_2 ℓ 2 -regularized logistic regression. result Large stepsizes can achieve O ~ ( κ ) \widetilde{\mathcal{O}}(\sqrtκ) O ( κ ) convergence, improving over O ~ ( κ ) \widetilde{\mathcal{O}}(\sqrtκ) O ( κ ) from classical theory. New BO method optimizes functions efficiently even with unknown hyperparameters.
problem Inaccurate estimation of Gaussian process hyperparameters degrades BO performance.
method Exploits multi-armed bandit and novel training loss function for consistent hyperparameter estimation.
result Sub-linear convergence to global optimum with unknown hyperparameters.
SDCA converges linearly in statistical estimation without strong convexity.
problem Statistical estimation problems not necessarily strongly convex.
method Stochastic dual coordinate (SDCA) without strong convexity assumption.
result SDCA converges linearly under restricted strong convexity conditions.
A new algorithm for optimizing probability distributions converges linearly.
problem Optimizing functionals over families of probability distributions.
method Variational transport: particle-based algorithm approximating Wasserstein gradient descent.
result Variational transport converges linearly to the global minimum of the objective functional.
Orthogonal initialization speeds up convergence in deep linear networks.
problem The impact of initialization on convergence speed and model performance in deep neural networks.
method Analysis of orthogonal initialization in deep linear networks, proving its superiority over Gaussian initialization.
result Orthogonal initialization speeds up convergence relative to Gaussian initialization in deep networks.
Gradient method converges locally linearly for overparameterized Gaussian mixtures.
problem Learning Gaussian mixtures under overparameterization.
method Gradient-based method alternating short descent steps and long Polyak steps.
result Gradient method converges locally linearly to minimizers.
In this paper we generalize the framework of the feasible descent method (FDM) to a randomized (R-FDM) and a coordinate-wise random feasible descent method (RC-FDM) framework. We show that the famous SDCA algorithm for optimizing the SVM dual problem, or the stochastic coordinate descent method for the LASSO problem, f…
ScaledGD accelerates ill-conditioned low-rank estimation.
problem Slow convergence of gradient descent in ill-conditioned problems.
method Scaled gradient descent (ScaledGD) with preconditioning.
result Linear convergence rate independent of condition number.
In this paper we consider the composite self-concordant (CSC) minimization problem, which minimizes the sum of a self-concordant function f f f and a (possibly nonsmooth) proper closed convex function g g g . The CSC minimization is the cornerstone of the path-following interior point methods for solving a broad class of co…
We consider the problem of maximum a posteriori (MAP) inference in discrete graphical models. We present a parallel MAP inference algorithm called Bethe-ADMM based on two ideas: tree-decomposition of the graph and the alternating direction method of multipliers (ADMM). However, unlike the standard ADMM, we use an inexa…
A fully decentralized multi-agent algorithm converges linearly with minimal memory.
problem Efficiently evaluating policies in multi-agent settings with limited exploration.
method Fully decentralized, combining off-policy learning, eligibility traces, and linear function approximation.
result Achieves linear convergence with minimal memory requirements.
Mix2FLD improves FL accuracy with FD, reducing convergence time.
problem Uplink-downlink capacity asymmetry in federated learning.
method Two-way mixup of local samples and model parameters, preserving privacy.
result Achieves up to 16.7% higher test accuracy with reduced convergence time.
In this paper, we study the proximal gradient algorithm with extrapolation for minimizing the sum of a Lipschitz differentiable function and a proper closed convex function. Under the error bound condition used in [19] for analyzing the convergence of the proximal gradient algorithm, we show that there exists a thresho…
A distributed subgradient method tackles non-convex optimization problems in networks.
problem Solving non-convex optimization problems in distributed networks.
method Proposes a distributed stochastic subgradient method (stoDPSM) with theoretical guarantees.
result Global convergence of stoDPSM using Moreau envelope stationarity measure, and linear convergence under sharpness condition.
New algorithm trains ReLU networks via alternating minimization.
problem Training deep neural networks with ReLU activations.
method Alternating minimization of activation patterns and weight updates.
result Proves linear convergence for recovering true parameters.