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

ADMM FOR NONSMOOTH COMPOSITE optimization UNDER ORTHOGONALITY CONSTRAINTS

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Yuan, Ganzhao Peng Cheng Laboratory China

We consider a class of structured, nonconvex, nonsmooth optimization problems under orthogonality constraints, where the objectives combine a smooth function, a nonsmooth concave function, and a nonsmooth weakly convex function. This class of problems finds diverse applications in statistical learning and data science. Existing methods for addressing these problems often fail to exploit the specific structure of orthogonality constraints, struggle with nonsmooth functions, or result in suboptimal oracle complexity. We propose OADMM, an Alternating Direction Method of Multipliers (ADMM) designed to solve this class of problems using efficient proximal linearized strategies. Two specific variants of OADMM are explored: one based on Euclidean Projection (OADMM-EP) and the other on Riemannian Retraction (OADMM-RR). Under mild assumptions, we prove that OADMM converges to a critical point of the problem with an ergodic convergence rate of O(1/ǫ3). Additionally, we establish a polynomial convergence rate or super-exponential convergence rate for OADMM, depending on the specific setting, under the Kurdyka-Lojasiewicz (KL) inequality. To the best of our knowledge, this is the first non-ergodic convergence result for this class of nonconvex nonsmooth optimization problems. Numerical experiments demonstrate that the proposed algorithm achieves state-of-the-art performance. © 2024, CC BY.

关键词： optimization algorithms

optimization Insights into Deep Diagonal Linear Networks

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Labarrière, Hippolyte Molinari, Cesare Rosasco, Lorenzo Villa, Silvia Vega, Cristian MaLGa DIBRIS Università degli Studi di Genova Genoa Italy MaLGa DIMA Università degli Studi di Genova Genoa Italy Center for Brains Minds and Machines MIT CambridgeMA United States Istituto Italiano di Tecnologia Genoa Italy Universidad de Tarapacà Arica Chile

Overparameterized models trained with (stochastic) gradient descent are ubiquitous in modern machine learning. These large models achieve unprecedented performance on test data, but their theoretical understanding is still limited. In this paper, we take a step towards filling this gap by adopting an optimization perspective. More precisely, we study the implicit regularization properties of the gradient flow "algorithm" for estimating the parameters of a deep diagonal neural network. Our main contribution is showing that this gradient flow induces a mirror flow dynamic on the model, meaning that it is biased towards a specific solution of the problem depending on the initialization of the network. Along the way, we prove several properties of the trajectory. © 2024, CC BY.

关键词： optimization algorithms

Exploration-Driven Policy optimization in RLHF: Theoretical Insights on Efficient Data Utilization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Du, Yihan Winnicki, Anna Dalal, Gal Mannor, Shie Srikant, R. University of Illinois Urbana-Champaign United States NVIDIA Research United States Technion

Reinforcement Learning from Human Feedback (RLHF) has achieved impressive empirical successes while relying on a small amount of human feedback. However, there is limited theoretical justification for this phenomenon. Additionally, most recent studies focus on value-based algorithms despite the recent empirical successes of policy-based algorithms. In this work, we consider an RLHF algorithm based on policy optimization (PO-RLHF). The algorithm is based on the popular Policy Cover-Policy Gradient (PC-PG) algorithm, which assumes knowledge of the reward function. In PO-RLHF, knowledge of the reward function is not assumed, and the algorithm uses trajectory-based comparison feedback to infer the reward function. We provide performance bounds for PO-RLHF with low query complexity, which provides insight into why a small amount of human feedback may be sufficient to achieve good performance with RLHF. A key novelty is a trajectory-level elliptical potential analysis, which bounds the reward estimation error when comparison feedback (rather than numerical reward observation) is given. We provide and analyze algorithms PG-RLHF and NN-PG-RLHF for two settings: linear and neural function approximation, respectively. © 2024, CC BY.

关键词： optimization algorithms

Non-Euclidean High-Order Smooth Convex optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Contreras, Juan Pablo Guzmán, Cristóbal Martínez-Rubio, David Institute for Mathematical and Computational Engineering Pontificia Universidad Católica de Chile Chile Institute for Mathematical and Computational Engineering Faculty of Mathematics School of Engineering Pontificia Universidad Católica de Chile Chile Signal Theory and Communications Department Universidad Carlos III de Madrid Spain

We develop algorithms for the optimization of convex objectives that have Hölder continuous q-th derivatives with respect to a p-norm by using a q-th order oracle, for p, q ≥ 1. We can also optimize other structured functions. We do this by developing a non-Euclidean inexact accelerated proximal point method that makes use of an inexact uniformly convex regularizer. We also provide nearly matching lower bounds for any deterministic algorithm that interacts with the function via a local oracle. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Quantum key distribution rates from non-symmetric conic optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Lorente, Andrés González Parellada, Pablo V. Castillo-Celeita, Miguel Araújo, Mateus Departamento de Física Teórica Atómica y Óptica Universidad de Valladolid Valladolid47011 Spain

