New algorithms optimize non-smooth, non-convex objectives with improved complexity.
problem Optimizing non-smooth, non-convex stochastic objectives.
method Reduction to online learning, applying optimistic online learning techniques.
result Improved complexity for finding ( δ , ε ) (δ,ε) ( δ , ε ) -stationary points. Generalizes smoothness conditions for optimization methods.
problem Optimization under non-uniform smoothness conditions.
method Develops a new analysis technique for bounding gradients.
result Obtains convergence rates for gradient descent and Nesterov's method.
MARINA-P improves non-smooth federated optimization with adaptive stepsizes.
problem Non-smooth federated optimization in machine learning applications.
method Extends EF21-P and MARINA-P to non-smooth convex setting, proving optimal convergence rate and communication complexity bounds.
result MARINA-P achieves O ( 1 / T ) O(1/\sqrt{T}) O ( 1/ T ) convergence rate and communication complexity matching classical subgradient methods. Paper tackles private optimization for non-smooth objectives efficiently.
problem Private stochastic convex optimization for non-smooth objectives.
method Noisy mirror descent algorithm.
result Achieves optimal rates in statistical complexity and number of queries.
This work speeds up hyperparameter selection for non-smooth convex models using implicit differentiation.
problem Optimizing hyperparameters of non-smooth convex models.
method Implicit differentiation of proximal gradient and coordinate descent methods.
result Implicit differentiation can speed up hyperparameter optimization, especially for non-smooth problems.
New algorithms for differentially private optimization in convex and non-convex settings with near-optimal rates.
problem Differentially private optimization in convex and non-convex settings.
method Developed algorithms for convex and non-convex settings with near-optimal excess population risk.
result Achieved near-optimal rates in near-linear time for convex settings and nearly dimension independent rates for non-convex settings.
This paper improves convergence guarantees for SGD algorithms in non-convex smooth functions.
problem Theoretical convergence properties of SGD algorithms for non-convex smooth functions.
method Analysis of SGD algorithms with arbitrary data ordering for non-convex smooth functions.
result Enhanced convergence guarantees for incremental gradient and single shuffle SGD, improving the optimization term of convergence guarantee.
In statistical learning theory, convex surrogates of the 0-1 loss are highly preferred because of the computational and theoretical virtues that convexity brings in. This is of more importance if we consider smooth surrogates as witnessed by the fact that the smoothness is further beneficial both computationally- by at…
New methods optimize functions on hyperbolic and spherical spaces, matching Euclidean rates up to logarithmic factors.
problem Optimizing functions on non-Euclidean spaces like hyperbolic and spherical geometries.
method Introduced accelerated global first-order methods for L L L -smooth and geodesically convex functions on hyperbolic and spherical spaces. result Achieved the same rates as accelerated gradient descent in Euclidean space, up to logarithmic factors.
Lower bounds for higher-order methods in non-convex optimization.
problem Proving lower bounds for higher-order methods in smooth non-convex finite-sum optimization.
method Analyzing deterministic and randomized algorithms, proposing a new smoothness assumption.
result Proves optimal lower bounds for simulating pth-order regularized methods on the whole function.
Paper analyzes convergence of stochastic methods under heavy-tailed noise.
problem Analyzing convergence of stochastic methods under heavy-tailed noise.
method Investigates vanilla and clipped stochastic subgradient descent methods.
result Demonstrates convergence properties under sub-Weibull and p-BCM noise assumptions.
Optimal private ERM and SCO with subquadratic gradient complexity.
problem Private optimization of non-smooth convex functions.
method Subquadratic gradient complexity algorithm using subsampling and smoothing.
result Achieved optimal excess empirical risk and population loss.
Optimized method tackles convex optimization with heavy-tailed noise.
problem Convex optimization problems with noisy gradients.
method Vanilla stochastic proximal subgradient method without gradient clipping or normalization.
result Achieves optimal complexity for various convex optimization types under heavy-tailed noise.
We consider the fundamental problem in non-convex optimization of efficiently reaching a stationary point. In contrast to the convex case, in the long history of this basic problem, the only known theoretical results on first-order non-convex optimization remain to be full gradient descent that converges in $O(1/\varep…
Improved regret bounds for online convex optimization under stochastic and adversarial settings.
problem Interpolating between stochastic and adversarial online convex optimization.
method Optimistic online mirror descent (OMD) for the Stochastically Extended Adversarial (SEA) model.
result Established new regret bounds for various function classes.
This paper focuses on convex constrained optimization problems, where the solution is subject to a convex inequality constraint. In particular, we aim at challenging problems for which both projection into the constrained domain and a linear optimization under the inequality constraint are time-consuming, which render …
New sampling algorithm for non-smooth potentials.
problem Sampling from non-smooth potentials.
method Proximal algorithm based on rejection sampling.
result Achieves better complexity than existing methods.
A new method solves convex optimization on curved spaces.
problem Optimization on curved spaces with non-smooth functions.
method Convex bundle method on Riemannian manifolds.
result The method converges to a minimizer under mild conditions.
We establish linear regret bounds for convex smooth losses using Fenchel-Young losses.
problem Establishing linear regret bounds for convex smooth losses.
method Constructing a convex smooth surrogate loss using Fenchel-Young losses generated by the convolutional negentropy.
result We derive a smooth loss with a linear surrogate regret bound.
New SPS variant improves non-smooth optimization without small gradients.
problem Improving non-smooth optimization without small gradients.
method Safeguarded Stochastic Polyak Step Size (SPS s a f e _{safe} s a f e ) for non-smooth optimization. result Rigorous convergence guarantees for non-smooth convex optimization without strong assumptions.
Unified analysis of stochastic gradient methods for convex and smooth optimization.
problem Minimizing composite convex and smooth functions.
method Unified convergence analysis of various stochastic gradient methods.
result Unified convergence rates for a variety of methods including proximal SGD, variance reduced methods, quantization, and coordinate descent.
Improved optimization technique reduces training complexity for non-convex problems.
problem Training non-convex optimization problems with exploding gradients.
method Employed variance reduction technique (SPIDER) with carefully designed learning rate.
result Improved stochastic gradient complexity to O ( ε − 3 ) O(ε^{-3}) O ( ε − 3 ) for ε ε ε -stationary solutions. Paper introduces a new G ⋆ G^\star G ⋆ regret measure for online convex optimization with smooth losses.
problem Online convex optimization with smooth losses.
method Introduces a new G ⋆ G^\star G ⋆ regret measure that depends on the cumulative squared gradient norm. result The G ⋆ G^\star G ⋆ regret can be arbitrarily sharper than existing measures when losses have vanishing curvature. This work accelerates gradient descent with anytime convergence guarantees.
problem Improving the convergence rate of gradient descent methods.
method Proposes a stepsize schedule for gradient descent that achieves anytime convergence rates.
result Gradient descent can achieve convergence rates of O ( T − 1.119 ) O(T^{-1.119}) O ( T − 1.119 ) for any stopping time T T T . Expanding FCCO to non-smooth weakly-convex problems, improving deep learning performance.
problem Addressing the limitations of current FCCO methods by tackling non-smooth weakly-convex problems.
method Developed a single-loop algorithm for non-smooth weakly-convex FCCO and extended it to tri-level problems.
result Established the complexity for finding ε-stationary points in the Moreau envelop of the objective function.
The paper proves optimal smoothness for certain Lagrangian graphs with specific Hölder continuity.
problem Optimal regularity for Hölder continuous Hamiltonian stationary Lagrangian graphs.
method Establishing smoothness conditions based on Hölder exponent and Lagrangian phase properties.
result Smoothness of graphs is achieved when Hölder exponent is strictly greater than 1/3 and Lagrangian phase is supercritical.
Finding efficient and provable methods to solve non-convex optimization problems is an outstanding challenge in machine learning and optimization theory. A popular approach used to tackle non-convex problems is to use convex relaxation techniques to find a convex surrogate for the problem. Unfortunately, convex relaxat…
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.
This paper optimizes functions of probability measures using particle gradient descent for displacement convex functions.
problem Optimizing functions of probability measures with displacement convex properties.
method Particle gradient descent applied to displacement convex functions with theoretical guarantees.
result Finite number of particles and computations are sufficient to find optimal solutions for displacement convex functions.
New algorithms optimize convex functions with high-order derivatives.
problem Optimizing convex functions with high-order derivatives under various norms.
method Developed a non-Euclidean inexact accelerated proximal point method using an inexact uniformly convex regularizer.
result Showed nearly optimal algorithms for high dimensions in the black-box oracle model for ℓ p \ell_p ℓ p -settings and all q ≥ 1 q \geq 1 q ≥ 1 . New algorithms ensure reproducibility and optimal convergence in convex optimization.
problem Trade-off between reproducibility and convergence rate in convex optimization.
method Regularization-based algorithms for smooth convex minimization and minimax optimization.
result Achieves optimal reproducibility and near-optimal gradient complexity for various oracle settings.
Estimates convex hulls of smooth function images with error bounds.
problem Estimating the convex hull of the image of a smooth boundary set.
method Using submersion properties and sampling inputs, derive bounds on Hausdorff distance.
result New tighter and more general error bounds for geometric inference.
This paper analyzes saddle points and minimax points in non-convex smooth games.
problem Understanding local optimal points in non-convex smooth games.
method Comprehensive analysis of local minimax points, including their optimality conditions and stability.
result Local saddle points are uniformly local minimax points under mild continuity assumptions.
State-of-the-art methods in convex and non-convex optimization employ higher-order derivative information, either implicitly or explicitly. We explore the limitations of higher-order optimization and prove that even for convex optimization, a polynomial dependence on the approximation guarantee and higher-order smoothn…
We study dual-based algorithms for distributed convex optimization problems over networks, where the objective is to minimize a sum ∑ i = 1 m f i ( z ) \sum_{i=1}^{m}f_i(z) ∑ i = 1 m f i ( z ) of functions over in a network. We provide complexity bounds for four different cases, namely: each function f i f_i f i is strongly convex and smooth, each function is ei…
Interesting theoretical associations have been established by recent papers between the fields of active learning and stochastic convex optimization due to the common role of feedback in sequential querying mechanisms. In this paper, we continue this thread in two parts by exploiting these relations for the first time …
We investigate the theoretical limits of pipeline parallel learning of deep learning architectures, a distributed setup in which the computation is distributed per layer instead of per example. For smooth convex and non-convex objective functions, we provide matching lower and upper complexity bounds and show that a na…
In this paper we study the differentially private Empirical Risk Minimization (ERM) problem in different settings. For smooth (strongly) convex loss function with or without (non)-smooth regularization, we give algorithms that achieve either optimal or near optimal utility bounds with less gradient complexity compared …
New method solves complex optimization problems faster.
problem Minimizing a convex smooth objective over the optimal solution set of another convex smooth problem.
method Uses a cutting plane approach to approximate the lower-level problem and an accelerated gradient method to update the upper-level objective.
result Shows that the method requires at most O ( max { 1 / ε f , 1 / ε g } ) \mathcal{O}(\max\{1/\sqrt{ε_{f}}, 1/ε_g\}) O ( max { 1/ ε f , 1/ ε g }) iterations to achieve ε f ε_f ε f -suboptimality and ε g ε_g ε g -infeasibility. New algorithm solves complex optimization problems efficiently.
problem Minimizing convex upper-level functions over optimal lower-level solutions.
method Reformulates bilevel problems into functionally constrained problems, achieving near-optimal rates.
result Achieves near-optimal rates for both smooth and nonsmooth problems.
A new algorithm speeds up convex clustering.
problem Optimizing clustering with convex optimization and avoiding local minima.
method Smoothing proximal gradient algorithm (Sproga) for convex clustering.
result Sproga is faster and uses less memory than existing methods.
Step decay schedules improve convergence in non-convex optimization.
problem Improving convergence in non-convex optimization problems.
method Analyzing convergence rates of step decay schedules in non-convex, convex, and strongly convex problems.
result Step decay schedules achieve O ( ln T / T ) \mathcal{O}(\ln T/\sqrt{T}) O ( ln T / T ) convergence rates in various optimization scenarios. We propose an adaptive smoothing algorithm based on Nesterov's smoothing technique in \cite{Nesterov2005c} for solving "fully" nonsmooth composite convex optimization problems. Our method combines both Nesterov's accelerated proximal gradient scheme and a new homotopy strategy for smoothness parameter. By an appropriat…
New algorithms achieve optimal robustness in stochastic convex optimization under contamination.
problem Determining optimal rates for robust stochastic convex optimization under ε ε ε -contamination. method Developed novel algorithms achieving minimax-optimal excess risk under ε ε ε -contamination model without stringent assumptions. result Achieved minimax-optimal excess risk (up to logarithmic factors) under ε ε ε -contamination model. Two new algorithms optimize decentralized convex optimization with reduced communication rounds.
problem Decentralized minimization of smooth strongly convex functions in a network.
method Proposes two new algorithms based on accelerated Forward Backward methods.
result First algorithm is optimal in terms of communication rounds and gradient computations.
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 O ( T ) \mathcal{O}(\sqrt{T}) O ( T ) regret for hidden-convex losses, matching optimal rate. New method turns optimization algorithms into uniformly stable learning algorithms for non-Euclidean norms.
problem Non-Euclidean norms in binary classification problems.
method Black-box reduction method using uniformly convex regularizers.
result Achieves optimal statistical risk bounds on excess risk for non-Euclidean norms.
We consider the problem of finding local minimizers in non-convex and non-smooth optimization. Under the assumption of strict saddle points, positive results have been derived for first-order methods. We present the first known results for the non-smooth case, which requires different analysis and a different algorithm…