Le présent article traite de l'optimisation convexe en ligne impliquant des fonctions de perte contradictoire et des contraintes contradictoires, où les contraintes sont révélées après avoir pris des décisions, et peuvent être tolérables à des violations instantanées mais doivent être satisfaites à long terme. La performance d'un algorithme en ligne dans ce contexte est évaluée par : i) la différence de ses pertes par rapport à la meilleure solution dynamique avec des informations à un créneau de la fonction de perte et de la contrainte (qui est ici appelée regret dynamique) ; et ii) le nombre accumulé de violations de contraintes (qui est ici appelé ajustement dynamique). Dans ce contexte, un schéma de point de selle en ligne modifié (MOSP) est développé et s'est avéré produire simultanément un regret et un ajustement dynamiques sous-linéaires, à condition que les variations accumulées des minimiseurs et des contraintes par créneau augmentent sous-linéairement avec le temps. Le MOSP est appliqué à la tâche d'allocation dynamique des ressources du réseau, et il est démontré qu'il surpasse la méthode bien connue du double gradient stochastique.

El presente documento trata sobre la optimización convexa en línea que implica funciones de pérdida adversaria y restricciones adversarias, donde las restricciones se revelan después de tomar decisiones, y pueden ser tolerables a violaciones instantáneas, pero deben satisfacerse a largo plazo. El rendimiento de un algoritmo en línea en este entorno se evalúa por: i) la diferencia de sus pérdidas en relación con la mejor solución dinámica con información de una ranura de la función de pérdida y la restricción (que aquí se denomina arrepentimiento dinámico); y, ii) la cantidad acumulada de violaciones de restricciones (que aquí se denomina ajuste dinámico). En este contexto, se desarrolla un esquema modificado de punto de silla en línea (MOSP) y se demuestra que produce simultáneamente arrepentimiento y ajuste dinámico sublineal, siempre que las variaciones acumuladas de minimizadores y restricciones por ranura crezcan sublinealmente con el tiempo. El MOSP se aplica a la tarea de asignación dinámica de recursos de red y se muestra que supera al conocido método estocástico de doble gradiente.

The present paper deals with online convex optimization involving adversarial loss functions and adversarial constraints, where the constraints are revealed after making decisions, and can be tolerable to instantaneous violations but must be satisfied in the long term. Performance of an online algorithm in this setting is assessed by: i) the difference of its losses relative to the best dynamic solution with one-slot-ahead information of the loss function and the constraint (that is here termed dynamic regret); and, ii) the accumulated amount of constraint violations (that is here termed dynamic fit). In this context, a modified online saddle-point (MOSP) scheme is developed, and proved to simultaneously yield sub-linear dynamic regret and fit, provided that the accumulated variations of per-slot minimizers and constraints are sub-linearly growing with time. MOSP is applied to the dynamic network resource allocation task, and shown to outperform the well-known stochastic dual gradient method.

تتعامل هذه الورقة مع التحسين المحدب عبر الإنترنت الذي يتضمن وظائف الخسارة العدائية والقيود العدائية، حيث يتم الكشف عن القيود بعد اتخاذ القرارات، ويمكن تحملها للانتهاكات الفورية ولكن يجب تلبيتها على المدى الطويل. يتم تقييم أداء الخوارزمية عبر الإنترنت في هذا الإعداد من خلال: 1) اختلاف خسائرها بالنسبة إلى أفضل حل ديناميكي مع معلومات الشق الأمامي لوظيفة الخسارة والقيود (التي تسمى هنا الندم الديناميكي )؛ و 2) المبلغ المتراكم لانتهاكات القيود (التي تسمى هنا التوافق الديناميكي). في هذا السياق، تم تطوير مخطط نقطة السرج (MOSP) المعدل عبر الإنترنت، وأثبت أنه ينتج في وقت واحد ندمًا ديناميكيًا دون خطي وملاءمة، بشرط أن تكون الاختلافات المتراكمة في عوامل التقليل والقيود لكل فتحة تنمو خطيًا مع مرور الوقت. يتم تطبيق MOSP على مهمة تخصيص موارد الشبكة الديناميكية، ويظهر أنه يتفوق على طريقة التدرج المزدوج العشوائي المعروفة.