Convex optimization: algorithms and complexity
From MaRDI portal
This monographs is based on the lectures given in Princeton University in 2013 and 2014 and presents the main complexity theorems in convex optimization and their corresponding algorithms. Starting from the fundamental theory of black-box optimization, the material progresses towards recent advances in structural optimization and stochastic optimization. The presentation of black-box optimization includes the analysis of cutting plane methods, as well as gradient descent schemes. The author pays special attention to non-Euclidean settings and discusses their relevance in machine learning. A gentle introduction to structural optimization, saddle-point mirror prox (Nemirovski's alternative to Nesterov's smoothing), and a concise description of interior point methods has been provided in the book. Stochastic gradient descent, mini-batches, random coordinate descent, and sublinear algorithms have been discussed in stochastic optimization. At the end, the author briefly touches upon convex relaxation of combinatorial problems and the use of randomness to round solutions, as well as random walks based methods.
Recommendations
Cited in
(only showing first 100 items - show all)- Complexity of convex optimization using geometry-based measures and a reference point
- Exact worst-case convergence rates of the proximal gradient method for composite convex minimization
- Adaptive block coordinate DIRECT algorithm
- Scale-free online learning
- Dimensionality reduction of SDPs through sketching
- Analysis of biased stochastic gradient descent using sequential semidefinite programs
- Natural gradient for combined loss using wavelets
- Convergence rates for optimised adaptive importance samplers
- Bounds for the tracking error of first-order online optimization methods
- A new look at the Hardy-Littlewood-Pólya inequality of majorization
- Bias of homotopic gradient descent for the hinge loss
- Regularisation of neural networks by enforcing Lipschitz continuity
- Infinite-dimensional gradient-based descent for alpha-divergence minimisation
- Solving convex min-min problems with smoothness and strong convexity in one group of variables and low dimension in the other
- Convex optimization with an interpolation-based projection and its application to deep learning
- Inverse reinforcement learning in contextual MDPs
- Convergence results of a nested decentralized gradient method for non-strongly convex problems
- Generalized Nesterov's accelerated proximal gradient algorithms with convergence rate of order o(1/k^2)
- Understanding the acceleration phenomenon via high-resolution differential equations
- A stochastic gradient algorithm with momentum terms for optimal control problems governed by a convection-diffusion equation with random diffusivity
- From inexact optimization to learning via gradient concentration
- Accelerated proximal envelopes: application to componentwise methods
- On the computational efficiency of catalyst accelerated coordinate descent
- Heteroskedastic PCA: algorithm, optimality, and applications
- Variable demand and multi-commodity flow in Markovian network equilibrium
- New Hadamard-type inequalities for E-convex functions involving generalized fractional integrals
- A stochastic subgradient method for distributionally robust non-convex and non-smooth learning
- Stochastic saddle-point optimization for the Wasserstein barycenter problem
- Divergences on symmetric cones and medians
- Vaidya's method for convex stochastic optimization problems in small dimension
- How can we identify the sparsity structure pattern of high-dimensional data: an elementary statistical analysis to interpretable machine learning
- The computational asymptotics of Gaussian variational inference and the Laplace approximation
- Elliptic quasi-variational inequalities under a smallness assumption: uniqueness, differential stability and optimal control
- Robust statistical learning with Lipschitz and convex loss functions
- A regularization interpretation of the proximal point method for weakly convex functions
- Accelerating incremental gradient optimization with curvature information
- Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
- Robust classification via MOM minimization
- Mirror descent algorithms for minimizing interacting free energy
- Accelerated methods for saddle-point problem
- Random batch methods (RBM) for interacting particle systems
- Convergence of distributed gradient-tracking-based optimization algorithms with random graphs
- Polynomial-time algorithms for submodular Laplacian systems
- Approximate inference for constructing astronomical catalogs from images
- Mass-spring-damper networks for distributed optimization in non-Euclidean spaces
- A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization
- Nudging the particle filter
- Robust and sparse regression in generalized linear model by stochastic optimization
- A fully polynomial time approximation scheme for the smallest diameter of imprecise points
- First-order and stochastic optimization methods for machine learning
- Spectral method and regularized MLE are both optimal for top-\(K\) ranking
- Exploiting problem structure in optimization under uncertainty via online convex optimization
- Intuitionistic-fuzzy goals in zero-sum multi criteria matrix games
- Duality gap estimates for weak Chebyshev greedy algorithms in Banach spaces
- Stochastic matrix-free equilibration
- A multiplicative weight updates algorithm for packing and covering semi-infinite linear programs
- Linear convergence of first order methods for non-strongly convex optimization
- Optimization based methods for partially observed chaotic systems
- Efficient, certifiably optimal clustering with applications to latent variable graphical models
- Behavior of accelerated gradient methods near critical points of nonconvex functions
- Accelerated gradient boosting
- Approachability, regret and calibration: implications and equivalences
- Numerical methods for the resource allocation problem in a computer network
- Inexact gradient projection method with relative error tolerance
- Bregman three-operator splitting methods
- Grundlagen der Mathematischen Optimierung
- A multiplicative weights update algorithm for packing and covering semi-infinite linear programs
- Efficient numerical methods for entropy-linear programming problems
- Bandit online optimization over the permutahedron
- How effectively train large-scale machine learning models?
- Polynomial-Time Algorithms for Linear and Convex Optimization on Jump Systems
- scientific article; zbMATH DE number 519872 (Why is no real title available?)
- scientific article; zbMATH DE number 1182920 (Why is no real title available?)
- Average stability is invariant to data preconditioning. Implications to exp-concave empirical risk minimization
- Perturbed iterate analysis for asynchronous stochastic optimization
- Metamodel construction for sensitivity analysis
- Strong convexity of sandwiched entropies and related optimization problems
- The Evolution of Methods of Convex Optimization
- Distributed Learning with Sparse Communications by Identification
- Graph-dependent implicit regularisation for distributed stochastic subgradient descent
- Making the last iterate of SGD information theoretically optimal
- Efficient online linear optimization with approximation algorithms
- Algorithms for convex optimization
- Path length bounds for gradient descent and flow
- A consensus-based global optimization method for high dimensional machine learning problems
- A finite time analysis of temporal difference learning with linear function approximation
- Low-Rank Matrix Estimation from Rank-One Projections by Unlifted Convex Optimization
- Tensor-structured sketching for constrained least squares
- Proximal gradient methods with adaptive subspace sampling
- On the convergence of exact distributed generalisation and acceleration algorithm for convex optimisation
- Fast Core Pricing for Rich Advertising Auctions
- An Accelerated Level-Set Method for Inverse Scattering Problems
- Efficient numerical methods to solve sparse linear equations with application to PageRank
- scientific article; zbMATH DE number 7626710 (Why is no real title available?)
- scientific article; zbMATH DE number 7626764 (Why is no real title available?)
- scientific article; zbMATH DE number 7626794 (Why is no real title available?)
- On numerical estimates of errors in solving convex optimization problems
- Random Batch Methods for Classical and Quantum Interacting Particle Systems and Statistical Samplings
- scientific article; zbMATH DE number 7625168 (Why is no real title available?)
- scientific article; zbMATH DE number 7625184 (Why is no real title available?)
This page was built for publication: Convex optimization: algorithms and complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2809807)
