SGD converges with positive probability for non-convex deep neural networks under specific conditions.
problem Convergence of SGD for non-convex deep neural networks.
method Established local convergence with positive probability under local Łojasiewicz condition and additional structural assumption.
result SGD converges with positive probability for non-convex deep neural networks under specific conditions.
We analyze the local convergence of proximal splitting algorithms to solve optimization problems that are convex besides a rank constraint. For this, we show conditions under which the proximal operator of a function involving the rank constraint is locally identical to the proximal operator of its convex envelope, hen…
Local Bayesian optimization shows strong performance and converges well, contrary to folklore.
problem Understanding the behavior and convergence of local Bayesian optimization methods.
method Studied the behavior of local optimization strategies and rigorously analyzed a specific algorithm.
result Local Bayesian optimization algorithms converge well and perform strongly, contrary to the folklore.
Local adaptive methods in FL can accelerate convergence but introduce bias, which is corrected.
problem The effect of using adaptive optimization methods for local updates in federated learning.
method Proposed correction techniques to overcome the bias introduced by local adaptive methods.
result Correction techniques can achieve faster convergence and higher test accuracy than baseline methods.
Proves convergence of gradient Ricci shrinkers with uniform bounds.
problem Compactness and energy concentration in gradient Ricci shrinkers.
method Bubble-tree convergence and local energy analysis.
result No energy concentrates in neck regions, leading to a local diffeomorphism finiteness theorem.
Local Gradient Descent with local steps converges to the centralized model in the interpolation regime.
problem Understanding the implicit bias of Local Gradient Descent in the interpolation regime.
method Analyzing the implicit bias of Local Gradient Descent for classification tasks with linearly separable data.
result The aggregated global model from Local-GD converges exactly to the centralized model in the interpolation regime.
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.
We investigate finite-time decoupled convergence in nonlinear two-time-scale stochastic approximation.
problem Achieving decoupled convergence in nonlinear two-time-scale stochastic approximation.
method Nested local linearity assumption, suitable step size selection, convergence analysis of matrix cross term, fourth-order moment convergence rates.
result Finite-time decoupled convergence rates can be achieved in nonlinear two-time-scale stochastic approximation with proper step size selection.
Paper develops a new local convexity condition for non-isolated minima in non-convex optimization.
problem Lack of theory for non-isolated minima in non-convex optimization.
method Formulates a new local convexity condition and studies SGD convergence under this condition.
result Shows SGD can converge locally under the new condition.
In this note we give necessary and sufficient conditions for the validity of the local spectral convergence, in balls, on the RCD∗-setting.
We study three different topologies on the moduli space Hmloc of equivariant isometry classes of m-dimensional locally homogeneous Riemannian spaces. As an application, we provide the first examples of locally homogeneous spaces converging to a limit space in the pointed Ck,α-topolo…
Study local convergence of GDA for training GANs with kernel-based discriminators.
problem Analyzing the local dynamics of GDA for GANs with kernel-based discriminators.
method Linearization of a non-linear dynamical system, under an isolated points model assumption.
result Showed phase transitions indicating convergence, oscillation, or divergence of GDA.
Policy gradient converges linearly with Hadamard parameterization in tabular settings.
problem Convergence of policy gradient methods under Hadamard parameterization.
method Studied convergence rate and established linear convergence after k0 iterations. result Algorithm converges linearly with rate $O( rac{1}{k})$ and faster locally after k0. FedSARSA converges with heterogeneous agents, achieving linear speed-up.
problem Convergence analysis of Federated SARSA with heterogeneous agents.
method Linear function approximation, local training, multi-step error expansion.
result FedSARSA achieves linear speed-up with respect to the number of agents.
Improved Local SGD convergence for general convex objectives with bounded second-order heterogeneity.
problem Understanding when and why Local SGD outperforms alternatives in distributed optimization.
method Established improved convergence guarantees for Local SGD on general convex objectives under bounded second-order heterogeneity.
result Upper bounds for Local SGD are nearly tight, providing a sharper convergence theory.
Arithmetic spaces' thin parts are negligible, impacting Betti numbers.
problem Understanding the structure of arithmetic locally symmetric spaces.
method Analyzing thin parts and deducing asymptotic results on Betti numbers.
result Arithmetic spaces' thin parts are negligible, impacting Betti numbers.
SGD with large learning rates can converge to local maxima.
problem Understanding the behavior of SGD with large learning rates.
method Constructing worst-case optimization problems.
result SGD can converge to local maxima under certain conditions.
Paper analyzes convergence of GDA for nonconvex-nonconcave minimax problems.
problem Understanding convergence of GDA for nonconvex-nonconcave minimax problems.
method Local convergence analysis of GDA with stepsize ratio Θ(κ).
result Stepsize ratio of Θ(κ) is necessary and sufficient for local convergence of GDA to a Stackelberg Equilibrium.
The abstract discusses convergence properties of Lipschitz functions and sets defined by equations.
problem Convergence of Lipschitz functions and sets defined by equations.
method Painlevé-Kuratowski convergence applied to Lipschitz functions and sets defined by equations.
result Generalizations and reverses of classical theorems on convergence of functions and sets.
Stochastic gradient methods are dominant in nonconvex optimization especially for deep models but have low asymptotical convergence due to the fixed smoothness. To address this problem, we propose a simple yet effective method for improving stochastic gradient methods named predictive local smoothness (PLS). First, we …
New insights into continual learning for deep models, showing convergence issues but local linear solutions.
problem Challenges in continual learning for homogeneous deep models.
method Sequential projections onto task margin sets, leveraging nonconvex projection theory.
result Local linear convergence under certain conditions for homogeneous deep networks.
Proves local convergence of various online and recurrent optimization algorithms.
problem Proves local convergence of online and recurrent optimization algorithms not covered by standard stochastic gradient descent theory.
method Uses a general set of assumptions for learning dynamical systems online, adopting an 'ergodic' viewpoint.
result Local convergence results for online and recurrent optimization algorithms, including RMSProp, NoBackTrack, UORO, Adam, and RTRL.
In this note we define a distance between two pointed locally integral current spaces. We prove that a sequence of pointed locally integral current spaces converges with respect to this distance if and only if it converges in the sense of Lang-Wenger. This enables us to state the compactness theorem by Lang-Wenger for …
Matrix completion has attracted much interest in the past decade in machine learning and computer vision. For low-rank promotion in matrix completion, the nuclear norm penalty is convenient due to its convexity but has a bias problem. Recently, various algorithms using nonconvex penalties have been proposed, among whic…
We study the quasi-convergence equivalence of some families of metrics on locally homogeneous closed 4-manifolds with trivial isotropy group, and identify the dimension of each equivalence class under certain conditions.
New convergence bounds for shuffling-based SGD methods in distributed learning.
problem Analyzing the performance of shuffling-based variants of SGD in distributed learning.
method Study of minibatch and local Random Reshuffling methods, proving convergence bounds and lower bounds.
result Shuffling-based variants converge faster than with-replacement sampling methods, and the bounds are tight.
In this paper, the convergence time of federated learning (FL), when deployed over a realistic wireless network, is studied. In particular, a wireless network is considered in which wireless users transmit their local FL models (trained using their locally collected data) to a base station (BS). The BS, acting as a cen…
The study extends convergence theorems for Ricci-limit spaces with bounded curvature.
problem Understanding convergence properties of Ricci-limit spaces with bounded curvature.
method Establishing C1,α-regularities and applying Fukaya's fibration theorem. result Optimal generalization of Fukaya's fibration theorem to C1,α limit spaces. Study homogenizes equations on parallelizable manifolds using tensor localization and periodicity.
problem Homogenizing oscillating linear elliptic equations on parallelizable manifolds.
method Two-scale convergence through localization and periodicity induced by geometry.
result Explicit cell formulae for the homogenization limit and a theory of two-scale convergence of tensors.
Unified analysis for decentralized SGD across various topologies and updates.
problem Analysis of decentralized SGD methods with changing topologies and local updates.
method Unified convergence analysis covering local SGD updates and adaptive network topology.
result Universal convergence rates for smooth problems, interpolating between heterogeneous and iid-data settings.
MSGD outperforms SGD in overparametrized settings with faster convergence rates.
problem Optimization of non-convex functions with momentum.
method Momentum Stochastic Gradient Descent (MSGD) with rigorous analysis.
result MSGD converges exponentially faster than SGD in overparametrized settings.
Gradient descent converges linearly in finite-width networks with positive NTK and compatible conditions.
problem Local convergence of gradient descent in finite-width networks.
method Positive Neural Tangent Kernel (NTK), local Polyak-Łojasiewicz inequality, fixed-step containment in Locally Quasi-Convex Region (LQCR).
result Linear convergence achieved under specific conditions.
AGGLIO optimizes non-convex functions with local convexity guarantees.
problem Optimizing non-convex functions with local convexity.
method Stage-wise, graduated optimization technique for locally convex functions.
result Global convergence to the global optimum for non-convex and locally convex objectives.
Local convergence theory for mildly over-parameterized neural nets.
problem Understanding why over-parameterization works in neural networks.
method Developed a local convergence theory for two-layer neural nets, showing neuron convergence under certain conditions.
result All student neurons converge to one of teacher neurons when the loss is below a threshold.
We study the convergence of the Expectation-Maximization (EM) algorithm for mixtures of linear regressions with an arbitrary number k of components. We show that as long as signal-to-noise ratio (SNR) is Ω~(k), well-initialized EM converges to the true regression parameters. Previous results for k≥3 hav…
Adaptive batch sizes improve local gradient methods in distributed training.
problem Communication bottlenecks in distributed deep learning.
method Adaptive batch size strategies for local gradient methods.
result Adaptive batch sizes reduce minibatch gradient variance and improve training efficiency.
In federated distributed learning, the goal is to optimize a global training objective defined over distributed devices, where the data shard at each device is sampled from a possibly different distribution (a.k.a., heterogeneous or non i.i.d. data samples). In this paper, we generalize the local stochastic and full gr…
Many tasks in modern machine learning can be formulated as finding equilibria in \emph{sequential} games. In particular, two-player zero-sum sequential games, also known as minimax optimization, have received growing interest. It is tempting to apply gradient descent to solve minimax optimization given its popularity a…
FedProx algorithm improved for non-smooth and heterogeneous data.
problem Theoretical understanding of FedProx for non-convex federated optimization.
method Local dissimilarity invariant convergence theory through algorithmic stability.
result Convergence guarantees for non-smooth FL problems and minibatch size.
Locally adaptive federated learning improves convergence in distributed machine learning.
problem Balancing local updates in federated learning leads to slow convergence.
method Locally adaptive federated learning algorithms that use uncoordinated stepsizes based on local geometric information.
result Locally adaptive methods can be particularly efficient in overparameterized settings and outperform standard federated algorithms.
New method uses public data to achieve optimal nonparametric classification with privacy constraints.
problem Optimal nonparametric classification under local differential privacy constraints.
method Locally differentially private classification tree with data-driven pruning.
result Achieves mini-max optimal convergence rate with public data.
Alt-GDA outperforms Sim-GDA in minimax games with near-optimal local convergence.
problem Minimax optimization convergence rate comparison
method Alternating Gradient Descent-Ascent (Alt-GDA) vs. Simultaneous Gradient Descent-Ascent (Sim-GDA)
result Alt-GDA achieves near-optimal local convergence rate for strongly convex-strongly concave problems, while Sim-GDA converges slower.
New insights into optimizing Local SGD's outer optimizer for faster convergence.
problem Understanding the impact of outer optimizer and its hyperparameters in Local SGD.
method Analyzing convergence guarantees with new outer learning rates and momentum.
result Tuning the outer learning rate can improve convergence and handle inner learning rate ill-tuning.
New proof shows local wealth condensation in economic models with biases.
problem Economic models with biases leading to wealth condensation.
method Elementary proof based on properties of wealth distributions.
result Local wealth condensation observed in models with wealth or poverty advantages.
Cyclic coordinate descent identifies models in finite time and converges linearly.
problem Model identification in composite nonsmooth optimization problems.
method Cyclic coordinate descent for a wide class of functions.
result Explicit local linear convergence rates for coordinate descent.
Paper improves a method for fast global and local convergence in optimization.
problem Slow global convergence in optimization methods with noisy Hessian estimates.
method Stochastic Newton Proximal Extragradient method using HPE framework.
result Faster global linear rate and superlinear convergence in fewer iterations.
We announce new results concerning the asymptotic behavior of the Betti numbers of higher rank locally symmetric spaces as their volumes tend to infinity. Our main theorem is a uniform version of the Lück Approximation Theorem \cite{luck}, which is much stronger than the linear upper bounds on Betti numbers given by Gr…
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.