Computing key rates in quantum key distribution (QKD) numerically is essential to unlock more powerful protocols, that use more sophisticated measurement bases or quantum systems of higher dimension. It is a difficult optimization problem, that depends on minimizing a convex non-linear function: the (quantum) relative entropy. Standard conic optimization techniques have for a long time been unable to handle the relative entropy cone, as it is a non-symmetric cone, and the standard algorithms can only handle symmetric ones. Recently, however, a practical algorithm has been discovered for optimizing over non-symmetric cones, including the relative entropy. Here we adapt this algorithm to the problem of computation of key rates, obtaining an efficient technique for lower bounding them. In comparison to previous techniques it has the advantages of flexibility, ease of use, and above all performance. © 2024, CC BY.

关键词： optimization algorithms

Modeling of Missing Data Prediction: Computational Intelligence and optimization algorithms

学校读者我要写书评

暂无评论

Modeling of Missing Data Prediction: Computational Intellige...

IEEE International Conference on Systems, Man, and Cybernetics

作者： Collins Leke Bhekisipho Twala Tshilidzi Marwala Department of Electrical and Electronic Engineering Science University of Johannesburg

ISBN: (纸本)9781479938414

Four optimization algorithms (genetic algorithm, simulated annealing, particle swarm optimization and random forest) were applied with an MLP based auto associative neural network on two classification datasets and one prediction dataset. This work was undertaken to investigate the effectiveness of using auto associative neural networks and optimization algorithms in missing data prediction and classification tasks. If performed appropriately, computational intelligence and optimization algorithm systems could lead to consistent, accurate and trustworthy predictions and classifications resulting in more adequate decisions. The results reveal GA, SA and PSO to be more efficient when compared to RF in terms of predicting the forest area to be affected by fire. GA, SA, and PSO had the same accuracy of 93.3%, while RF showed 92.99% accuracy. For the classification problems, RF showed 93.66% and 92.11% accuracy on the German credit and Heart disease datasets respectively, outperforming GA, SA and PSO.

关键词： optimization algorithms Auto-associative neural networks Prediction Classification Missing data

Constrained Multi-objective Bayesian optimization through Optimistic Constraints Estimation

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Li, Diantong Zhang, Fengxue Liu, Chong Chen, Yuxin School of Data Science Chinese University of Hong Kong Shenzhen China Department of Computer Science University of Chicago United States Department of Computer Science University at Albany State University of New York United States

Multi-objective Bayesian optimization has been widely adopted in scientific experiment design, including drug discovery and hyperparameter optimization. In practice, regulatory or safety concerns often impose additional thresholds on certain attributes of the experimental outcomes. Previous work has primarily focused on constrained single-objective optimization tasks or active search under constraints. The existing constrained multi-objective algorithms address the issue with heuristics and approximations, posing challenges to the analysis of the sample efficiency. We propose a novel constrained multi-objective Bayesian optimization algorithm (CMOBO) that balances active learning of the level-set defined on multiple unknowns with multi-objective optimization within the feasible region. We provide both theoretical analysis and empirical evidence, demonstrating the efficacy of our approach on various synthetic benchmarks and real-world applications. © 2024, CC BY.

关键词： optimization algorithms

Indirect Query Bayesian optimization with Integrated Feedback

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Zhang, Mengyan Bouabid, Shahine Ong, Cheng Soon Flaxman, Seth Sejdinovic, Dino University of Oxford United Kingdom Massachusetts Institute of Technology United States CSIRO Australian National University Australia University of Adelaide Australia

We develop the framework of Indirect Query Bayesian optimization (IQBO), a new class of Bayesian optimization problems where the integrated feedback is given via a conditional expectation of the unknown function f to be optimized. The underlying conditional distribution can be unknown and learned from data. The goal is to find the global optimum of f by adaptively querying and observing in the space transformed by the conditional distribution. This is motivated by real-world applications where one cannot access direct feedback due to privacy, hardware or computational constraints. We propose the Conditional Max-Value Entropy Search (CMES) acquisition function to address this novel setting, and propose a hierarchical search algorithm to address the multi-resolution setting and improve the computational efficiency. We show regret bounds for our proposed methods and demonstrate the effectiveness of our approaches on simulated optimization tasks. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Contaminated Online Convex optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Kamijima, Tomoya Ito, Shinji Department of Mathematical Informatics The University of Tokyo Tokyo Japan NEC Corporation Kanagawa Japan RIKEN AIP Tokyo Japan

In online convex optimization, some efficient algorithms have been designed for each of the individual classes of objective functions, e.g., convex, strongly convex, and exp-concave. However, existing regret analyses, including those of universal algorithms, are limited to cases in which the objective functions in all rounds belong to the same class and cannot be applied to cases in which the property of objective functions may change in each time step. This paper introduces a novel approach to address such cases, proposing a new regime we term as contaminated online convex optimization. For the contaminated case, we demonstrate that the regret is lower bounded by Ω(log T + √k). Here, k signifies the level of contamination in the objective functions. We also demonstrate that the regret is bounded by O(log T + √k log T) when universal algorithms are used. When our proposed algorithms with additional information are employed, the regret is bounded by O(log T + √k), which matches the lower bound. These are intermediate bounds between a convex case and a strongly convex or exp-concave case. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms