JournalTOCs

Foundations and Trends® in Optimization
Number of Followers: 2

Full-text available via subscription

Subscription journal
ISSN (Print) 2167-3888 - ISSN (Online) 2167-3918
Published by Now Publishers Inc

[28 journals]

AltGDmin: Alternating GD and Minimization for Partly-decoupled (Federated)
Optimization
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: AbstractThis monograph describes a novel optimization solutionframework, called alternating gradient descent (GD) andminimization (AltGDmin), that is useful for many problemsfor which alternating minimization (AltMin) is a popularsolution. AltMin is a special case of the block coordinatedescent algorithm that is useful for problems in which minimizationw.r.t one subset of variables keeping the otherfixed is closed form or otherwise reliably solved. Denotethe two blocks/subsets of the optimization variables Z byZslow, Zfast, i.e., Z = {Zslow, Zfast}. AltGDmin is often afaster solution than AltMin for any problem for which (i)the minimization over one set of variables, Zfast, is muchquicker than that over the other set, Zslow; and (ii) the costfunction is differentiable w.r.t. Zslow. Often, the reason forone minimization to be quicker is that the problem is "decoupled"for Zfast and each of the decoupled problems is quickto solve. This decoupling is also what makes AltGDmincommunication-efficient for federated settings.Important examples where this assumption holds include(a) low rank column-wise compressive sensing (LRCS), lowrank matrix completion (LRMC), (b) their outlier-corruptedextensions such as robust PCA, robust LRCS and robustLRMC; (c) phase retrieval and its sparse and low-rank modelbased extensions; (d) tensor extensions of many of theseproblems such as tensor LRCS and tensor completion; and(e) many partly discrete problems where GD does not apply– such as clustering, unlabeled sensing, and mixed linearregression. LRCS finds important applications in multi-taskrepresentation learning and few shot learning, federatedsketching, and accelerated dynamic MRI. LRMC and robustPCA find important applications in recommender systems,computer vision and video analytics.Suggested CitationNamrata Vaswani (2025), "AltGDmin: Alternating GD and Minimization for Partly-decoupled (Federated) Optimization", Foundations and Trends® in Optimization: Vol. 8: No. 4, pp 333-414. http://dx.doi.org/10.1561/2400000051
  PubDate: Wed, 28 May 2025 00:00:00 +020
Gradient-Based Algorithms for Zeroth-Order Optimization
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: AbstractThis monograph deals with methods for stochastic or data-driven optimization. The overall goal in these methods is to minimize a certain parameter-dependent objective function that for any parameter value is an expectation of a noisy sample performance objective whose measurement can be made from a real system or a simulation device depending on the setting used. We present a class of model-free approaches based on stochastic approximation which involve random search procedures to efficiently make use of the noisy observations. The idea here is to simply estimate the minima of the expected objective via an incremental-update or recursive procedure and not to estimate the whole objective function itself. We provide both asymptotic as well as finite sample analyses of the procedures used for convex as well as non-convex objectives.We present algorithms that either estimate the gradient in gradient-based schemes or estimate both the gradient and the Hessian in Newton-type procedures using random direction approaches involving noisy function measurements. Hence the class of approaches that we study fall under the broad category of zeroth order optimization methods. We provide both asymptotic convergence guarantees in the general setup as well as asymptotic normality results for various algorithms. We also provide an introduction to stochastic recursive inclusions as well as their asymptotic convergence analysis. This is necessitated because many of these settings involve set-valued maps for any given parameter. We also present a couple of interesting applications of these methods in the domain of reinforcement learning. Five appendices at the end of this work quickly summarize the basic material. A large portion of this work is driven by our own contributions to this area.Suggested CitationPrashanth L. A. and Shalabh Bhatnagar (2025), "Gradient-Based Algorithms for Zeroth-Order Optimization", Foundations and Trends® in Optimization: Vol. 8: No. 1–3, pp 1-332. http://dx.doi.org/10.1561/2400000047
  PubDate: Wed, 14 May 2025 00:00:00 +020
