Develops DP-SCD for stochastic coordinate descent, making it differentially private.
problem Privacy leak in auxiliary information during stochastic coordinate descent training.
method Develops DP-SCD, leveraging independent noise addition and decoupling/parallelizing coordinate updates.
result Demonstrates competitive performance against DP-SGD with less tuning.
New method reveals insights about stochastic optimization methods using modified equations.
problem Understanding the qualitative behavior of stochastic optimization algorithms.
method Developed a class of stochastic differential equations to approximate the dynamics of stochastic optimization methods.
result Mean-square stability of the modified equation provides qualitative insights about stochastic coordinate descent.
New algorithms improve stochastic optimization and online learning efficiency.
problem Efficient optimization and online learning algorithms for stochastic problems.
method Accelerated randomized coordinate descent algorithms.
result Significantly less per-iteration complexity and better regret performance.
Paper proves linear convergence of R-FDM and RC-FDM under weak strong convexity.
problem Optimizing SVM dual problem and LASSO problem.
method Randomized feasible descent method (R-FDM) and coordinate-wise random feasible descent method (RC-FDM).
result Both R-FDM and RC-FDM converge linearly under weak strong convexity assumption.
Efficient method solves large-scale saddle point problems with parallel updates.
problem Large-scale convex-concave saddle point problems with separable structure.
method Stochastic parallel block coordinate descent with adaptive primal-dual updates.
result Significantly better performance than state-of-the-art methods in various applications.
New stochastic gradient descent with random search directions improves efficiency and convergence.
problem Efficiency and convergence of stochastic gradient descent methods.
method Developed a new class of stochastic gradient descent algorithms with random search directions.
result Established almost sure convergence and provided Lp rates of convergence. Differentially private random block coordinate descent improves utility in machine learning.
problem Lack of privacy in classical CD methods when handling sensitive information.
method Proposes a differentially private random block coordinate descent method using sketch matrices and importance sampling.
result Demonstrates improved convergence rates and utility guarantees compared to non-private methods.
We propose a new stochastic coordinate descent method for minimizing the sum of convex functions each of which depends on a small number of coordinates only. Our method (APPROX) is simultaneously Accelerated, Parallel and PROXimal; this is the first time such a method is proposed. In the special case when the number of…
Paper improves accelerated coordinate descent by sqrt(n) with non-uniform sampling.
problem Optimization and machine learning problems, especially empirical risk minimization and solving linear systems.
method Non-uniform sampling of coordinates with probability proportional to the square root of their smoothness parameter.
result Improves the best known running time of accelerated coordinate descent by a factor up to sqrt(n).
Stochastic Gradient Descent (SGD) has become popular for solving large scale supervised machine learning optimization problems such as SVM, due to their strong theoretical guarantees. While the closely related Dual Coordinate Ascent (DCA) method has been implemented in various software packages, it has so far lacked go…
We propose and analyze a new parallel coordinate descent method---`NSync---in which at each iteration a random subset of coordinates is updated, in parallel, allowing for the subsets to be chosen non-uniformly. We derive convergence rates under a strong convexity assumption, and comment on how to assign probabilities t…
Proposes blockwise adaptive stepsize for faster training and better generalization in deep learning.
problem Widespread use of coordinate-wise adaptive methods like RMSprop and Adam leads to worse generalization than SGD.
method Splits network parameters into blocks and uses a blockwise adaptive stepsize, balancing adaptivity and generalization.
result Blockwise adaptive gradient descent converges faster and has lower generalization error than coordinate-wise adaptive methods.
New DP-CD method outperforms DP-SGD in solving composite DP-ERM problems.
problem Privacy-preserving machine learning with differential privacy.
method Differentially Private proximal Coordinate Descent (DP-CD) for composite Empirical Risk Minimization (ERM).
result DP-CD outperforms DP-SGD due to larger step sizes and better gradient exploitation.
Stochastic dual coordinate ascent (SDCA) is an effective technique for solving regularized loss minimization problems in machine learning. This paper considers an extension of SDCA under the mini-batch setting that is often used in practice. Our main contribution is to introduce an accelerated mini-batch version of SDC…
Adaptive method solves saddle point problems with separable structure.
problem Solving saddle point problems with separable structure in machine learning.
method Adaptive stochastic primal-dual coordinate descent with mini-batch updates.
result Adaptive stepsize leads to sharper linear convergence rate.
New SGD method uses adaptive sampling to converge faster in non-convex problems.
problem Non-convex optimization problems with noisy gradients.
method Adaptive coordinate sampling in stochastic gradient descent (SGD).
result Almost sure convergence and non-asymptotic bounds established.
Improved DNN training with BCD converging faster than SGD.
problem Training deep neural networks efficiently and accurately.
method Developed a smooth multi-convex formulation and BCD algorithm for training Tikhonov regularized DNNs.
result BCD algorithm converges globally to a stationary point with R-linear rate.
Accelerates coordinate descent methods for machine learning problems.
problem Slowness of coordinate descent methods in machine learning.
method Extrapolation-based accelerated coordinate descent.
result Significant speed-up in practice compared to existing methods.
Paper shows how to use geometric median for robust SGD in high dimensions.
problem Robustifying SGD for high-dimensional optimization problems with gross corruption.
method Applying geometric median to only chosen blocks of coordinates at a time.
result Retains optimal breakdown point of 0.5 for smooth non-convex problems.
Paper proposes an efficient algorithm for learning sparse Bayesian networks from discrete high-dimensional data.
problem Learning sparse structure Bayesian networks from high-dimensional discrete data.
method Score function for sparse DAG, block-wise stochastic coordinate descent with variance reduction.
result The proposed algorithm outperforms existing methods in synthetic data benchmarks.
We develop randomized (block) coordinate descent (CD) methods for linearly constrained convex optimization. Unlike most CD methods, we do not assume the constraints to be separable, but let them be coupled linearly. To our knowledge, ours is the first CD method that allows linear coupling constraints, without making th…
A new method improves coordinate descent by adaptively selecting coordinates.
problem Coordinate descent's inefficiency due to checking all coordinates.
method Adaptive multi-armed bandit algorithm to select coordinates.
result Improves convergence of coordinate descent methods.
Polyak-Łojasiewicz inequality simplifies linear convergence proofs.
problem Proving linear convergence without strong convexity.
method Using Polyak-Łojasiewicz inequality to analyze various optimization methods.
result New analyses and proofs of linear convergence for multiple machine learning problems.
New method reduces variance in random coordinate descent for Langevin Monte Carlo.
problem Efficient sampling from log-concave distributions in high dimensions.
method Introduces RCAD, a variance reduction technique for RCD-LMC.
result RCAD-O-LMC and RCAD-U-LMC converge within the same number of iterations as classical LMC methods, saving computational cost.
New algorithm resists up to half of Byzantine workers in distributed learning.
problem Resilience of distributed SGD in the presence of Byzantine attackers.
method Lipschitz-inspired coordinate-wise median approach (LICM-SGD).
result LICM-SGD can resist up to half of Byzantine workers in non-convex settings.
We present a generic framework for parallel coordinate descent (CD) algorithms that includes, as special cases, the original sequential algorithms Cyclic CD and Stochastic CD, as well as the recent parallel Shotgun algorithm. We introduce two novel parallel algorithms that are also special cases---Thread-Greedy CD and …
A new DP method for deep learning with faster convergence and better privacy.
problem Challenges in differentially private training of deep neural networks.
method Method of auxiliary coordinates with perturbed Taylor expansion for privacy.
result Empirically shows decent trained model quality with modest privacy budget.
Unified analysis of matching pursuit and coordinate descent methods.
problem Optimization of linear spaces using first-order methods.
method Unified analysis of matching pursuit and coordinate descent, providing rates for smooth and strongly convex objectives.
result Unified analysis leading to tightest known rates for steepest coordinate descent and accelerated convergence for matching pursuit.
Uniform sampling of training data has been commonly used in traditional stochastic optimization algorithms such as Proximal Stochastic Gradient Descent (prox-SGD) and Proximal Stochastic Dual Coordinate Ascent (prox-SDCA). Although uniform sampling can guarantee that the sampled stochastic quantity is an unbiased estim…
Distributed block coordinate descent solves large kernel problems.
problem Large scale kernel learning problems.
method Distributed block coordinate descent for kernel regression and classification.
result Nyström method generally achieves better statistical accuracy than random features.
New method improves convergence rates for convex optimization problems.
problem Convex optimization with nonsmooth objectives.
method Randomized coordinate descent with smoothing, acceleration, homotopy, and non-uniform sampling.
result First convergence rate guarantees for coordinate descent methods.
New method improves scalability of SGD for large datasets.
problem High variance in stochastic gradient descent.
method Adaptive measure reduction with Carathéodory's theorem.
result Improved scalability to high-dimensional spaces.
Optimizes CM for stochastic convex optimization with progressive precision.
problem Stochastic nature of objective function in convex optimization.
method Iterative coordinate minimization with optimal precision control.
result Order-optimal regret performance for strongly convex and nonsmooth functions.
SySCD improves SCD scalability and speeds up training.
problem Scalability issues in parallel SCD algorithms.
method Developed a system-aware parallel SCD algorithm (SySCD) to avoid bottlenecks.
result Offers up to x42 speedup compared to state-of-the-art GLM solvers.
Enhances LMC for log-concave sampling, reducing computational cost.
problem High computational cost of LMC for high-dimensional problems.
method Random coordinate descent (RCD) combined with variance reduction techniques (SAGA, SVRG).
result Achieves computational cost reduction compared to classical LMC, same number of iterations as LMC.
Develops an online dual coordinate ascent algorithm for streaming data.
problem Lack of scalability and online adaptability in existing dual coordinate ascent algorithms.
method Introduces an online dual coordinate ascent (O-DCA) algorithm that can handle streaming data without revisiting past data.
result The O-DCA algorithm enables continuous adaptation and learning for online learning scenarios.
This monograph presents the main complexity theorems in convex optimization and their corresponding algorithms. Starting from the fundamental theory of black-box optimization, the material progresses towards recent advances in structural optimization and stochastic optimization. Our presentation of black-box optimizati…
The paper analyzes inexact variants of iterative methods for solving optimization problems.
problem Solving optimization problems with inexact sub-problems.
method Inexact variants of stochastic gradient descent, Newton, proximal point, and subspace ascent methods.
result Iteration complexity results for inexact variants of various iterative methods.
Paper develops accelerated APCD for nonconvex nonsmooth problems with performance guarantees.
problem Efficient methods for nonconvex nonsmooth optimization problems with performance guarantees.
method Asynchronous Accelerated Proximal Coordinate Descent (AAPCD) for nonsmooth and nonconvex problems.
result AAPCD ensures that every limit point is a critical point and achieves linear and sublinear convergence rates.
Coordinate descent algorithms solve optimization problems by minimizing along coordinates.
problem Solving large-scale optimization problems in data science and engineering.
method Solve optimization problems by successively minimizing along each coordinate or coordinate hyperplane.
result Coordinate descent algorithms are effective for parallelized and distributed computing.
Stochastic gradient descent converges to universal limits in high dimensions.
problem Statistical tasks in high dimensions with specific data projections.
method Stochastic gradient descent applied to mixture distributions, proving universality of limits.
result The ODE limits are universal for mixtures of arbitrary product distributions.
New method speeds up optimization over probability measures.
problem High computational overhead in optimizing probability measures.
method Randomized coordinate descent on Wasserstein space.
result Significant speedups over full-gradient methods.
New algorithms connect active learning and stochastic convex optimization.
problem Combining active learning and stochastic convex optimization.
method Developed new algorithms by exploiting theoretical connections.
result Achieved optimal rates for stochastic convex optimization.
Adaptive sampling speeds up coordinate descent methods for optimization.
problem Solving large-scale convex optimization problems efficiently.
method Adaptive importance sampling rules for selecting coordinate updates.
result Improvements over state-of-the-art methods with theoretical and empirical validation.
New algorithm optimizes Bayesian network learning from Gaussian data.
problem Learning Bayesian networks from Gaussian observational data.
method Proposes a coordinate descent algorithm for ℓ0-penalized maximum likelihood estimation. result The algorithm converges to a coordinate-wise minimum and achieves optimal objective value as sample size increases.
New bounds show learning algorithms stable near global minima.
problem Generalization of learning algorithms converging to global minima.
method Black-box stability results based on convergence and loss function geometry.
result Stability of optimization algorithms like SGD, GD, RCD, and SVRG.
A new method uses Coordinate Descent to optimize ResNet networks for private inference.
problem Reducing ReLU count in ResNet networks for private inference.
method Directly optimizing in the discrete domain using Coordinate Descent.
result Our method yields a sparse solution and is state-of-the-art.
Paper introduces robust learning methods using coordinate gradient descent.
problem Supervised learning with corrupted features and labels.
method Coordinate gradient descent combined with robust estimators of partial derivatives.
result Robust learning methods with nearly identical numerical complexity to non-robust ones.