104 research outputs found
A Short Note of PAGE: Optimal Convergence Rates for Nonconvex Optimization
No full textIn this note, we first recall the nonconvex problem setting and introduce the optimal PAGE algorithm (Li et al., ICML'21). Then we provide a simple and clean convergence analysis of PAGE for achieving optimal convergence rates. Moreover, PAGE and its analysis can be easily adopted and generalized to other works. We hope that this note provides the insights and is helpful for future works
MARINA: Faster Non-Convex Distributed Learning with Compression
No full textWe develop and analyze MARINA: a new communication efficient method for non-convex distributed learning over heterogeneous datasets. MARINA employs a novel communication compression strategy based on the compression of gradient differences that is reminiscent of but different from the strategy employed in the DIANA method of Mishchenko et al. (2019). Unlike virtually all competing distributed first-order methods, including DIANA, ours is based on a carefully designed biased gradient estimator, which is the key to its superior theoretical and practical performance. The communication complexity bounds we prove for MARINA are evidently better than those of all previous first-order methods. Further, we develop and analyze two variants of MARINA: VR-MARINA and PP-MARINA. The first method is designed for the case when the local loss functions owned by clients are either of a finite sum or of an expectation form, and the second method allows for a partial participation of clients {–} a feature important in federated learning. All our methods are superior to previous state-of-the-art methods in terms of oracle/communication complexity. Finally, we provide a convergence analysis of all methods for problems satisfying the Polyak-{Ł}ojasiewicz condition.The work of Peter Richtarik, Eduard Gorbunov, Konstantin Burlachenko and Zhize Li was supported by KAUST Base-line Research Fund. The paper was written while E. Gorbunov was a research intern at KAUST. The work of E. Gorbunov in Sections 1, 2, and C was also partially supported by the Ministry of Science and Higher Education of the Russian Federation (Goszadaniye) 075-00337-20-03, projectNo. 0714-2020-0005, and in Sections 3, 4, D, E – byRFBR, project number 19-31-51001. We thank Konstantin Mishchenko (KAUST) for a suggestion related to the experiments, Elena Bazanova (MIPT) for the suggestions about improving the text, and Slavomır Hanzely (KAUST) and Egor Shulgin (KAUST) for spotting the typos
The Experimental Data for the Study "Frequency Fitness Assignment: Making Optimization Algorithms Invariant under Bijective Transformations of the Objective Function Value"
No full textThe Experimental Data for the Study "Frequency Fitness Assignment: Making Optimization Algorithms Invariant under Bijective Transformations of the Objective Function Value"
1. Introduction
Frequency Fitness Assignment (FFA) replaces the objective value in the selection step of an optimization method with its encounter frequency in any selection step so far. It turns static problems into dynamic ones. Here we experimentally investigated this approach in two important contexts: First, we integrated it into a basic (1+1)-EA, obtaining the (1+1)-FEA. We applied both algorithms to several well-known benchmark problems with bit-string based search spaces, including the OneMax, LeadingOnes, TwoMax, Jump, Plateau, and W-Model functions. We also applied them to the Max-3-Sat instances from SATLib. We then also integrated FFA into a Memetic Algorithm for the Job Shop Problem.
2. Paper
This data is used as the basis for the following article: Thomas Weise, Zhize Wu, Xinlu Li, and Yan Chen. Frequency Fitness Assignment: Making Optimization Algorithms Invariant under Bijective Transformations of the Objective Function Value, originally submitted to arxiv on 2020-01-06 (under the title Frequency Fitness Assignment: Making Optimization Algorithms Invariant under Bijective Transformations of the Objective Function), updated with the new data in June 2020, and submitted to the IEEE Transactions on Evolutionary Computation.
3. Data
This data set contains all the results of these experiments, the source codes used in the experiments (i.e., the algorithm implementations), as well as the scripts used for evaluating the results.
4. Version History
This is the second version of the data set, including extended experiments and more evaluation results. Most importantly, data for larger scales of OneMax and LeadingOnes has been added. The original version is at 10.5281/zenodo.3598172.
5. Contact
If you have any questions or suggestions, please contact Prof. Dr. Thomas Weise of the Institute of Applied Optimization at Hefei University in Hefei, Anhui, China via email to [email protected] with CC to [email protected]
CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression
No full textDue to the high communication cost in distributed and federated learning, methods relying on compressed communication are becoming increasingly popular. Besides, the best theoretically and practically performing gradient-type methods invariably rely on some form of acceleration/momentum to reduce the number of communications (faster convergence), e.g., Nesterov's accelerated gradient descent (Nesterov, 1983, 2004) and Adam (Kingma and Ba, 2014). In order to combine the benefits of communication compression and convergence acceleration, we propose a \emph{compressed and accelerated} gradient method based on ANITA (Li, 2021) for distributed optimization, which we call CANITA. Our CANITA achieves the \emph{first accelerated rate} O(root(1+sec(3) /n)L/is an element of+sec(1/is an element of)(1/3)), which improves upon the state-of-the-art non-accelerated rate O((1+sec/n)L/sec+sec(2)+sec+n1sec) of DIANA (Khaled et al., 2020) for distributed general convex problems, where is an element of is the target error, L is the smooth parameter of the objective, n is the number of machines/devices, and ? is the compression parameter (larger ? means more compression can be applied, and no compression implies sec=0). Our results show that as long as the number of devices n is large (often true in distributed/federated learning), or the compression ? is not very high, CANITA achieves the faster convergence rate O(L is an element of--v), i.e., the number of communication rounds is O(L is an element of--v) (vs. O(L is an element of) achieved by previous works). As a result, CANITA enjoys the advantages of both compression (compressed communication in each round) and acceleration (much fewer communication rounds
BEER: Fast <i>O</i>(1/<i>T</i>) Rate for Decentralized Nonconvex Optimization with Communication Compression
No full textCommunication efficiency has been widely recognized as the bottleneck for large-scale decentralized machine learning applications in multi-agent or federated environments. To tackle the communication bottleneck, there have been many efforts to design communication-compressed algorithms for decentralized nonconvex optimization, where the clients are only allowed to communicate a small amount of quantized information (aka bits) with their neighbors over a predefined graph topology. Despite significant efforts, the state-of-the-art algorithm in the nonconvex setting still suffers from a slower rate of convergence O((G/T)(2/3)) compared with their uncompressed counterpart, where G measures the data heterogeneity across different clients, and T is the number of communication rounds. This paper proposes BEER, which adopts communication compression with gradient tracking, and shows it converges at a faster rate of O(1/T). This significantly improves over the state-of-the-art rate, by matching the rate without compression even under arbitrary data heterogeneity. Numerical experiments are also provided to corroborate our theory and confirm the practical superiority of BEER in the data heterogeneous regime.The work of H. Zhao is supported in part by NSF, ONR, Simons Foundation, DARPA and SRC through awards to S. Arora. The work of B. Li, Z. Li and Y. Chi is supported in part by ONR N00014-19-1-2404, by AFRL under FA8750-20-2-0504, and by NSF under CCF-1901199, CCF-2007911 and CNS-2148212. B. Li is also gratefully supported by Wei Shen and Xuehong Zhang Presidential Fellowship at Carnegie Mellon University. The work of P. Richtarik is supported by KAUST Baseline Research Fund
BEER: Fast O(1/T) Rate for Decentralized Nonconvex Optimization with Communication Compression
No full textCommunication efficiency has been widely recognized as the bottleneck for large-scale decentralized machine learning applications in multi-agent or federated environments. To tackle the communication bottleneck, there have been many efforts to design communication-compressed algorithms for decentralized nonconvex optimization, where the clients are only allowed to communicate a small amount of quantized information (aka bits) with their neighbors over a predefined graph topology. Despite significant efforts, the state-of-the-art algorithm in the nonconvex setting still suffers from a slower rate of convergence O((G/T)2/3) compared with their uncompressed counterpart, where G measures the data heterogeneity across different clients, and T is the number of communication rounds. This paper proposes BEER, which adopts communication compression with gradient tracking, and shows it converges at a faster rate of O(1/T). This significantly improves over the state-of-the-art rate, by matching the rate without compression even under arbitrary data heterogeneity. Numerical experiments are also provided to corroborate our theory and confirm the practical superiority of BEER in the data heterogeneous regime.The work of H. Zhao is supported in part by NSF, ONR, Simons Foundation, DARPA and SRC through
awards to S. Arora. The work of B. Li and Y. Chi is supported in part by ONR N00014-19-1-2404, by AFRL
under FA8750-20-2-0504, and by NSF under CCF-1901199 and CCF-2007911. The work of Z. Li and P.
Richtárik is supported by KAUST Baseline Research Fund
SSRGD: Simple stochastic recursive gradient descent for escaping saddle points
No full textWe analyze stochastic gradient algorithms for optimizing nonconvex problems. In particular, our goal is to find local minima (second-order stationary points) instead of just finding first-order stationary points which may be some bad unstable saddle points. We show that a simple perturbed version of stochastic recursive gradient descent algorithm (called SSRGD) can find an (?, d)-second-order stationary point with Oe(vn/?2 + vn/d4 + n/d3) stochastic gradient complexity for nonconvex finite-sum problems. As a by-product, SSRGD finds an ?-first-order stationary point with O(n + vn/?2) stochastic gradients. These results are almost optimal since Fang et al. [11] provided a lower bound ?(vn/?2) for finding even just an ?-first-order stationary point. We emphasize that SSRGD algorithm for finding second-order stationary points is as simple as for finding first-order stationary points just by adding a uniform perturbation sometimes, while all other algorithms for finding second-order stationary points with similar gradient complexity need to combine with a negative-curvature search subroutine (e.g., Neon2 [4]). Moreover, the simple SSRGD algorithm gets a simpler analysis. Besides, we also extend our results from nonconvex finite-sum problems to nonconvex online (expectation) problems, and prove the corresponding convergence results
- …
