1,721,086 research outputs found
Recommended from our members
Minimax Optimization for Games and for Fine-Tuning of Language Models
Get PDFThis thesis advances the field of convex-concave minimax optimization by introducing novelalgorithms that outperform traditional methods in various stochastic optimization settings, including
separable strongly convex-strongly concave (SC-SC), bilinearly coupled strongly convex-strongly
concave (bi-SC-SC), bilinear games, etc. Notably, we propose the Accelerated Gradient-Optimistic
Gradient (AG-OG) Descent Ascent and the stochastic Accelerated Gradient-Extragradient (AG-EG)
method. Both algorithms achieve optimal convergence rates in separable minimax optimization and
strongly monotone variational inequalities, respectively, with lower-bound matching convergence
rates specifically in the bilinear game setting. Furthermore, we explore the application of minimax
optimization to enhance large language model fine-tuning through a novel self-play mechanism,
demonstrating significant performance improvements across multiple benchmarks. Our contributions
provide powerful tools for both theoretical research and practical applications in AI and ML,
pushing the boundaries of optimization techniques in these fields
Recommended from our members
Sample-Efficient Nonconvex Optimization Algorithms in Machine Learning and Reinforcement Learning
Get PDFMachine learning and reinforcement learning have achieved tremendous success in solving problems in various real-world applications. Many modern learning problems boil down to a nonconvex optimization problem, where the objective function is the average or the expectation of some loss function over a finite or infinite dataset. Solving such nonconvex optimization problems, in general, can be NP-hard. Thus one often tackles such a problem through incremental steps based on the nature and the goal of the problem: finding a first-order stationary point, finding a second-order stationary point (or a local optimum), and finding a global optimum. With the size and complexity of the machine learning datasets rapidly increasing, it has become a fundamental challenge to design efficient and scalable machine learning algorithms that can improve the performance in terms of accuracy and save computational cost in terms of sample efficiency at the same time. Though many algorithms based on stochastic gradient descent have been developed and widely studied theoretically and empirically for nonconvex optimization, it has remained an open problem whether we can achieve the optimal sample complexity for finding a first-order stationary point and for finding local optima in nonconvex optimization.
In this thesis, we start with the stochastic nested variance reduced gradient (SNVRG) algorithm, which is developed based on stochastic gradient descent methods and variance reduction techniques. We prove that SNVRG achieves the near-optimal convergence rate among its type for finding a first-order stationary point of a nonconvex function. We further build algorithms to efficiently find the local optimum of a nonconvex objective function by examining the curvature information at the stationary point found by SNVRG. With the ultimate goal of finding the global optimum in nonconvex optimization, we then provide a unified framework to analyze the global convergence of stochastic gradient Langevin dynamics-based algorithms for a nonconvex objective function. In the second part of this thesis, we generalize the aforementioned sample-efficient stochastic nonconvex optimization methods to reinforcement learning problems, including policy gradient, actor-critic, and Q-learning. For these problems, we propose novel algorithms and prove that they enjoy state-of-the-art theoretical guarantees on the sample complexity. The works presented in this thesis form an incomplete collection of the recent advances and developments of sample-efficient nonconvex optimization algorithms for both machine learning and reinforcement learning
Recommended from our members
Evaluating and Understanding Adversarial Robustness in Deep Learning
Get PDFDeep Neural Networks (DNNs) have made many breakthroughs in different areas of artificial intelligence. However, recent studies show that DNNs are vulnerable to adversarial examples. A tiny perturbation on an image that is almost invisible to human eyes could mislead a well-trained image classifier towards misclassification. This raises serious security concerns and trustworthy issues towards the robustness of Deep Neural Networks in solving real world challenges. Researchers have been working on this problem for a while and it has further led to a vigorous arms race between heuristic defenses that propose ways to defend against existing attacks and newly-devised attacks that are able to penetrate such defenses. While the arm race continues, it becomes more and more crucial to accurately evaluate model robustness effectively and efficiently under different threat models and identify those ``falsely'' robust models that may give us a false sense of robustness. On the other hand, despite the fast development of various kinds of heuristic defenses, their practical robustness is still far from satisfactory, and there are actually little algorithmic improvements in terms of defenses during recent years. This suggests that there still lacks further understandings toward the fundamentals of adversarial robustness in deep learning, which might prevent us from designing more powerful defenses. \\The overarching goal of this research is to enable accurate evaluations of model robustness under different practical settings as well as to establish a deeper understanding towards other factors in the machine learning training pipeline that might affect model robustness. Specifically, we develop efficient and effective Frank-Wolfe attack algorithms under white-box and black-box settings and a hard-label adversarial attack, RayS, which is capable of detecting ``falsely'' robust models. In terms of understanding adversarial robustness, we propose to theoretically study the relationship between model robustness and data distributions, the relationship between model robustness and model architectures, as well as the relationship between model robustness and loss smoothness. The techniques proposed in this dissertation form a line of researches that deepens our understandings towards adversarial robustness and could further guide us in designing better and faster robust training methods
Recommended from our members
Efficient Reinforcement Learning through Uncertainties
Get PDFThis dissertation is centered around the concept of uncertainty-aware reinforcement learning (RL), which seeks to enhance the efficiency of RL by incorporating uncertainty. RL is a vital mathematical framework in the field of artificial intelligence (AI) for creating autonomous agents that can learn optimal behaviors through interaction with their environments. However, RL is often criticized for being sample inefficient and computationally demanding. To tackle these challenges, the primary goals of this dissertation are twofold: to offer theoretical understanding of uncertainty-aware RL and to develop practical algorithms that utilize uncertainty to enhance the efficiency of RL.Our first objective is to develop an RL approach that is efficient in terms of sample usage for Markov Decision Processes (MDPs) with large state and action spaces. We present an uncertainty-aware RL algorithm that incorporates function approximation. We provide theoretical proof that this algorithm achieves near minimax optimal statistical complexity when learning the optimal policy. In our second objective, we address two specific scenarios: the batch learning setting and the rare policy switch setting. For both settings, we propose uncertainty-aware RL algorithms with limited adaptivity. These algorithms significantly reduce the number of policy switches compared to previous baseline algorithms while maintaining a similar level of statistical complexity. Lastly, we focus on estimating uncertainties in neural network-based estimation models. We introduce a gradient-based method that effectively computes these uncertainties. Our approach is computationally efficient, and the resulting uncertainty estimates are both valid and reliable.The methods and techniques presented in this dissertation contribute to the advancement of our understanding regarding the fundamental limits of RL. These research findings pave the way for further exploration and development in the field of decision-making algorithm design
Recommended from our members
Uncertainty-Aware Unsupervised and Robust Reinforcement Learning
Get PDFThis dissertation is centered around addressing several key concerns in reinforcement learning (RL). RL has been a popular topic in the design of autonomous intelligent agents that make decisions and learn optimal actions through interaction with the environment. Over the past decades, RL has achieved significant success in various domains. However, RL has consistently been criticized for its inefficiency in exploration and vulnerability to model errors or noise. This dissertation aims to tackle these challenges through uncertainty-aware methods.In the first part of this dissertation, we explore how an RL agent can efficiently explore the environment without human supervision. We begin with a theoretical framework on reward-free exploration and establish a connection between reward-free exploration and unsupervised reinforcement learning. We provide both theoretical analyses and practical algorithms that exhibit competitive empirical performance. In the second part of this dissertation, we aim to develop robust RL algorithm in a misspecified setting, where the function class (e.g., Neural Networks) cannot adequately approximate the underlying ground truth function. We show how significant does approximation error need to be in order to prevent the agent from efficiently learning the environment and making good decisions. We also present several algorithms that ensure the agent will only make a finite number of mistakes over infinite runs when this approximation error is small.The methods and techniques discussed in this dissertation advance the theoretical understanding of key concerns and limitations in RL, particularly in scenarios that require performance guarantees. Additionally, these findings not only suggest further research directions but also pose several open questions that would help better design more robust and efficient decision making processes in the future
Recommended from our members
On the Distance from Calibration in Sequential Prediction
Get PDFWe study a sequential binary prediction setting where the forecaster is evaluated in terms of the calibration distance, which is defined as the L1 distance between the predicted values and the set of predictions that are perfectly calibrated in hindsight. This is analogous to a calibration measure recently proposed by Błasiok, Gopalan, Hu and Nakkiran (STOC 2023) for the offline setting. The calibration distance is a natural and intuitive measure of deviation from perfect calibration, and satisfies a Lipschitz continuity property which does not hold for many popular calibration measures, such as the L1 calibration error and its variants. We prove that there is a forecasting algorithm that achieves an O(√T) calibration distance in expectation on an adversarially chosen sequence of T binary outcomes. At the core of this upper bound is a structural result showing that the calibration distance is accurately approximated by the lower calibration distance, which is a continuous relaxation of the former. We then show that an O(√T) lower calibration distance can be achieved via a simple minimax argument and a reduction to online learning on a Lipschitz class. On the lower bound side, an Ω(T^(1/3)) calibration distance is shown to be unavoidable, even when the adversary outputs a sequence of independent random bits, and has an additional ability to early stop (i.e., to stop producing random bits and output the same bit in the remaining steps). Interestingly, without this early stopping, the forecaster can achieve a much smaller calibration distance of polylog(T)
Recommended from our members
Towards Efficient and Effective Privacy-Preserving Machine Learning
Get PDFThe past decade has witnessed the fast growth and tremendous success of machine learning. However, recent studies showed that existing machine learning models are vulnerable to privacy attacks, such as membership inference attacks, and thus pose severe threats to personal privacy. Therefore, one of the major challenges in machine learning is to learn effectively from enormous amounts of sensitive data without giving up on privacy. This dissertation summarizes our contributions to the field of privacy-preserving machine learning, i.e., solving machine learning problems with strong privacy and utility guarantees.In the first part of the dissertation, we consider the privacy-preserving sparse learning problem. More specifically, we establish a novel differentially private hard-thresholding method as well as a knowledge-transfer framework for solving the sparse learning problem. We show that our proposed methods are not only efficient but can also achieve improved privacy and utility guarantees.In the second part of the dissertation, we propose novel efficient and effective algorithms for solving empirical risk minimization problems. To be more specific, our proposed algorithms can reduce the computational complexities and improve the utility guarantees for solving nonconvex optimization problems such as training deep neural networks. In the last part of the dissertation, we study the privacy-preserving empirical risk minimization in the distributed setting. In such a setting, we propose a new privacy-preserving framework by combining the multi-party computation (MPC) protocol and differentially private mechanisms and show that our framework can achieve better privacy and utility guarantees compared with existing methods.The methods and techniques proposed in this dissertation form a line of researches that deepens our understandings of the trade-off between privacy, utility and efficient in privacy-preserving machine learning, and
could also help us develop more efficient and effective private learning algorithms
Recommended from our members
Foundations for Efficient and Near-Optimal Reinforcement Learning
Get PDFThis dissertation addresses key challenges in reinforcement learning (RL): inefficiency in large state-action spaces and vulnerability in non-stationary environments. As a cornerstone of artificial intelligence (AI), RL enables autonomous agents to learn optimal decision-making through environmental interaction. While successful in many domains, RL often struggles with the complexity of vast state-action spaces and performance degradation in unstable settings. To overcome these limitations, this work establishes theoretical foundations and develops efficient algorithms tailored for these challenging scenarios.The first part of this dissertation focuses on achieving efficient and near-optimal RL in large state-action spaces. We introduce a function approximation approach that estimates expected cumulative rewards using a predefined function class, enabling effective exploration and exploitation. By employing a variance-aware weighted scheme, we theoretically guarantee optimal worst-case regret. Furthermore, we develop a linear function approximation-based RL algorithm that exploits the environment's specific structure to significantly reduce regret and enhance performance.The second part of this dissertation explores maintaining stable RL performance in non-stationary environments, addressing two specific challenges. First, we consider unreliable observations with potential adversarial corruption of rewards and transitions. To mitigate this, we introduce an uncertainty-aware weighted mechanism that adaptively weights observations, balancing the impact of adversarial influence. Based on this, we present an algorithm achieving optimal regret under a bounded adversary. Second, we focus on asynchronous federated reinforcement learning, enabling collaborative policy adjustment among multiple agents. We develop a robust algorithm that eliminates strict participation requirements, allowing voluntary agent contribution while ensuring near-optimal performance with low communication overhead.The methods and techniques presented herein contribute to a deeper theoretical understanding of RL's fundamental limitations, particularly in non-stationary environments. These findings also pave the way for future research and highlight open questions toward designing more robust and efficient decision-making algorithms
From patterned response dependency to structured covariate dependency: Entropy based categorical-pattern-matching
Get PDFData generated from a system of interest typically consists of measurements on many covariate features and possibly multiple response features across all subjects in a designated ensemble. Such data is naturally represented by one response-matrix against one covariate-matrix. A matrix lattice is an advantageous platform for simultaneously accommodating heterogeneous data types: continuous, discrete and categorical, and exploring hidden dependency among/between features and subjects. After each feature being individually renormalized with respect to its own histogram, the categorical version of mutual conditional entropy is evaluated for all pairs of response and covariate features according to the combinatorial information theory. Then, by applying Data Could Geometry (DCG) algorithmic computations on such a mutual conditional entropy matrix, multiple synergistic feature-groups are partitioned. Distinct synergistic feature-groups embrace distinct structures of dependency. The explicit details of dependency among members of synergistic features are seen through mutliscale compositions of blocks computed by a computing paradigm called Data Mechanics. We then propose a categorical pattern matching approach to establish a directed associative linkage: from the patterned response dependency to serial structured covariate dependency. The graphic display of such a directed associative linkage is termed an information flow and the degrees of association are evaluated via tree-to-tree mutual conditional entropy. This new universal way of discovering system knowledge is illustrated through five data sets. In each case, the emergent visible heterogeneity is an organization of discovered knowledge.</div
Recommended from our members
Understanding the Role of Optimization Algorithms in Learning Over-parameterized Models
Get PDFDeep learning has witnessed fast growth and wide application in recent years. One of the essential properties of the modern deep learning model is that it is sufficiently over-parameterized, i.e., it has much more learnable parameters than the number of training examples. The over-parameterization, on one hand, is the core of the superior approximation/representation ability of the neural network function, while, on the other hand, could lead to severe over-fitting issues, according to the conventional wisdom in learning theory. However, this is not consistent with the empirical success in deep learning, where the neural network model, trained by standard optimization algorithms (e.g., stochastic gradient descent, Adam, etc.), can not only perfectly fit the training data (i.e., finding the global solution of the training objective), but also generalizes well on the test data. This dissertation seeks to understand and explain this phenomenon by carefully characterizing the role of optimization algorithms in learning over-parameterized models.We begin the dissertation by studying arguably the simplest model: over-parameterized linear regression problems. In particular, we consider a class of SGD algorithms and prove problem-dependent generalization error bounds accordingly. Based on the established generalization guarantees, we will further characterize the sufficient conditions on the least square problem itself (e.g., conditions on data distribution and ground-truth model parameters) such that the SGD algorithm can generalize. Moreover, motivated by the recent work on the implicit regularization of SGD, we also provide a complete comparison between the SGD solution and the solution of regularized least square (i.e., ridge regression). We demonstrate the benefit of SGD compared to ridge regression for a large class of the least square problems classes, which partially explains the implicit regularization effect of SGD.In the second part, we study the effect of optimization algorithms for learning over-parameterized neural network models. Different from linear models that their optimization guarantees can be easily established, studying the optimization in training deep neural networks is challenging since the training objective is nonconvex or even nonsmooth. Therefore, we first study the optimization in training over-parameterized neural network models and establish global convergence guarantees for both GD and SGD under mild conditions on the data distribution. Based on the optimization analysis, we further establish an algorithm-dependent generalization analysis for SGD/GD. We show that if the data distribution admits certain good separation properties, a deep ReLU network with polylogarithmic width can be successfully trained with a global convergence guarantee and good generalization ability. Finally, we compare the generalization ability of two different optimization algorithms in learning over-parameterized neural networks: GD and Adam, and show that Adam and GD exhibit different algorithmic biases, which consequently leads to different solutions that have different generalization performances.The works covered in this dissertation form exploration in understanding the role of optimization algorithms in learning over-parameterized models, which is an incomplete collection of the recent advances in deep learning theory but shed light on a broader class of future directions in deep learning research
- …