Integer Programming Games
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: AbstractWe provide a comprehensive survey of Integer ProgrammingGames (IPGs), focusing on both simultaneous games andbilevel programs. These games are characterized by integralconstraints within the players’ strategy sets. We startfrom the fundamental definitions of these games and varioussolution concepts associated with them, and derive theproperties of the games and the solution concepts. For eachof the two types of games – simultaneous and bilevel – wehave one section dedicated to the analysis of the games andanother section dedicated to the development and analysesof algorithms to solve them. The analyses sections presentresults on the computational complexity of the general gameas well as various other restricted versions. These sectionsalso discuss the structural properties of the games and theequilibrium concepts associated with them. The algorithmsections, in contrast, present some of the state-of-the-artalgorithms developed to solve these games, either exactly,approximately or fast under fixed-parameter assumptions.These sections also contain proofs of the correctness of thesealgorithms and an assessment of their theoretical run timesin the worst-case scenario. Suggested CitationMargarida Carvalho, Gabriele Dragotto, Andrea Lodi and Sriram Sankaranarayanan (2025), "Integer Programming Games", Foundations and Trends® in Optimization: Vol. 7: No. 4, pp 264-391. http://dx.doi.org/10.1561/2400000040
  PubDate: Thu, 20 Feb 2025 00:00:00 +010
Multi-agent Online Optimization
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: AbstractThis monograph provides an overview of distributed onlineoptimization in multi-agent systems. Online optimizationapproaches planning and decision problems from a robustlearning perspective, where one learns through feedbackfrom sequentially arriving costs, resembling a game betweena learner (agent) and the environment. Recently, multi-agentsystems have become important in diverse areas includingsmart power grids, communication networks, machine learning,and robotics, where agents work with decentralized data,costs, and decisions to collectively minimize a system-widecost. In such settings, agents make distributed decisions andcollaborate with neighboring agents through a communicationnetwork, leading to scalable solutions that often performas well as centralized methods. The monograph offers a unifiedintroduction, starting with fundamental algorithms forbasic problems, and gradually covering state-of-the-art techniquesfor more complex settings. The interplay betweenindividual agent learning rates, network structure, and communicationcomplexity is highlighted in the overall systemperformance. Suggested CitationDeming Yuan, Alexandre Proutiere and Guodong Shi (2024), "Multi-agent Online Optimization", Foundations and Trends® in Optimization: Vol. 7: No. 2-3, pp 81-263. http://dx.doi.org/10.1561/2400000037
  PubDate: Mon, 16 Dec 2024 00:00:00 +010
An Invitation to Deep Reinforcement Learning
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: AbstractTraining a deep neural network to maximize a target objectivehas become the standard recipe for successful machinelearning over the last decade. These networks can be optimizedwith supervised learning if the target objective isdifferentiable. However, this is not the case for many interestingproblems. Common objectives like intersection over union(IoU), and bilingual evaluation understudy (BLEU) scoresor rewards cannot be optimized with supervised learning.A common workaround is to define differentiable surrogatelosses, leading to suboptimal solutions with respect to theactual objective. Reinforcement learning (RL) has emergedas a promising alternative for optimizing deep neural networksto maximize non-differentiable objectives in recentyears. Examples include aligning large language models viahuman feedback, code generation, object detection or controlproblems. This makes RL techniques relevant to the largermachine learning audience. The subject is, however, timeintensiveto approach due to the large range of methods,as well as the often highly theoretical presentation. Thismonograph takes an alternative approach that is differentfrom classic RL textbooks. Rather than focusing on tabularproblems, we introduce RL as a generalization of supervisedlearning, which we first apply to non-differentiable objectivesand later to temporal problems. Assuming only basicknowledge of supervised learning, the reader will be able tounderstand state-of-the-art deep RL algorithms like proximalpolicy optimization (PPO) after reading this tutorial. Suggested CitationBernhard Jaeger and Andreas Geiger (2024), "An Invitation to Deep Reinforcement Learning", Foundations and Trends® in Optimization: Vol. 7: No. 1, pp 1-80. http://dx.doi.org/10.1561/2400000049
  PubDate: Tue, 10 Dec 2024 00:00:00 +010
Constrained Reinforcement Learning with Average Reward Objective:
Model-Based and Model-Free Algorithms
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: Abstract Reinforcement Learning (RL) serves as a versatile frameworkfor sequential decision-making, finding applications acrossdiverse domains such as robotics, autonomous driving, recommendationsystems, supply chain optimization, biology,mechanics, and finance. The primary objective of these applicationsis to maximize the average reward. Real-worldscenarios often necessitate adherence to specific constraintsduring the learning process. This monograph focuses on the exploration of various modelbasedand model-free approaches for Constrained RL withinthe context of average reward Markov Decision Processes(MDPs). The investigation commences with an examinationof model-based strategies, delving into two foundationalmethods – optimism in the face of uncertainty and posteriorsampling. Subsequently, the discussion transitionsto parametrized model-free approaches, where the primaldual policy gradient-based algorithm is explored as a solutionfor constrained MDPs. The monograph provides regretguarantees and analyzes constraint violation for each of thediscussed setups. For the above exploration, we assume the underlying MDP tobe ergodic. Further, this monograph extends its discussionto encompass results tailored for weakly communicatingMDPs, thereby broadening the scope of its findings andtheir relevance to a wider range of practical scenarios. Suggested CitationVaneet Aggarwal, Washim Uddin Mondal and Qinbo Bai (2024), "Constrained Reinforcement Learning with Average Reward Objective: Model-Based and Model-Free Algorithms", Foundations and Trends® in Optimization: Vol. 6: No. 4, pp 193-298. http://dx.doi.org/10.1561/2400000038
  PubDate: Wed, 21 Aug 2024 00:00:00 +020
