Smooth minimization of non-smooth functions

2004/12/29 by Yu. Nesterov · 193 citations
Engineering · Computer Science · Mathematics · #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Advanced Optimization Algorithms Research

paper · doi:10.1007/s10107-004-0552-5

Cited by

• Primal-dual subgradient methods for convex problems
• First-order methods of smooth convex optimization with inexact oracle
• A dual method for minimizing a nonsmooth objective over one smooth inequality constraint
• GaugeQuant: Online Learning of Quantization-Optimal Bases from LLM Symmetries
• Singularity-aware Optimization via Randomized Geometric Probing: Towards Stable Non-smooth Optimization
• Bridging the Gap between Newton-Raphson Method and Regularized Policy Iteration
• Point Convergence of Nesterov's Accelerated Gradient Method: An AI-Assisted Proof
• A simple Newton method for local nonsmooth optimization
• Solving graph compression via optimal transport
• Numerical methods in large-scale optimization: inexact oracle and primal-dual analysis
• Inertial Three-Operator Splitting Method and Applications
• Online Learning for Classification of Low-rank Representation Features and Its Applications in Audio Segment Classification
• Implementation of an Optimal First-Order Method for Strongly Convex\n Total Variation Regularization
• An Efficient Primal-Dual Prox Method for Non-Smooth Optimization
• Simulation-based inference methods for partially observed Markov model via the R package is2
• Accelerating Min-Max Optimization with Application to Minimal Bounding Sphere
• Smooth Learning with Hard Constraints via Legendre-Regularized Policies
• The proximal-proximal gradient algorithm
• Adaptive First-Order Methods for General Sparse Inverse Covariance Selection
• Over-the-Air Computation via Reconfigurable Intelligent Surface
• On fundamental properties of high-order forward-backward envelope
• Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation
• Communication-Efficient Algorithms for Decentralized and Stochastic Optimization
• An accelerated inexact proximal point method for solving nonconvex-concave min-max problems
• Deep Legendre Transform
• Randomized multi-class classification under system constraints: a unified approach via post-processing
• A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applications
• An Elementary Proof of the Near Optimality of LogSumExp Smoothing
• Decentralized Non-Convex Learning with Linearly Coupled Constraints
• A Smooth Approximation Framework for Weakly Convex Optimization
• Dual Smoothing for Decentralized Optimization
• Control and Reinforcement Learning through the Lens of Optimization: An Algorithmic Perspective
• Gradient waveform design for variable density sampling in Magnetic Resonance Imaging
• Universal composite prox-method for strictly convex optimization problems
• Sparse Covariance Selection via Robust Maximum Likelihood Estimation
• Monotone Near-Zero-Sum Games: A Generalization of Convex-Concave Minimax
• Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
• High Dimensional Semiparametric Latent Graphical Model for Mixed Data
• Fairness Meets Privacy: Integrating Differential Privacy and Demographic Parity in Multi-class Classification
• Alternating Direction Algorithms for ℓ₁-Problems in Compressive Sensing
• Off-Road Navigation via Implicit Neural Representation of Terrain Traversability
• Scaling Conditional Autoencoders for Portfolio Optimization via Uncertainty-Aware Factor Selection
• Differentiable Dynamic Programming for Structured Prediction and Attention
• Combining Lagrangian Decomposition and Excessive Gap Smoothing Technique for Solving Large-Scale Separable Convex Optimization Problems
• Near-optimal Delta-convex Estimation of Lipschitz Functions
• Differentially Private Stochastic Optimization: New Results in Convex\n and Non-Convex Settings
• Breaking the Curse of Dimensionality with Convex Neural Networks
• Stochastic Smoothing for Nonsmooth Minimizations: Accelerating SGD by Exploiting Structure
• Computational Complexity of Inexact Gradient Augmented Lagrangian Methods: Application to Constrained MPC
• Structured Convex Optimization under Submodular Constraints
• A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems
• Fourier Domain Beamforming: The Path to Compressed Ultrasound Imaging
• An Efficient Algorithm for Minimizing Ordered Norms in Fractional Load Balancing
• Locally Linear Convergence for Nonsmooth Convex Optimization via Coupled Smoothing and Momentum
• The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle
• GenAI vs. Human Creators: Procurement Mechanism Design in Two-/Three-Layer Markets
• Proximal methods for the latent group lasso penalty
• Epi-convergent Smoothing with Applications to Convex Composite Functions
• Proximal gradient descent on the smoothed duality gap to solve saddle point problems
• Accelerated primal dual fixed point algorithm
• Near-Optimal Distributed Maximum Flow
• On solving large scale polynomial convex problems by randomized\n first-order algorithms
• Sparse Continuous Distributions and Fenchel-Young Losses
• Halpern-Type Accelerated and Splitting Algorithms For Monotone Inclusions
• A Proximal-Gradient Homotopy Method for the Sparse Least-Squares Problem
• Iteration complexity of first-order augmented Lagrangian methods for convex conic programming
• A Blahut-Arimoto Type Algorithm for Computing Classical-Quantum Channel Capacity
• Fast convex optimization via inertial dynamics with Hessian driven\n damping
• Non-asymptotic estimation of risk measures using stochastic gradient Langevin dynamics
• A Smoothing SQP Framework for a Class of Composite L_q Minimization over Polyhedron
• Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk\n Minimization
• Federated Composite Optimization
• Derivative-free global minimization for a class of multiple minima problems
• Fused Multiple Graphical Lasso
• A Simple and Fast Coordinate-Descent Augmented-Lagrangian Solver for Model Predictive Control
• Using Optimization to Solve Positive LPs Faster in Parallel
• Dualization of Signal Recovery Problems
• Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm
• A Survey on Metric Learning for Feature Vectors and Structured Data
• Faster Rates for training Max-Margin Markov Networks
• Accelerated Schemes For A Class of Variational Inequalities
• Convergence rate analysis of primal-dual splitting schemes
• Fast Convergence of Regularized Learning in Games
• Unified Acceleration Method for Packing and Covering Problems via Diameter Reduction
• Predictive support recovery with TV-Elastic Net penalty and logistic\n regression: an application to structural MRI
• Exploiting Smoothness in Statistical Learning, Sequential Prediction, and Stochastic Optimization
• Optimal rates for zero-order convex optimization: the power of two\n function evaluations
• Resource-aware Exact Decentralized Optimization Using Event-triggered Broadcasting
• An Efficient Inexact ABCD Method for Least Squares Semidefinite Programming
• Fast Nonsmooth Regularized Risk Minimization with Continuation
• KKT Conditions, First-Order and Second-Order Optimization, and Distributed Optimization: Tutorial and Survey
• Proximal Splitting Methods in Signal Processing
• Dual subgradient algorithms for large-scale nonsmooth learning problems
• Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method
• Online convex optimization for cumulative constraints
• An optimal subgradient algorithm for large-scale bound-constrained\n convex optimization
• A Preconditioner for a Primal-Dual Newton Conjugate Gradients Method for Compressed Sensing Problems
• Softmax is 1/2-Lipschitz: A tight bound across all ℓ_p norms
• Smoothing Multivariate Performance Measures
• Deep Unfolded Recovery of Sub-Nyquist Sampled Ultrasound Image
• A projection-free dynamics for nonsmooth composite optimization
• A Retraction-free Method for Nonsmooth Minimax Optimization over a Compact Manifold
• A Regularized Framework for Sparse and Structured Neural Attention
• Communication-Efficient Algorithms For Distributed Optimization
• A General Distributed Dual Coordinate Optimization Framework for Regularized Loss Minimization
• Unifying Width-Reduced Methods for Quasi-Self-Concordant Optimization
• Path-Following Gradient-Based Decomposition Algorithms For Separable Convex Optimization
• Improving Fast Dual Ascent for MPC - Part I: The Distributed Case
• Smooth Quasar-Convex Optimization with Constraints
• Matrix-free Interior Point Method for Compressed Sensing Problems
• Numerical methods for the resource allocation problem in networks
• Large-Scale Methods for Distributionally Robust Optimization
• Consistent Risk Estimation in Moderately High-Dimensional Linear Regression
• Accelerated Price Adjustment for Fisher Markets with Exact Recovery of Competitive Equilibrium
• Mitigating Smart Meter Asynchrony Error Via Multi-Objective Low Rank Matrix Recovery
• Learning with Smooth Hinge Losses
• LOTION: Smoothing the Optimization Landscape for Quantized Training
• A Solution for Large Scale Nonlinear Regression with High Rank and\n Degree at Constant Memory Complexity via Latent Tensor Reconstruction
• A FISTA-type accelerated gradient algorithm for solving smooth nonconvex composite optimization problems
• A Conditional Gradient-Based Augmented Lagrangian Framework
• Universal similar triangulars method for searching equilibriums in\n traffic flow distribution models
• Shuffle Private Stochastic Convex Optimization
• Learning Data-adaptive Nonparametric Kernels
• Private Federated Learning Without a Trusted Server: Optimal Algorithms\n for Convex Losses
• Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization
• Optimal Black-Box Reductions Between Optimization Objectives
• The chain rule for VU-decompositions of nonsmooth functions
• Generalized Direct Change Estimation in Ising Model Structure
• A Convergent Overlapping Domain Decomposition Method for Total Variation Minimization
• Applying Metric Regularity to Compute a Condition Measure of a Smoothing\n Algorithm for Matrix Games
• Convex Optimization without Projection Steps
• Distributed dual gradient methods and error bound conditions
• Solving Zero-Sum Games through Alternating Projections
• Composite Self-Concordant Minimization
• Efficient algorithms for multivariate shape-constrained convex regression problems
• Inference in topic models: sparsity and trade-off
• Decomposition of Large Scale Linear Programming Problems Containing both Linking Variables and Constraints via Accuracy Certificates
• An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected\n Graphs, and its Multicommodity Generalizations
• Searching of equilibriums in hierarchical congestion population games
• Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming
• Online Learning: A Modern Introduction Using Convex Optimization
• A successive difference-of-convex approximation method for a class of nonconvex nonsmooth optimization problems
• A FISTA-Type First Order Algorithm on Composite Optimization Problems that is Adaptable to the Convex Situation
• Nearly Maximum Flows in Nearly Linear Time
• Polyak Steps for Adaptive Fast Gradient Method
• PAL-Hom method for QP and an application to LP
• Bregman Douglas-Rachford Splitting Method
• ADMM for Multiaffine Constrained Optimization
• Solving Zero-Sum Games with Fewer Matrix-Vector Products
• Shuffling Heuristic in Variational Inequalities: Establishing New Convergence Guarantees
• GENO -- GENeric Optimization for Classical Machine Learning
• CoCoA: A General Framework for Communication-Efficient Distributed Optimization
• High-order methods beyond the classical complexity bounds, I: inexact high-order proximal-point methods
• Alternating proximal gradient method for nonnegative matrix factorization
• Stochastic Variance Reduction for Variational Inequality Methods
• Optimal Algorithms for Distributed Optimization
• Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria
• Optimization, Learning, and Games with Predictable Sequences
• Near-Optimal Algorithms for Minimax Optimization
• A Hybrid Algorithm for Convex Semidefinite Optimization
• Efficient, Certifiably Optimal Clustering with Applications to Latent\n Variable Graphical Models
• First Order Algorithm on an Optimization Problem with Improved Convergence when Problem is Convex
• Improving the resolution of Cryo-EM single particle analysis
• An inexact variable metric proximal linearization method for composite optimization over embedded submanifolds
• A Generic online acceleration scheme for Optimization algorithms via\n Relaxation and Inertia
• Theoretical and Practical Advances on Smoothing for Extensive-Form Games
• Chance constrained problems: a bilevel convex optimization perspective
• Convex Optimization Methods for Dimension Reduction and Coefficient Estimation in Multivariate Linear Regression
• Linear Convergence of Proximal Gradient Algorithm with Extrapolation for a Class of Nonconvex Nonsmooth Minimization Problems
• Fast non-coplanar beam orientation optimization based on group sparsity
• Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network
• Condition Number Analysis of Logistic Regression, and its Implications\n for Standard First-Order Solution Methods
• Smoothing Proximal Gradient Method for General Structured Sparse Learning
• Learning to Optimize: A Primer and A Benchmark
• Parallel and Distributed Methods for Nonconvex Optimization-Part I: Theory
• Large sparse signal recovery by conjugate gradient algorithm based on smoothing technique
• Multi-class Vector AutoRegressive Models for Multi-store Sales Data
• The Minimum-Rank Gram Matrix Completion via Modified Fixed Point Continuation Method
• Fast Saddle-Point Algorithm for Generalized Dantzig Selector and FDR Control with the Ordered l1-Norm
• Trace Norm Regularized Tensor Classification and Its Online Learning Approaches
• LAMA-Net: A Convergent Network Architecture for Dual-Domain Reconstruction
• Universal method with inexact oracle and its applications for searching\n equillibriums in multistage transport problems
• An Algorithmic Theory of Dependent Regularizers, Part 1: Submodular Structure
• Smoothing Algorithms for Computing the Projection onto a Minkowski Sum of Convex Sets
• Fast Stochastic Variance Reduced Gradient Method with Momentum Acceleration for Machine Learning
• Exact covariance thresholding into connected components for large-scale Graphical Lasso
• An inexact perturbed path-following method for Lagrangian decomposition\n in large-scale separable convex optimization
• Fast and Robust Fixed-Rank Matrix Recovery
• On learning to localize objects with minimal supervision
• Optimal Transport Relaxations with Application to Wasserstein GANs
• Efficient numerical algorithms for regularized regression problem with applications to traffic matrix estimations
• Mini-batch stochastic Nesterov's smoothing method for constrained convex stochastic composite optimization
• The Computational Power of Optimization in Online Learning