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. New algorithm POO optimizes noisy, unknown-smooth functions.
problem Optimizing functions with unknown smoothness and noisy evaluations.
method Adaptive optimization algorithm POO.
result POO performs nearly as well as known algorithms with smoothness knowledge, and works for broader classes of functions.
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. New algorithm solves federated minimax optimization problems.
problem Federated minimax optimization challenges.
method Federated Stochastic Smoothed Gradient Descent Ascent (FESS-GDA).
result FESS-GDA uniformly solves federated minimax problems.
Smooth activations enable optimal error rates in neural networks for Sobolev function classes.
problem Achieving optimal approximation and estimation error rates for neural networks in Sobolev function classes.
method Study of neural networks with smooth activations, proving optimal rates via approximation and statistical properties.
result Constant-depth networks with smooth activations achieve optimal rates of approximation and estimation, demonstrating smoothness adaptivity.
We analyze convergence rates of stochastic optimization procedures for non-smooth convex optimization problems. By combining randomized smoothing techniques with accelerated gradient methods, we obtain convergence rates of stochastic optimization procedures, both in expectation and with high probability, that have opti…
Smoothed fitness landscape improves protein optimization.
problem Infeasibility of combinatorially large protein sequence space.
method Formulate protein fitness as a graph signal, smooth using Tikunov regularization, and optimize with Gibbs sampling.
result 2.5 fold fitness improvement over training set.
We provide improved convergence rates for various \emph{non-smooth} optimization problems via higher-order accelerated methods. In the case of ℓ ∞ \ell_\infty ℓ ∞ regression, we achieves an O ( ε − 4 / 5 ) O(ε^{-4/5}) O ( ε − 4/5 ) iteration complexity, breaking the O ( ε − 1 ) O(ε^{-1}) O ( ε − 1 ) barrier so far present for previous methods. We arrive at a similar rate fo…
Paper proposes ZO-SMD for MERO, achieving optimal convergence rates.
problem Minimizing excess risk across all test distributions.
method Zeroth-order stochastic mirror descent algorithm for both smooth and non-smooth MERO.
result Converges at optimal rates of O ( 1 / t ) \mathcal{O}(1/\sqrt{t}) O ( 1/ t ) for estimates and optimization errors. The paper explores various stationarity concepts in non-smooth optimization.
problem Understanding stationarity in non-smooth optimization problems.
method Introduction and discussion of different stationarity concepts for non-convex non-smooth functions.
result Clarification of the relationship among different stationarity concepts and their relevance in iterative methods.
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.
A new shape space allows optimization of non-smooth shapes in fluid mechanics.
problem Optimizing non-smooth shapes in fluid mechanics.
method Constructing a product manifold to include piecewise-smooth shapes.
result Numerical results show applicability in minimizing viscous energy dissipation.
AdaGrad fails to adapt to Hölder-smoothness in composite optimization problems.
problem AdaGrad's convergence rate is suboptimal for composite objectives.
method Exhibited a simple one-dimensional convex problem to highlight AdaGrad's limitations.
result AdaGrad does not achieve the classical convergence rate for Hölder-smooth objectives.
Paper improves stochastic bilevel optimization methods for highly-smooth problems.
problem Finding ε ε ε -stationary points in stochastic bilevel optimization. method Proposes F 2 {}^2 2 SA- p p p methods using p p p th-order finite differences for hyper-gradient approximation. result Achieves upper complexity bound of i l d e O ( p ε − 4 − p / 2 ) ilde{\mathcal{O}}(p ε^{-4-p/2}) i l d e O ( p ε − 4 − p /2 ) for p p p th-order smooth problems. New method smooths optimization for sparse regularization.
problem Non-smooth, non-convex optimization problems for sparsity.
method Overparameterization and smooth surrogate penalties.
result Surrogate objective has identical global and local minima.
SWEEN improves certified robustness via weighted ensembling of smoothed classifiers.
problem Finding optimal base classifiers for randomized smoothing.
method Smoothed WEighted ENsembling (SWEEN) scheme.
result SWEEN achieves optimal certified robustness under mild assumptions.
New algorithm tackles nonconvex machine learning problems with adaptive normalization and independent sampling.
problem Nonconvex machine learning problems with generalized-smoothness.
method Adaptive gradient normalization, independent sampling, and gradient clipping.
result Achieves an O(ε^(-4)) sample complexity for fast convergence.
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.
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.
Stochastic Gradient Descent (SGD) is one of the simplest and most popular stochastic optimization methods. While it has already been theoretically studied for decades, the classical analysis usually required non-trivial smoothness assumptions, which do not apply to many modern applications of SGD with non-smooth object…
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…
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 …
Adaptive data fusion boosts efficiency in multi-task optimization.
problem Multi-task non-smooth optimization in various fields.
method Adaptive data fusion approach leveraging commonalities among objectives.
result Significant improvements in sample efficiency with sharp statistical guarantees.
Optimal smooth subspaces approximate large data sets efficiently.
problem Approximating large data sets with invariant subspaces.
method Smooth functions under lattice translations or crystallographic groups, with optimal selection of Paley-Wiener space.
result Optimal lattice selection enhances approximation efficiency.
This paper investigates the question of which smooth compact 4-manifolds admit Riemannian metrics that minimize the L2-norm of the curvature tensor. Metrics with this property are called OPTIMAL; Einstein metrics and scalar-flat anti-self-dual metrics provide us with two interesting classes of examples. Using twistor m…
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.
New methods improve online matrix optimization with reduced computational cost.
problem Online matrix optimization with operator norm constraints.
method Gradient-based prediction scheme with smoothed potentials for nuclear norm.
result Adaptive matrix optimizers match Shampoo's regret up to a constant factor.
LSAM optimizes deep learning training with improved efficiency.
problem Inefficiency in distributed large-batch training with Sharpness-Aware Minimization (SAM).
method Integrates SAM's adversarial steps with an asynchronous distributed sampling strategy.
result Higher final accuracy compared to data-parallel SAM.
Advances smooth over-parameterization for solving non-smooth optimization problems.
problem Non-smooth optimization with structural constraints in imaging and machine learning.
method Smooth over-parameterization of non-smooth problems, using gradient descent and mirror descent.
result Gradient descent on the reformulated smooth problem converges efficiently without parameter tuning.
Some methods based on simple regularizing geometric element transformations have heuristically been shown to give runtime efficient and quality effective smoothing algorithms for meshes. We describe the mathematical framework and a systematic approach to global optimization-based versions of such methods for mixed volu…
Smoothness analysis of adversarial training reveals L ∞ L_\infty L ∞ constraints cause more non-smoothness.
problem Non-smoothness of adversarial training loss function.
method Analyzed the smoothness of adversarial training loss function using optimal attacks for model parameters.
result The L ∞ L_\infty L ∞ constraint causes more non-smoothness than L 2 L_2 L 2 constraint. This research optimizes Andrews plots for better visual clarity in high-dimensional data.
problem Visualizing high-dimensional datasets with clarity and aesthetics.
method Developed a method to add spectral smoothing to Andrews plots to reduce visual clutter.
result Optimal spatial-spectral smoothing leads to more aesthetically pleasing and clutter-free visualizations.
Robust learning method combines kernel smoothing and robust optimization.
problem Certifying robustness against distribution shifts in machine learning models.
method Adapting integral operator using supremal convolution for robustness, leveraging optimal transport.
result The method provides theoretical guarantees for certified robustness and competitive performance.
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. New algorithm for differentially private distributed optimization of smooth, non-convex problems.
problem No differentially private distributed method for smooth, non-convex optimization problems.
method Smoothed normalization integrated with an error-feedback mechanism.
result Achieves superior convergence rate and first differentially private distributed optimization algorithm with provable convergence guarantees.
The (global) Lipschitz smoothness condition is crucial in establishing the convergence theory for most optimization methods. Unfortunately, most machine learning and signal processing problems are not Lipschitz smooth. This motivates us to generalize the concept of Lipschitz smoothness condition to the relative smoothn…
NSGD-M optimizes machine learning models without hyperparameter tuning, even under relaxed smoothness.
problem Training machine learning models with optimal complexity under relaxed smoothness assumptions.
method Normalized Stochastic Gradient Descent with Momentum (NSGD-M) without stepsize tuning.
result NSGD-M achieves nearly optimal complexity without prior knowledge of problem parameters.
Novel method for shape optimization of non-smooth PDEs.
problem Optimizing shapes governed by non-smooth PDEs.
method Functional variational approach and sensitivity analysis.
result Necessary conditions for locally optimal shapes.
We provide tight upper and lower bounds on the complexity of minimizing the average of m m m convex functions using gradient and prox oracles of the component functions. We show a significant gap between the complexity of deterministic vs randomized optimization. For smooth functions, we show that accelerated gradient de…
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.
Study on optimal rates for sequential probability assignment using smoothed analysis.
problem Optimal rates for sequential probability assignment under smoothed adversaries.
method General-purpose reduction from minimax rates to transductive learning, development of an efficient algorithm using MLE oracle.
result Optimal (logarithmic) fast rates for parametric and finite VC dimension classes, sublinear regret for general classes.
New algorithm adapts to unknown demand smoothness for dynamic pricing.
problem Dynamic pricing with unknown Hölder smoothness of demand function.
method Self-similarity condition and adaptive algorithm.
result Adaptive algorithm achieves minimax optimal regret without prior knowledge of smoothness.
Paper studies minimax optimal regression using Laplacian smoothing over graphs.
problem Minimax optimal regression over Sobolev spaces.
method Laplacian smoothing on neighborhood graphs.
result Upper bounds match minimax optimal rates for first-order Sobolev class.
In high dimensional sparse regression, pivotal estimators are estimators for which the optimal regularization parameter is independent of the noise level. The canonical pivotal estimator is the square-root Lasso, formulated along with its derivatives as a "non-smooth + non-smooth" optimization problem. Modern technique…
New algorithms achieve uniform stability for empirical risk minimization.
problem Designing uniformly stable optimization algorithms for empirical risk minimization.
method Black-box conversion of smooth optimization algorithms and development of Mirror Descent for smooth optimization.
result Optimal algorithms with uniform stability and convergence rates for smooth optimization.
Bayesian optimization tackles non-smooth tuning problems.
problem Optimizing black-box functions with non-smoothness and limited samples.
method Proposed a clustered Gaussian process (cGP) model for non-smooth optimization.
result Improvement of up to 90% in performance for repetitive experiments.
The paper examines smoothness of value function in consumption-investment models with borrowing constraints.
problem Investor's optimal consumption and investment under consumption-wealth utility and borrowing constraint.
method Second-order smoothness of value function, optimal consumption-investment policy in feedback form, smooth fit condition.
result The value function is second-order smooth and the constraint is binding under certain conditions.
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.