检索结果-内蒙古大学图书馆

Clipped SGD algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Li, Qiang Yemini, Michal Wai, Hoi-To faculty of Engineering Bar-Ilan University Israel Department of Systems Engineering and Engineering Management The Chinese University of Hong Kong Hong Kong

This paper studies the convergence of clipped stochastic gradient descent (SGD) algorithms with decision-dependent data distribution. Our setting is motivated by privacy preserving optimization algorithms that interact with performative data where the prediction models can influence future outcomes. This challenging setting involves the non-smooth clipping operator and non-gradient dynamics due to distribution shifts. We make two contributions in pursuit for a performative stable solution using clipped SGD algorithms. First, we characterize the clipping bias with projected clipped SGD (PCSGD) algorithm which is caused by the clipping operator that prevents PCSGD from reaching a stable solution. When the loss function is strongly convex, we quantify the lower and upper bounds for this clipping bias and demonstrate a bias amplification phenomenon with the sensitivity of data distribution. When the loss function is non-convex, we bound the magnitude of stationarity bias. Second, we propose remedies to mitigate the bias either by utilizing an optimal step size design for PCSGD, or to apply the recent DiceSGD algorithm [Zhang et al., 2024]. Our analysis is also extended to show that the latter algorithm is free from clipping bias in the performative setting. Numerical experiments verify our findings. © 2024, CC BY.

关键词： optimization algorithms

Optimizing LPB algorithms using Simulated Annealing

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Hamad, Dana Rasul Rashid, Tarik A.

Learner Performance-based Behavior using Simulated Annealing (LPBSA) is an improvement of the Learner Performance-based Behavior (LPB) algorithm. LPBSA, like LPB, has been proven to deal with single and complex problems. Simulated Annealing (SA) has been utilized as a powerful technique to optimize LPB. LPBSA has provided results that outperformed popular algorithms, like the Genetic Algorithm (GA), Particle Swarm optimization (PSO), and even LPB. This study outlines the improved algorithm's working procedure by providing a main population and dividing it into Good and Bad populations, and then applying crossover and mutation operators. When some individuals were born in the crossover stage, they have to go through the mutation process. Between these two steps, we have applied SA using the Metropolis Acceptance Criterion (MAC) so as to accept only the best and useful individuals to be used in the next iteration. Finally, the outcomes demonstrate that the population is enhanced, leading to improved efficiency and validating the performance of LPBSA. © 2024, CC BY.

关键词： optimization algorithms

Near-Optimal Algorithm for Non-Stationary Kernelized Bandits

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Iwazaki, Shogo Takeno, Shion MI-6 Ltd. Japan Nagoya University Japan RIKEN AIP Japan

This paper studies a non-stationary kernelized bandit (KB) problem, also called time-varying Bayesian optimization, where one seeks to minimize the regret under an unknown reward function that varies over time. In particular, we focus on a near-optimal algorithm whose regret upper bound matches the regret lower bound. For this goal, we show the first algorithm-independent regret lower bound for non-stationary KB with squared exponential and Matérn kernels, which reveals that an existing optimization-based KB algorithm with slight modification is near-optimal. However, this existing algorithm suffers from feasibility issues due to its huge computational cost. Therefore, we propose a novel near-optimal algorithm called restarting phased elimination with random permutation (R-PERP), which bypasses the huge computational cost. A technical key point is the simple permutation procedures of query candidates, which enable us to derive a novel tighter confidence bound tailored to the non-stationary problems. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Online Delay Management on a Single Train Line with Predictions

学校读者我要写书评

暂无评论

SSRN

SSRN 2024年

作者： Eichhorn, Daniel Krumke, Sven Oliver RPTU Kaiserslautern-Landau Department of Mathematics Paul-Ehrlich-Str. 14 Kaiserslautern67653 Germany

We study the Online Delay Management on a Single Train Line~\odmp\ with an additional prediction for future input data the online algorithm makes use of. The online optimization problem~\odmp\ deals with the question at which station the train should wait for the~$\delta$ minutes delayed passengers instead of forcing them to take the next train~$T$ minutes later. The goal is to minimize the total passenger delay. Two desired qualities for online algorithms with advice are called consistency and robustness, denoting the competitive ratio in case of best and worst prediction respectively. We present a family of algorithms, which uses hyper parameter~$\lambda\in(0,1)$ measuring the ``trust'' in the given prediction. This allows to achieve $(1+\lambda)$-consistency and~$(1+\sqrt{(T-\delta)/T}\cdot 1/\lambda)$-robustness. Moreover we provide a lower bound for the trade-off between consistency and robustness, which differs from that of our algorithm only by a number close to~1 for~$T\gg\delta$. © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Approximating Metric Magnitude of Point Sets

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Andreeva, Rayna Ward, James Skraba, Primoz Gao, Jie Sarkar, Rik School of Informatics University of Edinburgh United Kingdom Queen Mary University of London United Kingdom Rutgers University United States

