We generalize stochastic smoothing for gradient estimation of non-differentiable functions.
problem Gradient estimation for non-differentiable functions.
method Developed a general framework for relaxation and gradient estimation of non-differentiable black-box functions using stochastic smoothing with reduced assumptions.
result Empirically validated the effectiveness of variance reduction strategies for various non-differentiable tasks.
New algorithms achieve better regret bounds for online classification with relaxed benchmarks.
problem Competing with worst-case optimal binary loss in online classification.
method Comparing against predictors robust to small input perturbations, performing well under Gaussian smoothing, or maintaining a prescribed output margin.
result Regret guarantees depend only on VC dimension and instance space complexity, with an O(log(1/γ)) dependence on the generalized margin. Signal estimation problems with smoothness and sparsity priors can be naturally modeled as quadratic optimization with ℓ0-"norm" constraints. Since such problems are non-convex and hard-to-solve, the standard approach is, instead, to tackle their convex surrogates based on ℓ1-norm relaxations. In this paper…
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…
For a bounded smooth domain in the plane and smooth boundary data we consider the minimisation of the Willmore functional for graphs subject to Dirichlet or Navier boundary conditions. For H2-regular graphs we show that bounds for the Willmore energy imply area and diameter bounds. We then consider the L1-lower s…
Label assignment problems with large state spaces are important tasks especially in computer vision. Often the pairwise interaction (or smoothness prior) between labels assigned at adjacent nodes (or pixels) can be described as a function of the label difference. Exact inference in such labeling tasks is still difficul…
Researchers relax the CVF's smoothness requirement to create more flexible flow models.
problem Challenges in constructing flexible density models due to the CVF's smoothness requirement.
method Introduce L-diffeomorphisms as generalized transformations that may violate smoothness on zero Lebesgue-measure sets. result The relaxation allows for the use of non-smooth activation functions like ReLU in residual flows.
Defines weak normals for irregular curves in high-dimensional spaces.
problem Dealing with irregular curves in high-dimensional Euclidean spaces.
method Using sequences of inscribed polygonals and Gram-Schmidt procedure, introduces a relaxed notion of weak normals.
result Weak normals for irregular curves are the strong limit of approximating polygonals and agree with relaxed energy.
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.
Paper relaxes SGD privacy and generalization guarantees for non-smooth convex losses.
problem Privacy and generalization in SGD for non-smooth convex losses.
method Relaxes Lipschitz and strong smoothness assumptions to Hölder smoothness, proving (ε,δ)-DP and optimal excess risk. result Noisy SGD with α-Hölder smooth losses achieves optimal excess risk with linear gradient complexity for α≥1/2. Paper studies Adam's convergence under relaxed assumptions, proving a rate of O(poly(log T)/sqrt(T)).
problem Understanding Adam's convergence in non-convex, stochastic optimization with unbounded gradients and noise.
method Introduced a comprehensive noise model and used it to prove Adam's convergence rate.
result Adam finds a stationary point with a rate of O(poly(log T)/sqrt(T)) in high probability.
New algorithm tackles stochastic bilevel optimization under relaxed smoothness conditions.
problem Optimal algorithms for stochastic bilevel optimization under relaxed smoothness conditions.
method Introduces a novel fully single-loop and Hessian-inversion-free algorithmic framework for stochastic bilevel optimization.
result Demonstrates state-of-the-art oracle complexity results for multi-objective robust bilevel optimization.
CRA improves UL-based CO solvers by dynamically smoothing and enforcing discreteness.
problem Local optima and artificial rounding issues in UL-based CO solvers.
method Continuous Relaxation Annealing (CRA) strategy that dynamically shifts from continuous to discrete solutions.
result Significantly enhances UL-based CO solver performance and eliminates artificial rounding.
Maximum a posteriori (MAP) inference is a fundamental computational paradigm for statistical inference. In the setting of graphical models, MAP inference entails solving a combinatorial optimization problem to find the most likely configuration of the discrete-valued model. Linear programming (LP) relaxations in the Sh…
This paper analyzes the convergence of Federated Average under relaxed assumptions.
problem Lack of theoretical analysis for Federated Average under assumptions beyond smoothness.
method Relaxing assumptions of strong smoothness to semi-smoothness and semi-Lipschitz properties, and introducing a bound on the gradient.
result Provides a theoretical convergence study on Federated Learning under new assumptions.
Adam converges to stationary points under relaxed conditions.
problem Understanding and proving convergence of Adam under realistic assumptions.
method New proof of boundedness of gradients and variance-reduced Adam.
result Adam converges to ε-stationary points with O(ε⁻⁴) gradient complexity under realistic conditions.
We propose a DC proximal Newton algorithm for solving nonconvex regularized sparse learning problems in high dimensions. Our proposed algorithm integrates the proximal Newton algorithm with multi-stage convex relaxation based on the difference of convex (DC) programming, and enjoys both strong computational and statist…
Counterexample shows state-constrained optimal control problems can have Young measure gaps.
problem Existence of Young measure gaps in state-constrained optimal control problems.
method Provided a counterexample for smooth controllable systems state-constrained to the unit ball.
result Gap occurs in a regular setting with non-convex Lagrangian density.
Study revisits AdaGrad convergence with relaxed noise assumptions.
problem Non-convex smooth optimization problems with general noise.
method General noise model with function value gap and gradient magnitude control.
result Probabilistic convergence rate of ( ilde{\mathcal{O}}(1/\sqrt{T})) under general noise.
Differentiable relaxation for inferring partial orders from noisy linear data.
problem Inference of partial orders from linear data with noisy observations.
method Introducing a differentiable relaxation to model noisy linear extensions, replacing discontinuous precedence and feasibility with smooth surrogates.
result Smooth posterior that preserves partial-order semantics, supports gradient-based inference, and converges to hard likelihood.
New analysis improves denoising of modulo signals on graphs.
problem Robustly unwrapping noisy modulo samples of smooth functions.
method Analyzing sphere-relaxation and unconstrained relaxation of a QCQP on a graph.
result Proves denoising of modulo observations w.r.t the ℓ2 norm in Gaussian noise. New algorithms achieve decision calibration without sample complexity dependent on feature dimension.
problem Achieving decision calibration for nonlinear loss functions with polynomial sample complexity.
method Developed smooth relaxation of decision calibration, enabling dimension-free algorithms.
result Efficient algorithms post-process predictors to satisfy decision calibration without worsening accuracy.
GDM models time series with smoother transitions and interpretable states.
problem Capturing smooth, variable-speed transitions and stochastic mixtures of states.
method Introduces a continuous relaxation of discrete states and a Gumbel noise model.
result Models real-world datasets more faithfully with smoother dynamics and interpretable states.
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) for ε-stationary solutions. A new fuzzy clustering method using hyperbolic smoothing for large datasets.
problem Building fuzzy clusters for large data sets efficiently.
method A novel smoothing numerical approach to relax the sum-of-squares criterion, converting the problem into a differentiable optimization problem.
result The method produces better fuzzy partitions compared to traditional fuzzy C-means. Paper relaxes stability and generalization assumptions for SGD.
problem Stability and generalization for SGD under restrictive assumptions.
method Introduces on-average model stability and develops novel bounds.
result First-ever-known fast bounds in low-noise setting using stability approach.
The paper studies ideal flows of closed curves, classifying critical points and proving flow behavior.
problem Analyzing the generalised ideal flow of closed planar curves.
method Completely classifies critical points and proves properties of the m-ideal flow. result For m>1, the m-ideal flow of closed curves converges to a round multiply-covered circle. Improved Bayesian computation for imaging problems using a new MCMC method.
problem Challenges in Bayesian computation for imaging inverse problems due to high dimensionality and non-smoothness.
method Introduces a new accelerated proximal MCMC method (ls SK-ROCK) that combines data augmentation and relaxation with proximal MCMC.
result The method converges faster and achieves better accuracy than state-of-the-art approaches.
We study Hamiltonian Monte Carlo (HMC) for sampling from a strongly logconcave density proportional to e−f where f:Rd→R is μ-strongly convex and L-smooth (the condition number is κ=L/μ). We show that the relaxation time (inverse of the spectral gap) of ideal HMC is O(κ), improving…
We present the min-max construction of critical points of the area using penalization arguments. Precisely, for any immersion of a closed surface Σ into a given closed manifold, we add to the area Lagrangian a term equal to the Lq norm of the second fundamental form of the immersion times a "viscosity" parameter. …
Paper proposes an algorithm for sampling from complex mixture distributions without requiring smoothness.
problem Sampling from a mixture of weakly smooth potentials.
method Unadjusted Langevin algorithm with Euler discretization for a mixture of weakly smooth distributions.
result Convergence in Kullback-Leibler divergence and Lβ-Wasserstein metric with polynomial dependence on dimension. Algorithm recovers function samples from noisy modulo samples with high probability.
problem Recovering function samples from noisy modulo samples.
method Two-stage algorithm involving k-NN regression and SDP relaxation.
result Uniform error rate of O((nlogn)d+21) for function samples. 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.
In many problem settings, parameter vectors are not merely sparse but dependent in such a way that non-zero coefficients tend to cluster together. We refer to this form of dependency as "region sparsity." Classical sparse regression methods, such as the lasso and automatic relevance determination (ARD), which model par…
We propose a family of relaxations of the optimal transport problem which regularize the problem by introducing an additional minimization step over a small region around one of the underlying transporting measures. The type of regularization that we obtain is related to smoothing techniques studied in the optimization…
We study a hybrid conditional gradient - smoothing algorithm (HCGS) for solving composite convex optimization problems which contain several terms over a bounded set. Examples of these include regularization problems with several norms as penalties and a norm constraint. HCGS extends conditional gradient methods to cas…
New method improves neural network verification by considering multivariate input space of ReLU neurons.
problem Improving the effectiveness of neural network verification algorithms.
method A new tightened convex relaxation for ReLU neurons considering multivariate input space.
result Our convex relaxation is significantly stronger than the commonly used univariate-input relaxation.
Improved neural network robustness certification through tighter convex relaxations.
problem Certifying neural network robustness to perturbed and adversarial inputs.
method Exploiting ReLU network structure, novel partition-based certification procedure.
result Tightens existing linear programming relaxations to achieve zero relaxation error asymptotically.
New method solves subspace optimization problems efficiently.
problem Finding a k-dimensional subspace in high dimensions.
method Local linear convergence of gradient methods under strict complementarity.
result Gradient method converges linearly in high dimensions.
In this note we compare two recently proposed semidefinite relaxations for the sparse linear regression problem by Pilanci, Wainwright and El Ghaoui (Sparse learning via boolean relaxations, 2015) and Dong, Chen and Linderoth (Relaxation vs. Regularization A conic optimization perspective of statistical variable select…
Diffuse interface methods have recently been introduced for the task of semi-supervised learning. The underlying model is well-known in materials science but was extended to graphs using a Ginzburg--Landau functional and the graph Laplacian. We here generalize the previously proposed model by a non-smooth potential fun…
Despite their impressive performance on diverse tasks, neural networks fail catastrophically in the presence of adversarial inputs---imperceptibly but adversarially perturbed versions of natural inputs. We have witnessed an arms race between defenders who attempt to train robust networks and attackers who try to constr…
We propose convex relaxations for convolutional neural nets with one hidden layer where the output weights are fixed. For convex activation functions such as rectified linear units, the relaxations are convex second order cone programs which can be solved very efficiently. We prove that the relaxation recovers the glob…
Dynamic programming (DP) solves a variety of structured combinatorial problems by iteratively breaking them down into smaller subproblems. In spite of their versatility, DP algorithms are usually non-differentiable, which hampers their use as a layer in neural networks trained by backpropagation. To address this issue,…
Many high dimensional sparse learning problems are formulated as nonconvex optimization. A popular approach to solve these nonconvex optimization problems is through convex relaxations such as linear and semidefinite programming. In this paper, we study the statistical limits of convex relaxations. Particularly, we con…
Improved model for non-smooth signals with complex spectra.
problem Current models struggle with non-smooth signals and complex spectral structures.
method CGPCM and RGPCM models with causality and Bayesian nonparametric interpretations, improved variational inference.
result Proposed models show better performance on synthetic and real-world data.
New method solves nonsmooth low-rank matrix optimization problems efficiently.
problem Nonsmooth and low-rank matrix optimization problems in statistics and machine learning.
method Low-rank Extragradient Method with warm-start initialization.
result The extragradient method converges to an optimal solution with rate O(1/t) and requires only two low-rank SVDs per iteration.