First order methods can take extremely long to find global minima of non-convex functions.
problem Finding global minimizers of non-convex functions.
method Designing a family of non-convex functions and using statistical lower bounds for parameter estimation.
result First order methods can take exponential time to converge to a global minimizer.
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.
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.
Improved generalization bounds for SGD in non-convex learning.
problem Understanding generalization properties of SGD in non-convex settings.
method Introducing Type II perturbed SGD (T2pm-SGD) to analyze generalization error bounds.
result Tighter generalization error bounds for SGD in non-convex learning, especially for sub-Gaussian and bounded loss functions.
Improved DP algorithms for non-convex optimization with tighter generalization bounds.
problem Private stochastic non-convex optimization in high-dimensional spaces.
method Differential privacy techniques, including adaptive algorithms like DP RMSProp and DP Adam, combined with adaptive data analysis.
result Achieved a sharper rate of p 4 / n \sqrt[4]{p}/\sqrt{n} 4 p / n for population loss, improving upon previous bounds. Study finds eigenvalue bounds for non-convex domains using cohomology.
problem Eigenvalue bounds for non-convex domains.
method Cohomology, Poincaré-type inequalities, Cheeger-McGowan gluing lemma.
result Established geometric lower bounds for eigenvalues in non-convex domains.
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 bounds for SGLD show error decreases with more data.
problem Establishing generalization error bounds for SGLD in non-convex settings.
method Using dissipativity, smoothness, and uniform stability, time-independent bounds are derived.
result Error bounds decay to zero as sample size increases.
New bounds found for optimizing non-convex functions with noisy data.
problem Limits of first-order stochastic optimization in non-convex settings.
method Divergence decomposition to construct challenging subclasses.
result Sharp lower bounds on noisy gradient queries for various non-convex classes.
New algorithm finds approximate stationary points in non-convex optimization.
problem Finding approximate stationary points in non-convex stochastic optimization.
method Design of an algorithm using O ( ε − 3 ) O(ε^{-3}) O ( ε − 3 ) stochastic gradient and Hessian-vector products. result Optimal rate of O ( ε − 3 ) O(ε^{-3}) O ( ε − 3 ) for finding ε ε ε -approximate stationary points, matching lower bounds. Paper develops probabilistic bounds for a stochastic gradient algorithm in non-convex problems.
problem Stochastic optimization in non-convex finite sum problems.
method Develops a new dimension-free Azuma-Hoeffding type bound for a martingale difference sequence.
result Empirical results show superior probabilistic performance of Prob-SARAH compared to other algorithms.
An Euler discretization of the Langevin diffusion is known to converge to the global minimizers of certain convex and non-convex optimization problems. We show that this property holds for any suitably smooth diffusion and that different diffusions are suitable for optimizing different classes of convex and non-convex …
Optimal control in changing systems without strong convexity assumptions.
problem Adversarial changes in convex costs for unknown linear systems.
method Non-convex lower confidence bounds and computationally-efficient regret minimization.
result Achieves T \smash{\sqrt{T}} T -regret rate, optimal compared to best stabilizing controller. Algorithm-dependent generalization error bounds are central to statistical learning theory. A learning algorithm may use a large hypothesis space, but the limited number of iterations controls its model capacity and generalization error. The impacts of stochastic gradient methods on generalization error for non-convex …
Novel bounds for SGLD show generalization error decreases with more samples.
problem Understanding the generalization error of SGLD in non-convex optimization.
method Information-theoretic approach focusing on Kullback-Leibler divergence and sub-exponential loss function.
result Time-independent generalization bounds for SGLD, independent of step size and number of iterations.
AdaGrad outperforms SGD in non-convex optimization problems by a factor of d.
problem Finding near-stationary points in stochastic non-convex optimization.
method Refined assumptions on smoothness and gradient noise variance, l 1 l_1 l 1 -norm stationarity measure. result AdaGrad achieves a convergence rate favorable over SGD in certain non-convex settings.
Unified stability bounds for noisy SGD across convex and non-convex losses.
problem Deriving generalization bounds for noisy stochastic gradient descent.
method Unified approach using Lyapunov functions and applied probability.
result Time-uniform stability bounds for SGD on various loss functions.
New approach for distributed online optimization of non-convex losses with sublinear regret.
problem Regret evaluation and consensus in distributed, multi-agent systems with non-convex losses.
method Composite regret metric and consensus-based online normalized gradient (CONGD) approach for pseudo-convex losses; offline optimization oracle for general non-convex losses.
result First sublinear regret bound for general distributed online non-convex learning.
Non-convex optimization is ubiquitous in machine learning. Majorization-Minimization (MM) is a powerful iterative procedure for optimizing non-convex functions that works by optimizing a sequence of bounds on the function. In MM, the bound at each iteration is required to \emph{touch} the objective function at the opti…
CDP reduces point cloud dimensions by preserving detour-induced local non-convexity.
problem Preserving local non-convexity in point cloud dimensionality reduction.
method CDP builds a k-NN graph, identifies admissible pairs, aggregates normalized directions, and uses top-k eigenvectors for projection.
result CDP provides verifiable guarantees on post-projection distortion and direction energy.
Improved algorithm finds second-order stationary points in non-convex optimization.
problem Minimizing non-convex objectives while preserving training data privacy.
method SpiderBoost framework with two gradient oracles: precise and less precise.
result Improved rates for finding second-order stationary points.
New algorithm finds critical points in non-convex optimization with heavy-tailed gradients.
problem Non-convex stochastic optimization with heavy-tailed gradient estimates.
method Gradient clipping, momentum, and normalized gradient descent.
result High-probability convergence to critical points with best-known rates.
We lower bound the complexity of finding ε ε ε -stationary points (with gradient norm at most ε ε ε ) using stochastic first-order methods. In a well-studied model where algorithms access smooth, potentially non-convex functions through queries to an unbiased stochastic gradient oracle with bounded variance, we prove that (i…
New method estimates GGLM parameters, overcoming non-convexity.
problem Estimating parameters in GGLM with dependencies.
method Monotone operator-based variational inequality method.
result Guarantees for parameter recovery in GLM and GGLM.
New PAC-Bayesian bounds for online learning with data streams.
problem Challenges of traditional PAC-Bayesian bounds in dynamic data collection.
method Developed new PAC-Bayesian bounds in online learning framework, using updated regret definition and batch-to-online conversion.
result PAC-Bayesian bounds hold for online learning with dependent data and non-convex losses.
We rigorously prove statistical physics predictions for non-convex GLMs in high dimensions.
problem Analyzing high-dimensional optimization problems in non-convex Generalized Linear Models.
method Developed a systematic framework using the Gaussian Min-Max Theorem and AMP to rigorously prove replica-symmetric formulas.
result Validated statistical physics predictions for non-convex GLMs, aligning with physicist's conjectures.
New bounds explain deterministic non-smooth deep nets without large Lipschitz constants.
problem Challenges in explaining generalization of deterministic non-smooth deep nets.
method De-randomized PAC-Bayes margin bounds for deterministic non-convex and non-smooth predictors.
result New bounds avoid large Lipschitz constants, providing generalization guarantees.
Study on policy testing in MDPs with lower bounds and new algorithm.
problem Deciding if policy value exceeds a threshold with limited samples.
method Derived lower bound, proposed new algorithm, reformulated problem, used policy optimization in reversed MDP.
result New algorithm outperforms existing methods in policy testing.
Paper improves stability analysis of SGD for various loss functions and data distributions.
problem Improving stability analysis of SGD for non-convex loss functions and data distributions.
method Analyzes stability of SGD for convex and non-convex loss functions, and improves data-dependent bounds.
result Improved stability bounds for non-convex loss functions and convex regularized loss functions.
This paper analyzes convergence of RMSProp and Adam in non-convex optimization with tight complexity bounds.
problem Analyzing convergence of RMSProp and Adam in non-convex optimization with relaxed assumptions.
method Developed new convergence analyses for RMSProp and Adam, considering adaptive learning rates and affine noise variance.
result RMSProp and Adam converge to ε-stationary points with iteration complexities of O(ε^(-4)) under proper hyperparameters.
Paper proposes GPM for simultaneous community detection and group synchronization.
problem Simultaneous community detection and group synchronization in networks.
method Generalized Power Method (GPM) for non-convex optimization.
result GPM achieves exact recovery in O ( n log 2 n ) O(n\log^2n) O ( n log 2 n ) time, outperforming SDP. The paper bounds generalization error for iterative learning with bounded updates.
problem Generalization error of iterative learning algorithms with bounded updates for non-convex loss functions.
method Information-theoretic techniques, reformulating mutual information as update uncertainty, variance decomposition.
result Improved generalization error bounds for iterative learning algorithms with bounded updates.
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.
AEGD optimizes non-convex functions with dynamic energy updates.
problem Optimizing non-convex functions efficiently and robustly.
method Adaptive Gradient Descent (AEGD) with a dynamically updated energy variable.
result AEGD achieves energy-dependent convergence rates for both convex and non-convex objectives.
Improved variance reduction for Riemannian non-convex optimization with adaptive batch size.
problem Optimizing non-convex functions on Riemannian manifolds.
method Batch size adaptation in R-SVRG, R-SRG, and R-SPIDER.
result Achieves lower total complexities for various non-convex functions.
In this paper, we consider the problem of learning high-dimensional tensor regression problems with low-rank structure. One of the core challenges associated with learning high-dimensional models is computation since the underlying optimization problems are often non-convex. While convex relaxations could lead to polyn…
Online algorithms for identifying river pollution sources.
problem Real-time estimation of river pollution sources from downstream data.
method Gradient-based online learning algorithms with adaptive step sizes and escaping from saddle points module.
result High estimation accuracy in three dimensions, superior to existing methods.
SGD generalization bounds derived from information theory.
problem Understanding generalization of SGD for non-convex functions.
method Combining information-theoretic bounds with perturbation analysis.
result Upper bounds on SGD's generalization error based on gradient variance and function smoothness.
Paper proposes a working set algorithm for non-convex sparse regression with provable convergence.
problem Estimating sparse linear models from high-dimensional data using non-convex regularizers.
method FireWorks algorithm based on non-convex reformulation and leveraging residual geometry.
result Convergence to a stationary point of the full problem with provable guarantees.
This paper studies quasar-convex functions to improve optimization methods.
problem Improving optimization methods for non-convex functions.
method Study of first order methods for quasar-convex functions.
result Proves complexity upper bounds similar to convex functions.
Study spectral learning for odeco tensors, addressing initialization bottlenecks.
problem Recovering orthogonally decomposable tensors under noise.
method Investigates perturbation bounds, non-convex optimization, and initialization strategies.
result Initialization is the main bottleneck for efficient algorithms.
Unified distributed SGD improves non-convex optimization for large datasets.
problem Bottleneck in scaling SGD for non-convex functions and large datasets.
method Distributed and parallel implementation of SGD (DPSGD) combining asynchronous distribution and lock-free parallelism.
result DPSGD achieves better convergence rate and speed-up with more cores and workers.
New bounds for non-convex estimators without Bernstein condition.
problem Sharp excess risk bounds for non-convex and improper estimators.
method Exponential-tail local Rademacher complexity risk bounds with offset condition.
result Sharp bounds for non-convex and improper estimators without Bernstein condition.
In this paper, we propose a novel uniform generalization bound on the time and inverse temperature for stochastic gradient Langevin dynamics (SGLD) in a non-convex setting. While previous works derive their generalization bounds by uniform stability, we use Rademacher complexity to make our generalization bound indepen…
New sampling method guarantees approximate first-order stationary points for non-convex functions.
problem Sampling from non-log-concave densities with non-convex potential functions.
method Averaged Langevin Monte Carlo with complexity analysis.
result Langevin Monte Carlo outputs a sample with ε-relative Fisher information after O(L²d²/ε²) iterations.
Proposes r2SGLD for efficient constrained exploration in non-convex learning.
problem Stagnation in high-temperature chains of reSGLD in distribution tails.
method r2SGLD: replica exchange with reflection steps in a bounded domain.
result Reflection steps enhance mixing rates with quadratic improvement in domain diameter.
Majorization-minimization algorithms consist of successively minimizing a sequence of upper bounds of the objective function. These upper bounds are tight at the current estimate, and each iteration monotonically drives the objective function downhill. Such a simple principle is widely applicable and has been very popu…
Paper checks SSC for matrix factorizations using Gurobi.
problem Checking the SSC for various matrix factorizations.
method Formulated as a non-convex quadratic optimization problem over a bounded set, solved with Gurobi.
result SSC can be checked in reasonable time for realistic scenarios.