Metric magnitude is a measure of the "size" of point clouds with many desirable geometric properties. It has been adapted to various mathematical contexts and recent work suggests that it can enhance machine learning and optimization algorithms. But its usability is limited due to the computational cost when the dataset is large or when the computation must be carried out repeatedly (e.g. in model training). In this paper, we study the magnitude computation problem, and show efficient ways of approximating it. We show that it can be cast as a convex optimization problem, but not as a submodular optimization. The paper describes two new algorithms - an iterative approximation algorithm that converges fast and is accurate, and a subset selection method that makes the computation even faster. It has been previously proposed that magnitude of model sequences generated during stochastic gradient descent is correlated to generalization gap. Extension of this result using our more scalable algorithms shows that longer sequences in fact bear higher correlations. We also describe new applications of magnitude in machine learning - as an effective regularizer for neural network training, and as a novel clustering criterion. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Evolutionary Algorithm with Detection Region Method for Constrained Multi-Objective Problems with Binary Constraints

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Huang, Weixiong Wang, Rui Zhang, Tao Qi, Sheng Wang, Ling College of Systems Engineering National University of Defense Technology Changsha410073 China Xiangjiang Laboratory Changsha410205 China Department of Automation Tsinghua University Beijing100084 China

Solving constrained multi-objective optimization problems (CMOPs) is a challenging task. While many practical algorithms have been developed to tackle CMOPs, real-world scenarios often present cases where the constraint functions are unknown or unquantifiable, resulting in only binary outcomes (feasible or infeasible). This limitation reduces the effectiveness of constraint violation guidance, which can negatively impact the performance of existing algorithms that rely on this approach. Such challenges are particularly detrimental for algorithms employing the ϵ-based method, as they hinder effective relaxation of the feasible region. To address these challenges, this paper proposes a novel algorithm called DRMCMO based on the detection region method. In DRMCMO, detection regions dynamic monitor feasible solutions to enhance convergence, helping the population escape local optima. Additionally, these regions collaborate with the neighbor pairing strategy to improve population diversity within narrow feasible areas. We have modified three existing test suites to serve as benchmark test problems for CMOPs with binary constraints(CMOP/BC) and conducted comprehensive comparative experiments with state-ofthe- art algorithms on these test suites and real-world problems. The results demonstrate the strong competitiveness of DRMCMO against state-of-the-art algorithms. Given the limited research on CMOP/BC, our study offers a new perspective for advancing this field. Impact Statement-CMOPs are common in real-world optimization scenarios, with those involving binary constraints presenting significant challenges for existing algorithms. This work introduces DRMCMO, a novel algorithm designed to address CMOPs with binary constraints. The detection region method empowers traditional algorithms to solve these challenges effectively, and its high portability indicates that it may serve as a valuable tool for optimization researchers and practitioners in the future. Comprehensive ex

关键词： optimization algorithms

Randomized Rounding Approaches to Online Allocation, Sequencing, and Matching

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ma, Will Graduate School of Business and Data Science Institute Columbia University New YorkNY10027 United States

Randomized rounding is a technique that was originally used to approximate hard offline discrete optimization problems from a mathematical programming relaxation. Since then it has also been used to approximately solve sequential stochastic optimization problems, overcoming the curse of dimensionality. To elaborate, one first writes a tractable linear programming relaxation that prescribes probabilities with which actions should be taken. Rounding then designs a (randomized) online policy that approximately preserves all of these probabilities, with the challenge being that the online policy faces hard constraints, whereas the prescribed probabilities only have to satisfy these constraints in expectation. Moreover, unlike classical randomized rounding for offline problems, the online policy’s actions unfold sequentially over time, interspersed by uncontrollable stochastic realizations that affect the feasibility of future actions. This tutorial provides an introduction for using randomized rounding to design online policies, through four self-contained examples representing fundamental problems in the area: online contention resolution, stochastic probing, stochastic knapsack, and stochastic matching. © 2024, CC BY.

关键词： optimization algorithms

A bilevel optiization based algorithm for solving a class of price equilibrium problems

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Hai, Nguyen Ngoc Muu, Le Dung van Quy, Nguyen Trade Union University Hanoi Viet Nam TIMAS Thang Long University Institute of Mathmatics VAST Hanoi Viet Nam Financial University Hanoi Viet Nam

We consider class of equilibrium models including the implicit Walras supply-demand and competitive models. Such a model in this class, in general, is ill-posed. We formulate such a model in the form a variational inequality having certain monotonicity property which allow us to describe a regularization algorithm avoiding the ill-posedness based upon the bilevel optimization for finding a point that is nearest to the given guessed or desired equilibrium price for the model. The obtained computational results with many randomly generated data show that the proposed algorithm works well for this class of the equilibrium models. © 2024, CC0.

关键词： optimization algorithms

Submodular Framework for Structured-Sparse Optimal Transport

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Manupriya, Piyushi Jawanpuria, Pratik Gurumoorthy, Karthik S. Jagarlapudi, SakethaNath Mishra, Bamdev Department of Computer Science and Engineering IIT Hyderabad India Microsoft India Walmart Global Tech India

Unbalanced optimal transport (UOT) has recently gained much attention due to its flexible framework for handling un-normalized measures and its robustness properties. In this work, we explore learning (structured) sparse transport plans in the UOT setting, i.e., transport plans have an upper bound on the number of non-sparse entries in each column (structured sparse pattern) or in the whole plan (general sparse pattern). We propose novel sparsity-constrained UOT formulations building on the recently explored maximum mean discrepancy based UOT. We show that the proposed optimization problem is equivalent to the maximization of a weakly submodular function over a uniform matroid or a partition matroid. We develop efficient gradient-based discrete greedy algorithms and provide the corresponding theoretical guarantees. Empirically, we observe that our proposed greedy algorithms select a diverse support set and we illustrate the efficacy of the proposed approach in various applications. © 2024, CC BY.

关键词： optimization algorithms