Stochastic Optimization Methods for Policy Evaluation in Reinforcement
Learning
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: Abstract This monograph introduces various value-based approachesfor solving the policy evaluation problem in the online reinforcementlearning (RL) scenario, which aims to learnthe value function associated with a specific policy undera single Markov decision process (MDP). Approaches varydepending on whether they are implemented in an on-policyor off-policy manner: In on-policy settings, where the evaluationof the policy is conducted using data generated fromthe same policy that is being assessed, classical techniquessuch as TD(0), TD(λ), and their extensions with functionapproximation or variance reduction are employed in this setting.For off-policy evaluation, where samples are collectedunder a different behavior policy, this monograph introducesgradient-based two-timescale algorithms like GTD2,TDC, and variance-reduced TDC. These algorithms are designedto minimize the mean-squared projected Bellmanerror (MSPBE) as the objective function. This monographalso discusses their finite-sample convergence upper boundsand sample complexity. Suggested CitationYi Zhou and Shaocong Ma (2024), "Stochastic Optimization Methods for Policy Evaluation in Reinforcement Learning", Foundations and Trends® in Optimization: Vol. 6: No. 3, pp 145-192. http://dx.doi.org/10.1561/2400000045
  PubDate: Thu, 15 Aug 2024 00:00:00 +020
Numerical Methods for Convex Multistage Stochastic Optimization
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: Abstract Optimization problems involving sequential decisions in a stochastic environment were studied in Stochastic Programming (SP), Stochastic Optimal Control (SOC) and Markov Decision Processes (MDP). In this monograph, we mainly concentrate on SP and SOC modeling approaches. In these frameworks, there are natural situations when the considered problems are convex. The classical approach to sequential optimization is based on dynamic programming. It has the problem of the so-called “curse of dimensionality”, in that its computational complexity increases exponentially with respect to the dimension of state variables. Recent progress in solving convex multistage stochastic problems is based on cutting plane approximations of the cost-to-go (value) functions of dynamic programming equations. Cutting plane type algorithms in dynamical settings is one of the main topics of this monograph. We also discuss stochastic approximation type methods applied to multistage stochastic optimization problems. From the computational complexity point of view, these two types of methods seem to be complementary to each other. Cutting plane type methods can handle multistage problems with a large number of stages but a relatively smaller number of state (decision) variables. On the other hand, stochastic approximation type methods can only deal with a small number of stages but a large number of decision variables. Suggested CitationGuanghui Lan and Alexander Shapiro (2024), "Numerical Methods for Convex Multistage Stochastic Optimization", Foundations and Trends® in Optimization: Vol. 6: No. 2, pp 63-144. http://dx.doi.org/10.1561/2400000044
  PubDate: Wed, 22 May 2024 00:00:00 +020
A Tutorial on Hadamard Semidifferentials
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: AbstractThe Hadamard semidifferential is more general than the Fréchet differential now dominant in undergraduate mathematics education. By slightly changing the definition of the forward directional derivative, the Hadamard semidifferential rescues the chain rule, enforces continuity, and permits differentiation across maxima and minima. It also plays well with convex analysis and naturally extends differentiation to smooth embedded submanifolds, topological vector spaces, and metric spaces of shapes and geometries. The current elementary exposition focuses on the more familiar territory of analysis in Euclidean spaces and applies the semidifferential to some representative problems in optimization and statistics. These include algorithms for proximal gradient descent, steepest descent in matrix completion, and variance components models.Suggested CitationKenneth Lange (2024), "A Tutorial on Hadamard Semidifferentials", Foundations and Trends® in Optimization: Vol. 6: No. 1, pp 1-62. http://dx.doi.org/10.1561/2400000041
  PubDate: Mon, 13 May 2024 00:00:00 +020

HOME > Browse the 73 Subjects covered by JournalTOCs
Subject	Total Journals